Supongamos que tengo una secuencia monotónicamente creciente $\{d_{n}\}$ que también está acotado por encima. El $d_{n}$ satisfacen una determinada recurrencia, sin embargo computacionalmente tienden muy lentamente al límite. ¿Cuáles son algunas formas que puedo utilizar para acelerar la convergencia de esta secuencia computacionalmente? Estoy calculando estos $d_{n}$ en PARI/GP si es una información útil.
Respuestas
¿Demasiados anuncios?
*crujidos de nudillos*
Bien, en primer lugar, en cuanto a la elección de los métodos de transformación de la secuencia, uno haría bien en leer el Apéndice A de El reto de los 100 dígitos de SIAM: Un estudio sobre el cálculo numérico de alta precisión de Dirk Laurie, así como el (¡largo!) artículo de encuesta Transformaciones secuenciales no lineales para la aceleración de la convergencia y la suma de series divergentes por Ernst Joachim Weniger. (De hecho, hay libros sobre este tema, pero creo que no son demasiado "amigables" para los principiantes).
Una vez sacadas estas recomendaciones, un consejo: es una buena idea estimar al menos el comportamiento asintótico de su secuencia; la mayoría de los métodos en la práctica hacen suposiciones (¡a veces injustificadas!) sobre el comportamiento asintótico de la secuencia.
En la respuesta a este problema en particular En la sección de la página web de la Comisión Europea, mencioné dos de los caballos de batalla más comunes para extrapolar una secuencia hasta su límite (y en algunos casos hasta su antilímite, si es necesario): La extrapolación de Richardson y la transformación de Shanks (las mencioné también aquí .). He dado las fórmulas para la extrapolación de Richardson en el primer enlace; sólo diré aquí que Richardson esencialmente ajusta un polinomio interpolante a su secuencia junto con una secuencia auxiliar que tiende a 0 como abscisas, y luego evalúa el polinomio en 0. Por otro lado, la transformación de Shanks asume que la secuencia dada es de hecho los valores de las sumas parciales de una serie de potencias, y luego trata de encontrar los valores correspondientes de sucesivas Aproximaciones de Padé (la función racional cuyos primeros términos coinciden con la serie de potencias dada) de la serie supuesta.
También hay métodos especializados, si por ejemplo su secuencia se generó como las sumas parciales de una serie alterna, o como la salida de una iteración de punto fijo $x_{i+1}=f(x_i)$ . En el primer caso, uno de los métodos más sencillos es el método de Cohen, Rodríguez Villegas y Zagier (este es uno de los métodos utilizados internamente por PARI/GP para sumar series alternas); brevemente, explota las propiedades de los polinomios de Chebyshev para construir una aproximación racional a la serie alterna. La transformación de Levin (de la que hablé brevemente aquí ), por otro lado, utiliza las diferencias hacia adelante sucesivamente para eliminar los términos de error de una serie alterna.
Sólo he dado cuatro de los algoritmos que he utilizado; lo que debes sacar de aquí es que, o bien debes averiguar el comportamiento asintótico de tu secuencia, o bien tendrás que experimentar no sólo con una, sino con varias transformaciones de la secuencia si no puedes o no quieres diagnosticar el comportamiento asintótico. Como he dicho, un método de aceleración de la convergencia puede fallar estrepitosamente si sus supuestos no son aplicables a la secuencia de entrada.
Jorrit Reedijk
Puntos
129
Esto debería ir como comentario, pero quiero añadir un ejemplo, así que necesito más espacio.
Pero primero: secundo los otros comentarios, que tu pregunta debería dar más contexto y características de tu secuencia.
Aquí tenemos un ejemplo de procedimiento rápido y sucio: es una suma de Euler con negativo orden. La suma de Euler funciona mejor con series de signo alterno y crecimiento aproximadamente geométrico. Si tenemos series/secuencias crecientes no alternas, entonces se ralentiza la convergencia. Pero el orden negativo es una posibilidad en un cierto, aunque pequeño, rango de parámetros. Para tener un ejemplo utilizo la secuencia $p_k$ de sumas parciales del $\zeta(2)$ : es creciente y acotada. Entonces, como la suma de Euler suma una serie, utilizamos las diferencias $p_k-p_{k-1}$ que no son más que los cuadrados recíprocos, y obtener los términos $e_k$ de la secuencia acelerada. Aquí están las tres filas de ejemplo. (Mi ejemplo de código en Pari/GP utilizando funciones básicas propias de vector/matriz):
Gp:> Mat([Z(2),DrPow(1.0)*Z(2),ESum(-0.43)*Z(2.0)])
diff p_k Eulersummed e_k
---------------------------------
1 1 1.0000000
1/4 1.2500000 1.4385965
1/9 1.3611111 1.4497110
1/16 1.4236111 1.5208230
1/25 1.4636111 1.5315428
1/36 1.4913889 1.5569019
1/49 1.5117971 1.5648384
1/64 1.5274221 1.5770663
... ... ...
1/3136 1.6272354 1.6348067
1/3249 1.6275432 1.6349835
1/3364 1.6278405 1.6351543
1/3481 1.6281277 1.6353192
1/3600 1.6284055 1.6354787
1/3721 1.6286743 1.6356330
1/3844 1.6289344 1.6357824
1/3969 1.6291864 1.6359270
1/4096 1.6294305 1.6360671
