Zero-Stability, Consistency and Convergence Theorem

6.3. Zero-Stability, Consistency and Convergence Theorem#

Definition 6.6 (Zero-Stability)

A linear multistep method (6.1) is said to be zero-stable if it satisfies the root condition given in Definition 6.3.

This means no root of the first characteristic polynomial \(\,\rho(z)\,\) has modulus greater that one, and every root of modulus one is simple.

Note

In electrical engineering and control theory, the right hand side of the first-order ODE

\[\diff{y}{x}=f(x, y)\]

is called the input of the system. In this context, we can interpret zero-stability as the stability of the system with zero input.

We use the root condition to assess whether the discretised system (difference equation) can remain stable under zero input condition.

Definition 6.7 (Consistency)

In numerical analysis, consistency is the property of a numerical method performing differentiation or integration in a way similar to the actual differentiation or integration. In another word, consistency tells how similar is the discrete system to the original continuous system.

The condition for the discrete system produced by a linear multistep method (6.1)

\[ \sum_{i=0}^{k}\alpha_i y_{j+i}~=~ h\sum_{i=0}^{k}\beta_i f_{j+i}, \qquad \text{with}~ \alpha_k =1 \]

being consistent with the continuous differential equation

\[ \diff{y}{x} = f(x, y) \]

or its integral

\[ \int_{x_j}^{x_{j+k}} \diff{y}{x} \dx = \int_{x_j}^{x_{j+k}} f(x, y) \dx \]

is that the method has an order of accuracy \(p \geq 1\).

In terms of error constants \(C_p\) introduced in Section 5.2, the condition of consistency is equivalent to \(C_0 = 0\), \(C_1 = 0\). This ensures the method has an order of accuracy \(p\geq 1\). Thus the condition of consistency can also be expressed by the relations

\[ \begin{aligned} && \sum_{i=0}^{k} \alpha_i ~&=~ 0\,; & \sum_{i=0}^{k} i\alpha_i ~&=~ \sum_{i=0}^{k} \beta_i\,. && \end{aligned} \]

Note

\[ C_0= \alpha_0 + \alpha_1 + \cdots + \alpha_k \]
\[ C_1= \left(\alpha_1 + 2\alpha_2 + 3\alpha_3 + \cdots + k\alpha_k\right) - \left( \beta_0 + \beta_1 + \cdots + \beta_k \right) \]

And in terms of the first and second characteristic polynomials \(\rho(z)\) and \(\sigma(z)\), the condition of consistency can be expressed by the following relations - i.e. the linear multistep method (6.1) is consistent iff:

\[ \begin{aligned} \rho(1) ~&=~ 0\,, \qquad\text{and}\qquad \rho'(1) = \sigma(1)\,. \end{aligned} \]

Thus, for a consistent method, the first characteristic polynomial always has a root at \(+1\), i.e. the principal root \(z_1\). The remaining roots \(\,z_i\,, ~i=2,3,\dots,k\,\), are the parasitic roots.

Remark 6.1 (Condition of Consistency)

In summary there are three equivalent conditions of consistency:

  1. The method’s order of accuracy \(p \geq 1\).

  2. The error constants satisfy \(C_0=0\) and \(C_1=0\).

  3. \(\rho(1)=0\) and \(\rho'(1)=\sigma(1)\).

If a linear multistep method satisfies any of these three conditions, then it is a consistent method.

A linear multistep method which is zero-stable is frequently called ‘stable’. Essentially a method is stable if errors produced at one step are not propagated (or amplified) at subsequent steps.

In addition, it is also important for us to know whether the numerical solution \(y\)num will approach the exact solution \(y\)ex when we reduce the step size \(h\) towards zero.

Definition 6.8 (Convergence)

For an initial value problem

\[\begin{split} \left\{ \begin{aligned} y'&=f(t, y) \\ y(0)&=y_0 \end{aligned} \right. \qquad t \in [0, T], \end{split}\]

when we reduce the step size \(h\) towards zero, if the numerical solution \(y\)num approaches to the exact solution \(y\)ex, we says the numerical solution converges to the exact solution, and we call the numerical method a convergent method.

\[ \max _{t\in [0, T]} \| y_\text{num}(t) - y_\text{ex}(t) \| \rightarrow 0 \qquad \mbox{as} \qquad {h}\rightarrow 0. \]

Zero-stability ensures that the parasitic solutions of the general solution to a difference equation are damped out in the limit as \(\,h \to 0\,\) — this effect is related to the fundamental theorem on linear multistep methods by Dahlquist:

Theorem 6.2 (Dahlquist Equivalence)

The necessary and sufficient conditions for a linear multistep method to be convergent are that it is consistent and zero-stable.

Example 6.4

Investigate the convergence of the third order Adams-Bashforth formula:

\[ \begin{aligned} y_{j+1} ~=~ y_j + \frac{h}{12} \bigl[ 23f_j - 16f_{j-1} + 5f_{j-2} \bigr] \end{aligned} \]

Solution

Rearranging the formula to obtain

\[ \begin{aligned} y_{j+1} - y_{j} + 0 y_{j-1} + 0y_{j-2} ~=~ h \left( 0f_{j+1}+ \frac{23}{12}f_j - \frac{16}{12}f_{j-1} + \frac{5}{12}f_{j-2} \right) \end{aligned} \]

we have the following coefficents

\[\begin{split} \begin{aligned} && \alpha_3 &= 1\,, & \alpha_2 &= {-1}\,, & \alpha_1 &= 0\,, & \alpha_0 &= 0 && \\[1em] && \beta_3 &= 0\,, & \beta_2 &= \frac{23}{12}\,, & \beta_1 &= -\frac{16}{12}\,, & \beta_0 &= \frac{5}{12} && \end{aligned} \end{split}\]

and the first and second characteristic polynomials

\[\begin{split} \begin{aligned} &\rho (z) = \alpha_3z^3 + \alpha_2z^2 + \alpha_1z + \alpha_0 = z^3 - z^2 \\ &\sigma(z) = \beta_3z^3 + \beta_2z^2 + \beta_1z + \beta_0 = \frac{1}{12}(23z^2 - 16z + 5) \end{aligned} \end{split}\]

Let

\[ \rho (z) = z^3 - z^2 = z^2(z - 1) = 0 \]

so we get the roots \(z_1 = 0\,, \qquad z_2 = 0\,, \qquad z_3 = 1\).

Since \(\,z_1,\,z_2\,\) are less than \(1\), and \(\,z_3\!=\!1\) is simple, the corresponding characteristic polynomial satisfies the root condition and is zero-stable.

Checking the consistency, we have

\[\begin{split} \begin{aligned} \rho(1)=&1^3 - 1^2 =0 \\ \rho'(1)= & \left.(3z^2-2z)\right\vert_{z=1} = 3(1)-2(1) = 1 \\ \sigma(1)= & \frac{1}{12}\left(23(1)^2-16(1)+5\right) = 1 \end{aligned} \end{split}\]

so the method is also consistent \((\text{i.e.}\,\rho(1) = 0,~ \rho'(1) = \sigma(1) )\).

Therefore the method is convergent.

Example 6.5

Investigate the stability of the Milne’s predictor method:

\[ \begin{aligned} y_{j+4} - y_j ~=~ \frac{4h}{3} \bigl[ 2f_{j+3} - f_{j+2} + 2f_{j+1} \bigr] \end{aligned} \]

Solution

We find the following coefficients:

\[\begin{split} \begin{aligned} && \alpha_0 &= -1\,, & \alpha_1 &= 0\,, & \alpha_2 &= 0\,, & \alpha_3 &= 0\,, & \alpha_4 &= 1 && \\[1ex] && \beta_0 &= 0\,, & \beta_1 &= \frac{8}{3}\,, & \beta_2 &= - \frac{4}{3}\,, & \beta_3 &= \frac{8}{3}\,, & \beta_4 &= 0 && \end{aligned} \end{split}\]

and

\[\begin{split} \begin{aligned} \rho(z) ~&=~ \alpha_4z^4 + \alpha_3z^3 + \alpha_2z^2 + \alpha_1z + \alpha_0 ~=~ z^4 - 1 \\ \sigma(z) ~&=~ \frac{4}{3} \bigl[ 2z^3 - z^2 + 2z \bigr] \end{aligned} \end{split}\]

\(\therefore\qquad z^4 - 1 = 0\,,\)
\(\therefore\qquad z^2 = \pm 1\,,\qquad z_1 = 1\,,\quad z_2 = -1\,,\quad z_3 = -i\,,\quad z_4 = +i\)
There are no repeated roots, and modulus of all roots are \(\,\leq 1\,\), therefore the method satisfies the root condition, but since there are more than one root with modulus one the method is weakly stable. The method is consistent \((\text{i.e.}\ \,\rho(1) = 0,~ \rho'(1) = \sigma(1) = 4)\), and since zero stable, the method is also convergent.

Remark 6.2 (Adams methods)

The characteristic polynomial \(\rho\) for all Adams methods (AB and AM) are of the form:

\[\begin{split} \begin{aligned} \rho(z) ~&=~ z^k - z^{k-1}\\ &=~ z^{k-1}(z - 1) \end{aligned} \end{split}\]

Hence, \(z_1 = 1\), and the reminding roots \(z_2,z_3,\dots,z_k = 0\), they all satisfy the root conditions and are zero stable. It can be shown that they are consistent and therefore, all Adams methods are convergent.