Gauss-Legendre Algoritması

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

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[değiştir | kaynağı değiştir]

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[değiştir | kaynağı değiştir]

Aritmetik-geometrik ortalamanın sınırları[değiştir | kaynağı değiştir]

İki sayının aritmetik-geometrik ortalaması, a0 ve b0, 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.[1] [2] [3]

Legendre’ın özdeşliği[değiştir | kaynağı değiştir]

Ö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\!

Kaynakça[değiştir | kaynağı değiştir]

  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): 151–176, http://wwwmaths.anu.edu.au/~brent/pub/pub028.html, erişim tarihi: 8 September 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): 565–570, ISSN 0025--5718