El algoritmo de Gauss-Legendre es un algoritmo para calcular los dígitos de π . Es notable por ser rápidamente convergente, con solo 25 iteraciones que producen 45 millones de dígitos correctos de π . Sin embargo, el inconveniente es que requiere mucha memoria de la computadora y, por lo tanto, a veces se utilizan fórmulas similares a las de Machin .
El método se basa en el trabajo individual de Carl Friedrich Gauss (1777–1855) y Adrien-Marie Legendre (1752–1833) combinado con algoritmos modernos de multiplicación y raíces cuadradas . Reemplaza repetidamente dos números por su media aritmética y geométrica , para aproximar su media aritmético-geométrica .
La versión que se presenta a continuación también se conoce como algoritmo de Gauss-Euler , Brent-Salamin (o Salamin-Brent ) ; [1] Fue descubierto de forma independiente en 1975 por Richard Brent y Eugene Salamin . Se utilizó para calcular los primeros 206,158,430,000 dígitos decimales de π del 18 al 20 de septiembre de 1999, y los resultados se verificaron con el algoritmo de Borwein .
Algoritmo
1. Configuración del valor inicial:
2. Repita las siguientes instrucciones hasta que la diferencia de y está dentro de la precisión deseada:
3. Entonces, π se aproxima como:
Las primeras tres iteraciones dan (aproximaciones dadas hasta el primer dígito incorrecto incluido):
El algoritmo tiene convergencia cuadrática , lo que esencialmente significa que el número de dígitos correctos se duplica con cada iteración del algoritmo.
Fondo matemático
Límites de la media aritmética-geométrica
La media aritmética-geométrica de dos números, a 0 y b 0 , se encuentra calculando el límite de las sucesiones.
que ambos convergen hacia el mismo límite.
Si y entonces el limite es dónde es la integral elíptica completa del primer tipo
Si , , luego
dónde es la integral elíptica completa del segundo tipo :
- y
Gauss conocía ambos resultados. [2] [3] [4]
La identidad de Legendre
Para y tal que Legendre demostró la identidad:
- [2]
- Equivalentemente,
Prueba elemental con cálculo integral
El algoritmo de Gauss-Legendre se puede probar sin funciones modulares elípticas. Esto se hace aquí [5] y aquí [6] utilizando únicamente cálculo integral.
Ver también
Referencias
- ^ Brent, Richard , Algoritmos antiguos y nuevos para pi , Cartas al editor, Avisos del AMS 60 (1), p. 7
- ^ a b Brent, Richard (1975), Traub, JF (ed.), "Métodos de búsqueda de cero de precisión múltiple y la complejidad de la evaluación de funciones elementales" , Analytic Computational Complexity , Nueva York: Academic Press, págs. 151-176 , consultado el 8 de septiembre de 2007
- ^ Salamin, Eugene , Computación de pi , Nota 74-19 de la ISS del Laboratorio Charles Stark Draper, 30 de enero de 1974, Cambridge, Massachusetts
- ^ Salamin, Eugene (1976), "Cálculo de pi utilizando la media aritmética-geométrica", Matemáticas de cálculo , 30 (135), págs. 565–570, doi : 10.2307 / 2005327 , ISSN 0025-5718
- ^ Lord, Nick (1992), "Recent Calculations of π: The Gauss-Salamin Algorithm", The Mathematical Gazette , 76 (476): 231–242, doi : 10.2307 / 3619132 , JSTOR 3619132
- ^ Milla, Lorenz (2019), Prueba fácil de tres algoritmos π recursivos , arXiv : 1907.04110