Extrapolación de Richardson

Método de aceleración de secuencias en análisis numérico

Un ejemplo del método de extrapolación de Richardson en dos dimensiones.

En el análisis numérico , la extrapolación de Richardson es un método de aceleración de secuencias utilizado para mejorar la tasa de convergencia de una secuencia de estimaciones de algún valor . En esencia, dado el valor de para varios valores de , podemos estimar extrapolando las estimaciones a . Recibe su nombre de Lewis Fry Richardson , quien introdujo la técnica a principios del siglo XX, ^{[1] [2]} aunque la idea ya era conocida por Christiaan Huygens en su cálculo de . ^[3] En palabras de Birkhoff y Rota , "su utilidad para los cálculos prácticos difícilmente puede sobreestimarse". ^[4] ${\displaystyle A^{\ast }=\lim _{h\to 0}A(h)}$ ${\displaystyle A(h)}$ ${\displaystyle h}$ ${\displaystyle A^{\ast }}$ ${\displaystyle h=0}$ ${\displaystyle \pi }$

Las aplicaciones prácticas de la extrapolación de Richardson incluyen la integración de Romberg , que aplica la extrapolación de Richardson a la regla del trapezoide , y el algoritmo de Bulirsch-Stoer para resolver ecuaciones diferenciales ordinarias.

Fórmula general

Notación

Sea una aproximación de (valor exacto) que depende de un tamaño de paso h (donde ) con una fórmula de error de la forma donde son constantes desconocidas y son constantes conocidas tales que . Además, representa el error de truncamiento de la aproximación tal que De manera similar, en la aproximación se dice que es una aproximación. ${\displaystyle A_{0}(h)}$ ${\displaystyle A^{*}}$ ${\textstyle 0<h<1}$ $${\displaystyle A^{*}=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots }$$ ${\displaystyle a_{i}}$ ${\displaystyle k_{i}}$ ${\displaystyle h^{k_{i}}>h^{k_{i+1}}}$ ${\displaystyle O(h^{k_{i}})}$ ${\displaystyle A_{i}(h)}$ ${\displaystyle A^{*}=A_{i}(h)+O(h^{k_{i}}).}$ ${\displaystyle A^{*}=A_{i}(h)+O(h^{k_{i}}),}$ ${\displaystyle A_{i}(h)}$ ${\displaystyle O(h^{k_{i}})}$

Nótese que al simplificar con la notación Big O , las siguientes fórmulas son equivalentes: $${\displaystyle {\begin{aligned}A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots \\A^{*}&=A_{0}(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\\A^{*}&=A_{0}(h)+O(h^{k_{0}})\end{aligned}}}$$

Objetivo

La extrapolación de Richardson es un proceso que encuentra una mejor aproximación de al cambiar la fórmula de error de a Por lo tanto, al reemplazar con el error de truncamiento se ha reducido de a para el mismo tamaño de paso . El patrón general ocurre en que es una estimación más precisa que cuando . Mediante este proceso, hemos logrado una mejor aproximación de al restar el término más grande en el error que era . Este proceso se puede repetir para eliminar más términos de error para obtener aproximaciones aún mejores. ${\displaystyle A^{*}}$ ${\displaystyle A^{*}=A_{0}(h)+O(h^{k_{0}})}$ ${\displaystyle A^{*}=A_{1}(h)+O(h^{k_{1}}).}$ ${\displaystyle A_{0}(h)}$ ${\displaystyle A_{1}(h)}$ ${\displaystyle O(h^{k_{0}})}$ ${\displaystyle O(h^{k_{1}})}$ ${\displaystyle h}$ ${\displaystyle A_{i}(h)}$ ${\displaystyle A_{j}(h)}$ ${\displaystyle i>j}$ ${\displaystyle A^{*}}$ ${\displaystyle O(h^{k_{0}})}$

Proceso

Utilizando los tamaños de paso y para alguna constante , las dos fórmulas para son: ${\displaystyle h}$ ${\displaystyle h/t}$ ${\displaystyle t}$ ${\displaystyle A^{*}}$

Para mejorar nuestra aproximación de a eliminando el primer término de error, multiplicamos la ecuación 2 por y restamos la ecuación 1 para obtener Esta multiplicación y resta se realizó porque es una aproximación de . Podemos resolver nuestra fórmula actual para a que se puede escribir como estableciendo ${\displaystyle O(h^{k_{0}})}$ ${\displaystyle O(h^{k_{1}})}$ ${\displaystyle t^{k_{0}}}$ $${\displaystyle (t^{k_{0}}-1)A^{*}={\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}+{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}+{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}+O(h^{k_{3}}).}$$ ${\textstyle {\big [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\big ]}}$ ${\displaystyle O(h^{k_{1}})}$ ${\displaystyle (t^{k_{0}}-1)A^{*}}$ ${\displaystyle A^{*}}$ $${\displaystyle A^{*}={\frac {{\bigg [}t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h){\bigg ]}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{1}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{1}}-a_{1}h^{k_{1}}{\bigg )}}{t^{k_{0}}-1}}+{\frac {{\bigg (}t^{k_{0}}a_{2}{\bigg (}{\frac {h}{t}}{\bigg )}^{k_{2}}-a_{2}h^{k_{2}}{\bigg )}}{t^{k_{0}}-1}}+O(h^{k_{3}})}$$ ${\displaystyle A^{*}=A_{1}(h)+O(h^{k_{1}})}$ $${\displaystyle A_{1}(h)={\frac {t^{k_{0}}A_{0}\left({\frac {h}{t}}\right)-A_{0}(h)}{t^{k_{0}}-1}}.}$$

Relación de recurrencia

Se puede definir una relación de recurrencia general para las aproximaciones por donde satisface $${\displaystyle A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}}$$ ${\displaystyle k_{i+1}}$ $${\displaystyle A^{*}=A_{i+1}(h)+O(h^{k_{i+1}}).}$$

Propiedades

La extrapolación de Richardson puede considerarse como una transformación de secuencia lineal .

Además, la fórmula general se puede utilizar para estimar (comportamiento del tamaño del paso de orden principal del error de truncamiento ) cuando ni su valor ni se conocen a priori . Dicha técnica puede ser útil para cuantificar una tasa de convergencia desconocida . Dadas aproximaciones de a partir de tres tamaños de paso distintos , , y , la relación exacta produce una relación aproximada (tenga en cuenta que la notación aquí puede causar un poco de confusión, los dos O que aparecen en la ecuación anterior solo indican el comportamiento del tamaño del paso de orden principal, pero sus formas explícitas son diferentes y, por lo tanto, la cancelación de los dos términos O solo es aproximadamente válida) que se puede resolver numéricamente para estimar para algunas opciones válidas arbitrarias de , , y . ${\displaystyle k_{0}}$ ${\displaystyle A^{*}}$ ${\displaystyle A^{*}}$ ${\displaystyle h}$ ${\displaystyle h/t}$ ${\displaystyle h/s}$ $${\displaystyle A^{*}={\frac {t^{k_{0}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}+O(h^{k_{1}})={\frac {s^{k_{0}}A_{i}\left({\frac {h}{s}}\right)-A_{i}(h)}{s^{k_{0}}-1}}+O(h^{k_{1}})}$$ $${\displaystyle A_{i}\left({\frac {h}{t}}\right)+{\frac {A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{0}}-1}}\approx A_{i}\left({\frac {h}{s}}\right)+{\frac {A_{i}\left({\frac {h}{s}}\right)-A_{i}(h)}{s^{k_{0}}-1}}}$$ ${\displaystyle k_{0}}$ ${\displaystyle h}$ ${\displaystyle s}$ ${\displaystyle t}$

Como , si y se elige de modo que , esta relación aproximada se reduce a una ecuación cuadrática en , que se resuelve fácilmente en términos de y . ${\displaystyle t\neq 1}$ ${\displaystyle t>0}$ ${\displaystyle s}$ ${\displaystyle s=t^{2}}$ ${\displaystyle t^{k_{0}}}$ ${\displaystyle k_{0}}$ ${\displaystyle h}$ ${\displaystyle t}$

Ejemplo de extrapolación de Richardson

Supongamos que deseamos aproximar , y tenemos un método que depende de un parámetro pequeño de tal manera que ${\displaystyle A^{*}}$ ${\displaystyle A(h)}$ ${\displaystyle h}$ $${\displaystyle A(h)=A^{\ast }+Ch^{n}+O(h^{n+1}).}$$

Definamos una nueva función donde y son dos tamaños de paso distintos. $${\displaystyle R(h,t):={\frac {t^{n}A(h/t)-A(h)}{t^{n}-1}}}$$ ${\displaystyle h}$ ${\displaystyle {\frac {h}{t}}}$

Entonces se llama extrapolación de Richardson de A ( h ), y tiene una estimación de error de orden superior en comparación con . $${\displaystyle R(h,t)={\frac {t^{n}(A^{*}+C\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{*}+Ch^{n}+O(h^{n+1}))}{t^{n}-1}}=A^{*}+O(h^{n+1}).}$$ ${\displaystyle R(h,t)}$ ${\displaystyle O(h^{n+1})}$ ${\displaystyle A(h)}$

Muy a menudo, es mucho más fácil obtener una precisión dada utilizando R ( h ) en lugar de A ( h′ ) con un h′ mucho menor . Donde A ( h′ ) puede causar problemas debido a la precisión limitada ( errores de redondeo ) y/o debido al creciente número de cálculos necesarios (ver ejemplos a continuación).

Ejemplo de pseudocódigo para la extrapolación de Richardson

El siguiente pseudocódigo en estilo MATLAB demuestra la extrapolación de Richardson para ayudar a resolver la EDO , con el método trapezoidal . En este ejemplo, dividimos a la mitad el tamaño del paso en cada iteración y, por lo tanto, en la discusión anterior tendríamos que . El error del método trapezoidal se puede expresar en términos de potencias impares, de modo que el error en varios pasos se puede expresar en potencias pares; esto nos lleva a elevar a la segunda potencia y a tomar potencias de en el pseudocódigo. Queremos encontrar el valor de , que tiene la solución exacta de ya que la solución exacta de la EDO es . Este pseudocódigo supone que existe una función llamada que intenta calcular realizando el método trapezoidal en la función , con punto de inicio y y tamaño de paso . ${\displaystyle y'(t)=-y^{2}}$ ${\displaystyle y(0)=1}$ ${\displaystyle h}$ ${\displaystyle t=2}$ ${\displaystyle t}$ ${\displaystyle 4=2^{2}=t^{2}}$ ${\displaystyle y(5)}$ ${\displaystyle {\frac {1}{5+1}}={\frac {1}{6}}=0.1666...}$ ${\displaystyle y(t)={\frac {1}{1+t}}}$Trapezoidal(f, tStart, tEnd, h, y0)y(tEnd)fy0tStarth

Tenga en cuenta que comenzar con un tamaño de paso inicial demasiado pequeño puede generar errores en la solución final. Aunque existen métodos diseñados para ayudar a elegir el mejor tamaño de paso inicial, una opción es comenzar con un tamaño de paso grande y luego permitir que la extrapolación de Richardson reduzca el tamaño del paso en cada iteración hasta que el error alcance la tolerancia deseada.

tStart = 0 % Tiempo de inicio tEnd = 5 % Tiempo de finalización f = - y ^ 2 % La derivada de y, por lo que y' = f(t, y(t)) = -y^2 % La solución de esta EDO es y = 1/(1 + t) y0 = 1 % La posición inicial (es decir, y0 = y(tStart) = y(0) = 1) tolerancia = 10 ^ - 11 % Se desea una precisión de 10 dígitos                % No permita que la iteración continúe indefinidamente maxRows = 20 % Elija un tamaño de paso inicial initialH = tStart - tEnd % ¿Pudimos encontrar la solución dentro de la tolerancia deseada? todavía no. haveWeFoundSolution = false        h = H inicial  % Cree una matriz 2D de tamaño maxRows por maxRows para contener las extrapolaciones de Richardson. % Tenga en cuenta que esta será una matriz triangular inferior y que, como máximo, se necesitan dos filas en cualquier momento del cálculo. A = zeroMatrix ( maxRows , maxRows )   % Calcular el elemento superior izquierdo de la matriz. % La primera fila de esta matriz (triangular inferior) ya está completa. A ( 1 , 1 ) = Trapezoidal ( f , tStart , tEnd , h , y0 )       % Cada fila de la matriz requiere una llamada a Trapezoidal % Este bucle comienza llenando la segunda fila de la matriz, % ya que la primera fila se calculó anteriormente para i = 1 : maxRows - 1 % Comenzando en i = 1, itera como máximo maxRows - 1 veces % Reduce a la mitad el valor anterior de h ya que este es el comienzo de una nueva fila. h = h / 2             % Comenzando a llenar la fila i+1 desde la izquierda llamando a la función trapezoidal con este nuevo tamaño de paso más pequeño A ( i + 1 , 1 ) = Trapezoidal ( f , tStart , tEnd , h , y0 )            % Recorrer esta fila actual (i+1)-ésima hasta alcanzar la diagonal para j = 1 : i % Para calcular A(i + 1, j + 1), que es la siguiente extrapolación de Richardson, % utilizar el valor calculado más recientemente (es decir, A(i + 1, j)) % y el valor de la fila superior (es decir, A(i, j)).          A ( i + 1 , j + 1 ) = (( 4 ^ j ) .* A ( i + 1 , j ) - A ( i , j )) / ( 4 ^ j - 1 ); fin % Después de salir del bucle interno anterior, se ha calculado el elemento diagonal de la fila i + 1 % Este elemento diagonal es la última extrapolación de Richardson que se calculará. % La diferencia entre esta extrapolación y la última extrapolación de la fila i es una buena % indicación del error. if ( absoluteValue ( A ( i + 1 , i + 1 ) - A ( i , i )) < tolerancia ) % Si el resultado está dentro de la tolerancia % Muestra el resultado de la extrapolación de Richardson print ( "y = " , A ( i + 1 , i + 1 )) haveWeFoundSolution = true % Listo, por lo que se sale del bucle break fin fin                                                % Si no pudimos encontrar una solución dentro de la tolerancia deseada if ( not haveWeFoundSolution ) print ( "Advertencia: No se pudo encontrar una solución dentro de la tolerancia deseada de " , tolerancia ); print ( "La última extrapolación calculada fue " , A ( maxRows , maxRows )) end       

Véase también

• Proceso delta-cuadrado de Aitken
• Takebe Kenko
• Iteración de Richardson

Referencias

1. Richardson, LF (1911). "La solución aritmética aproximada por diferencias finitas de problemas físicos, incluyendo ecuaciones diferenciales, con una aplicación a las tensiones en una presa de mampostería". Philosophical Transactions of the Royal Society A . 210 (459–470): 307–357. doi : 10.1098/rsta.1911.0009 .
2. Richardson, LF ; Gaunt, JA (1927). "La aproximación diferida al límite". Philosophical Transactions of the Royal Society A . 226 (636–646): 299–349. doi : 10.1098/rsta.1927.0008 .
3. Brezinski, Claude (1 de noviembre de 2009), "Algunos pioneros de los métodos de extrapolación", El nacimiento del análisis numérico , WORLD SCIENTIFIC, págs. 1–22, doi :10.1142/9789812836267_0001, ISBN 978-981-283-625-0
4. Página 126 de Birkhoff, Garrett ; Gian-Carlo Rota (1978). Ecuaciones diferenciales ordinarias (3.ª ed.). John Wiley and sons. ISBN 0-471-07411-X.OCLC 4379402  .

• Métodos de extrapolación. Teoría y práctica , C. Brezinski y M. Redivo Zaglia , Holanda Septentrional, 1991.
• Ivan Dimov, Zahari Zlatev, Istvan Farago, Agnes Havasi: Extrapolación de Richardson: aspectos prácticos y aplicaciones , Walter de Gruyter GmbH & Co KG, ISBN 9783110533002 (2017). 

Enlaces externos

• Extrapolación de Richardson
• Extrapolación de Richardson en un sitio web de Robert Israel (Universidad de Columbia Británica)
• Código Matlab para extrapolación genérica de Richardson.
• Código Julia para extrapolación genérica de Richardson.