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:

$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ı $a_{n}\!$ ve $b_{n}\!$'nin farkı istenen doğruluk seviyesine gelene kadar uygulamaya devam edin.

${\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:

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

İlk 3 iterasyonun sonucu:

$3.140\dots \!$

$3.14159264\dots \!$

$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

${\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 $a_{0}=1\!$ ve $b_{0}=\cos \varphi \!$ ise limit ${\pi \over 2K(\sin \varphi )}\!$ değerine yakınsar; öyle ki $K(k)\!$ birinci tür tam olmayan eliptik integraldir.

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

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

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

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

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

Gauss tüm bu sonuçları biliyordu.

Legendre’ın özdeşliği

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

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