Gauss-Legendre Algoritması

Gauss-Legendre Algoritması π sayısının basamaklarını hesaplamak için kullanılan bir algoritmadır. Sadece 25 iterasyonda π sayısının 45 milyon basamağını doğru olarak hesaplıyor.

Bu yöntem Carl Friedrich Gauss (1777-1855) ve Adrien-Marie Legendre (1752-1833) ikilisinin bireysel çalışmalarıyla modern çarpma ve karekök bulma algoritmalarının bir birleşimine dayanmaktadır.

Aşağıda gösterilen çeşidiyse Brent-Salamin(ya da Salamin-Brent) algoritması olarak da bilinir; 1975 yılında Richard Brent ve Eugene Salamin tarafından keşfedilmiştir. Bu algoritma 18-20 Eylül 1999'da π sayısının ilk 206,158,430,000 ondalık basamaklarını hesaplamakta kullanıldı ve sonuçlar Borwein Algoritması'yla kontrol edildi.

Algoritma

1. Başlangıç değeri ayarlama:

${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1\!}$

2. Aşağıdaki talimatları ${\displaystyle a_{n}\!}$ ve ${\displaystyle b_{n}\!}$'nin farkı istenen doğruluk seviyesine gelene kadar uygulamaya devam edin.

${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\\t_{n+1}&=t_{n}-p_{n}(a_{n}-a_{n+1})^{2},\\p_{n+1}&=2p_{n}.\end{aligned}}}$

3.π yaklaşık olarak şu çıkar:

${\displaystyle \pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}.\!}$

İlk 3 iterasyonun sonucu:

${\displaystyle 3.140\dots \!}$

${\displaystyle 3.14159264\dots \!}$

${\displaystyle 3.1415926535897932382\dots \!}$

Matematiksel arka plan

Aritmetik-geometrik ortalamanın sınırları

İki sayının aritmetik-geometrik ortalaması, a₀ ve b₀, aşağıdaki dizilerin limitleri alınarak bulunur

${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\end{aligned}}}$

Bu iki denklem de aynı limit değerine yakınsar. Eğer ${\displaystyle a_{0}=1\!}$ ve ${\displaystyle b_{0}=\cos \varphi \!}$ ise limit ${\displaystyle {\pi \over 2K(\sin \varphi )}\!}$ değerine yakınsar; öyle ki ${\displaystyle K(k)\!}$ birinci tür tam olmayan eliptik integraldir.

${\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.\!}$

Eğer ${\displaystyle c_{0}=\sin \varphi \!}$, ${\displaystyle c_{i+1}=a_{i}-a_{i+1}\!}$ ise

${\displaystyle \sum _{i=0}^{\infty }2^{i-1}c_{i}^{2}=1-{E(\sin \varphi ) \over K(\sin \varphi )}\!}$

öyle ki ${\displaystyle E(k)\!}$ ikinci tür tam olmayan integraldir.

${\displaystyle E(k)=\int _{0}^{\pi /2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\,d\theta .\!}$

Gauss tüm bu sonuçları biliyordu.^{[1] [2] [3]}

Legendre’ın özdeşliği

Öyle bir ${\displaystyle \varphi \!}$ ve ${\displaystyle \theta \!}$ sayıları vardır ki ${\displaystyle \varphi +\theta ={1 \over 2}\pi \!}$ eşitliğini sağlar. Legendre bu ödeşliği kanıtlamıştır:

${\displaystyle K(\sin \varphi )E(\sin \theta )+K(\sin \theta )E(\sin \varphi )-K(\sin \varphi )K(\sin \theta )={1 \over 2}\pi \!}$

Kaynakça

1. Brent, Richard (1975), Traub, J F (Ed.), "Multiple-precision zero-finding methods and the complexity of elementary function evaluation", Analytic Computational Complexity, New York: Academic Press, ss. 151-176, 23 Temmuz 2008 tarihinde kaynağından arşivlendi, erişim tarihi: 8 Eylül 2007 
2. Salamin, Eugene. Computation of pi, Charles Stark Draper Laboratory ISS memo 74–19, 30 January, 1974, Cambridge, Massachusetts
3. Salamin, Eugene (1976), "Computation of pi Using Arithmetic-Geometric Mean", Mathematics of Computation, 30 (135), ss. 565-570, ISSN 0025-5718