09 - Multistep Methods

Linear Step Method

Let $X>x_0$ be a final time
Let $N,k\in \mathbb{N}$ with $N\ge k$
Let

$$h:=\frac{X-x_0}{N}\text{ and }{x}_n:=x_0+hn$$

Linear $k$-step method is an iterative method computing approximation

$${\mathbf{y}}_{n+k}\text{ to }\mathbf{y}(x_{n+k})$$

by solving

$$\sum _{j=0}^k{\alpha }_j{\mathbf{y}}_{n+j}=h\sum _{j=0}^k{\beta }_j\mathbf{f}(x_{n+j},\mathbf{y}{)}_{n+j}$$

where $\{{\alpha }_j{\}}_{j=0}^k$ and $\{{\beta }_j{\}}_{j=0}^k$ are real coefficients

Note that ${\alpha }_k\ne 0$ and ${\alpha }_0^2+{\beta }_0^2\ne 0$ to avoid degenerate cases
Note that also if ${\beta }_k=0$ then method is explicit

First Characteristic Polynomials

Let $k$-step method be defined as by Linear Step Method then

First Characteristic Polynomial is defined by

$$\rho (z)=\sum _{j=0}^k{\alpha }_j{z}^j$$

Second Characteristic Polynomials

Let $k$-step method be defined as by Linear Step Method then

Second Characteristic Polynomial is defined by

$$\sigma (z)=\sum _{j=0}^k{\beta }_j{z}^j$$

Root Condition

Linear $k$-step satisfies root condition if

All roots of first characteristic polynomial $\rho (z)$ lie in closed unit disc
with every root on the unit circle being simple

Note that this is also known as Zero-Stability

Consistency Error

Consistency Error of linear $k$-step method (with $\sigma (1)\ne 0$) is defined by

$$\tau (h)=\frac{\sum _{j=0}^k{\alpha }_j\mathbf{y}(x_j)-h\sum _{j=0}^k{\beta }_j{\mathbf{y}}^{\prime }(x_j)}{h\sum _{j=0}^k{\beta }_j}$$

where $\mathbf{y}$ is a smooth function

Consistency Order of a Linear Multistep Method

Linear Multi-Step method has consistency order $p$ if

$$\tau (h)=O(h^p)$$

Stability Polynomial

Stability Polynomial of a Linear $k$-step method is defined by

$$\pi (x)=\pi (x;z):=\sum _{j=0}^k(a_{j}z{\beta }_j)x^j=\rho (x)-z\sigma (x)$$

Stability Domain

Stability Domain of Linear Multistep Method is defined by

$$S:=\{z\in \mathbb{C}:\text{ if }\pi (x;z)=0\text{ then }|x|\le 1;\text{ multiple zeros satisfy }|x|<1\}$$

Zero-Stable

If $0\in S$ then method is zero-stable