16. 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

Link to original

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

Link to original

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

Link to original

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

Link to original

Consistency and Zero-Stability Imply Convergence

Consider a linear multi step method then

$$\text{Consistentcy}+\text{Zero-Stability}⟹\text{Convergence}$$

Link to original

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

Link to original

Consistency Order of a Linear Multistep Method

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

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

Link to original

Order Conditions for Linear Multistep Methods

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

$$\sigma (1)\ne 0\text{ and }\sum _{j=0}^k{\alpha }_j=0\text{ and }\sum _{j=0}^k{\alpha }_j{j}^q=q\sum _{j=0}^k{\beta }_j{j}^{q-1}\text{ for }q=1,\cdots ,p$$

where it is consistent if it is satisfied for at least $p=1$

Consistent

Consistent if

$$\rho (1)=0\text{ and }{\rho }^{\prime }(1)=\sigma (1)\ne 0$$

Link to original

Dahlquist's Equivalence Theorem

Consider consistent linear $k$-step method with consistent starting values

Root Condition (zero-stability) is necessary and sufficient for convergence so

$$\underset{h\to 0}{\lim }{\mathbf{y}}_N=\mathbf{y}(X)\text{ where }N=(X-x_0)/h$$

Moreover if

$$\tau (h)=O(h^p)\text{ and }||\mathbf{y}(x_s)-{\eta }_s(h)||=O(h^p)\text{ for }s=0,\cdots ,k-1$$

Then

$$\underset{0\le n\le N}{\max }||\mathbf{y}(x_n)-{\mathbf{y}}_n||=O(h^p)$$

Link to original

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

Link to original

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

Link to original

Dahlquist’s Second Barrier

Consider $A$-stable Linear Multi-step Method then

Method must be implicit and of order $p\le 2$

Note that the trapezium rule is the second-order $A$-stable linear multi-step method with smallest error constant

Link to original