Dahlquist barriers

Builds on Linear multistep method Backward differentiation formula

Statement

Consider a linear $k$ -step method $\sum_{i=0}^k \alpha_i y_{j+i} = h \sum_{i=0}^k \beta_i f_{j+i}$ with $\alpha_k = 1$ and characteristic polynomials $\rho(\zeta) = \sum_i \alpha_i \zeta^i$ , $\sigma(\zeta) = \sum_i \beta_i \zeta^i$ , where $\rho$ and $\sigma$ have no common root. The method has order $p$ if $\rho(e^z) - z \sigma(e^z) = O(z^{p+1})$ as $z \to 0$ . It is zero-stable if every root of $\rho$ has modulus at most $1$ and the roots of modulus $1$ are simple. It is A-stable if, for every complex $\lambda$ with $\operatorname{Re} \lambda < 0$ and every $h > 0$ , every sequence produced by the method for $y' = \lambda y$ tends to $0$ .

First Dahlquist barrier: a zero-stable linear $k$ -step method has order $p \le k + 2$ if $k$ is even, and $p \le k + 1$ if $k$ is odd. If it is moreover explicit, then $p \le k$ .
Second Dahlquist barrier: an A-stable linear multistep method has order $p \le 2$ , and no explicit linear multistep method is A-stable.

Remarks

For the first barrier, the substitution $\zeta = \frac{1 + w}{1 - w}$ maps the left half plane $\operatorname{Re} w < 0$ onto the open unit disk. It turns the order conditions into conditions on the power series of a rational function of $w$ . Zero-stability forces sign conditions on the coefficients that are incompatible with a higher order. For the second barrier, A-stability means that $\rho(\zeta) - z \sigma(\zeta)$ has all its roots in the open unit disk whenever $\operatorname{Re} z < 0$ . Hence $\operatorname{Re} \frac{\rho(\zeta)}{\sigma(\zeta)} \ge 0$ for $\abs{\zeta} > 1$ , and this positivity is incompatible with order greater than $2$ . Example: Simpson's two-step method $y_{j+2} - y_j = \frac{h}{3} (f_{j+2} + 4 f_{j+1} + f_j)$ has order $4 = k + 2$ and is zero-stable, so the first barrier is sharp for $k = 2$ . The trapezoidal rule $y_{j+1} - y_j = \frac{h}{2} (f_{j+1} + f_j)$ has order $2$ and is A-stable, so the second barrier is sharp; among A-stable methods of order $2$ it has the smallest error constant. The backward differentiation formulas of order $3$ to $6$ are zero-stable but not A-stable, as the second barrier requires.

Going deeper

For a student

A $k$ -step method can reach order $2k$ , but such methods are not zero-stable for $k \ge 3$ . The first barrier explains why practical codes use Adams methods instead, of order $k$ or $k + 1$ for $k$ steps. The second barrier explains why stiff solvers use BDF methods. Above order $2$ these methods give up full A-stability, but they keep stability in a large sector of the left half plane. It also motivates implicit Runge–Kutta methods, which escape the barrier because they are not linear multistep methods: the Gauss–Legendre methods are A-stable of every even order. Both barriers were proved by Germund Dahlquist.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Backward differentiation formula concept
Linear multistep method concept
Dahlquist barriers statement

Tag	`BQBZ7QMJE2`
URI	`m2://BQBZ7QMJE2`
Kind	statement, theorem
Writing	W0 stub
MSC	65L06, 65L20
Status	This copy of the site has no build data. Run `m2 status BQBZ7QMJE2`.
About	Linear multistep method
Uses	Linear multistep method, Backward differentiation formula