Linear Stability of Adams-Bashforth and Adams-Moulton Schemes

In Figure (12), which is taken from ``Spectral Methods'' book from Hussaini, et al, we reproduce the stability boundaries for several AB and AM methods...

Figure 12: Stability Boundaries for several AM and AB schemes

Remember that a $p$-step multistep method requires $p$ values, including the initial condition, i.e. the ``initial values.'' Since we only have 1 of these values, we must recast the stability issue in terms that are much stronger than is practically-necessary: We require linear stability FOR ALL POSSIBLE VALUES OF $y_0, y_1, \cdots y_{p-1}$:

Write multi-step method as

$$\sum^P_{m=0}a_my_{n+m}=h\lambda \sum^P_{m=0} b_m y_{n+m}\quad n=0,1\cdots$$ (64)

when applied to $y'=\lambda y$.

(64) written as

$$\sum^P_{m=0}(a_m-h\lambda b_m)y_{n+m}=0\quad n= 0,1\cdots$$ (65)

Get linear difference equation (see notes on linear-diff equations for a brush-up on topic).

To solve (64), form characteristic polynomial

$$c(w)\equiv\sum^P_{m=0}g_m w^m$$

$$g(m)=a_m-h\lambda b_m$$

Let $w_1, w_2,\cdots w_q$ be the zeros of $c(w)$ with multiplicatives $k_1, k_2, k_3,\cdots k_q$ where $$\sum^q_{i=1}k_i=p$$. Then the general solution of (64)

$$y_n=\sum^q_{i=1}\left(\sum^{k_i-1}_{j=0}a_{i,j}n^j\right)w^n_i\quad n=0,1\cdots$$ (66)

The constants are $p a_{i,j}$ uniquely determined by the $p$ starting values $y_0, y_1, \cdots y_{p-1}$.

Lemma (A-Stability for Multi-Step): Suppose the zeros (as a function of w) of

$$c(z,w)=\sum^{P}_{m=0}(a_m-b_mz)w^m\quad z\in {\mathbb{C}}\quad z=\lambda h$$

are $w_1(z), w_2(z)\cdots, w_{q(z)}(z)$ and their multiplicatives $k_1(z), k_2(z)\cdots k_{q(z)}(z)$ respectively. Then the multi-step method (1) is A-stable if and only if

$$\vert w_i(z)\vert<1\quad i=1, 2\cdots q(z)\quad \forall z\in {\mathbb{C}}$$ (67)

Proof

Examining (65) we see that $y_n$ behavior is determined by magnitude of $w_i(h\lambda) i=1, 2\cdots, q(h\lambda)$. If they all reside inside complex unit disk then their powers decay faster than any polynomial in $n$, thus, $y_n\rightarrow 0$

Hence (67) is sufficient for A-Stability.

On the other hand, if $\vert w_i(h\lambda)\vert\ge 1$, say, then there exist starting values such that $a_{1,0}\ne 0 \therefore$ it is impossible for $y_n\rightarrow 0$ as $x_n\rightarrow\infty$. We deduce that (66) is necessary for A-Stability.

$\Box$

Example

Is the AB $y_{n+1}=y_n+\displaystyle \frac{h \lambda}{2}\left[3yn-y_{n-1}\right]$ solution for $Y' = \lambda Y$ A-Stable?

$,n\ge 1$

The characteristic equation

$$r^2-(1+\frac32h\lambda)r+\frac{1}{2} h\lambda=0$$

$$r^2-(1+\frac32z)r+\frac{1}{2} z=0$$

The roots are: $r_{0,1}=\frac{1}{2} \left\{1+\frac{3}{2}z\pm \sqrt{1+z+\frac94 z^2}\right\}$

Region of absolute stability are such that $\vert r_0(z)\vert<1, \vert r_1(z)<1$ so $-1<z<0$. Thus not A-Stable.

General Comments comparing $AB$ and $BM$:

1)

Find that for both, region of absolute stability becomes smaller the higher the order.

2)

For a given order, region of absolute stability is larger for AM.

3)

Size of region usually acceptable from the point of view of practicality.

4)

The Adams family is very easy to adapt to variable order (DEABM is a popular fortran code that does this).

5)

No Adams scheme is A-Stable. Also, in general, the higher the order, the smaller the region of stability, but with higher order you get to include more of the right hand side of the eigenvalue plane. Hence, for mildly stiff problems and slightly unstable problems one can use a high order Adams, provided $h$ is small enough.