Linear multistep method

Linear multistep methods are methods used in numerical analysis to solve numerically ordinary differential equations. One-step methods (such as Euler's method) refer to only to one previous value to determine the current value. Multi-step methods may refer to several previous function values, and thus, more initial points must be determined, and these intial points are usually determined with a one-step method.

Examples

Adams-Bashforth methods

The Adams-Bashforth methods are explicit $s+1$ step methods and are of the form

$y_{n+1}=y_{n}+h\sum _{i=0}^{s}b_{j}f(t_{n-j},y_{n-j}),\quad 0\leq r\leq n$

where

$b_{j}={(-1)^{j} \over j!(r-j)!}\int _{0}^{1}\prod _{i=0}^{r}(u+i)^{[i\neq j]}\,du,\quad j=0,\ldots ,r.$

and the brackets are the Iverson bracket.

For example:

$s=1$

$y_{n+1}=y_{n}+h\left({3 \over 2}f(t_{n},y_{n})-{1 \over 2}f(t_{n-1},y_{n-1})\right)$

$s=2$

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

etc.

Observe that both $t_{n},y_{n}$ and $t_{n-1},y_{n-1}$ are necessary to determine $y_{n+1}$, making it a multistep method. The method is determined from the Lagrange form of the polynomial to interpolate $f$ at data points $t_{n-r}$,...,$t_{n}$, say this polynomial is $p$ and then expanding $y_{n+1}=y_{n}+\int _{t_{n}}^{t_{n+1}}p(t)\,dt$.

Adams-Moulton methods

The Adams-Moulton methods are similar to the Adams-Bashforth methods, however, these are implicit and are $s$ step methods. They are often used in tandem with the Adams-Bashforth methods as a predictor-corrector pair.

The methods are of the form

$y_{n+1}=y_{n}+h\sum _{i=-1}^{s-1}b_{j}f(t_{n-j},y_{n-j}),\quad 0\leq r\leq n$

and

$b_{j}={(-1)^{j} \over (j+1)!(r-j-1)!}\int _{0}^{1}\prod _{i=-1}^{s-1}(u+i)^{[i\neq j]}\,du,\quad j=-1,0,\ldots ,s-1$

For example:

$s=2$

$y_{n+1}=y_{n}+h\left({5 \over 12}f(t_{n+1},y_{n+1})+8f(t_{n},y_{n})-f(t_{n-1},y_{n-1})\right)$

However, for $s=1$

$y_{n+1}=y_{n}+h\left({1 \over 2}f(t_{n+1},y_{n+1})+{1 \over 2}f(t_{n},y_{n})\right)$

is a one-step method.

The derivation of the Adams-Moulton methods is similar to that of the derivation of the Adams-Bashforth methods, instead the interpolating polynomial uses points $t_{n-r+1}$,...,$t_{n+1}$ instead.

Analysis

Convergence and stability are of concern to the analysis of multistep methods. The stability of a multistep method

$y_{n+1}=\sum _{i=0}^{s}a_{i}y_{n-i}+h\sum _{j=-1}^{r}b_{j}f(t_{n-j},y_{n-j}),0\leq r\leq n$

is determined by the characteristic polynomial

$q(z)=z^{s+1}-\sum _{i=0}^{s}a_{i}z^{s-i}$

The method is convergent if and only if the roots of the characteristic polynomial have modulus less or equal 1 for all roots, and the roots of modulus 1 must be of multiplicity 1. Consequently, the method is stable if and only if this condition is statisfied, thus the method is convergent if and only if it is stable.

Furthermore, if the method is stable, the method is said to be strongly stable if $z=1$ is the only root of modulus 1, otherwise, it is said to be weakly stable.

Example

Consider the Adams-Bashforth three-step method

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

The characteristic equation is thus

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

which has roots $z=0,1$, and the conditions above are satisfied. As $z=1$ is the only root of modulus 1, the method is strongly stable.