Transformación de Shanks

En análisis numérico , la transformación de Shanks es un método de aceleración de series no lineales para aumentar la tasa de convergencia de una secuencia . Este método recibe su nombre de Daniel Shanks , quien redescubrió esta transformación de secuencias en 1955. Fue derivada y publicada por primera vez por R. Schmidt en 1941. ^{[ 1 ]}

Para una secuencia${\displaystyle \left\{a_{m}\right\}_{m\in \mathbb {N} }}$la serie

${\displaystyle A=\sum _{m=0}^{\infty }a_{m}\,}$

debe determinarse. Primero, la suma parcial${\displaystyle A_{n}}$se define como:

${\displaystyle A_{n}=\sum _{m=0}^{n}a_{m}\,}$

y forma una nueva secuencia${\displaystyle \left\{A_{n}\right\}_{n\in \mathbb {N} }}$Siempre que la serie converja,${\displaystyle A_{n}}$también se acercará al límite${\displaystyle A}$como${\displaystyle n\to \infty .}$ La transformación de Shanks${\displaystyle S(A_{n})}$de la secuencia${\displaystyle A_{n}}$es la nueva secuencia definida por ^{[ 2 ] [ 3 ]}

${\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}}$

donde esta secuencia${\displaystyle S(A_{n})}$a menudo converge más rápidamente que la secuencia${\displaystyle A_{n}.}$ Se puede obtener una mayor aceleración mediante el uso repetido de la transformación de Shanks, calculando${\displaystyle S^{2}(A_{n})=S(S(A_{n})),}$${\displaystyle S^{3}(A_{n})=S(S(S(A_{n}))),}$etc.

Tenga en cuenta que la transformación no lineal utilizada en la transformación de Shanks es esencialmente la misma que la utilizada en el proceso delta-cuadrado de Aitken, de modo que, al igual que con el método de Aitken, la expresión más a la derecha en${\displaystyle S(A_{n})}$definición de (es decir${\displaystyle S(A_{n})=A_{n+1}-{\frac {(A_{n+1}-A_{n})^{2}}{(A_{n+1}-A_{n})-(A_{n}-A_{n-1})}}}$) es numéricamente más estable que la expresión a su izquierda (es decir,${\displaystyle S(A_{n})={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}}$Tanto el método de Aitken como la transformación de Shanks operan sobre una secuencia, pero la secuencia sobre la que opera la transformación de Shanks se suele considerar como una secuencia de sumas parciales, aunque cualquier secuencia puede verse como una secuencia de sumas parciales.

Como ejemplo, consideremos la serie de convergencia lenta ^{[ 3 ].}

${\displaystyle 4\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{2k+1}}=4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots \right)}$

que tiene la suma exacta π  ≈  3.14159265. La suma parcial${\displaystyle A_{6}}$Tiene una precisión de solo un dígito, mientras que para obtener una precisión de seis cifras se requieren sumar aproximadamente 400.000 términos.

En la tabla siguiente, las sumas parciales${\displaystyle A_{n}}$la transformación de Shanks${\displaystyle S(A_{n})}$sobre ellos, así como las repetidas transformaciones de Shanks${\displaystyle S^{2}(A_{n})}$y${\displaystyle S^{3}(A_{n})}$se dan para${\displaystyle n}$hasta 12. La figura de la derecha muestra el error absoluto para las sumas parciales y los resultados de la transformación de Shanks, lo que muestra claramente la mejora en la precisión y la tasa de convergencia.

La transformación de Shanks${\displaystyle S(A_{1})}$ya tiene una precisión de dos dígitos, mientras que las sumas parciales originales solo establecen la misma precisión en${\displaystyle A_{24}.}$Extraordinariamente,${\displaystyle S^{3}(A_{3})}$tiene una precisión de seis dígitos, obtenida a partir de transformaciones de Shanks repetidas aplicadas a los primeros siete términos.${\displaystyle A_{0},\ldots ,A_{6}.}$Como se mencionó anteriormente,${\displaystyle A_{n}}$Solo se obtiene una precisión de 6 dígitos después de sumar aproximadamente 400.000 términos.

La transformación de Shanks está motivada por la observación de que —para valores mayores${\displaystyle n}$— la suma parcial${\displaystyle A_{n}}$Con bastante frecuencia se comporta aproximadamente como ^{[ 2 ]}

${\displaystyle A_{n}=A+\alpha q^{n},\,}$

con${\displaystyle |q|<1}$de modo que la secuencia converge transitoriamente al resultado de la serie.${\displaystyle A}$para${\displaystyle n\to \infty .}$ Entonces para${\displaystyle n-1,}$${\displaystyle n}$y${\displaystyle n+1}$Las sumas parciales respectivas son:

${\displaystyle A_{n-1}=A+\alpha q^{n-1}\quad ,\qquad A_{n}=A+\alpha q^{n}\qquad {\text{and}}\qquad A_{n+1}=A+\alpha q^{n+1}.}$

Estas tres ecuaciones contienen tres incógnitas:${\displaystyle A,}$${\displaystyle \alpha }$y${\displaystyle q.}$Resolver para${\displaystyle A}$da ^{[ 2 ]}

${\displaystyle A={\frac {A_{n+1}\,A_{n-1}\,-\,A_{n}^{2}}{A_{n+1}-2A_{n}+A_{n-1}}}.}$

En el caso (excepcional) de que el denominador sea igual a cero: entonces${\displaystyle A_{n}=A}$a pesar de${\displaystyle n.}$

La transformación de Shanks generalizada de orden k se da como la razón de los determinantes : ^{[ 4 ]}

${\displaystyle S_{k}(A_{n})={\frac {\begin{vmatrix}A_{n-k}&\cdots &A_{n-1}&A_{n}\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}{\begin{vmatrix}1&\cdots &1&1\\\Delta A_{n-k}&\cdots &\Delta A_{n-1}&\Delta A_{n}\\\Delta A_{n-k+1}&\cdots &\Delta A_{n}&\Delta A_{n+1}\\\vdots &&\vdots &\vdots \\\Delta A_{n-1}&\cdots &\Delta A_{n+k-2}&\Delta A_{n+k-1}\\\end{vmatrix}}},}$

con${\displaystyle \Delta A_{p}=A_{p+1}-A_{p}.}$Es la solución de un modelo para el comportamiento de convergencia de las sumas parciales.${\displaystyle A_{n}}$con${\displaystyle k}$transitorios distintos:

${\displaystyle A_{n}=A+\sum _{p=1}^{k}\alpha _{p}q_{p}^{n}.}$

Este modelo para el comportamiento de convergencia contiene${\displaystyle 2k+1}$incógnitas. Al evaluar la ecuación anterior en los elementos${\displaystyle A_{n-k},A_{n-k+1},\ldots ,A_{n+k}}$y resolver para${\displaystyle A,}$Se obtiene la expresión anterior para la transformación de Shanks de orden k . La transformación de Shanks generalizada de primer orden es igual a la transformación de Shanks ordinaria:${\displaystyle S_{1}(A_{n})=S(A_{n}).}$

La transformación generalizada de Shanks está estrechamente relacionada con los aproximantes de Padé y las tablas de Padé . ^{[ 4 ]}

Nota: El cálculo de determinantes requiere muchas operaciones aritméticas; sin embargo, Peter Wynn descubrió un procedimiento de evaluación recursiva llamado algoritmo épsilon que evita el cálculo de determinantes. ^{[ 5 ] [ 6 ]}

• Proceso delta-cuadrado de Aitken
• aceleración de Anderson
• Tasa de convergencia
• Extrapolación de Richardson
• Transformación de secuencias

• Shanks, D. (1955), "Transformación no lineal de secuencias divergentes y de convergencia lenta", Journal of Mathematics and Physics , 34 ( 1–4 ): 1–42 , doi : 10.1002/sapm19553411
• Schmidt, RJ (1941), "Sobre la solución numérica de sistemas de ecuaciones lineales mediante un método iterativo", Philosophical Magazine , 32 (214): 369–383 , doi : 10.1080/14786444108520797
• Van Dyke, MD (1975), Métodos de perturbación en mecánica de fluidos (  edición anotada), Parabolic Press, ISBN 0-915760-01-0
• Bender, CM ; Orszag, SA (1999), Métodos matemáticos avanzados para científicos e ingenieros , Springer, ISBN 0-387-98931-5
• Weniger, EJ (1989). "Transformaciones de secuencias no lineales para la aceleración de la convergencia y la suma de series divergentes". Computer Physics Reports . 10 ( 5– 6): 189– 371. arXiv : math.NA/0306302 . Bibcode : 1989CoPhR..10..189W . doi : 10.1016/0167-7977(89)90011-7 .
• Brezinski, C.; Redivo-Zaglia, M .; Saad, Y. (2018), "Transformaciones de secuencias de Shanks y aceleración de Anderson", SIAM Review , 60 (3): 646– 669, doi : 10.1137/17M1120725 , hdl : 11577/3270110
• Senhadji, MN (2001), "Sobre los números de condición de la transformación de Shanks", J. Comput. Appl. Math. , 135 (1): 41– 61, Bibcode : 2001JCoAM.135...41S , doi : 10.1016/S0377-0427(00)00561-6
• Wynn, P. (1956), "Sobre un dispositivo para calcular la transformación e _m (S _{n )",} Mathematical Tables and Other Aids to Computation , 10 (54): 91– 96, doi : 10.2307/2002183 , JSTOR 2002183 
• Wynn, P. (1962), "Técnicas de aceleración para problemas iterativos de vectores y matrices", Math. Comp. , 16 (79): 301– 322, doi : 10.1090/S0025-5718-1962-0145647-X