next up previous contents
Next: Long Term Behaviour Up: Multistep Methods Previous: Multistep Methods

Linear Multistep Methods

A general linear k-step method may be written as

(2.34) $\displaystyle \sum_{j=0}^k \alpha_j x_{n+j}=h \sum_{j=0}^k \beta_j f(x_{n+j}).$

It is conventional to normalize (2.35) by setting $ \alpha_k=1$, furthermore if $ \beta_k=0$ the method is explicit, otherwise it is said to be implicit.
The method require $ k$ starting vectors $ x_j$, which are often obtained from $ x_0$ using a one-step method.
The definition (2.35) may be formulated in a more compact notation. Let us use the first characteristic polynomial $ \rho(\xi)$ and let us define $ \sigma(\xi)$, which is said to be the second characteristic polynomial of (2.35), i.e.

    $\displaystyle \rho(\xi)=\sum_{j=0}^k \alpha_j \xi^j \ \quad \ \sigma(\xi)=\sum_{j=0}^k \beta_j \xi^j ,\quad \xi \in {\mathbb {C}}$

and the forward shift operator

    $\displaystyle E(x_n)=x_{n+1}$   for all$\displaystyle \ n \in {\mathbb {N}}.$

Thus the formula (2.35) becomes

(2.35) $\displaystyle \rho(E)x_n=h\sigma(E)f(x_n).$

It is immediately that the consistency is guaranteed if

(2.36) $\displaystyle \rho(1)= 0$   and$\displaystyle \quad \sigma(1)=\rho'(1),$

while, in contrast to the one-step case, there the zero-stability should be verified through the root condition.

The following statements are equivalent order condition:

Proposition 2.19   A multistep method is of order $ r\geq 1$ if and only if

Later, another concept will be useful:

Definition 2.20   If $ \rho(z)$ and $ \sigma(z)$ have no common factors then the linear multistep method is said to be irreducible, and otherwise it is said to be reducible.

Let us show any famous multistep methods:
Two-stage Theta method
For $ k=1$ and $ \rho(z)=z-1$, $ \sigma(z)=(1-\theta)+ \theta z$ one achieves the one-step linear method, which can lead to the explicit and implicit Euler method, too. If $ \theta=\frac{1}{2}$ it is a second order method, otherwise a first order.
Midpoint Rule
The equation

    $\displaystyle x_{n+2}=x_n + 2 h f(x_n),$

due to the assumptions $ \rho(z)=z^2-1$   and $ \sigma(z)=2z$, defines a second order explicit method.
Simpson Rule

    $\displaystyle x_{n+2}-x_n=\frac{h}{3}\Bigl(f(x_{n+2})+4f(x_{n+1})+f(x_n)\Bigr)$

which is a Generalized Milne-Simpson method. The methods of this class are implicit and zero-stable for all $ k$.
Backward Differentiation Formulae (BDF method)
The following

    $\displaystyle \sum_{j=1}^k \frac{1}{j} \triangle x_{n+k}=h f(x_{n+k}),$

where $ \triangle x_n=x_n - x_{n-1}$ and recursively $ \triangle^i x_n=\triangle(\triangle^{i-1}x_n)$, describes a general BDF method. It is be proved that only for $ k=1,...,6$ the method is convergent.
Note that for $ r=1$ the order conditions imply the consistency, in accordance with what shown for the one-step method family.


A natural question to ask is what is the highest order that can be achieved by a convergent linear k-step method. In seeking high order, the consistency condition is automatically satisfied, but a very real barrier is met in attempting to satisfy the root condition.

Proposition 2.21   No zero-stable linear k-step method can have order exceeding $ (k+2)$ when k is even, $ (k+1)$ when k is odd and $ (k)$ if the method is explicit. $ \clubsuit$

[ Proof: [25]]


Since $ f$ is considered at least Lipschitz continuous, i.e. the solution is bounded over a finite time interval $ [t_0,t_N]$, it worth:

Proposition 2.22   Consider a zero-stable multistep method of order $ r\geq 1$ applied to the equation (2.5). Provided that there exists $ C_1, \ \overline{h} >0$ such that

    $\displaystyle \Vert x_0 -x(t_0)\Vert \leq C_1 h^r$   for all h$\displaystyle \in (0,\overline{h})$

then it follows that there exists $ C_2(t_0-t_N, x_0), \ h_c(x_0)>0$ such that for all $ h \in (0,h_c)$

    $\displaystyle \Vert x_n -x(t_n)\Vert \leq C_2 h^r$   for all n$\displaystyle \ \in [t_0,t_N].\clubsuit$

[ Proof: [22]]


( For further investigation, see [26], [27], [28], [29], [30].)
next up previous contents
Next: Long Term Behaviour Up: Multistep Methods Previous: Multistep Methods

Nardin Patrizia
2001-03-30