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{align} 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{align}$

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 arkaplan

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{align} a_{n+1} & = \frac{a_n+b_n}{2}, \\ b_{n+1} & = \sqrt{a_n b_n}, \end{align}$

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; öyleki $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)}\!$

öyleki $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\!$