En análisis numérico , la extrapolación de Richardson es un método de aceleración de secuencia , 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 . Lleva el nombre de Lewis Fry Richardson , quien introdujo la técnica a principios del siglo XX. [1] [2] En palabras de Birkhoff y Rota , "difícilmente se puede sobrestimar su utilidad para cálculos prácticos". [3]
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.
Ejemplo de extrapolación de Richardson
Supongamos que deseamos aproximarnos y tenemos un método eso depende de un pequeño parámetro de una manera que
Definamos una nueva función
dónde y son dos tamaños de paso distintos.
Luego
se llama extrapolación de Richardson de A ( h ), y tiene una estimación de error de orden superior en comparación con .
Muy a menudo, es mucho más fácil obtener una precisión dada usando R (h) en lugar de A (h ') con una 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).
Formula general
Dejar ser una aproximación de (valor exacto) que depende de un tamaño de paso positivo h con una fórmula de error de la forma
donde las a i son constantes desconocidas y las k i son constantes conocidas tales que h k i > h k i + 1 .
Además, k 0 es el comportamiento del tamaño de paso de orden principal del error de truncamiento como
El valor exacto buscado puede estar dado por
que se puede simplificar con la notación Big O para ser
Uso de la tamaños de paso h ypara alguna t constante , las dos fórmulas para A son:
Multiplicar la segunda ecuación por t k 0 y restar la primera ecuación da
que se puede resolver para dar
Por lo tanto, usando el error de truncamiento se ha reducido a . Esto contrasta condonde el error de truncamiento es para el mismo tamaño de paso
Mediante este proceso, hemos logrado una mejor aproximación de A restando el término más grande en el error que era O ( h k 0 ). Este proceso se puede repetir para eliminar más términos de error y obtener aproximaciones aún mejores.
Una relación de recurrencia general que comienza con se puede definir para las aproximaciones por
dónde satisface
- .
La extrapolación de Richardson se puede considerar como una transformación de secuencia lineal .
Además, la fórmula general se puede utilizar para estimar k 0 (comportamiento del tamaño de paso de orden principal del error de truncamiento ) cuando ni su valor ni A * (valor exacto) se conocen a priori . Esta técnica puede resultar útil para cuantificar una tasa de convergencia desconocida . Dadas aproximaciones de A de tres tamaños de paso distintos h , h / t y h / s , la relación exacta
produce una relación aproximada (tenga en cuenta que la notación aquí puede causar un poco de confusión, las dos O que aparecen en la ecuación anterior solo indican el comportamiento del tamaño de paso del orden principal, pero sus formas explícitas son diferentes y, por lo tanto, cancelar los dos términos O es aproximadamente válido)
que pueden resolverse numéricamente para estimación k 0 para algunas elecciones arbitrarias de h , s y t .
Ejemplo de código 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, reducimos a la mitad el tamaño del paso. 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 levantar al segundo poder y tomar poderes 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 asume que Trapezoidal(f, tStart, tEnd, h, y0)
existe una función llamada que intenta calcular y(tEnd)
realizando el método trapezoidal en la función f
, con punto de partida y0
y tStart
tamaño de paso h
.
Tenga en cuenta que comenzar con un tamaño de paso inicial demasiado pequeño puede introducir 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 de paso en cada iteración hasta que el error alcance la tolerancia deseada.
tStart = 0 % Hora de inicio tEnd = 5 % Hora de finalización f = - y ^ 2 % La derivada de y, entonces y '= f (t, y (t)) = -y ^ 2 % La solución a 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 precisión de 10 dígitos maxRows = 20 % No permita que la iteración continúe indefinidamente initialH = tStart - tEnd % Elija un tamaño de paso inicial haveWeFoundSolution = false % ¿ Pudimos encontrar la solución dentro de la tolerancia deseada? aún no. h = initialH % 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 dos filas son en realidad% necesario en cualquier momento del cálculo.A = zeroMatrix ( maxRows , maxRows ) % Calcule el elemento superior izquierdo de la matriz. La primera fila de esta matriz (triangular inferior) ahora se ha llenado.A ( 1 , 1 ) = Trapezoidal ( f , tStart , tEnd , h , y0 ) % Cada fila de la matriz requiere una llamada a Trapezoidal% Este ciclo comienza llenando la segunda fila de la matriz, ya que la primera fila se calculó arribapara i = 1 : maxRows - 1 % Comenzando en i = 1, iterar como máximo maxRows - 1 veces h = h / 2 % Reducir a la mitad el valor anterior de h ya que este es el comienzo de una nueva fila. % 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 ) para j = 1 : i % Ir a través de esta corriente (i + 1) -ésima fila hasta alcanzar la diagonal % Para calcular A (i + 1, j + 1), que es la siguiente extrapolación de Richardson, % utiliza el valor calculado más recientemente (es decir, A (i + 1, j)) y el valor de la % fila encima de ella (es decir, A (i, j)). A ( i + 1 , j + 1 ) = (( 4 ^ j ) . * A ( i + 1 , j ) - A ( i , j )) / ( 4 ^ j - 1 ); final % Después de dejar el bucle interior anterior, se ha calculado el elemento diagonal de la fila i + 1 % Este elemento diagonal es la última extrapolación de Richardson calculada. % La diferencia entre esta extrapolación y la última extrapolación de la fila i es una buena % indicación del error. if (valor absoluto ( A ( i + 1 , i + 1 ) - A ( i , i )) < tolerancia ) % Si el resultado está dentro de la tolerancia print ( "y =" , A ( i + 1 , i + 1 )) % Muestra el resultado de la extrapolación de Richardson haveWeFoundSolution = verdadero break % Done, así que deja el bucle finalfinalif ( 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" , A ( maxRows , maxRows )) final
Ver también
Referencias
- ^ 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 de la Royal Society A . 210 (459–470): 307–357. doi : 10.1098 / rsta.1911.0009 .
- ^ Richardson, LF ; Gaunt, JA (1927). "El acercamiento diferido al límite" . Philosophical Transactions de la Royal Society A . 226 (636–646): 299–349. doi : 10.1098 / rsta.1927.0008 .
- ^ Página 126 de Birkhoff, Garrett ; Gian-Carlo Rota (1978). Ecuaciones diferenciales ordinarias (3ª ed.). John Wiley e hijos. ISBN 0-471-07411-X. OCLC 4379402 .
- Métodos de extrapolación. Teoría y práctica de 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
- Métodos fundamentales de extrapolación numérica con aplicaciones , mit.edu
- 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 de Julia para la extrapolación genérica de Richardson.