Proceso delta-cuadrado de Aitken

En el 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. Recibe su nombre en honor a Alexander Aitken , quien introdujo este método en 1926. ^{[1] Es más útil para acelerar la convergencia de una secuencia 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 con el proceso delta-cuadrado de Aitken, se asocia a esta secuencia la nueva secuencia ${\displaystyle X={(x_{n})}}$${\displaystyle n=0,1,2,3,\lpuntos ,}$

$${\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 y Ambos son la misma secuencia algebraicamente pero el último ha mejorado la estabilidad numérica en la implementación computacional. ${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$${\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}$

${\textstyle A[X]}$está mal definida si la secuencia contiene un elemento cero, lo que ocurre si la secuencia de diferencias hacia adelante 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 con índices tales que sea el último índice para el cual la secuencia se repite. En la práctica, los primeros términos de la secuencia generalmente proporcionan la precisión deseada; además, al calcular numéricamente la secuencia, uno debe tener cuidado de detener el cálculo antes de que los errores de redondeo en el denominador se vuelvan demasiado grandes, ya que la transformación de la secuencia puede cancelar dígitos significativos . ${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_ {n})}$${\textstyle \Delta [X]=(\Delta x_ {n}),}$${\estilo de visualización X}$$estilo de visualización n>n_{0}$${\estilo de visualización n_{0}}$${\textstyle \Delta [X]}$${\textstyle \Delta ^{2}}$

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

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

$${\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 casi en la misma proporción, 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 convergencia como${\estilo de visualización \mu ,}$${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

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

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

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

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 , donde : La secuencia irá entonces al límite como tiende a cero. ${\displaystyle x_{n}=\ell+a^{n}+b^{n}}$${\displaystyle 0<b<a<1}$${\estilo de visualización A[X]}$${\textstyle \ell }$$Estilo de visualización 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 una secuencia converge 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 (respectivamente 100) decimales correctas después de 5 (respectivamente 7) iteraciones (comenzando con 1 dígito correcto); por lo general, no se necesita aceleración en ese caso). ${\displaystyle X}$${\displaystyle \ell }$${\displaystyle A[X]}$

En la práctica, a menudo 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 (lo que implica solo el cálculo de diferencias, una multiplicación y una división) que calcular muchos más términos de la secuencia . Sin embargo, se debe tener cuidado para evitar introducir errores debido a una precisión insuficiente al calcular las diferencias en el numerador y el denominador de la expresión. ${\displaystyle A[X]}$${\displaystyle X}$${\displaystyle A[X]}$${\displaystyle X}$

Ejemplo 1 : El valor de se puede aproximar asumiendo un valor inicial para e iterando la siguiente secuencia, llamada método de Heron : Comenzando con${\displaystyle {\sqrt {2}}\approx 1.4142136}$${\displaystyle x_{0}}$$${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$$${\displaystyle x_{0}=1:}$

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

Ejemplo 2 : El valor de puede calcularse como una suma infinita mediante la fórmula de Leibniz para π :${\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 que converge sublinealmente y acelera considerablemente la convergencia. La convergencia sigue siendo sublineal, pero mucho más rápida que la convergencia original: el primer valor, cuyo cálculo requirió los tres primeros valores, está más cerca del límite que el octavo valor. ${\textstyle A[X]}$${\textstyle X}$${\textstyle X}$

El siguiente es un ejemplo de uso de la extrapolación de Aitken para ayudar a encontrar el límite de la secuencia cuando se da un valor inicial donde se supone que el límite de esta secuencia es un punto fijo (por ejemplo, ). Por ejemplo, si la secuencia está dada por con un punto de partida , entonces la función será que tiene como punto fijo (ver Métodos para calcular raíces cuadradas ); es este punto fijo cuyo valor se aproximará. ${\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 verificar si el denominador se vuelve demasiado pequeño, lo que podría suceder si ya tenemos una gran cantidad de precisión; sin esta verificación, la división podría introducir una gran cantidad de error. Este pequeño número se denotará por . 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 verdadero. ${\displaystyle f^{\prime }(\alpha )}$aitkenXepsilontolerance

%Estas opciones dependen del problema a resolver 
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 epsilon = 10 ^ - 16 %No divida 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? todavía no            
   

para i = 1 : máxIteraciones 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 end   
                
    

    denominador = ( x2 - x1 ) - ( x1 - x0 );        

    if ( absoluteValue ( denominador ) < epsilon ) % Para evitar un gran aumento del error, no divida por un número demasiado pequeño print ( 'ADVERTENCIA: el denominador es demasiado pequeño' ) break % Salga del bucle end           
        
                                                
    

    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, entonces sal del bucle end        
    
              
                
          
                                                
    

    x0 = aitkenX %Actualizar x0 para comenzar de nuevo                   fin                                       


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 ) end      
     
     

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

• William H. Press, et al. , Numerical Recipes in 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