Algoritmo de Gauss-Legendre

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El algoritmo de Gauss-Legendre es un algoritmo para computar los dígitos de π.

El método se basa en los trabajos individuales de Carl Friedrich Gauss (1777-1855) y Adrien-Marie Legendre (1752-1833) combinados con algoritmos modernos para la multiplicación y la raíz cuadrada. Sustituye repetidamente dos números por sus medias aritmética y geométrica, para obtener una aproximación a su media aritmético-geométrica.

La versión que se presenta aquí se conoce también como el algoritmo de Brent-Salamin (o Salamin-Brent); que fue descubierto en 1975 y de forma independiente por Richard Brent y Eugene Salamin. Se usó entre el 18 y el 20 de septiembre de 1999 para calcular los primeros 206.158.430.000 dígitos decimales de π, y el resultado se comprobó usando el algoritmo de Borwein.

Algoritmo[editar]

1. Establecimiento del valor inicial:

a_0 = 1\qquad b_0 = \frac{1}{\sqrt{2}}\qquad t_0 = \frac{1}{4}\qquad p_0 = 1

2. Repetir las siguientes instrucciones hasta que la diferencia entre a_n y b_n se encuentre dentro de la precisión deseada:

x_{n+1} = \frac{a_n + b_n}{2} \,
y_{n+1} = \sqrt{a_n b_n} \,
t_{n+1} = t_n - p_n(a_n - x_{n+1})^2 \,
a_{n+1} = x_{n+1} \,
b_{n+1} = y_{n+1} \,
p_{n+1} = 2p_n \,

3. π se aproxima usando a_n, b_n y t_n como:

\pi \approx \frac{(a_n+b_n)^2}{4t_n} \,

Las primeras tres iteraciones dan:

3.140...
3.14159264...
3.14159265358979...

El algoritmo tiene naturaleza convergente de segundo orden, que esencialmente significa que el número de dígitos correctos se duplica con cada paso del algoritmo.

Véase también[editar]

Enlaces externos[editar]