📂Numerical Analysis

Consistency and Order of Convergence of Multistep Methods

Theorem

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}$, the multistep method $$ \displaystyle 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} ) $$ is consistent if and only if (i), and has order of convergence $m \in \mathbb{N}$ if and only if (ii).

• (i): $$\begin{cases} \displaystyle \sum_{j = 0}^{p} a_{j} = 1 \\ \displaystyle - \sum_{j = 0}^{p} j a_{j} + \sum_{j = -1}^{p} b_{j} = 1 \end{cases}$$
• (ii): For $i = 0, 1 , \cdots , m$, $$\sum_{j=0}^{p} (-j)^{i} a_{j} + i \sum_{j=-1}^{p} (- j )^{i-1} b_{j} = 1$$

Explanation

Rather than any one particular method, the multistep method is best seen as a form that encompasses numerous methods. This theorem is useful for checking the consistency and order of convergence of various methods, and since both (i) and (ii) are necessary and sufficient conditions, it can conversely be used to figure out when a method is meaningful and how much its speed of convergence can be raised.

Proof¹

(i)

The truncation error $\displaystyle 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}$ is linear. In other words, $$ T_{n} ( \alpha Y + \beta W ) = \alpha T_{n} (Y) + \beta T_{n} (W) $$

---

Part 1.

Expanding the solution $Y(x)$ of the initial value problem in an $m$th-order Taylor expansion about $x_{n}$ gives $$ Y(x) = \sum_{i=0}^{m} {{1} \over {i! }} (x - x_{n} )^{i} Y^{ ( i ) } ( x_{n} ) + R_{m+1} (x) $$ Expressing this in terms of the truncation error, $$ T_{n} (Y) = \sum_{i=0}^{m} {{1} \over {i! }} Y^{ ( i ) } ( x_{n} ) T_{n} \left( (x - x_{n} )^{i} \right) + T_{n} \left( R_{m+1} \right) $$

---

Part 2.

Let us compute $T_{n} \left( (x - x_{n} )^{i} \right)$.

• Case 1. $i = 0$
  $$ \displaystyle T_{n} (1) = 1 - \sum_{j=0}^{p} a_{j} 1 + h \sum_{j = -1}^{p} b_{j} ( 1 ) ' = 1 - \sum_{j=0}^{p} a_{j} $$ Here, set $\displaystyle c_{0} : = 1 - \sum_{j=0}^{p} a_{j}$.
• Case 2. $i \ge 1$
  $$ \begin{align*} \displaystyle T_{n} \left( ( x - x_{n})^{i} \right) =& (x_{n+1} - x_{n})^{i} - \left[ \sum_{j=0}^{p} a_{j} ( x_{n-j} - x_{n} )^{i} + h \sum_{j = -1}^{p} b_{j} i ( x_{n-j} - x_{n} )^{i-1} \right] \\ =& h^{i} - \left[ h^{i} \sum_{j=0}^{p} a_{j} ( -j )^{i} + h^{i} i \sum_{j = -1}^{p} b_{j} ( -j )^{i-1} \right] \\ =& h^{i} \left[ 1 - \left( \sum_{j=0}^{p} ( -j )^{i} a_{j} + i \sum_{j = -1}^{p} ( -j )^{i-1} b_{j} \right) \right] \end{align*} $$ Here, set $\displaystyle c_{i} : =1 - \left( \sum_{j=0}^{p} ( -j )^{i} a_{j} + i \sum_{j = -1}^{p} ( -j )^{i-1} b_{j} \right)$.

In the end, whatever $i$ may be, we obtain the following. $$ T_{n} (Y) = \sum_{i=0}^{m} {{c_{i} h^{i} } \over {i! }} Y^{ ( i ) } ( x_{n} ) + T_{n} \left( R_{m+1} \right) $$

---

Part 3.

For the multistep method to be consistent, we need $$ \lim_{h \to 0} \max_{x_{p} \le x_{n} \le b} \left| {{T_{n}} \over {h}} (Y) \right| = 0 $$ so it suffices to satisfy $T_{n} (Y) = O(h^2)$. Since in Part 2 above we had $$ T_{n} (Y) = \sum_{i=0}^{m} {{c_{i} h^{i} } \over {i! }} Y^{ ( i ) } ( x_{n} ) + T_{n} \left( R_{m+1} \right) $$ it suffices that $c_{0} = c_{1} = 0$ with $m=1$. Rearranging, $$ \begin{cases} \displaystyle \sum_{j = 0}^{p} a_{j} = 1 \\ \displaystyle - \sum_{j = 0}^{p} j a_{j} + \sum_{j = -1}^{p} b_{j} = 1 \end{cases} $$

■

(ii)

Part 4. $$ R_{m+1} = {{1} \over { (m+1)! }} (x - x_{n} )^{m+1} Y^{(m+1)} (x_{n}) + \cdots = O (h^{m+1} ) $$ so $$ T_{n} ( R_{m+1} ) = {{ c_{m+1} } \over { (m+1)! }} h^{m+1} Y^{(m+1)} (x_{n}) + O (h^{m+2} ) $$ holds. For the multistep method to have order of convergence $m$, we need $$ \max_{x_{p} \le x_{n} \le b} \left| {{T_{n}} \over {h}} (Y) \right| = O ( h^{m} ) $$ so it suffices to satisfy $T_{n} (Y) = O(h^{m+1})$. Quite simply, this holds if $c_{i} = 0$ for $i = 0,1, \cdots , m$. Rearranging, for $i = 0, 1 , \cdots , m$, $$ \sum_{j=0}^{p} (-j)^{i} a_{j} + i \sum_{j=-1}^{p} (- j )^{i-1} b_{j} = 1 $$

■