Método lineal de varios pasos

Clase de métodos numéricos iterativos para resolver ecuaciones diferenciales.

Los métodos lineales de varios pasos se utilizan para la solución numérica de ecuaciones diferenciales ordinarias . Conceptualmente, un método numérico comienza desde un punto inicial y luego avanza un pequeño paso en el tiempo para encontrar el siguiente punto de solución. El proceso continúa con pasos posteriores para trazar la solución. Los métodos de un solo paso (como el método de Euler ) se refieren solo a un punto anterior y su derivada para determinar el valor actual. Los métodos como Runge-Kutta toman algunos pasos intermedios (por ejemplo, medio paso) para obtener un método de orden superior, pero luego descartan toda la información previa antes de dar un segundo paso. Los métodos de varios pasos intentan ganar eficiencia manteniendo y utilizando la información de los pasos anteriores en lugar de descartarla. En consecuencia, los métodos de varios pasos se refieren a varios puntos anteriores y valores derivados. En el caso de métodos lineales de varios pasos, se utiliza una combinación lineal de los puntos anteriores y los valores derivados.

Definiciones

Los métodos numéricos para ecuaciones diferenciales ordinarias aproximan soluciones a problemas de valores iniciales de la forma

$${\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.}$$

El resultado son aproximaciones para el valor de en tiempos discretos : ${\displaystyle y(t)}$ ${\displaystyle t_{i}}$

$${\displaystyle y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,}$$

${\displaystyle h}$ ${\displaystyle \Delta t}$ ${\displaystyle i}$

Los métodos de varios pasos utilizan información de los pasos anteriores para calcular el siguiente valor. En particular, un método lineal de varios pasos utiliza una combinación lineal de y para calcular el valor de para el paso actual deseado. Por tanto, un método lineal de varios pasos es un método de la forma ${\displaystyle s}$ ${\displaystyle y_{i}}$ ${\displaystyle f(t_{i},y_{i})}$ ${\displaystyle y}$

$${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}\cdot y_{n+s-1}+a_{s-2}\cdot y_{n+s-2}+\cdots +a_{0}\cdot y_{n}\\&\qquad {}=h\cdot \left(b_{s}\cdot f(t_{n+s},y_{n+s})+b_{s-1}\cdot f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}\cdot f(t_{n},y_{n})\right)\\&\Leftrightarrow \sum _{j=0}^{s}a_{j}y_{n+j}=h\sum _{j=0}^{s}b_{j}f(t_{n+j},y_{n+j}),\end{aligned}}}$$

${\displaystyle a_{s}=1}$ ${\displaystyle a_{0},\dotsc ,a_{s-1}}$ ${\displaystyle b_{0},\dotsc ,b_{s}}$

Se puede distinguir entre métodos explícitos e implícitos . Si , entonces el método se llama "explícito", ya que la fórmula puede calcular directamente . Si entonces el método se llama "implícito", ya que el valor de depende del valor de , y la ecuación debe resolverse para . A menudo se utilizan métodos iterativos como el método de Newton para resolver la fórmula implícita. ${\displaystyle b_{s}=0}$ ${\displaystyle y_{n+s}}$ ${\displaystyle b_{s}\neq 0}$ ${\displaystyle y_{n+s}}$ ${\displaystyle f(t_{n+s},y_{n+s})}$ ${\displaystyle y_{n+s}}$

A veces se utiliza un método explícito de varios pasos para "predecir" el valor de . Luego, ese valor se utiliza en una fórmula implícita para "corregir" el valor. El resultado es un método predictor-corrector . ${\displaystyle y_{n+s}}$

Ejemplos

Consideremos por ejemplo el problema

$${\displaystyle y'=f(t,y)=y,\quad y(0)=1.}$$

${\displaystyle y(t)=e^{t}}$

Euler de un paso

Un método numérico simple es el método de Euler:

$${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).}$$

Este método, aplicado con tamaño de paso sobre el problema , da los siguientes resultados: ${\displaystyle h={\tfrac {1}{2}}}$ ${\displaystyle y'=y}$

$${\displaystyle {\begin{aligned}y_{1}&=y_{0}+hf(t_{0},y_{0})=1+{\tfrac {1}{2}}\cdot 1=1.5,\\y_{2}&=y_{1}+hf(t_{1},y_{1})=1.5+{\tfrac {1}{2}}\cdot 1.5=2.25,\\y_{3}&=y_{2}+hf(t_{2},y_{2})=2.25+{\tfrac {1}{2}}\cdot 2.25=3.375,\\y_{4}&=y_{3}+hf(t_{3},y_{3})=3.375+{\tfrac {1}{2}}\cdot 3.375=5.0625.\end{aligned}}}$$

Adams-Bashforth de dos pasos

El método de Euler es un método de un solo paso. Un método simple de varios pasos es el método Adams-Bashforth de dos pasos.

$${\displaystyle y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).}$$

${\displaystyle y_{n+1}}$ ${\displaystyle y_{n}}$ ${\displaystyle y_{n+2}}$ ${\displaystyle y_{0}=1}$ ${\displaystyle y_{1}}$

$${\displaystyle {\begin{aligned}y_{2}&=y_{1}+{\tfrac {3}{2}}hf(t_{1},y_{1})-{\tfrac {1}{2}}hf(t_{0},y_{0})=1.5+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1=2.375,\\y_{3}&=y_{2}+{\tfrac {3}{2}}hf(t_{2},y_{2})-{\tfrac {1}{2}}hf(t_{1},y_{1})=2.375+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5=3.7812,\\y_{4}&=y_{3}+{\tfrac {3}{2}}hf(t_{3},y_{3})-{\tfrac {1}{2}}hf(t_{2},y_{2})=3.7812+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 3.7812-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375=6.0234.\end{aligned}}}$$

${\displaystyle t=t_{4}=2}$ ${\displaystyle e^{2}=7.3891\ldots }$

Familias de métodos de varios pasos.

Se utilizan habitualmente tres familias de métodos lineales de varios pasos: los métodos de Adams-Bashforth, los métodos de Adams-Moulton y las fórmulas de diferenciación hacia atrás (BDF).

Métodos Adams-Bashforth

Los métodos Adams-Bashforth son métodos explícitos. Los coeficientes son y , mientras que los se eligen de manera que los métodos tengan orden s (esto determina los métodos de forma única). ${\displaystyle a_{s-1}=-1}$ ${\displaystyle a_{s-2}=\cdots =a_{0}=0}$ ${\displaystyle b_{j}}$

Los métodos de Adams-Bashforth con s = 1, 2, 3, 4, 5 son (Hairer, Nørsett & Wanner 1993, §III.1; Butcher 2003, p. 103):

$${\displaystyle {\begin{aligned}y_{n+1}&=y_{n}+hf(t_{n},y_{n}),\qquad {\text{(This is the Euler method)}}\\y_{n+2}&=y_{n+1}+h\left({\frac {3}{2}}f(t_{n+1},y_{n+1})-{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {23}{12}}f(t_{n+2},y_{n+2})-{\frac {16}{12}}f(t_{n+1},y_{n+1})+{\frac {5}{12}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {55}{24}}f(t_{n+3},y_{n+3})-{\frac {59}{24}}f(t_{n+2},y_{n+2})+{\frac {37}{24}}f(t_{n+1},y_{n+1})-{\frac {9}{24}}f(t_{n},y_{n})\right),\\y_{n+5}&=y_{n+4}+h\left({\frac {1901}{720}}f(t_{n+4},y_{n+4})-{\frac {2774}{720}}f(t_{n+3},y_{n+3})+{\frac {2616}{720}}f(t_{n+2},y_{n+2})-{\frac {1274}{720}}f(t_{n+1},y_{n+1})+{\frac {251}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

Los coeficientes se pueden determinar de la siguiente manera. Utilice la interpolación polinomial para encontrar el polinomio p de grado tal que ${\displaystyle b_{j}}$ ${\displaystyle s-1}$

$${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$$

fórmula de Lagrange

$${\displaystyle p(t)=\sum _{j=0}^{s-1}{\frac {(-1)^{s-j-1}f(t_{n+j},y_{n+j})}{j!(s-j-1)!h^{s-1}}}\prod _{i=0 \atop i\neq j}^{s-1}(t-t_{n+i}).}$$

pp ${\displaystyle y'=f(t,y)}$ ${\displaystyle y'=p(t)}$

$${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.}$$

p . ${\displaystyle b_{j}}$

$${\displaystyle b_{s-j-1}={\frac {(-1)^{j}}{j!(s-j-1)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s-1}(u+i)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s-1.}$$

ph ^sde s pasos tiene de hecho orden s ${\displaystyle f(t,y)}$

Los métodos Adams-Bashforth fueron diseñados por John Couch Adams para resolver una ecuación diferencial que modela la acción capilar debida a Francis Bashforth . Bashforth (1883) publicó su teoría y el método numérico de Adams (Goldstine 1977).

Métodos Adams-Moulton

Los métodos Adams-Moulton son similares a los métodos Adams-Bashforth en que también tienen y . Nuevamente los coeficientes b se eligen para obtener el orden más alto posible. Sin embargo, los métodos de Adams-Moulton son métodos implícitos. Al eliminar la restricción de que , un método Adams-Moulton de s pasos puede alcanzar el orden , mientras que un método Adams-Bashforth de s pasos solo tiene orden s . ${\displaystyle a_{s-1}=-1}$ ${\displaystyle a_{s-2}=\cdots =a_{0}=0}$ ${\displaystyle b_{s}=0}$ ${\displaystyle s+1}$

Se enumeran los métodos de Adams-Moulton con s = 0, 1, 2, 3, 4 (Hairer, Nørsett & Wanner 1993, §III.1; Quarteroni, Sacco & Saleri 2000), donde los dos primeros métodos son el método de Euler hacia atrás. y la regla trapezoidal respectivamente:

$${\displaystyle {\begin{aligned}y_{n}&=y_{n-1}+hf(t_{n},y_{n}),\\y_{n+1}&=y_{n}+{\frac {1}{2}}h\left(f(t_{n+1},y_{n+1})+f(t_{n},y_{n})\right),\\y_{n+2}&=y_{n+1}+h\left({\frac {5}{12}}f(t_{n+2},y_{n+2})+{\frac {8}{12}}f(t_{n+1},y_{n+1})-{\frac {1}{12}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {9}{24}}f(t_{n+3},y_{n+3})+{\frac {19}{24}}f(t_{n+2},y_{n+2})-{\frac {5}{24}}f(t_{n+1},y_{n+1})+{\frac {1}{24}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {251}{720}}f(t_{n+4},y_{n+4})+{\frac {646}{720}}f(t_{n+3},y_{n+3})-{\frac {264}{720}}f(t_{n+2},y_{n+2})+{\frac {106}{720}}f(t_{n+1},y_{n+1})-{\frac {19}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

La derivación de los métodos Adams-Moulton es similar a la del método Adams-Bashforth; sin embargo, el polinomio de interpolación utiliza no sólo los puntos , como arriba, sino también . Los coeficientes están dados por ${\displaystyle t_{n-1},\dots ,t_{n-s}}$ ${\displaystyle t_{n}}$

$${\displaystyle b_{s-j}={\frac {(-1)^{j}}{j!(s-j)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s}(u+i-1)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s.}$$

Los métodos Adams-Moulton se deben únicamente a John Couch Adams , al igual que los métodos Adams-Bashforth. El nombre de Forest Ray Moulton se asoció con estos métodos porque se dio cuenta de que podían usarse junto con los métodos Adams-Bashforth como un par predictor-corrector (Moulton 1926); Milne (1926) tuvo la misma idea. Adams utilizó el método de Newton para resolver la ecuación implícita (Hairer, Nørsett & Wanner 1993, §III.1).

Fórmulas de diferenciación hacia atrás (BDF)

Los métodos BDF son métodos implícitos con y los demás coeficientes elegidos de manera que el método alcance el orden s (el máximo posible). Estos métodos se utilizan especialmente para la solución de ecuaciones diferenciales rígidas . ${\displaystyle b_{s-1}=\cdots =b_{0}=0}$

Análisis

Los conceptos centrales en el análisis de métodos lineales de varios pasos, y de hecho de cualquier método numérico para ecuaciones diferenciales, son la convergencia, el orden y la estabilidad .

Consistencia y orden

La primera pregunta es si el método es consistente: ¿la ecuación en diferencias

$${\displaystyle {\begin{aligned}&a_{s}y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$$

consistenteerror de truncamiento localhherror de truncamiento localseries de Taylor ${\displaystyle y'=f(t,y)}$ ${\displaystyle y_{n+s}}$ ${\displaystyle y_{n+s-1},\ldots ,y_{n}}$ ${\displaystyle t_{n+s}}$

$${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad \sum _{k=0}^{s}b_{k}=s+\sum _{k=0}^{s-1}ka_{k}.}$$

Si el método es consistente, entonces la siguiente pregunta es qué tan bien se aproxima la ecuación en diferencias que define el método numérico a la ecuación diferencial. Se dice que un método de varios pasos tiene orden p si el error local es de orden cuando h tiende a cero. Esto equivale a la siguiente condición sobre los coeficientes de los métodos: ${\displaystyle O(h^{p+1})}$

$${\displaystyle \sum _{k=0}^{s-1}a_{k}=-1\quad {\text{and}}\quad q\sum _{k=0}^{s}k^{q-1}b_{k}=s^{q}+\sum _{k=0}^{s-1}k^{q}a_{k}{\text{ for }}q=1,\ldots ,p.}$$

s pasos tiene orden ss ${\displaystyle s+1}$

Estas condiciones a menudo se formulan utilizando los polinomios característicos.

$${\displaystyle \rho (z)=z^{s}+\sum _{k=0}^{s-1}a_{k}z^{k}\quad {\text{and}}\quad \sigma (z)=\sum _{k=0}^{s}b_{k}z^{k}.}$$

p

$${\displaystyle \rho (e^{h})-h\sigma (e^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.}$$

${\displaystyle \rho (1)=0}$ ${\displaystyle \rho '(1)=\sigma (1)}$

Estabilidad y convergencia

La solución numérica de un método de un paso depende de la condición inicial , pero la solución numérica de un método de s pasos depende de todos los s valores iniciales . Por tanto, es de interés si la solución numérica es estable con respecto a las perturbaciones en los valores iniciales. Un método lineal de varios pasos es estable en cero para una determinada ecuación diferencial en un intervalo de tiempo dado, si una perturbación en los valores iniciales de tamaño ε causa que la solución numérica durante ese intervalo de tiempo cambie en no más de K ε para algún valor de K que no depende del tamaño del paso h . Esto se llama "estabilidad cero" porque basta con comprobar la condición de la ecuación diferencial (Süli y Mayers 2003, p. 332). ${\displaystyle y_{0}}$ ${\displaystyle y_{0},y_{1},\ldots ,y_{s-1}}$ ${\displaystyle y'=0}$

Si todas las raíces del polinomio característico ρ tienen un módulo menor o igual a 1 y las raíces del módulo 1 son de multiplicidad 1, decimos que se cumple la condición de la raíz . Un método lineal de varios pasos es estable en cero si y sólo si se satisface la condición de la raíz (Süli y Mayers 2003, p. 335).

Ahora supongamos que se aplica un método lineal consistente de varios pasos a una ecuación diferencial suficientemente suave y que todos los valores iniciales convergen al valor inicial como . Entonces, la solución numérica converge a la solución exacta como si y sólo si el método es estable en cero. Este resultado se conoce como teorema de equivalencia de Dahlquist , llamado así en honor a Germund Dahlquist ; este teorema es similar en espíritu al teorema de equivalencia de Lax para métodos de diferencias finitas . Además, si el método tiene orden p , entonces el error global (la diferencia entre la solución numérica y la solución exacta en un tiempo fijo) es (Süli & Mayers 2003, p. 340). ${\displaystyle y_{1},\ldots ,y_{s-1}}$ ${\displaystyle y_{0}}$ ${\displaystyle h\to 0}$ ${\displaystyle h\to 0}$ ${\displaystyle O(h^{p})}$

Además, si el método es convergente, se dice que es fuertemente estable si es la única raíz del módulo 1. Si es convergente y todas las raíces del módulo 1 no se repiten, pero hay más de una de esas raíces, es Se dice que es relativamente estable . Tenga en cuenta que 1 debe ser una raíz para que el método sea convergente; por tanto, los métodos convergentes son siempre uno de estos dos. ${\displaystyle z=1}$

Para evaluar el rendimiento de los métodos lineales de varios pasos en ecuaciones rígidas , considere la ecuación de prueba lineal y' = λ y . Un método de varios pasos aplicado a esta ecuación diferencial con un tamaño de paso h produce una relación de recurrencia lineal con un polinomio característico

$${\displaystyle \pi (z;h\lambda )=(1-h\lambda \beta _{s})z^{s}+\sum _{k=0}^{s-1}(\alpha _{k}-h\lambda \beta _{k})z^{k}=\rho (z)-h\lambda \sigma (z).}$$

polinomio de estabilidadabsolutamente establehA-establehregión de estabilidad absolutalos hecuaciones rígidas y métodos de varios pasos

Ejemplo

Considere el método de tres pasos de Adams-Bashforth

$${\displaystyle y_{n+3}=y_{n+2}+h\left({23 \over 12}f(t_{n+2},y_{n+2})-{4 \over 3}f(t_{n+1},y_{n+1})+{5 \over 12}f(t_{n},y_{n})\right).}$$

$${\displaystyle \rho (z)=z^{3}-z^{2}=z^{2}(z-1)}$$

${\displaystyle z=0,1}$ ${\displaystyle z=1}$

El otro polinomio característico es

$${\displaystyle \sigma (z)={\frac {23}{12}}z^{2}-{\frac {4}{3}}z+{\frac {5}{12}}}$$

Primera y segunda barreras de Dahlquist

Estos dos resultados fueron demostrados por Germund Dahlquist y representan un límite importante para el orden de convergencia y para la estabilidad A de un método lineal de varios pasos. La primera barrera de Dahlquist se demostró en Dahlquist (1956) y la segunda en Dahlquist (1963).

Primera barrera de Dahlquist

La primera barrera de Dahlquist establece que un método de múltiples pasos lineal y estable en cero no puede alcanzar un orden de convergencia mayor que q + 1 si q es impar y mayor que q + 2 si q es par. Si el método también es explícito, entonces no puede alcanzar un orden mayor que q (Hairer, Nørsett & Wanner 1993, Thm III.3.5).

Segunda barrera de Dahlquist

La segunda barrera de Dahlquist establece que ningún método lineal explícito de varios pasos es A-estable . Además, el orden máximo de un método lineal multipaso A-estable (implícito) es 2. Entre los métodos lineales multipaso A-estable de orden 2, la regla trapezoidal tiene la constante de error más pequeña (Dahlquist 1963, Thm 2.1 y 2.2).

Ver también

• Ganancia de energía digital

Referencias

• Bashforth, Francis (1883), Un intento de probar las teorías de la acción capilar comparando las formas teórica y medida de gotas de fluido. Con una explicación del método de integración empleado en la construcción de las tablas que dan las formas teóricas de tales gotas, por JC Adams , Cambridge{{citation}}: CS1 maint: location missing publisher (link).
• Butcher, John C. (2003), Métodos numéricos para ecuaciones diferenciales ordinarias , John Wiley, ISBN 978-0-471-96758-3.
• Dahlquist, Germund (1956), "Convergencia y estabilidad en la integración numérica de ecuaciones diferenciales ordinarias", Mathematica Scandinavica , 4 : 33–53, doi : 10.7146/math.scand.a-10454.
• Dahlquist, Germund (1963), "Un problema especial de estabilidad para métodos lineales de varios pasos", BIT , 3 : 27–43, doi :10.1007/BF01963532, ISSN  0006-3835, S2CID  120241743.
• Goldstine, Herman H. (1977), Una historia del análisis numérico del siglo XVI al XIX , Nueva York: Springer-Verlag, ISBN 978-0-387-90277-7.
• Hairer, Ernst; Norsett, Syvert Paul; Wanner, Gerhard (1993), Resolución de ecuaciones diferenciales ordinarias I: problemas no rígidos (2ª ed.), Berlín: Springer Verlag, ISBN 978-3-540-56670-0.
• Hairer, Ernst; Wanner, Gerhard (1996), Resolución de ecuaciones diferenciales ordinarias II: problemas rígidos y algebraicos diferenciales (2ª ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-3-540-60452-5.
• Iserles, Arieh (1996), Primer curso sobre análisis numérico de ecuaciones diferenciales , Cambridge University Press, ISBN 978-0-521-55655-2.
• Milne, WE (1926), "Integración numérica de ecuaciones diferenciales ordinarias", American Mathematical Monthly , Mathematical Association of America, 33 (9): 455–460, doi :10.2307/2299609, JSTOR  2299609.
• Moulton, Forest R. (1926), Nuevos métodos en balística exterior , University of Chicago Press.
• Quarteroni, Alfio ; Sacco, Ricardo; Saleri, Fausto (2000), Matematica Numerica , Springer Verlag, ISBN 978-88-470-0077-3.
• Süli, Endre; Mayers, David (2003), Introducción al análisis numérico , Cambridge University Press , ISBN 0-521-00794-1.

enlaces externos

• Weisstein, Eric W. "Método Adams". MundoMatemático .