Método lineal de pasos múltiples

Un método numérico sencillo es el método de Euler: $${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).}$$ El método de Euler puede considerarse como un método explícito de varios pasos para el caso degenerado de un solo paso.

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

El método de Euler es un método de un solo paso . Un método simple de varios pasos es el método de 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}).}$$ Este método necesita dos valores,${\displaystyle y_{n+1}}$y${\displaystyle y_{n}}$, para calcular el siguiente valor,${\displaystyle y_{n+2}}$Sin embargo, el problema del valor inicial proporciona solo un valor,${\displaystyle y_{0}=1}$. Una posibilidad para resolver este problema es utilizar el${\displaystyle y_{1}}$calculado mediante el método de Euler como el segundo valor. Con esta elección, el método de Adams-Bashforth produce (redondeado a cuatro dígitos): $${\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}}}$$ La solución exacta en${\displaystyle t=t_{4}=2}$es${\displaystyle e^{2}=7.3891\ldots }$Por lo tanto, el método de Adams-Bashforth de dos pasos es más preciso que el método de Euler. Esto siempre ocurre si el tamaño del paso es lo suficientemente pequeño.

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

Los métodos de Adams-Bashforth con s = 1, 2, 3, 4, 5 son ( Hairer, Nørsett y 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${\displaystyle b_{j}}$se puede determinar de la siguiente manera. Utilice la interpolación polinómica para encontrar el polinomio p de grado${\displaystyle s-1}$de tal manera que $${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$$ La fórmula de Lagrange para la interpolación polinómica produce: $${\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}).}$$ El polinomio p es localmente una buena aproximación del lado derecho de la ecuación diferencial.${\displaystyle y'=f(t,y)}$Eso debe resolverse, así que consideremos la ecuación.${\displaystyle y'=p(t)}$en cambio. Esta ecuación se puede resolver exactamente; la solución es simplemente la integral de p . Esto sugiere tomar $${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.}$$ El método de Adams-Bashforth surge cuando se sustituye la fórmula para p . Los coeficientes${\displaystyle b_{j}}$resultan ser dados por $${\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.}$$ Reemplazar${\displaystyle f(t,y)}$por su interpolante p incurre en un error de orden h ^s , y de ello se deduce que el método Adams-Bashforth de s pasos tiene efectivamente orden s ( Iserles 1996 , §2.1)

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

Los métodos de Adams-Moulton son similares a los métodos de Adams-Bashforth en que también tienen${\displaystyle a_{s-1}=-1}$y${\displaystyle a_{s-2}=\cdots =a_{0}=0}$. 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 que${\displaystyle b_{s}=0}$, un método Adams-Moulton de s pasos puede alcanzar el orden${\displaystyle s+1}$, mientras que un método Adams-Bashforth de s pasos solo tiene orden s .

Los métodos de Adams-Moulton con s = 0, 1, 2, 3, 4 se enumeran ( Hairer, Nørsett y Wanner 1993 , §III.1 ; Quarteroni, Sacco y Saleri 2000 ), donde los dos primeros métodos son el método de Euler hacia atrás y la regla trapezoidal (también conocido como el método de Crank-Nicolson ) respectivamente: $${\displaystyle {\begin{aligned}y_{n}&=&y_{n-1}&+hf(t_{n},y_{n}),\\y_{n+1}&=&y_{n}&+h\left({\frac {1}{2}}f(t_{n+1},y_{n+1})+{\frac {1}{2}}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 de Adams-Moulton es similar a la del método de Adams-Bashforth; sin embargo, el polinomio interpolador no solo utiliza los puntos${\displaystyle t_{n-1},\dots ,t_{n-s}}$, como se indicó anteriormente, pero también${\displaystyle t_{n}}$Los coeficientes vienen dados por $${\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 de Adams-Moulton se deben exclusivamente a John Couch Adams , al igual que los métodos de 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 de Adams-Bashforth como un par predictor-corrector ( Moulton, 1926 ) ; Milne (1926) tuvo la misma idea. Adams usó el método de Newton para resolver la ecuación implícita ( Hairer, Nørsett y Wanner, 1993 , §III.1) .

Los métodos BDF son métodos implícitos con${\displaystyle b_{s-1}=\cdots =b_{0}=0}$y los demás coeficientes elegidos de tal 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 .

La primera pregunta es si el método es consistente: ¿es la ecuación de 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}}}$$ una buena aproximación de la ecuación diferencial${\displaystyle y'=f(t,y)}$Más precisamente, un método de pasos múltiples es consistente si el error de truncamiento local tiende a cero más rápido que el tamaño del paso h cuando h tiende a cero, donde el error de truncamiento local se define como la diferencia entre el resultado${\displaystyle y_{n+s}}$del método, suponiendo que todos los valores anteriores${\displaystyle y_{n+s-1},\ldots ,y_{n}}$son exactos, y la solución exacta de la ecuación en el tiempo${\displaystyle t_{n+s}}$. Un cálculo utilizando series de Taylor muestra que un método lineal de pasos múltiples es consistente si y solo si $${\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}.}$$ Todos los métodos mencionados anteriormente son consistentes ( Hairer, Nørsett y Wanner 1993 , §III.2) .

Si el método es consistente, entonces la siguiente pregunta es qué tan bien la ecuación de diferencias que define el método numérico aproxima la ecuación diferencial. Se dice que un método de pasos múltiples tiene orden p si el error local es de orden${\displaystyle O(h^{p+1})}$cuando h tiende a cero. Esto es equivalente a la siguiente condición sobre los coeficientes de los métodos: $${\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.}$$ El método Adams-Bashforth de s pasos tiene orden s , mientras que el método Adams-Moulton de s pasos tiene orden${\displaystyle s+1}$( Hairer, Nørsett y Wanner 1993 , §III.2) .

Estas condiciones se formulan a menudo 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}.}$$ En términos de estos polinomios, la condición anterior para que el método tenga orden p se convierte en: $${\displaystyle \rho (e^{h})-h\sigma (e^{h})=O(h^{p+1})\quad {\text{as }}h\to 0.}$$ En particular, el método es consistente si tiene orden al menos uno, lo cual es el caso si${\displaystyle \rho (1)=0}$y${\displaystyle \rho '(1)=\sigma (1)}$.

La solución numérica de un método de un paso depende de la condición inicial.${\displaystyle y_{0}}$, pero la solución numérica de un método de s pasos depende de todos los s valores iniciales,${\displaystyle y_{0},y_{1},\ldots ,y_{s-1}}$Por lo tanto, es de interés si la solución numérica es estable con respecto a perturbaciones en los valores iniciales. Un método lineal multipaso es cero-estable para una determinada ecuación diferencial en un intervalo de tiempo dado, si una perturbación en los valores iniciales de tamaño ε hace que la solución numérica en 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 es suficiente para verificar la condición para la ecuación diferencial.${\displaystyle y'=0}$( Süli y Mayers 2003 , p. 332) . 

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

Ahora supongamos que se aplica un método lineal multipaso consistente a una ecuación diferencial suficientemente suave y que los valores iniciales${\displaystyle y_{1},\ldots ,y_{s-1}}$Todos convergen al valor inicial.${\displaystyle y_{0}}$como${\displaystyle h\to 0}$. Entonces, la solución numérica converge a la solución exacta cuando${\displaystyle h\to 0}$si y solo si el método es cero-estable. Este resultado se conoce como el 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${\displaystyle O(h^{p})}$( Süli y Mayers 2003 , p. 340) . 

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

Para evaluar el rendimiento de los métodos multipaso lineales en ecuaciones rígidas , considere la ecuación de prueba lineal y' = λ y . Un método multipaso aplicado a esta ecuación diferencial con tamaño de paso h produce una relación de recurrencia lineal con 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).}$$ Este polinomio se denomina polinomio de estabilidad del método multipaso. Si todas sus raíces tienen módulo menor que uno, la solución numérica del método multipaso convergerá a cero y se dice que el método multipaso es absolutamente estable para ese valor de hλ . Se dice que el método es A-estable si es absolutamente estable para todo hλ con parte real negativa. La región de estabilidad absoluta es el conjunto de todos los hλ para los cuales el método multipaso es absolutamente estable ( Süli y Mayers, 2003 , pp. 347 y 348) . Para más detalles, consulte la sección sobre ecuaciones rígidas y métodos multipaso . 

Consideremos 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).}$$ Un polinomio característico es, por lo tanto, $${\displaystyle \rho (z)=z^{3}-z^{2}=z^{2}(z-1)}$$ que tiene raíces${\displaystyle z=0,1}$y se cumplen las condiciones anteriores. Como${\displaystyle z=1}$es la única raíz de módulo 1, el método es fuertemente estable.

El otro polinomio característico es $${\displaystyle \sigma (z)={\frac {23}{12}}z^{2}-{\frac {4}{3}}z+{\frac {5}{12}}}$$

La primera barrera de Dahlquist establece que un método multipaso de q pasos , estable en cero y lineal, 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 y Wanner 1993 , Teorema III.3.5) .

La segunda barrera de Dahlquist establece que ningún método lineal multipaso explícito 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-estables de orden 2, la regla trapezoidal tiene la constante de error más pequeña ( Dahlquist 1963 , Teorema 2.1 y 2.2) .