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=1b_0=\frac{1}{\sqrt{2}}{t}_0=\frac{1}{4}{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{array}{cc}{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{array}$

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{array}{cc}{a}_{n+1}& =\frac{a_n+b_n}{2},\\ b_{n+1}& =\sqrt{a_n{b}_n},\end{array}$

Bu iki denklem de aynı limit değerine yakınsar. Eğer $a_0=1$ ve $b_0=\cos \phi$ ise limit $\frac{\pi }{2K(\sin \phi )}$ değerine yakınsar; öyle ki $K(k)$ birinci tür tam olmayan eliptik integraldir.

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

Eğer $c_0=\sin \phi$, $c_{i+1}=a_i-a_{i+1}$ ise

$\sum _{i=0}^{\mathrm{\infty }}{2}^{i-1}{c}_i^2=1-\frac{E(\sin \phi )}{K(\sin \phi )}$

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

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

Gauss tüm bu sonuçları biliyordu.

Legendre’ın özdeşliği

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

$K(\sin \phi )E(\sin \theta )+K(\sin \theta )E(\sin \phi )-K(\sin \phi )K(\sin \theta )=\frac{1}{2}\pi$