Método lineal multipaso
# Método lineal multipaso

Los métodos lineales multipaso se utilizan para la resolución numérica de ecuaciones diferenciales ordinarias. Conceptualmente, los métodos numéricos comienzan tras la elección de un punto inicial y a continuación realizan un paso de aproximación para encontrar el siguiente punto que permita seguir acercándose a la solución. El proceso continúa con los siguientes pasos para reconocer la solución.

Los métodos de un solo paso (como el método de Euler) se refieren solo a un punto anterior y a su derivada para determinar el valor buscado. Métodos como el de Runge–Kutta utilizan un paso más (por ejemplo, un paso intermedio) para obtener un método de orden superior, para luego descartar la información anterior antes de dar un segundo paso. Los métodos de varios pasos intentan obtener eficiencia manteniendo y utilizando la información de los pasos anteriores, en lugar de descartarla. Por consiguiente, se refieren a distintos puntos anteriores y a los valores de sus derivadas. En el caso de los métodos lineales "multipaso", se utiliza una combinación lineal de los puntos anteriores y de los valores de sus derivadas.

## Definiciones

Los métodos numéricos para obtener soluciones aproximadas a ecuaciones diferenciales ordinarias, abordan el problema de elegir valores iniciales de la forma

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

El resultado es un conjunto de aproximaciones para el valor de $y(t)$ en momentos discretos $t_{i}$: $y_{i}\approx y(t_{i})\quad {\text{donde}}\quad t_{i}=t_{0}+ih,$ siendo $h$ es el paso o incremento del tiempo elegido (a veces referido como $\Delta t$) y siendo $i$ un entero.

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

    ${\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),\end{aligned}}$

Los coeficientes $a_{0},\dotsc ,a_{s-1}$ y $b_{0},\dotsc ,b_{s}$ determinan el método. El diseñador del método elige los coeficientes, equilibrando la necesidad de obtener una buena aproximación a la verdadera solución, frente a la necesidad de obtener un método que sea fácil de aplicar. A menudo, muchos coeficientes son cero para simplificar el método.

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

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

## Ejemplos

Considérese por ejemplo el problema

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

La solución exacta es $y(t)=\mathrm {e} ^{t}$.

### Euler de un paso

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

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

El método de Euler puede ser visto como un método multipaso explícito, para el caso degenerado de un solo paso.

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

    ${\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 de dos pasos de Adams-Bashforth

    $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, $y_{n+1}$ y $y_{n}$, para calcular el siguiente valor, $y_{n+2}$. Sin embargo, el problema de valor inicial proporciona solo un valor, $y_{0}=1$. Una posibilidad para resolver este problema es utilizar el $y_{1}$ calculado por el método de Euler como el segundo valor. Con esta opción, el método de Adams-Bashforth produce (redondeado a cuatro dígitos):

${\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 $t=t_{4}=2$ es $\mathrm {e} ^{2}=7.3891\ldots$, por lo que el método de dos pasos de Adams-Bashforth es más preciso que el método de Euler. Esto es siempre el caso si el tamaño del paso es lo suficientemente pequeño.

## Familias de métodos de varios pasos

Se utilizan comúnmente tres familias de métodos lineales de varios pasos: los métodos de Adams-Bashforth, los métodos de Adams-Moulton y las fórmula de diferenciación hacia atrás.

### Métodos de Adams-Bashforth

Los métodos de Adams-Bashforth son métodos explícitos. Los coeficientes son $a_{s-1}=-1$ y $a_{s-2}=\cdots =a_{0}=0$, mientras que los $b_{j}$ son elegidos de tal manera que los métodos tienen orden s (esto determina los métodos únicamente).

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):

    ${\begin{aligned}y_{n+1}&=y_{n}+hf(t_{n},y_{n}),\qquad {\text{(este paso es el método de Euler)}}\\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 {4}{3}}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 {3}{8}}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 {1387}{360}}f(t_{n+3},y_{n+3})+{\frac {109}{30}}f(t_{n+2},y_{n+2})-{\frac {637}{360}}f(t_{n+1},y_{n+1})+{\frac {251}{720}}f(t_{n},y_{n})\right).\end{aligned}}$

Los coeficientes $b_{j}$ se pueden determinar como sigue: utilícese la interpolación polinómica para encontrar el polinomio p de grado $s-1$ tal que:

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

La fórmula de Lagrange para la interpolación polinómica resulta

    $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 $y'=f(t,y)$ que se va a resolver, por lo que puede considerarse la ecuación $y'=p(t)$ en su lugar. Esta ecuación puede ser resuelta exactamente; la solución es simplemente la integral de p. Esto sugiere que:

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

El método de Adams-Bashforth surge cuando se sustituye p en la fórmula. Los coeficientes $b_{j}$ resultan ser dados por

    $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)\,du,\qquad {\text{para }}j=0,\ldots ,s-1.$

Reemplazar $f(t,y)$ por su interpolante p supone incurrir en un error de orden $h^s,$ de lo que se sigue que el método de 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 un modelo de ecuaciones diferenciales de capilaridad planteado por Francis Bashforth.Bashforth (1883) publicó su teoría y el método numérico de Adams (Goldstine, 1977).

### Métodos de Adams-Moulton

Los métodos de Adams-Moulton se parecen a los métodos de Adams-Bashforth en que también tienen $a_{s-1}=-1$ y $a_{s-2}=\cdots =a_{0}=0$. De nuevo se eligen los coeficientes "b" 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 $b_{s}=0$, un método de Adams-Moulton "paso a paso" puede alcanzar el orden $s+1$, mientras que los métodos de Adams-Bashforth en el paso s solo tienen orden s.

Los métodos de Adams-Moulton con s = 0, 1, 2, 3, 4 son (Hairer, Nørsett y Wanner, 1993, §III.1;Quarteroni, Sacco y Saleri, 2000):

    ${\begin{aligned}y_{n}&=y_{n-1}+hf(t_{n},y_{n}),\qquad {\text{(este paso es el método de Euler hacia atrás)}}\\y_{n+1}&=y_{n}+{\frac {1}{2}}h\left(f(t_{n+1},y_{n+1})+f(t_{n},y_{n})\right),\qquad {\text{(este paso es la regla trapezoidal)}}\\y_{n+2}&=y_{n+1}+h\left({\frac {5}{12}}f(t_{n+2},y_{n+2})+{\frac {2}{3}}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 {3}{8}}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 deducción de los métodos de Adams-Moulton es similar a la del método de Adams-Bashforth; sin embargo, el polinomio de interpolación utiliza no solo los puntos $t_{n-1},\dots ,t_{n-s}$, como anteriormente, sino también $t_{n}$. Los coeficientes vienen dados por

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

Los métodos de Adams-Moulton se deben únicamente 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 podrían ser utilizados en tándem con los métodos de Adams-Bashforth como un par de métodos predictor-corrector (Moulton, 1926);Milne (1926) tenía la misma idea. Adams utilizó el método de Newton para resolver la ecuación implícita (Hairer, Nørsett y Wanner, 1993, §III.1).

### Fórmulas de diferenciación hacia atrás

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

## Análisis

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

### Coherencia y orden

La primera pregunta es si el método es coherente: ¿es la ecuación diferencial

    ${\begin{aligned}&y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad=h{\biglb_{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 $y'=f(t,y)$? Más precisamente, un método de varios pasos es consistente si el error de truncamiento local se acerca a cero más rápido que el tamaño de paso h cuando h tiende a cero, donde se define elerror de truncamiento local como la diferencia entre el resultado del método $y_{n+s}$ (suponiendo que todos los valores anteriores $y_{n+s-1},\ldots ,y_{n}$ son exactos), y la solución exacta de la ecuación para el instante $t_{n+s}$. Un cálculo utilizando la serie de Taylor muestra que un método lineal multipaso es coherente si y solo si:

    $\sum _{k=0}^{s-1}a_{k}=-1\quad {\text{y}}\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 en qué manera la ecuación que define el método numérico se aproxima a la ecuación diferencial. Se dice que un método de varios pasos tiene orden p si el error local es de orden $O(h^{p+1})$ cuando h tiende a cero. Esto es equivalente a la condición siguiente sobre los coeficientes de los métodos:

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

El método de Adams-Bashforth de la etapa s tiene orden s, mientras que el método de Adams-Moulton en la etapa s tiene orden $s+1$ (Hairer, Nørsett y Wanner, 1993, §III.2).

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

    $\rho (z)=z^{s}+\sum _{k=0}^{s-1}a_{k}z^{k}\quad {\text{y}}\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:

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

En particular, el método es coherente si tiene orden al menos uno, que es el caso si $\rho (1)=0$ y $\rho '(1)=\sigma (1)$.

### Estabilidad y convergencia

La solución numérica con un método de un paso depende de la condición inicial $y_{0}$, pero la solución numérica de un método de "s" pasos, depende de todos los valores iniciales de "s", $y_{0},y_{1},\ldots ,y_{s-1}$. Por lo tanto, es de interés determinar si la solución numérica es estable con respecto a perturbaciones en los valores de partida. 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 del tamaño ε hace que la solución numérica sobre ese intervalo de tiempo cambie por 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 comprobar la condición de la ecuación diferencial $y'=0$ (Süli y Mayers, 2003, p. 332).

Si 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, se dice que la condición raíz está satisfecha. Un método lineal multipaso es cero-estable si y solo si la condición raíz se satisface (Süli y Mayers, 2003, p. 335).

Supóngase ahora que un método lineal multipaso coherente se aplica a una ecuación diferencial suficientemente suave y que los valores iniciales $y_{1},\ldots ,y_{s-1}$ convergen todos al valor inicial $y_{0}$ cuando $h\to 0$. Entonces, la solución numérica converge a la solución exacta cuando $h\to 0$ si y solo si el método es cero-estable. Este resultado se conoce como el "teorema de equivalencia de Dahlquist", nombrado así en memoria de Germund Dahlquist. El razonamiento de este teorema es similar al del teorema de equivalencia de Lax para el método de las diferencias finitas. Además, si el método tiene orden p, entonces el error global de truncado (la diferencia entre la solución numérica y la solución exacta en un tiempo fijo) es $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 $z=1$ es la única raíz de módulo 1. Si es convergente y no se repiten todas las raíces de módulo 1, pero hay más de una raíz de este tipo, se dice que es "relativamente estable". Téngase en cuenta que 1 debe ser una raíz para que el método sea convergente; los métodos convergentes son siempre uno de estos dos.

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

    $\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 un módulo menor que uno, entonces la solución numérica del método de varios pasos convergerá a cero y se dice que el método de varios pasos es "absolutamente estable" para ese valor de hλ. Se dice que el método es A-estable si es absolutamente estable para todos los hλ con la 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 & 348). Para obtener más detalles, consúltese la sección sobre ecuaciones diferenciales rígidas.

### Ejemplo

Considérese el método de tres pasos de Adams-Bashforth:

    $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).$

Así, un polinomio característico toma la forma:

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

con raíces $z=0,1$, y las condiciones anteriores se satisfacen. Como $z=1$ es la única raíz del módulo 1, el método es fuertemente estable.

El otro polinomio característico es:

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

## Primera y segunda barreras de Dahlquist

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

### Primera barrera de Dahlquist

Un método de paso múltiple de paso q escalable a 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 y Wanner, 1993, Thm III.3.5).

### Segunda barrera de Dahlquist

No hay métodos explícitos A-estables y multipaso lineales. Los implícitos tienen un orden de convergencia de 2 como máximo. La regla trapezoidal tiene la menor constante de error entre los métodos de paso múltiple lineal A-estables de orden 2.

