Proceso delta cuadrado de Aitken

Método de aceleración de series de análisis numérico.

En análisis numérico , el proceso delta cuadrado de Aitken o extrapolación de Aitken es un método de aceleración en serie , utilizado para acelerar la tasa de convergencia de una secuencia. Lleva el nombre de Alexander Aitken , quien introdujo este método en 1926. ^[1] Su forma temprana era conocida por Seki Kōwa (finales del siglo XVII) y se descubrió para la rectificación del círculo, es decir, el cálculo de π. Es más útil para acelerar la convergencia de una secuencia que converge linealmente.

Definición

Dada una secuencia , se asocia con esta secuencia la nueva secuencia que, con una estabilidad numérica mejorada , también puede escribirse como o de manera equivalente como donde y para . ${\displaystyle X={(x_{n})}_{n\in \mathbb {N} }}$ $${\displaystyle AX={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)}_{n\in \mathbb {Z} ^{*}},}$$ $${\displaystyle (AX)_{n}=x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}},}$$ $${\displaystyle (AX)_{n}=x_{n+2}-{\frac {(\Delta x_{n+1})^{2}}{\Delta ^{2}x_{n}}}=x_{n+2}-{\frac {(x_{n+2}-x_{n+1})^{2}}{(x_{n+2}-x_{n+1})-(x_{n+1}-x_{n})}}}$$ $${\displaystyle \Delta x_{n}={(x_{n+1}-x_{n})},\ \Delta x_{n+1}={(x_{n+2}-x_{n+1})},}$$ $${\displaystyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n},\ }$$ ${\displaystyle n=0,1,2,3,\dots }$

Obviamente, está mal definida si contiene un elemento cero, o de manera equivalente, si la secuencia de primeras diferencias tiene un término repetido. ${\displaystyle AX}$ ${\displaystyle \Delta ^{2}x}$

Desde un punto de vista teórico, si eso ocurre sólo para un número finito de índices, uno podría fácilmente aceptar considerar la secuencia restringida a índices con un valor suficientemente grande . Desde un punto de vista práctico, en general se consideran sólo los primeros términos de la secuencia, que normalmente proporcionan la precisión necesaria. Además, al calcular numéricamente la secuencia, hay que tener cuidado de detener el cálculo cuando los errores de redondeo en el denominador sean demasiado grandes, donde la operación Δ ² puede cancelar demasiados dígitos significativos . (Sería mejor utilizar cálculos numéricos en lugar de .) ${\displaystyle AX}$ ${\displaystyle n>n_{0}}$ ${\displaystyle n_{0}}$ ${\displaystyle \Delta x_{n+1}-\Delta x_{n}\ =(x_{n+2}-x_{n+1})-(x_{n+1}-x_{n})\ }$ ${\displaystyle x_{n}-2x_{n+1}+x_{n+2}\ }$

Propiedades

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

La convergencia de un límite se llama "lineal" si hay algún número μ ∈ (0, 1) para lo cual significa que la distancia entre la secuencia y su límite se reduce casi en la misma proporción en cada paso, y esa tasa de reducción se vuelve más cerca de ser constante en cada paso. (Esto también se llama "convergencia geométrica"; esta forma de convergencia es común para las series de potencias ). ${\displaystyle \ \{x_{n}\}_{n=1}^{\infty }\ }$ ${\displaystyle \ \ell \ }$ $${\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu \ .}$$

El método de Aitken acelerará la secuencia si ${\displaystyle x_{n}}$ ${\textstyle \ \lim _{n\to \infty }{\frac {(Ax)_{n}-\ell }{x_{n}-\ell }}=0\ .}$

${\displaystyle A}$no es un operador lineal, pero se elimina un término constante, a saber: if es una constante. Esto se desprende claramente de la expresión de en términos del operador de diferencias finitas ${\displaystyle \ A[x-\ell ]=Ax-\ell \ ,}$ ${\displaystyle \ell }$ ${\displaystyle \ Ax\ }$ ${\displaystyle \ \Delta \ .}$

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

Empíricamente, la operación A elimina el "término de error más importante". Se puede comprobar esto considerando una secuencia de la forma , donde : La secuencia irá entonces al límite como va a cero. ${\displaystyle x_{n}=\ell +a^{n}+b^{n}}$ ${\displaystyle 0<b<a<1}$ ${\displaystyle Ax}$ ${\displaystyle b^{n}}$

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

También se puede demostrar que si llega a su límite a una tasa estrictamente mayor que 1, 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 o 100 decimales correctos después de 5 o 7 iteraciones (comenzando con 1 dígito correcto); normalmente no se necesita aceleración en ese caso). ${\displaystyle x}$ ${\displaystyle \ell }$ ${\displaystyle Ax}$

En la práctica, converge mucho más rápido al límite que lo hace, como lo demuestran los cálculos de ejemplo a continuación. Por lo general, es mucho más barato calcular (implicando solo el cálculo de diferencias, una multiplicación y una división) que calcular muchos más términos de la secuencia . Hay que tener cuidado, sin embargo, de no introducir errores por falta de precisión al calcular las diferencias en el numerador y denominador de la expresión. ${\displaystyle Ax}$ ${\displaystyle x}$ ${\displaystyle Ax}$ ${\displaystyle x}$

Cálculos de ejemplo

Ejemplo 1 : El valor de se puede aproximar asumiendo un valor inicial para e iterando lo siguiente: Comenzando con ${\displaystyle {\sqrt {2}}\approx 1.4142136}$ ${\displaystyle a_{0}}$ $${\displaystyle a_{n+1}={\frac {a_{n}+{\frac {2}{a_{n}}}}{2}}.}$$ ${\displaystyle a_{0}=1:}$

Vale la pena señalar aquí que el método de Aitken no guarda dos pasos de iteración; El cálculo de los primeros tres valores de Ax requirió los primeros cinco valores de x . Además, el segundo valor de Ax es decididamente inferior al cuarto valor de x, principalmente debido al hecho de que el proceso de Aitken supone una convergencia lineal, en lugar de cuadrática. ^{[ cita necesaria ]}

Ejemplo 2 : El valor de puede calcularse como una suma infinita: ${\displaystyle {\frac {\pi }{4}}}$

$${\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 sublinealmente convergente, acelerando considerablemente la convergencia. Sigue siendo sublineal, pero mucho más rápida que la convergencia original: el primer valor de Ax, cuyo cálculo requirió los primeros tres valores de x, está más cerca del límite que el octavo valor de x.

Pseudocódigo de ejemplo para la extrapolación de Aitken

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

Este pseudocódigo también calcula la aproximación de Aitken a . Las extrapolaciones de Aitken se denotarán por . 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 verificación, la división podría introducir una gran cantidad de errores. Este pequeño número se indicará con . Debido a 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 del valor real. ${\displaystyle f^{\prime }(\alpha )}$aitkenXepsilontolerance

%Estas elecciones 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 este              maxIterations = 20 % No permitir que las iteraciones continúen indefinidamente haveWeFoundSolution = false % ¿Pudimos encontrar la solución dentro de la tolerancia deseada? aún no      para i = 1 : maxIteraciones x1 = f ( x0 ) x2 = f ( x1 )             if ( x1 ~= x0 ) lambda = valor absoluto (( x2 - x1 ) / ( x1 - x0 )) %OPCIONAL: Calcula una aproximación de |f'(fixedPoint)|, que se denota por el extremo lambda             denominador = ( x2 - x1 ) - ( x1 - x0 );         if ( valor absoluto ( 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 %Deje el final del ciclo         aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / denominador if ( absoluteValue ( aitkenX - x2 ) < tolerancia ) %Si el valor está dentro de la tolerancia print ( "El punto fijo es " , aitkenX )) %Mostrar el resultado de la extrapolación de Aitken haveWeFoundSolution = true break %Listo, así que deje el final del ciclo                          x0 = aitkenX %Actualizar x0 para empezar de nuevo finalizar   if ( 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 " , tolerancia ) print ( "La última extrapolación calculada fue " , aitkenX ) fin        

Ver también

• Tasa de convergencia
• Límite de una secuencia
• iteración de punto fijo
• extrapolación de Richardson
• Transformación de secuencia
• Transformación de mangos
• El método de Steffensen.

Notas

1. Aitken, Alejandro (1926). "Sobre la solución numérica de ecuaciones algebraicas de Bernoulli". Actas de la Real Sociedad de Edimburgo . 46 : 289–305. doi :10.1017/S0370164600022070.

Referencias

• William H. Press, et al. , Recetas numéricas en C , (1987) Cambridge University Press, ISBN 0-521-43108-5 (Ver 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