Algoritmus Gauss – Legendre - Gauss–Legendre algorithm

The Algoritmus Gauss – Legendre je algoritmus vypočítat číslice π. Je pozoruhodné, že je rychle konvergentní, pouze 25 iterací produkuje 45 milionů správných číslicπ. Nevýhodou však je, že je paměť počítače -intenzivní, a proto někdy Machinovy ​​vzorce místo toho se používají.

Metoda je založena na individuální práci Carl Friedrich Gauss (1777–1855) a Adrien-Marie Legendre (1752–1833) v kombinaci s moderními algoritmy pro násobení a odmocniny. Opakovaně nahrazuje dvě čísla jejich aritmetický a geometrický průměr, aby se přiblížil jejich aritmeticko-geometrický průměr.

Verze uvedená níže je také známá jako Gauss – Euler, Brent – ​​Salamin (nebo Salamin – Brent) algoritmus;^[1] to bylo nezávisle objeveno v roce 1975 Richard Brent a Eugene Salamin. Bylo použito k výpočtu prvních 206 158 430 000 desetinných míst π 18. až 20. září 1999 a výsledky byly zkontrolovány Borweinův algoritmus.

Algoritmus

1. Počáteční nastavení hodnoty:

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

2. Opakujte následující pokyny, dokud nebude rozdíl ${ displaystyle a_ {n}}$ a ${ displaystyle b_ {n}}$ je v požadované přesnosti:

${ 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 {zarovnáno}}}$

3. π je pak aproximován jako:

${ displaystyle pi cca { frac {(a_ {n + 1} + b_ {n + 1}) ^ {2}} {4t_ {n + 1}}}.}$

První tři iterace dávají (přibližné hodnoty až do první nesprávné číslice včetně):

${ displaystyle 3,140 tečky}$

${ displaystyle 3.14159264 dots}$

${ Displaystyle 3.1415926535897932382 tečky}$

Algoritmus má kvadratická konvergence, což v podstatě znamená, že počet správných číslic se zdvojnásobuje opakování algoritmu.

Matematické pozadí

Meze aritmeticko – geometrického průměru

The aritmeticko – geometrický průměr dvou čísel, a₀ a b₀, je zjištěno výpočtem limitu sekvencí

${ displaystyle { begin {aligned} a_ {n + 1} & = { frac {a_ {n} + b_ {n}} {2}}, [6pt] b_ {n + 1} & = { sqrt {a_ {n} b_ {n}}}, end {zarovnáno}}}$

které oba konvergují ke stejné hranici.
Li ${ displaystyle a_ {0} = 1}$ a ${ displaystyle b_ {0} = cos varphi}$ pak je limit ${ textstyle { pi nad 2K ( sin varphi)}}$ kde ${ displaystyle K (k)}$ je kompletní eliptický integrál prvního druhu

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

Li ${ displaystyle c_ {0} = sin varphi}$, ${ displaystyle c_ {i + 1} = a_ {i} -a_ {i + 1}}$, pak

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

kde ${ displaystyle E (k)}$ je úplný eliptický integrál druhého druhu:

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

Gauss věděl o obou těchto výsledcích.^[2][3][4]

Legendrova identita

Pro ${ displaystyle varphi}$ a ${ displaystyle theta}$ takhle ${ textstyle varphi + theta = {1 nad 2} pi}$ Legendre prokázal totožnost:

${ Displaystyle K ( sin varphi) E ( sin theta) + K ( sin theta) E ( sin varphi) -K ( sin varphi) K ( sin theta) = {1 nad 2} pi.}$^[2]

Ekvivalentně

${ displaystyle forall varphi: K ( sin varphi) [E ( cos varphi) -K ( cos varphi)] + K ( cos varphi) E ( sin varphi) = { frac { pi} {2}}}$

Elementární důkaz s integrálním počtem

Algoritmus Gauss-Legendre lze prokázat bez eliptických modulárních funkcí. To se děje tady^[5] a tady^[6] pouze pomocí integrálního počtu.

Viz také

• Numerické aproximace π

Reference