📂Numerical Analysis

Multistep Method

Definition¹

For a continuous function $f$ defined on $D \subset \mathbb{R}^2$, suppose the initial value problem $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$ is given. Suppose the interval $(a,b)$ is split into node points such as $a \le x_{0} < x_{1} < \cdots < x_{n} < \cdots x_{N} \le b$. In particular, for a sufficiently small $h > 0$, let $x_{j} = x_{0} + j h$; then, given the initial values, if $a_{p} \ne 0$ or $b_{p} \ne 0$ for $0 \le p \le m$, the following is called a $(p+1)$-step method. $$ y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n-j} + h \sum_{j = -1}^{p} b_{j} f (x_{n-j} , y_{n-j} ) $$

Explanation

Of course, there is no harm in thinking of $f \in C^{q}(D)$ defined on $D \subset \mathbb{R}^2$ with $q \ge 1$ as large as needed. In this general form, if in particular $p=0$ and $a_{0} = 1 , b_{0} = 1 , b_{-1} = 0$, it becomes the Euler method.

Since multistep methods use the information of more data, they usually have higher accuracy than one-step methods. For the initial value problem $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$, let the truncated error be $$ T_{n} (Y) := Y_{n+1} - \sum_{j=0}^{p} a_{j} Y_{n-j} + h \sum_{j = -1}^{p} b_{j} Y’_{n-j} $$ For this we write $\displaystyle \tau_{n} (Y) := {{1} \over {h}} T_{n} (Y) $, and if $\displaystyle \lim_{h \to 0} \max_{x_{p} \le x_{n} \le b} | \tau_{n} (Y) | = 0$ is satisfied, the method is said to have the consistency condition. It looks complicated written out as a formula, but simply put, it means that the truncation error shrinks faster than $h$ does. Here, the largest $m$ satisfying $$ \tau (h) : = \max_{x_{p} \le x_{n} \le b} | \tau_{n} (Y) | = O (h^m) $$ is called the order of Convergence of the method.

In particular, if $b_{-1} = 0$, then $y_{n+1}$ appears only on the left-hand side, so it is called an explicit method. If $b_{-1} \ne 0$, then $y_{n+1}$ appears on both sides, so it is called an implicit method. Explicit methods are the convenient ones to compute with, while the commonly known implicit methods perform well but require additional computation.