Algoritmo di Gauss-Legendre

Niente fonti!
Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

L'algoritmo di Gauss–Legendre è un algoritmo per il calcolo di π. È noto per essere rapidamente convergente, 25 iterazioni producono ben 45 milioni di cifre decimali corrette di π. L'inconveniente è un intensivo uso di memoria.

Il metodo è basato sui lavori di Gauss e Legendre unitamente ai moderni algoritmi per la moltiplicazione e l'estrazione di radice quadrata. Si basa sulla continua sostituzione di due numeri con la loro media aritmetica e geometrica per approssimare la loro media aritmetica-geometrica.

Esempio di algoritmo

La versione presentata qui sotto è anche conosciuta come algoritmo di Brent-Salamin (o Salamin-Brent); è stata scoperta indipendentemente da Richard Brent e Eugene Salamin[1]. È stata usata per calcolare le prime 206 158 430 000 cifre decimali di π tra il 18 e il 20 settembre 1999 e il risultato è stato controllato con l'algoritmo di Borwein.

  1. Valori iniziali:
    a 0 = 1 b 0 = 1 2 t 0 = 1 4 p 0 = 1. {\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{\sqrt {2}}}\qquad t_{0}={\frac {1}{4}}\qquad p_{0}=1.}
  2. Ripetere le seguenti istruzioni finché la differenza fra a n {\displaystyle a_{n}} e b n {\displaystyle b_{n}} è della precisione voluta:
    a n + 1 = a n + b n 2 {\displaystyle a_{n+1}={\frac {a_{n}+b_{n}}{2}}} ,
    b n + 1 = a n b n , {\displaystyle b_{n+1}={\sqrt {a_{n}b_{n}}},}
    t n + 1 = t n − p n ( a n − a n + 1 ) 2 , {\displaystyle t_{n+1}=t_{n}-p_{n}(a_{n}-a_{n+1})^{2},}
    p n + 1 = 2 p n . {\displaystyle p_{n+1}=2p_{n}.}
  3. π è approssimato con a n {\displaystyle a_{n}} , b n {\displaystyle b_{n}} e t n {\displaystyle t_{n}} come:
    π ≈ ( a n + b n ) 2 4 t n . {\displaystyle \pi \approx {\frac {(a_{n}+b_{n})^{2}}{4t_{n}}}.}

Le prime tre iterazioni danno:

3.140... {\displaystyle 3.140...}
3.14159264... {\displaystyle 3.14159264...}
3.14159265358979... {\displaystyle 3.14159265358979...}

L'algoritmo ha convergenza del secondo ordine, cioè il numero di cifre corrette raddoppia a ogni passo dell'algoritmo.

Note

  1. ^ Richard P. Brent, Old and new algorithms for pi, in Notices of the AMS, vol. 60, n. 1, American Mathematical Society, gennaio 2013, p. 7, arΧiv:1303.2762.

Collegamenti esterni

  • (EN) Eric W. Weisstein, Algoritmo di Gauss-Legendre, su MathWorld, Wolfram Research. Modifica su Wikidata
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica