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 , que se utiliza para acelerar la tasa de convergencia de una secuencia. Lleva el nombre de Alexander Aitken , quien introdujo este método en 1926. [1] Seki Kōwa conocía su forma temprana (finales del siglo XVII) y se encontró 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 puede, con una estabilidad numérica mejorada , también escribirse como
o equivalentemente como
dónde
y
por
Obviamente, está mal definido si contiene un elemento cero, o de manera equivalente, si la secuencia de las primeras diferencias tiene un término que se repite.
Desde un punto de vista teórico, si eso ocurre solo para un número finito de índices, uno podría fácilmente estar de acuerdo en considerar la secuencia restringido a índices con un suficientemente grande . Desde un punto de vista práctico, en general uno considera solo los primeros términos de la secuencia, que generalmente proporcionan la precisión necesaria. Además, cuando se calcula numéricamente la secuencia, se debe tener cuidado de detener el cálculo cuando los errores de redondeo en el denominador se vuelven demasiado grandes, donde la operación Δ² puede cancelar demasiados dígitos significativos . (Sería mejor para el cálculo numérico usar en vez de .)
Propiedades
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 .
se converger linealmente a si existe un número μ ∈ (0, 1) tal que
El método de Aitken acelerará la secuencia Si
no es un operador lineal, pero desaparece un término constante, a saber: , Si es una constante. Esto se desprende de la expresión deen términos del operador de diferencias finitas.
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 función iterada para alguna función , convergiendo a un punto fijo, la convergencia es cuadrática. En este caso, la técnica se conoce como método de Steffensen .
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, dónde : La secuencia luego irá al límite como va a cero.
Geométricamente, la gráfica de una función exponencial que satisface , y tiene una asíntota horizontal en (Si ).
También se puede demostrar que si va a su límite a una tasa estrictamente superior a 1, no tiene una mejor tasa de convergencia. (En la práctica, uno rara vez tiene, por ejemplo, convergencia cuadrática, lo que significaría más de 30 o 100 lugares decimales correctos después de 5 o 7 iteraciones (comenzando con 1 dígito correcto); generalmente no se necesita aceleración en ese caso).
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 económico calcular (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 . Se debe tener cuidado, sin embargo, para evitar introducir errores debido a una precisión insuficiente al calcular las diferencias en el numerador y denominador de la expresión.
Cálculos de ejemplo
Ejemplo 1 : el valor de puede aproximarse asumiendo un valor inicial para e iterando lo siguiente:
Empezando con
norte | x = valor iterado | Hacha |
0 | 1 | 1.4285714 |
1 | 1,5 | 1.4141414 |
2 | 1.4166667 | 1.4142136 |
3 | 1.4142157 | - |
4 | 1.4142136 | - |
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 4º valor de x, principalmente debido al hecho de que el proceso de Aitken asume una convergencia lineal, en lugar de cuadrática [ cita requerida ] .
Ejemplo 2 : el valor de se puede calcular como una suma infinita:
norte | término | x = suma parcial | Hacha |
0 | 1 | 1 | 0,79166667 |
1 | −0,33333333 | 0.66666667 | 0,78333333 |
2 | 0,2 | 0.86666667 | 0,78630952 |
3 | −0,14285714 | 0,72380952 | 0,78492063 |
4 | 0.11111111 | 0,83492063 | 0,78567821 |
5 | −9,0909091 × 10 −2 | 0,74401154 | 0,78522034 |
6 | 7,6923077 × 10 −2 | 0,82093462 | 0,78551795 |
7 | -6,6666667 × 10 −2 | 0,75426795 | - |
8 | 5.8823529 × 10 −2 | 0.81309148 | - |
En este ejemplo, el método de Aitken se aplica a una serie de convergencia sublineal, lo que acelera considerablemente la convergencia. Sigue siendo sublineal, pero mucho más rápido 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.
Ejemplo de pseudocódigo 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 (decir ). Por ejemplo, si la secuencia viene dada por con punto de partida entonces la función será que tiene como un punto fijo (ver Métodos para calcular raíces cuadradas ); es este punto fijo cuyo valor será aproximado.
Este pseudocódigo también calcula la aproximación de Aitken a . Las extrapolaciones de Aitken se denotarán con aitkenX
. Durante el cálculo de la extrapolación, es importante comprobar 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 indicará con epsilon
. 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 tolerance
del valor real.
% Estas opciones dependen del problema que se resuelvax0 = 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 precisión de 10 dígitos épsilon = 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? aún no para i = 1 : maxIteraciones x1 = f ( x0 ) x2 = f ( x1 ) si ( x1 ~ = x0 ) lambda = valor absoluto (( x2 - x1 ) / ( x1 - x0 )) % OPCIONAL: Calcula una aproximación de | f '(FixedPoint) |, que se denota por lambda final denominador = ( x2 - x1 ) - ( x1 - x0 ); if (valor absoluto ( denominador ) < épsilon ) % Para evitar un gran aumento del error, no divida por un número demasiado pequeño print ( 'ADVERTENCIA: el denominador es demasiado pequeño' ) romper ; % Deja el bucle final aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / denominador if (valor absoluto ( aitkenX - x2 ) < tolerancia ) % Si el valor está dentro de la tolerancia print ( "El punto fijo es" , aitkenX )) % Muestra el resultado de la extrapolación de Aitken haveWeFoundSolution = verdadero romper ; % Listo, así que deja el bucle final x0 = aitkenX % Actualiza x0 para empezar de nuevo finalif ( haveWeFoundSolution == false ) % Si no pudimos encontrar una solución dentro de la tolerancia deseada print ( "Advertencia: No se puede encontrar una solución dentro de la tolerancia deseada de" , tolerancia ) print ( "La última extrapolación calculada fue" , aitkenX ) final
Ver también
Notas
- ^ Alexander Aitken, "Sobre la solución numérica de ecuaciones algebraicas de Bernoulli", Actas de la Royal Society of Edinburgh (1926) 46 pp. 289-305.
Referencias
- William H. Press y col. , 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