📂Numerical Analysis

Multistep Methods

Definition ¹

Given a continuous function defined in $D \subset \mathbb{R}^2$ for the initial value problem given in $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$, let’s say we have broken down interval $(a,b)$ into nodes like $a \le x_{0} < x_{1} < \cdots < x_{n} < \cdots x_{N} \le b$. Especially for a sufficiently small $h > 0$, if we say $x_{j} = x_{0} + j h$, then for the initial value and $0 \le p \le m$, if $a_{p} \ne 0$ or $b_{p} \ne 0$, 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, it is permissible to think of a sufficiently large $q \ge 1$ and $f \in C^{q}(D)$ defined from $D \subset \mathbb{R}^2$. Especially in this general form, if particularly $p=0$ and $a_{0} = 1 , b_{0} = 1 , b_{-1} = 0$ then it becomes the Euler method.

Multistep methods generally have a higher accuracy as they use more data information compared to one-step methods. For the initial value problem given in $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$, let’s consider the truncation error as $$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}$$ and write this as $\displaystyle \tau_{n} (Y) := {{1} \over {h}} T_{n} (Y)$, if it satisfies $\displaystyle \lim_{h \to 0} \max_{x_{p} \le x_{n} \le b} | \tau_{n} (Y) | = 0$, then the method is said to have a consistency condition. It might look complicated when written in equations but simply put, this means the speed at which the truncation error decreases is faster than the speed at which $h$ decreases. Where $$\tau (h) : = \max_{x_{p} \le x_{n} \le b} | \tau_{n} (Y) | = O (h^m)$$ among $m$, the highest number is called the method’s order of convergence.

Especially if $b_{-1} = 0$, then $y_{n+1}$ is referred to as an explicit method because it appears only in the left side. If $b_{-1} \ne 0$, then because $y_{n+1}$ appears on both sides, it is referred to as an implicit method. While explicit methods are convenient for calculations, generally known implicit methods perform well but require additional calculations.