הצגת המקור של הדף "אלגוריתם גאוס-לז'נדר"

'''אלגוריתם גאוס-לז'נדר''' הוא [[אלגוריתם]] מהיר לחישוב קירובים של [[קבוע מתמטי|הקבוע המתמטי]] [[פאי|<math>\pi</math>]], המבוסס על [[ממוצע אריתמטי-גאומטרי|הממוצע האריתמטי-גאומטרי]] של שני מספרים. מספר הספרות המדויקות בהערכת הקבוע מוכפל בכל צעד, ובעזרת מחשב מודרני האלגוריתם מאפשר לחשב מיליארדי ספרות, ואף יותר.

אלגוריתם זה, ודומים לו, נחקרו על ידי [[קרל פרידריך גאוס]] ו[[אדריאן-מארי לז'נדר]] בראשית [[המאה ה-19]]. האלגוריתם [[איטרציה|איטרטיבי]] מטבעו, ומבוסס על החלפה חוזרת של שני מספרים ב[[ממוצע|ממוצעים האריתמטי והגאומטרי]] שלהם. 

הגרסה השנייה המוצגת כאן ידועה כ"אלגוריתם בראנט-סלאמין", בשל העובדה שהאלגוריתם נתגלה מחדש, באופן בלתי תלוי, על ידי מדען המחשבים ריצ'רד בראנט והמתמטיקאי יוג'ין סלאמין ב-[[1975]]. 

==האלגוריתם של גאוס==
ב-[[1800]], חקירותיו של גאוס על הממוצע האריתמטי גאומטרי הובילו אותו לגלות את הנוסחה הנפלאה:
:<math>\sum_{k=0}^\infty2^k(b_k^2-a_k^2)=1-\frac{2M^2}{\pi}</math>
כאשר <math>a_0=\frac{1}{\sqrt2},b_0=1</math> ו-<math>M</math> הוא הממוצע האריתמטי-גאומטרי של <math>a_0,b_0</math>.

==תיאור אלגוריתם בראנט סלאמין==
'''אתחול האלגוריתם''' מתבצע על ידי מתן הערכים ההתחלתיים
:<math>a_0=\frac{1}{\sqrt2}\qquad b_0=1\qquad t_0=\frac14\qquad p_0=1</math>
'''השלב האיטרטיבי''', בו חוזרים ומעדכנים את ערכי הפרמטרים בנוסחאות הבאות עד השגת מספר הספרות הרצוי: 
(עד שההפרש בין <math>a_n,b_n</math>  קטן מערך רצוי)
:<math>\begin{align}a_{n+1}=\sqrt{a_n b_n}\\b_{n+1}=\frac{a_n+b_n}{2}\\t_{n+1}=t_n-p_n(b_n-b_{n+1})^2\\p_{n+1}=2p_n\end{align}</math>
'''בתום השלב האיטרטיבי''' מחושב הקירוב ל-<math>\pi</math> בעזרת הפרמטרים <math>a_n,b_n,t_n</math> לעיל, על ידי הנוסחה:
:<math>\pi\approx\frac{(a_n+b_n)^2}{4t_n}</math>
ארבע ההצבות הראשונות בנוסחה נותנות:
:<math>\begin{align}&3.14\ldots\\&3.1415926\ldots\\&3.141592653589793238\ldots\\&3.1415926535897932384626433832795028841971\ldots\end{align}</math>

==לקריאה נוספת==
*,PI and the AGM: A Study in Analytic Number Theory and Computational Complexity, Jonathan M. Borwein, Peter B. Borwein. 1987.

==קישורים חיצוניים==
*{{MathWorld}}

[[קטגוריה:אלגוריתמים|גאוס-לז'נדר]]
[[קטגוריה:פאי]]
[[קטגוריה:קרל פרידריך גאוס]]