📂Numerical Analysis

Multistep Methods' Root Condition

Definition ¹

Multi-step method: Given the continuous function defined by $D \subset \mathbb{R}^2$ for $f$ and the initial value problem $\begin{cases} y ' = f(x,y) \\ ( y( x_{0} ) , \cdots , y(x_{p}) ) = (Y_{0}, \cdots , Y_{p} ) \end{cases}$ on the interval $(a,b)$. Let’s divide the interval into nodes as $a \le x_{0} < x_{1} < \cdots < x_{n} < \cdots x_{N} \le b$. Especially, for a sufficiently small $h > 0$, if $x_{j} = x_{0} + j h$, for the initial value and $0 \le p \le m$, if it satisfies either $a_{p} \ne 0$ or $b_{p} \ne 0$, then it 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} ) $$

Consistency of Multi-step Method: The necessary and sufficient condition for a multi-step method to have consistency is $\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}$

Assuming we have a consistent multi-step method as $\displaystyle \rho ( r) = r^{p+1} - \sum_{j=0}^{p} a_{j} r^{p-j}$. When the roots $r_{0} , \cdots , r_{p}$ of equation $\rho (r ) = 0$ satisfy the following conditions, the given multi-step method meets the Root Condition:

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

Explanation

(i) means that all roots lie within the unit circle on the complex plane $\left\{ z \ | \ |z| \le 1 \right\}$. (ii) implies that roots on the boundary of $\left\{ z \ | \ |z| \le 1 \right\}$ are not multiple roots.

If there is a condition of consistency, then $\displaystyle \sum_{j = 0}^{p} a_{j} = 1$, starting with the trivial root $r_{0} = 1$. This root condition is equivalent to both convergency in a consistent multi-step method and also equivalent to stability. Parasitic solutions are examples that directly violate the root condition, indicating weak stability.

From the described equivalence relationships, we obtain the following corollary.

Corollary

If a multi-step method is consistent, then the method has stability $\iff$ and the method has convergency