Proceso delta-cuadrado de Aitken

En análisis numérico , el proceso delta-cuadrado de Aitken o extrapolación de Aitken es un método de aceleración de series que se utiliza para acelerar la tasa de convergencia de una sucesión. Recibe su nombre de Alexander Aitken , quien introdujo este método en 1926 como parte de una extensión del método de Bernoulli . ^{[ 1 ]} Es más útil para acelerar la convergencia de una sucesión que converge linealmente. Seki Kōwa (1642-1708) conocía una forma precursora y la aplicó a la rectificación del círculo, es decir, al cálculo de π.

Dada una secuencia${\displaystyle X={(x_{n})}}$con${\displaystyle n=0,1,2,3,\ldots ,}$El proceso delta-cuadrado de Aitken asocia a esta secuencia la nueva secuencia.

$${\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}$$

que también se puede escribir como

$${\displaystyle A[X]=\left(x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}$$

con${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$y${\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}$Ambas son la misma secuencia algebraicamente, pero la segunda tiene una estabilidad numérica mejorada en la implementación computacional.

${\textstyle A[X]}$está mal definido si la secuencia${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_ {n})}$contiene un elemento cero, lo que ocurre si la secuencia de diferencias hacia adelante ,${\textstyle \Delta [X]=(\Delta x_ {n}),}$tiene algún término repetido. Desde un punto de vista teórico, si eso ocurre solo para un número finito de índices, se podría aplicar el proceso de Aitken solo a la parte de la secuencia.${\displaystyle X}$con índices${\displaystyle n>n_{0}}$ de tal manera que${\displaystyle n_{0}}$es el último índice para el cual la secuencia${\textstyle \Delta [X]}$ Se repite. En la práctica, los primeros términos de la secuencia suelen proporcionar la precisión deseada; además, al calcular numéricamente la secuencia, hay que tener cuidado de detener el cálculo antes de que los errores de redondeo en el denominador se vuelvan demasiado grandes, ya que${\textstyle \Delta ^{2}}$La transformación de secuencias puede cancelar dígitos significativos .

El proceso delta-cuadrado de Aitken es un método de aceleración de la convergencia y un caso particular de una transformación de secuencia no lineal .

Una secuencia${\textstyle X=(x_{n})}$que converge a un valor límite${\textstyle \ell }$Se dice que converge linealmente , o más técnicamente Q-linealmente, si hay algún número${\textstyle \mu \in (0,1)}$para qué

$${\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu .}$$

Esto significa que, asintóticamente, la distancia entre la secuencia y su límite se reduce en casi la misma proporción,${\displaystyle \mu ,}$en cada paso y la razón de reducción se acerca cada vez más a esa proporción. Esto también se denomina a veces "convergencia geométrica", ya que es una propiedad característica de las series geométricas , o "convergencia exponencial", ya que es una convergencia como${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

El método de Aitken acelerará la convergencia de una secuencia.${\displaystyle X}$si${\displaystyle A[X]=(a_{n}),}$con los términos definidos anteriormente, satisface${\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}$

${\displaystyle A}$no es un operador lineal sobre secuencias, pero sí es lineal con respecto a la suma de secuencias constantes:${\textstyle A[XC]=A[X]-C,}$si ${\displaystyle C}$es cualquier secuencia constante${\displaystyle C=(c)}$, constante para todos${\displaystyle n.}$Esto queda claro a partir de la expresión de${\displaystyle A[X]}$en términos del operador de diferencias finitas${\displaystyle \Delta .}$

El nuevo proceso no converge en general de forma cuadrática, pero para una secuencia de funciones iteradas que satisface${\displaystyle x_{n+1}=f(x_{n})}$para alguna función${\displaystyle f}$Al converger a un punto fijo , la convergencia de la secuencia acelerada es cuadrática. En este caso, la técnica se conoce como el método de Steffensen .

Empíricamente, la operación A elimina el "término de error más importante". Esto se puede comprobar considerando una secuencia de la forma${\displaystyle x_{n}=\ell +a^{n}+b^{n}}$, dónde${\displaystyle 0<b<a<1}$: La secuencia${\displaystyle A[X]}$entonces llegará al límite${\textstyle \ell }$como${\displaystyle b^{n}}$va a cero.

Geométricamente, la gráfica de una función exponencial${\displaystyle f(t)}$que satisface${\displaystyle f(n)=x_{n}}$,${\displaystyle f(n+1)=x_{n+1}}$y${\displaystyle f(n+2)=x_{n+2}}$tiene una asíntota horizontal en${\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}$(si${\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}$).

También se puede demostrar que si una secuencia${\displaystyle X}$converge a su límite${\displaystyle \ell }$a una tasa estrictamente mayor que 1,${\displaystyle A[X]}$no tiene una mejor tasa de convergencia. (En la práctica, rara vez se tiene, por ejemplo, convergencia cuadrática, lo que significaría más de 30 (respectivamente 100) decimales correctos después de 5 (respectivamente 7) iteraciones (comenzando con 1 dígito correcto); por lo general, en ese caso no se necesita aceleración).

En la práctica,${\displaystyle A[X]}$a menudo converge mucho más rápido al límite que${\displaystyle X}$Sí, como demuestran los cálculos de ejemplo a continuación. Por lo general, es mucho más barato calcular.${\displaystyle A[X]}$(que implica únicamente el cálculo de diferencias, una multiplicación y una división) que calcular muchos más términos de la secuencia${\displaystyle X}$Sin embargo, se debe tener cuidado para evitar introducir errores debido a una precisión insuficiente al calcular las diferencias entre el numerador y el denominador de la expresión.

Ejemplo 1 : El valor de${\displaystyle {\sqrt {2}}\approx 1.4142136}$puede aproximarse asumiendo un valor inicial para${\displaystyle x_{0}}$y repitiendo la siguiente secuencia, llamada método de Herón : $${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$$ Comenzando con${\displaystyle x_{0}=1:}$

Cabe señalar aquí que el método de Aitken no ahorra el costo de calcular dos iteraciones aquí; el cálculo de las tres primeras${\textstyle A[X]}$valores requeridos los primeros cinco${\textstyle X}$valores. Además, el segundo${\textstyle A[X]}$El valor es menos preciso que el cuarto.${\textstyle X}$valor, lo cual no es sorprendente debido a que el proceso de Aitken es más adecuado para secuencias que convergen linealmente, en lugar de cuadráticamente, y el método de Herón para calcular raíces cuadradas converge cuadráticamente.

Ejemplo 2 : El valor de${\displaystyle {\frac {\pi }{4}}}$puede calcularse como una suma infinita mediante la fórmula de Leibniz para π :

$${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}$$

En este ejemplo, el método de Aitken se aplica a una serie de convergencia sublineal y acelera considerablemente la convergencia. La convergencia sigue siendo sublineal, pero mucho más rápida que la convergencia original: la primera${\textstyle A[X]}$valor, cuyo cálculo requirió los tres primeros${\textstyle X}$valores, está más cerca del límite que el octavo${\textstyle X}$valor.

El siguiente es un ejemplo del uso de la extrapolación de Aitken para ayudar a encontrar el límite de la secuencia.${\displaystyle x_{n+1}=f(x_{n})}$cuando se le da algún dato inicial${\displaystyle x_{0},}$donde se supone que el límite de esta secuencia es un punto fijo.${\displaystyle f}$(decir${\displaystyle \alpha =f(\alpha )}$). Por ejemplo, si la secuencia está dada por${\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}$con punto de partida${\displaystyle x_{0}=1,}$entonces la función será${\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}$que tiene${\displaystyle \alpha$ :={\sqrt {2}}} como punto fijo (ver Métodos para calcular raíces cuadradas ); es este punto fijo cuyo valor se aproximará.

Este pseudocódigo también calcula la aproximación de Aitken a${\displaystyle f^{\prime }(\alpha )}$Las extrapolaciones de Aitken se denotarán por aitkenX. Durante el cálculo de la extrapolación, es importante comprobar si el denominador se vuelve demasiado pequeño, lo que podría ocurrir si ya tenemos una gran precisión; sin esta comprobación, la división podría introducir un gran error. Este pequeño número se denotará por epsilon. Dado que la representación binaria del punto fijo podría ser infinita (o al menos demasiado grande para caber en la memoria disponible), el cálculo se detendrá una vez que la aproximación esté dentro tolerancedel valor verdadero.

%Estas opciones dependen del problema que se esté resolviendo x0 = 1 %El valor inicial f ( x ) = ( 1 / 2 ) * ( x + 2 / x ) %La función que encuentra el siguiente elemento en la secuencia tolerancia = 10 ^- 10 %Se desea una precisión de 10 dígitos épsilon = 10 ^- 16 %No dividir por un número menor que estemaxIterations = 20 %No permitir que las iteraciones continúen indefinidamente haveWeFoundSolution = false %¿Hemos podido encontrar la solución dentro de la tolerancia deseada? Todavía nopara i = 1 : maxIterations x1 = f ( x0 ) x2 = f ( x1 )if ( x1 ~= x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) %OPCIONAL: Calcula una aproximación de |f'(fixedPoint)|, que se denota por lambda enddenominador = ( x2 - x1 ) - ( x1 - x0 );if ( valorAbsolute ( denominador ) < épsilon ) % Para evitar un error que aumente considerablemente, no divida por un número demasiado pequeño print ( 'ADVERTENCIA: el denominador es demasiado pequeño' ) break % Salir del bucle endaitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / denominadorif ( absoluteValue ( aitkenX - x2 ) < tolerance ) %Si el valor está dentro de la tolerancia print ( "El punto fijo es " , aitkenX )) %Muestra el resultado de la extrapolación de Aitken haveWeFoundSolution = true break %Hecho, así que salimos del bucle endx0 = aitkenX %Actualizar x0 para volver a empezar finif ( haveWeFoundSolution == false ) %Si no pudimos encontrar una solución dentro de la tolerancia deseada print ( "Advertencia: No se pudo encontrar una solución dentro de la tolerancia deseada de " , tolerance ) print ( "La última extrapolación calculada fue " , aitkenX ) end

• Tasa de convergencia
• Límite de una secuencia
• Iteración de punto fijo
• Extrapolación de Richardson
• Transformación de secuencias
• Transformación de Shanks
• El método de Steffensen

• William H. Press, et al. , Recetas numéricas en C , (1987) Cambridge University Press, ISBN 0-521-43108-5(Véase la sección 5.1 )
• Abramowitz y Stegun, Manual de funciones matemáticas , sección 3.9.7
• Kendall E. Atkinson, Introducción al análisis numérico , (1989) John Wiley & Sons, Inc., ISBN 0-471-62489-6