📂Numerical Analysis

Convergence and Root Condition of Consistent Multistep Methods

Theorem

If a multistep method is consistent, then: the method is convergent $\iff$ the method satisfies the root condition

Explanation

For the closed interval $[x_{0} , b]$, when we create node points by cutting it into units of $h$, let $x_{0} \le x_{1} \le \cdots \le x_{N(h) -1} \le x_{N(h) } \le b$. Here $N(h)$ denotes the index of the last node point, which varies with $h$.

The method is convergent means that if $\displaystyle \eta (h) : = \max_{0 \le n \le p} | Y_{n} - y_{ n} | \to 0$ as $h \to 0$, then $\displaystyle \max_{x_{0} \le x_{n} \le b } | Y_{n} - y_{ n} | \to 0$ as $h \to 0$.

Proof¹

Consistent multistep method: 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 $$ 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} ) $$ satisfies the following. $$ \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} $$

Root condition: For a consistent multistep method, let $\displaystyle \rho ( r) = r^{p+1} - \sum_{j=0}^{p} a_{j} r^{p-j}$. When the roots $r_{0} , \cdots , r_{p}$ of the equation $\rho (r ) = 0$ satisfy the following conditions, the given multistep method is said to satisfy the root condition.

• (i): $| r_{j} | \le 1$
• (ii): $|r_{j}| = 1 \implies \rho ‘(r_{j}) \ne 0$

---

$(\Rightarrow)$

Suppose that the method is convergent and yet does not satisfy the root condition. We will show that the initial value problem $\begin{cases} y ' = 0 \\ y(0) = 0 \end{cases}$ serves as a counterexample to this assumption.

The true solution of the given problem is trivially $Y_{n} = 0$ for all $n \ge 0$.

And since $f = 0$, the numerical solution is $\displaystyle y_{n+1} = \sum_{j=0}^{p} a_{j} y_{n - j}$. In particular, suppose $y_{0} , \cdots , y_{p}$ satisfy $$ \eta (h) = \max_{0 \le n \le p} | Y_{n} - y_{ n} | = \max_{0 \le n \le p} | y_{ n} | \to 0 $$ as $h \to 0$. Now, for some $0 \le j \le p$, consider the following two cases.

• Case 1.
  When (i) fails, so that $|r_{j}| > 1$ for $ j$: as $h \to 0$, $\displaystyle y_n = h r_{j} ^n$ satisfies $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h \left| r_{j} \right| ^{p} \to 0 $$ However, since $N(h) \to \infty$ as $h \to 0$, $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} \right| ^{N (h) } \to \infty $$ Therefore the method is not convergent.
• Case 2.
  When (ii) fails, so that $|r_{j}| = 1 \implies \rho’(r_{j}) = 0$ for $ j$: this means that if $|r_{j}| = 1$ then $r_{j}$ is a repeated root of the characteristic equation, so there exists at least one repeated root $r_{j}$. Therefore the particular solution $n r_{j}^{n}$ exists, so that as $h \to 0$, $\displaystyle y_n = h n r_{j} ^n$ satisfies $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h p \left| r_{j} \right| ^{p} \to 0 $$ and, as $h \to 0$, $\displaystyle y_n = h \left[ r_{j} (0) \right]^n$ satisfies $$ \eta (h) = \max_{0 \le n \le p} | y_{ n} | = h \left| r_{j} (0) \right| ^{p} \to 0 $$ However, as $h \to 0$, $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} (0) \right| ^{N (h) } \to \infty $$ Therefore the method is not convergent.

---

$(\Leftarrow)$ The original proof is exceedingly difficult, so there are many leaps here².

If we set $e_{n} : = Y_{n} -y_{n}$, we can think of this as solving the nonhomogeneous linear differential equation $Y = y + e$.

Conversely, $y = Y - e$ becomes a homogeneous linear differential equation. $$ \begin{align} 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} ) \end{align} $$

$$ \begin{align} 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} ) \end{align} $$ Subtracting $(2)$ from $(1)$ gives $$ e_{n+1} = \sum_{i=0}^{n} a_{j} e_{n-j} + h \sum_{j= -1}^{p} b_{j} \left[ f(x_{n-j} , Y_{n- j }) - f(x_{n-j} , y_{n- j }) \right] $$ If we let $Y_{n} = d_{0} s_{0}^{n} + d_{1} s_{1}^{n} + \cdots + d_{p} s_{p}^{n}$, then $$ e_{n} = g_{0} ( r_{0} + s_{0} )^n + g_{1} ( r_{1} + s_{1} )^n + \cdots + g_{p} ( r_{p} + s_{p} )^n $$ When $N \ge p$, the given method satisfies the root condition also for the $( r_{0} + s_{0} ) , \cdots , ( r_{p} + s_{p} )$ appearing in $$ e_{N} = g_{0} ( r_{0} + s_{0} )^N + g_{1} ( r_{1} + s_{1} )^N + \cdots + g_{p} ( r_{p} + s_{p} )^N $$ so $$ \begin{align*} | e_{N} | & =& | g_{0} | | r_{0} + s_{0} |^N + | g_{1} | | r_{1} + s_{1} | ^N + \cdots + | g_{p} | | r_{p} + s_{p} |^N \\ \le & \max_{0 \le n \le p} | Y_{ n} - y_{n} | \end{align*} $$ Here, if we assume that $\displaystyle \max_{0 \le n \le p} | Y_{ n} - y_{n} | \to 0$ as $h \to 0$, then $e_{N} \to 0$, so we must have $$ \max_{x_{0} \le x_{n} \le b} | Y_{n} - y_{ n} | = h \left| r_{j} (0) \right| ^{N (h) } \to 0 $$ and therefore the method is convergent.

■