43.10.03 · numerical-analysis / numerical-odes

Zero-stability, the root condition, and the Dahlquist equivalence theorem

shipped3 tiersLean: none

Anchor (Master): Hairer-Nørsett-Wanner 1993 *Solving Ordinary Differential Equations I: Nonstiff Problems* 2e (Springer) §III.3-III.4 (the root/Wurzelbedingung condition, the stability theorem, and the first Dahlquist barrier with its order-star/order-bound proof); Henrici 1962 *Discrete Variable Methods in Ordinary Differential Equations* (Wiley) Ch. 5 §5.2-5.3 (the companion-matrix stability analysis and the equivalence theorem); Dahlquist 1956 *Convergence and stability in the numerical integration of ordinary differential equations* (Mathematica Scandinavica 4) (the original equivalence proof)

Intuition Beginner

A multistep method blends several past values to predict the next one. That blend has a hidden personality: even before you ask it to solve a real problem, it has opinions about how a sequence of numbers should grow or shrink on its own. Zero-stability is the question of whether those opinions are calm or violent. A calm method lets small mistakes stay small as you march forward; a violent one lets a tiny early slip double, then double again, until the computed curve flies off the screen.

Picture the most boring problem there is: the slope is always zero, so the true answer is a flat line. A good method handed a flat line should keep returning that same flat value forever. The blend, though, also has spare ways to behave that have nothing to do with the real answer. These extra behaviors are called parasitic modes: ghost solutions the recurrence can support on its own. If a ghost mode stays bounded, it is harmless background noise. If a ghost mode grows, it eventually swamps the real answer no matter how accurate the method looked on paper.

The size of a ghost mode is decided by a short list of numbers called the roots of the method's first characteristic polynomial. Each root is a growth factor: a root of size less than one fades away, a root of size exactly one holds steady, and a root of size bigger than one explodes. The healthy situation is the root condition: every growth factor has size at most one, and any factor sitting right at size one is not repeated. One root, the principal root, always equals one and carries the real answer; the rest are ghosts that must be kept on a leash.

Here is the surprising part, and the heart of the unit. For a one-step method, being accurate was almost enough to be trustworthy. For a multistep method, accuracy and trustworthiness split apart. A method can match the true curve beautifully over a single step and still diverge, because a ghost root crept outside the safe zone. The Dahlquist equivalence theorem is the clean verdict: a method that is both accurate in the small (consistent) and calm in its ghosts (zero-stable) is exactly a method whose computed answer actually converges to the truth. Neither half alone will do.

Visual Beginner

Picture two number lines stacked. The top line tracks the real answer of a flat problem: it should sit unchanged at the same height step after step. The bottom line tracks a ghost mode the method secretly carries. Whether the bottom line stays flat, holds level, or rockets upward is decided entirely by the size of that ghost's growth factor.

The table below sorts the possible growth factors by size and says what each one does to a small starting error. Reading down, the only safe rows are the ones where every factor has size at most one and no size-one factor is repeated. The last column names the verdict on the whole method.

growth factor size	what a small error does	safe?
less than one	fades toward zero	yes
exactly one, not repeated	holds at constant size	yes
exactly one, repeated	grows step by step in a ramp	no
greater than one	doubles and explodes	no

Each row is a fate for a ghost mode, and the whole method is trustworthy only when every one of its ghost modes lands in a safe row.

Worked example Beginner

Let us watch a healthy method and a sick method behave on the flattest problem possible. The slope rule is "the slope is always zero," so the true answer starts at height $1$ and stays at $1$ forever. We feed each method two starting values that are exact, $u^{0} = 1$ and $u^{1} = 1$ , and let it march.

The healthy method is the two-step Adams-Bashforth blend, which on a zero slope reduces to $u^{n + 2} = u^{n + 1}$ . Step by step: $u^{2} = u^{1} = 1$ , then $u^{3} = u^{2} = 1$ , and so on. Every value stays exactly $1$ . Its growth factors are $1$ and $0$ , both inside or on the unit circle with the boundary one not repeated, so it is calm.

The sick method is a made-up two-step blend $u^{n + 2} = 3 u^{n + 1} - 2 u^{n}$ , which on a zero slope is purely this recurrence. Its growth factors turn out to be $1$ and $2$ . The factor $2$ is the troublemaker. Watch what one tiny error does.

Step 1. Suppose rounding nudges the second start to $u^{1} = 1.001$ instead of $1$ , an error of just one thousandth. The first start is still $u^{0} = 1$ .

Step 2. March the sick recurrence: $u^{2} = 3 (1.001) - 2 (1) = 3.003 - 2 = 1.003$ . The error has grown from $0.001$ to $0.003$ .

Step 3. Keep going: $u^{3} = 3 (1.003) - 2 (1.001) = 3.009 - 2.002 = 1.007$ ; then $u^{4} = 3 (1.007) - 2 (1.003) = 3.021 - 2.006 = 1.015$ . The errors run $0.001, 0.003, 0.007, 0.015$ , each roughly double the last.

Step 4. See the pattern. The error is being multiplied by about $2$ every step. After thirty steps the original thousandth-of-a-unit slip has grown past a million times its size, burying the true answer of $1$ .

What this tells us: both methods can look reasonable, but the sick one carries a ghost factor of size $2$ , and that single bad number turns a rounding whisper into an avalanche. The root condition is the rule that forbids exactly this.

Check your understanding Beginner

Exercise (easy, multiple choice).

A multistep method is accurate over a single step but one of its growth factors has size $1.5$ . What will happen when it runs many steps on a smooth problem?

A. It converges, because accuracy is all that matters. B. It diverges, because a ghost mode grows without bound. C. It stays exactly correct, because the principal factor is still one. D. Nothing can be said without more information.

Hint

A growth factor bigger than one multiplies a small error every step. Recall the sick-method example.

Answer

B. It diverges. Feedback-correct: a growth factor of size $1.5$ violates the root condition, so any small starting error is multiplied by about $1.5$ each step and eventually swamps the answer, regardless of single-step accuracy. Feedback-wrong: accuracy in the small does not rescue a method whose ghost modes grow; the principal factor being correct cannot hold back a runaway parasitic factor.

Formal definition Intermediate+

Consider the initial-value problem (IVP) $y^{'} (t) = f (t, y (t))$ , $y (t_{0}) = y_{0}$ , with $f : [t_{0}, T] \times R^{d} \to R^{d}$ continuous and globally Lipschitz in $y$ , so the unique $C^{1}$ solution exists by the Picard-Lindelöf theorem 02.12.01. Fix a step $h > 0$ , set $t_{n} = t_{0} + nh$ , $N = ⌊(T - t_{0}) / h ⌋$ , and let an $r$ -step linear multistep method (LMM) 43.10.02 $$ \sum_{j=0}^{r} \alpha_j, u^{n+j} = h\sum_{j=0}^{r} \beta_j, f^{n+j}, \qquad \alpha_r = 1, $$ have first and second characteristic polynomials $ρ (ζ) = \sum_{j} α_{j} ζ^{j}$ and $σ (ζ) = \sum_{j} β_{j} ζ^{j}$ . The method requires $r$ starting values $u^{0}, \dots, u^{r - 1}$ , supplied by a one-step method 43.10.01 with $∥ u^{k} - y (t_{k}) ∥ \to 0$ as $h \to 0$ .

Definition (root condition). The method satisfies the root condition if every root $ζ_{i}$ of $ρ$ obeys $∣ ζ_{i} ∣ \leq 1$ , and every root on the unit circle $∣ ζ_{i} ∣ = 1$ is simple (multiplicity one). Because consistency forces $ρ (1) = 0$ 43.10.02, $ζ = 1$ is always a root; it is the principal root, and the remaining roots are the spurious or parasitic roots. The root condition therefore demands that $ζ = 1$ be simple and that no other root reach or exceed modulus one.

Definition (zero-stability). The method is zero-stable if there is a constant $S$ , independent of $h$ , such that for any two numerical solutions $(u^{n})$ and $(\tilde{u}^{n})$ generated by the same method with the same right-hand side but possibly different starting values and per-step perturbations $δ^{n}$ , $$ \max_{0 \le n \le N}|u^n - \tilde u^n| ;\le; S\left(\max_{0\le k \le r-1}|u^k - \tilde u^k| + \sum_{n} |\delta^n|\right) $$ uniformly as $h \to 0$ with $N h \leq T - t_{0}$ . Equivalently, the discrete solution operator that advances the perturbed homogeneous recurrence is bounded uniformly in $h$ and in the step count. Zero-stability is stability of the discretisation at $h = 0$ : it concerns only the homogeneous recurrence $\sum_{j} α_{j} u^{n + j} = 0$ governed by $ρ$ , not the right-hand side carried by $σ$ .

Definition (convergence). The method is convergent if, whenever the starting values satisfy $∥ u^{k} - y (t_{k}) ∥ \to 0$ for $0 \leq k \leq r - 1$ as $h \to 0$ , the global error satisfies $$ \max_{0 \le n \le N}|u^n - y(t_n)| ;\longrightarrow; 0 \qquad (h \to 0) $$ for every IVP with globally Lipschitz $f$ . It is convergent of order $p$ if the global error is $O (h^{p})$ whenever the starting errors are $O (h^{p})$ .

The companion-matrix representation makes the link to eigenvalues 01.01.08 explicit. Stacking $U^{n} = (u^{n}, u^{n + 1}, \dots, u^{n + r - 1})^{⊤}$ , the homogeneous recurrence $\sum_{j} α_{j} u^{n + j} = 0$ becomes $U^{n + 1} = C U^{n}$ with $C$ the companion matrix of $ρ$ , whose eigenvalues are exactly the roots of $ρ$ . The roots $ζ_{i}$ , the companion matrix $C$ , the principal/spurious-root terminology, the discrete solution operator, and the $O (h^{p})$ Landau symbol are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Consistency implies convergence, as for one-step methods." For $r \geq 2$ it does not. The two-step method $u^{n + 2} + 4 u^{n + 1} - 5 u^{n} = h (4 f^{n + 1} + 2 f^{n})$ is consistent of order $3$ , yet $ρ (ζ) = ζ^{2} + 4 ζ - 5 = (ζ - 1) (ζ + 5)$ has the spurious root $ζ = - 5$ of modulus $5$ , so it violates the root condition and diverges. Consistency controls accuracy at $ζ = 1$ ; zero-stability controls the other roots. Both are needed, which is the content of the equivalence theorem below.
"Any root inside the unit disc is fine, so a root at $ζ = 1$ of multiplicity two is fine." A boundary root must be simple. A double root at $ζ = 1$ makes the homogeneous recurrence support the growing solution $u^{n} = n$ , an unbounded parasitic mode, so the root condition fails even though no root leaves the closed disc.
"Zero-stability and absolute stability are the same." Zero-stability is the $h \to 0$ property of $ρ$ alone, asking only that parasitic modes not grow as the grid refines. Absolute stability 43.10.04 is a fixed- $h$ property of the combined polynomial $ρ (ζ) - z σ (ζ)$ on the test equation $y^{'} = λ y$ , asking that all roots stay in the disc for a given $z = hλ \neq = 0$ . A method can be zero-stable yet have a small absolute-stability region.

Key theorem with proof Intermediate+

The signature result is the Dahlquist equivalence theorem: for a consistent linear multistep method, convergence is the same condition as zero-stability, and zero-stability is the same condition as the root condition on $ρ$ . This collapses an analytic question about the limit of computed trajectories into a finite algebraic check on the roots of a single polynomial, and it is the multistep analogue of the one-step convergence theorem 43.10.01 in which the Lipschitz/Gronwall stability bound is replaced by power-boundedness of the companion matrix of $ρ$ .

Theorem (Dahlquist equivalence). Let an $r$ -step LMM with polynomials $ρ, σ$ be consistent (so $ρ (1) = 0$ and $ρ^{'} (1) = σ (1)$ ). Then the following are equivalent:

the method is convergent;
the method is zero-stable;
$ρ$ satisfies the root condition.

Moreover, when these hold and the method has consistency order $p$ with starting errors $O (h^{p})$ , the global error is $O (h^{p})$ : the order of convergence equals the order of consistency. ^{[LeVeque §6.3-6.4; Süli-Mayers §12.9-12.10]}

Proof. We prove $(3) \Rightarrow (2) \Rightarrow (1)$ and then $(1) \Rightarrow (3)$ , which closes the cycle.

$(3) \Rightarrow (2)$ : the root condition gives zero-stability. Pass to the companion form. The homogeneous recurrence $\sum_{j = 0}^{r} α_{j} v^{n + j} = 0$ is $V^{n + 1} = C V^{n}$ with $V^{n} = (v^{n}, \dots, v^{n + r - 1})^{⊤}$ and $C$ the companion matrix of $ρ$ , so $V^{n} = C^{n} V^{0}$ . The eigenvalues of $C$ are the roots of $ρ$ 01.01.08. A power $C^{n}$ is bounded uniformly in $n$ exactly when every eigenvalue has modulus at most one and every eigenvalue of modulus one is non-defective, that is, lies in a Jordan block of size one. Simplicity of the boundary roots is precisely non-defectiveness there, while roots strictly inside the disc contribute powers $ζ_{i}^{n} \to 0$ . Hence the root condition gives a bound $∥ C^{n} ∥ \leq M$ for all $n$ , with $M$ independent of $n$ .

Now compare two perturbed solutions. Writing $e^{n} = u^{n} - \tilde{u}^{n}$ and stacking $E^{n}$ , the inhomogeneous recurrence with the Lipschitz right-hand side and per-step perturbations $δ^{n}$ reads $E^{n + 1} = C E^{n} + h B^{n} + D^{n}$ , where $∥ B^{n} ∥ \leq Γ L max_{k \leq n + r} ∥ e^{k} ∥$ collects the $σ$ -weighted $f$ -differences (with $Γ$ depending only on the coefficients) and $D^{n}$ carries the $δ^{n}$ . By discrete variation of constants, $E^{n} = C^{n} E^{0} + \sum_{m = 0}^{n - 1} C^{n - 1 - m} (h B^{m} + D^{m})$ , so $$ |E^n| \le M|E^0| + M\sum_{m=0}^{n-1}\big(h\Gamma L \max_{k}|e^k| + |D^m|\big). $$ The factor $h$ on the $B^{m}$ sum over $O (1/ h)$ terms keeps that contribution $O (1)$ times $max_{k} ∥ e^{k} ∥$ with a coefficient $M Γ L (T - t_{0})$ ; absorbing it by a discrete Gronwall argument 43.10.01 gives $max_{n} ∥ e^{n} ∥ \leq S (∥ E^{0} ∥ + \sum_{m} ∥ D^{m} ∥)$ with $S = M e^{M Γ L (T - t_{0})}$ , independent of $h$ . This is zero-stability.

$(2) \Rightarrow (1)$ : zero-stability plus consistency gives convergence. Treat the exact solution as a perturbed numerical solution. Substituting $y (t_{n})$ into the scheme leaves the residual $h τ^{n}$ with $τ^{n} = O (h^{p})$ the local truncation error 43.10.02, so $(y (t_{n}))$ satisfies the same recurrence as $(u^{n})$ up to per-step perturbations $δ^{n} = h τ^{n}$ . The starting errors are $∥ u^{k} - y (t_{k}) ∥ = O (h^{p})$ by hypothesis. Apply the zero-stability estimate with $\tilde{u}^{n} = y (t_{n})$ : $$ \max_n|u^n - y(t_n)| \le S\Big(\max_{k\le r-1}|u^k - y(t_k)| + \sum_n h|\tau^n|\Big) \le S\big(O(h^p) + (T-t_0),O(h^p)\big) = O(h^p), $$ the sum $\sum_{n} h ∥ τ^{n} ∥$ having $O (1/ h)$ terms each $O (h \cdot h^{p})$ . In particular the error tends to zero, so the method converges, with order equal to the consistency order $p$ .

$(1) \Rightarrow (3)$ : convergence forces the root condition. Argue by contraposition: a method violating the root condition cannot converge. Suppose $ρ$ has a root $ζ_{*}$ with $∣ ζ_{*} ∣ > 1$ , or a repeated root on the unit circle. Apply the method to the IVP $y^{'} = 0$ , $y (0) = 0$ , whose exact solution is identically zero, with starting values $u^{k} = h ζ_{*}^{k}$ (when $∣ ζ_{*} ∣ > 1$ ) or $u^{k} = h k ζ_{*}^{k}$ (for a repeated boundary root). These starting values tend to zero with $h$ , so a convergent method would force $max_{n} ∥ u^{n} ∥ \to 0$ . But on $y^{'} = 0$ the recurrence is the homogeneous $\sum_{j} α_{j} u^{n + j} = 0$ , whose solution with these data is $u^{n} = h ζ_{*}^{n}$ (respectively $h n ζ_{*}^{n}$ ). At a fixed time $t = nh$ with $n = t / h$ , $∥ u^{n} ∥ = h ∣ ζ_{*} ∣^{t / h}$ (respectively $h (t / h) ∣ ζ_{*} ∣^{t / h}$ ), which grows without bound as $h \to 0$ because $∣ ζ_{*} ∣^{1/ h} \to \infty$ faster than $h \to 0$ . The computed solution diverges while the true solution is zero, contradicting convergence. Hence convergence forces the root condition. $□$

The estimate manufactured in $(3) \Rightarrow (2)$ is a discrete variation-of-constants formula: the companion matrix $C$ plays the role the scalar amplification factor $1 + h Λ$ played for one-step methods 43.10.01, and power-boundedness $∥ C^{n} ∥ \leq M$ is the multistep replacement for the single-step Lipschitz contraction. The whole content of zero-stability is that this $M$ exists uniformly in $h$ .

Bridge. The equivalence theorem is the foundational reason a multistep method's reliability is read off the roots of $ρ$ and nothing else: consistency pins the principal root at $ζ = 1$ with the correct first derivative, while zero-stability is the demand that the remaining companion-matrix spectrum stay power-bounded, and this is exactly the point at which the one-step story of 43.10.01 generalises — there the scalar factor $1 + h Λ$ was automatically power-bounded, here the companion matrix of $ρ$ is power-bounded only under the root condition. This builds toward the absolute-stability theory of 43.10.04, where the same companion-matrix idea is applied to the combined polynomial $ρ (ζ) - z σ (ζ)$ at fixed $z = hλ \neq = 0$ ; putting these together, zero-stability is the $z = 0$ edge of absolute stability, and the central insight is that "consistency plus stability equals convergence" is one template realised twice, with stability meaning a Gronwall bound for one-step methods and power-boundedness of $C$ for multistep methods. The theorem appears again in 43.11.05 as the Lax-Richtmyer equivalence for finite-difference PDE schemes, where the companion matrix is replaced by the evolution operator $C (Δ t)$ and power-boundedness becomes uniform $∥ C (Δ t)^{n} ∥ \leq K$ ; the bridge is the recognition that all three theorems are the statement that a consistent scheme converges precisely when its discrete solution operator does not amplify.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Show that a multistep method whose $ρ$ has a double root at $ζ = 1$ is not zero-stable, by exhibiting an unbounded solution of the homogeneous recurrence.

Hint

If $ρ (ζ) = (ζ - 1)^{2} q (ζ)$ , the homogeneous recurrence $\sum_{j} α_{j} u^{n + j} = 0$ admits both $u^{n} = 1$ and $u^{n} = n$ as solutions. Verify the second.

Answer

For a recurrence with characteristic polynomial $ρ$ , a root $ζ_{0}$ of multiplicity $m$ contributes the independent solutions $ζ_{0}^{n}, n ζ_{0}^{n}, \dots, n^{m - 1} ζ_{0}^{n}$ . A double root at $ζ_{0} = 1$ therefore gives the solutions $u^{n} = 1^{n} = 1$ and $u^{n} = n \cdot 1^{n} = n$ . The sequence $u^{n} = n$ solves $\sum_{j} α_{j} u^{n + j} = \sum_{j} α_{j} (n + j) = n ρ (1) + ρ^{'} (1) = 0$ , using $ρ (1) = 0$ and $ρ^{'} (1) = 0$ (the latter because $ζ = 1$ is a double root). This $u^{n} = n$ is unbounded as $n \to \infty$ , so with starting data $u^{0} = 0, u^{1} = 1, \dots$ scaled to vanish with $h$ the solution still grows like $t / h$ , defeating uniform boundedness. Hence a double principal root breaks zero-stability. Rubric: full credit for identifying $u^{n} = n$ and verifying it solves the homogeneous recurrence via $ρ (1) = ρ^{'} (1) = 0$ .

Exercise 7 (hard, symbolic).

Prove that power-boundedness of the companion matrix $C$ of a monic polynomial $ρ$ is equivalent to the root condition on $ρ$ . Address the role of multiplicity on the unit circle.

Hint

Use the Jordan form of $C$ . The size of the Jordan block at an eigenvalue $ζ_{i}$ controls whether $C^{n}$ carries factors $n^{k} ζ_{i}^{n}$ . Recall that the companion matrix is non-derogatory, so each eigenvalue sits in a single Jordan block whose size equals its algebraic multiplicity.

Answer

Put $C$ in Jordan form $C = P J P^{- 1}$ , so $C^{n} = P J^{n} P^{- 1}$ and $∥ C^{n} ∥$ is bounded iff $∥ J^{n} ∥$ is. For a single Jordan block of size $m$ at eigenvalue $ζ_{i}$ , the entries of $J^{n}$ are $(k n) ζ_{i}^{n - k}$ for $0 \leq k \leq m - 1$ , so $∥ J^{n} ∥$ behaves like $n^{m - 1} ∣ ζ_{i} ∣^{n}$ up to constants. This stays bounded in $n$ iff either $∣ ζ_{i} ∣ < 1$ (any block size, since $n^{m - 1} ∣ ζ_{i} ∣^{n} \to 0$ ), or $∣ ζ_{i} ∣ = 1$ with $m = 1$ (so no polynomial factor, $∣ J^{n} ∣ = 1$ ). It is unbounded if $∣ ζ_{i} ∣ > 1$ (exponential growth) or if $∣ ζ_{i} ∣ = 1$ with $m \geq 2$ (the $n^{m - 1}$ factor grows). The companion matrix is non-derogatory: its minimal and characteristic polynomials coincide, so each eigenvalue $ζ_{i}$ lies in exactly one Jordan block of size equal to its multiplicity as a root of $ρ$ . Therefore $C^{n}$ is bounded iff every root has $∣ ζ_{i} ∣ \leq 1$ and every root with $∣ ζ_{i} ∣ = 1$ has multiplicity one — precisely the root condition. Rubric: full credit for the Jordan-block growth analysis, the non-derogatory remark linking block size to root multiplicity, and the two-sided equivalence.

Exercise 8 (hard, symbolic).

State the first Dahlquist barrier and verify it is sharp at $r = 2$ by exhibiting a zero-stable two-step method of order $3$ . Confirm the order and zero-stability.

Hint

The barrier caps a zero-stable $r$ -step method at order $r + 2$ for even $r$ . For $r = 2$ that is order $4$ ? No — recompute: even $r = 2$ gives the cap $r + 2 = 4$ only for the optimal boundary-root methods; Simpson's rule $u^{n + 2} - u^{n} = \frac{h}{3} (f^{n + 2} + 4 f^{n + 1} + f^{n})$ is the order- $4$ extreme. An order- $3$ example with strict interior spurious root is easier to certify.

Answer

The first Dahlquist barrier: a zero-stable $r$ -step LMM has order at most $r + 2$ if $r$ is even and $r + 1$ if $r$ is odd, with order $r + 2$ attained only when all roots of $ρ$ lie on the unit circle. For $r = 2$ the cap is order $4$ , realised by Simpson's rule $u^{n + 2} - u^{n} = \frac{h}{3} (f^{n + 2} + 4 f^{n + 1} + f^{n})$ : here $ρ (ζ) = ζ^{2} - 1 = (ζ - 1) (ζ + 1)$ , both roots on the circle and simple, so the root condition holds and the method is zero-stable; matching error constants gives order $4$ (one checks $C_{0} = \dots = C_{4} = 0$ , $C_{5} = - \frac{1}{90} \neq = 0$ ). This realises the even- $r$ extreme with all roots on the circle. A strictly interior example of order $3$ is the third-order Adams-Moulton method $u^{n + 1} = u^{n} + h (\frac{5}{12} f^{n + 1} + \frac{2}{3} f^{n} - \frac{1}{12} f^{n - 1})$ from 43.10.02, whose $ρ (ζ) = ζ^{2} - ζ$ has roots $1$ and $0$ (root condition holds) and order $3$ , comfortably under the $r = 2$ cap. Rubric: full credit for the correct barrier statement and either certified example with its root analysis and order.

Advanced results Master

The equivalence theorem is the convergence backbone; its sharp consequences are the barriers that bound how much order a usable method can carry, the refined stability notions that separate methods sharing the root condition, and the analytic machinery that proves the order bound.

Theorem 1 (first Dahlquist barrier). A zero-stable $r$ -step linear multistep method has order $p \leq r + 2$ if $r$ is even and $p \leq r + 1$ if $r$ is odd. The maximal order $r + 2$ (even $r$ ) is attained only by methods all of whose $ρ$ -roots lie on the unit circle — the optimal methods — which have poor damping of the parasitic modes and are rarely used. The proof studies the analytic function $ρ (ζ) / lo g ζ - σ (ζ)$ , whose vanishing to order $p$ at $ζ = 1$ is the order condition 43.10.02; the root condition constrains the zeros of $ρ$ to the closed disc with simple boundary zeros, and a contour/argument-principle count of how many such zeros $ρ$ can carry while $ρ / lo g ζ - σ$ vanishes to high order yields the bound. The order-star reformulation of Wanner-Hairer-Nørsett gives the cleanest modern proof ^{[Hairer-Nørsett-Wanner §III.3-III.4]}.

Theorem 2 (strong stability, relative stability, and weak instability). Among zero-stable methods, the location of the spurious roots on the circle refines the classification. A method is strongly stable if $ζ = 1$ is the only root on the unit circle, so all parasitic modes decay — the Adams and BDF families are strongly stable. It is weakly stable if other roots lie on the circle: the leapfrog/midpoint method, with spurious root $ζ = - 1$ , is zero-stable but its parasitic mode neither grows nor decays, producing the oscillatory error contamination that makes leapfrog unsuitable for dissipative problems without filtering. Relative stability compares the growth of spurious roots to the principal root on the test equation $y^{'} = λ y$ and is the bridge from this $h \to 0$ theory to the fixed- $h$ absolute stability of 43.10.04.

Theorem 3 (convergence order under root condition, quantitative). If a consistent zero-stable $r$ -step method has order $p$ , starting errors $∥ u^{k} - y (t_{k}) ∥ \leq c_{0} h^{p}$ , and is applied to an IVP with $f \in C^{p}$ and globally Lipschitz, then $$ \max_{0\le n\le N}|u^n - y(t_n)| \le S\Big(c_0 h^p + (T - t_0),\overline{C},h^p\Big) = O(h^p), $$ with $S$ the zero-stability constant (the power bound $∥ C^{n} ∥ \leq M$ inflated by a Gronwall factor) and $\overline{C}$ a bound on the principal-error-constant times the $(p + 1)$ -st derivative of $y$ . The estimate is the multistep counterpart of the one-step bound of 43.10.01; the only structural change is the replacement of the scalar amplification by the companion-matrix power bound ^{[Hairer-Nørsett-Wanner §III.4]}.

Theorem 4 (the spurious roots carry no accuracy but all the danger). Write the numerical solution near a smooth exact solution as a superposition over the roots: $u^{n} \approx \sum_{i} p_{i} (n) ζ_{i}^{n} e^{μ_{i} t_{n}}$ , where the principal root $ζ_{1} = 1$ tracks the true solution and each spurious root $ζ_{i}$ contributes a parasitic component damped by $∣ ζ_{i} ∣^{n}$ . The order conditions are statements about the principal branch alone; the spurious branches contribute nothing to the order but become the dominant error if any $∣ ζ_{i} ∣$ approaches or exceeds one. This is the structural reason high-order methods built by pushing all coefficients into accuracy fail: extra order is bought by relocating the spurious roots toward and across the unit circle, exactly where the root condition forbids them ^{[Henrici 1962]}.

Theorem 5 (necessity of one-step starters and their order). A convergent $r$ -step method requires $r$ starting values; for order- $p$ convergence the starting values must themselves be accurate to $O (h^{p})$ , which is why a one-step Runge-Kutta starter 43.10.01 of order at least $p$ is used to bootstrap the recurrence. Under zero-stability the starting errors propagate without amplification — the same power-bound $∥ C^{n} ∥ \leq M$ controls their contribution — so a starter of matching order suffices and no order is lost in the transient. Lower-order starters degrade the global order to that of the starter, a failure mode invisible in the asymptotic theory until the starting errors dominate ^{[Süli-Mayers §12.10]}.

Synthesis. The root condition on $ρ$ is the foundational reason the entire convergence theory of multistep methods reduces to a finite eigenvalue check: zero-stability is power-boundedness of the companion matrix of $ρ$ , convergence is zero-stability together with consistency, and the equivalence theorem makes these three the same condition, so the analytic limit of computed trajectories is decided by the moduli and multiplicities of $r$ algebraic numbers.

This is exactly the structure met for one-step methods in 43.10.01, where the scalar amplification factor was automatically power-bounded and only the Lipschitz/Gronwall ingredient mattered; the central insight is that the multistep recurrence introduces spurious roots that carry no accuracy and all the instability, and it generalises the one-step convergence theorem by promoting the scalar factor to the companion matrix whose spectrum is the roots of $ρ$ . Putting these together, the first Dahlquist barrier is the exact accounting of the tension the order theory of 43.10.02 left open — order conditions can always be met, but only by relocating $ρ$ -roots where the root condition forbids — and the optimal even- $r$ methods that touch the barrier pay for their order with all roots on the circle and no parasitic damping. The bridge to the rest of the chapter is the recognition that this $h \to 0$ stability is dual to the fixed- $h$ absolute stability of 43.10.04, which studies the same companion-matrix idea applied to $ρ (ζ) - z σ (ζ)$ at $z = hλ \neq = 0$ , with zero-stability the $z = 0$ boundary case; the same template appears again as the Lax-Richtmyer equivalence theorem 43.11.05, completing the consistency-plus-stability story across ODE and PDE discretisations.

Full proof set Master

Proposition 1 (root condition $\Leftrightarrow$ bounded homogeneous solutions). The homogeneous recurrence $\sum_{j = 0}^{r} α_{j} v^{n + j} = 0$ (with $α_{r} = 1$ ) has all solution sequences $(v^{n})$ bounded in $n$ if and only if $ρ$ satisfies the root condition.

Proof. The general solution of the recurrence is a superposition of $n^{k} ζ_{i}^{n}$ over the distinct roots $ζ_{i}$ of $ρ$ with $0 \leq k \leq m_{i} - 1$ , where $m_{i}$ is the multiplicity of $ζ_{i}$ — this is the standard solution basis of a linear constant-coefficient recurrence, and the ${n^{k} ζ_{i}^{n}}$ are linearly independent. A term $n^{k} ζ_{i}^{n}$ is bounded in $n$ iff $∣ ζ_{i} ∣ < 1$ (any $k$ , since the exponential decay beats the polynomial), or $∣ ζ_{i} ∣ = 1$ with $k = 0$ . It is unbounded iff $∣ ζ_{i} ∣ > 1$ , or $∣ ζ_{i} ∣ = 1$ with $k \geq 1$ , the latter requiring $m_{i} \geq 2$ . Every solution is bounded iff every basis term is bounded, iff every root has $∣ ζ_{i} ∣ \leq 1$ and every root with $∣ ζ_{i} ∣ = 1$ has multiplicity one. That is the root condition. $□$

Proposition 2 (the consistent unstable method diverges on a smooth problem). The two-step method $u^{n + 2} + 4 u^{n + 1} - 5 u^{n} = h (4 f^{n + 1} + 2 f^{n})$ is consistent of order $3$ but diverges on the IVP $y^{'} = y$ , $y (0) = 1$ , with vanishing starting errors.

Proof. Consistency and order $3$ are verified through the error constants $C_{q}$ 43.10.02: $ρ (ζ) = ζ^{2} + 4 ζ - 5$ , $σ (ζ) = 4 ζ + 2$ , and one computes $C_{0} = ρ (1) = 0$ , $C_{1} = ρ^{'} (1) - σ (1) = 6 - 6 = 0$ , and $C_{2} = C_{3} = 0$ by direct substitution, with $C_{4} \neq = 0$ . Now apply the method to $y^{'} = y$ . The recurrence is $u^{n + 2} + 4 u^{n + 1} - 5 u^{n} = h (4 u^{n + 1} + 2 u^{n})$ , a linear constant-coefficient recurrence with characteristic equation $ζ^{2} + (4 - 4 h) ζ - (5 + 2 h) = 0$ . At $h = 0$ the roots are those of $ρ$ , namely $1$ and $- 5$ . For small $h > 0$ they perturb to $ζ_{1} (h) = 1 + h + O (h^{2})$ (the principal root tracking $e^{h}$ ) and $ζ_{2} (h) = - 5 + O (h)$ . The general solution is $u^{n} = A ζ_{1} (h)^{n} + B ζ_{2} (h)^{n}$ . Even with starting values chosen so that $B = O (h^{q})$ for any fixed $q$ , at a fixed time $t = nh$ the parasitic term is $B (- 5 + O (h))^{t / h}$ , and $∣ - 5 ∣^{t / h} = 5^{t / h} \to \infty$ as $h \to 0$ faster than any power $h^{q} \to 0$ . Thus $∣ u^{n} ∣ \to \infty$ at fixed $t$ , while the exact solution is $e^{t}$ , finite. The method diverges. $□$

Proposition 3 (Simpson's rule is order $4$ and zero-stable, attaining the barrier). The method $u^{n + 2} - u^{n} = \frac{h}{3} (f^{n + 2} + 4 f^{n + 1} + f^{n})$ has $ρ (ζ) = ζ^{2} - 1$ satisfying the root condition, and has order $4$ , realising the first Dahlquist barrier for $r = 2$ .

Proof. The roots of $ρ (ζ) = ζ^{2} - 1$ are $ζ = 1$ and $ζ = - 1$ , both of modulus $1$ and both simple, so the root condition holds and the method is zero-stable (Proposition 1). For the order, index the window $j \in {0, 1, 2}$ with $α = (- 1, 0, 1)$ and $β = (\frac{1}{3}, \frac{4}{3}, \frac{1}{3})$ , and compute the error constants $C_{q} = \frac{1}{q !} \sum_{j} α_{j} j^{q} - \frac{1}{( q - 1 )!} \sum_{j} β_{j} j^{q - 1}$ . Then $C_{0} = - 1 + 1 = 0$ ; $C_{1} = (0 + 2) - (\frac{1}{3} + \frac{4}{3} + \frac{1}{3}) = 2 - 2 = 0$ ; $C_{2} = \frac{1}{2} (0 + 4) - (\frac{4}{3} + 2 \cdot \frac{1}{3}) = 2 - 2 = 0$ ; $C_{3} = \frac{1}{6} (0 + 8) - \frac{1}{2} (\frac{4}{3} + 4 \cdot \frac{1}{3}) = \frac{4}{3} - \frac{1}{2} \cdot \frac{8}{3} = \frac{4}{3} - \frac{4}{3} = 0$ ; $C_{4} = \frac{1}{24} (0 + 16) - \frac{1}{6} (\frac{4}{3} + 8 \cdot \frac{1}{3}) = \frac{2}{3} - \frac{1}{6} \cdot 4 = \frac{2}{3} - \frac{2}{3} = 0$ ; and $C_{5} = \frac{1}{120} (0 + 32) - \frac{1}{24} (\frac{4}{3} + 16 \cdot \frac{1}{3}) = \frac{32}{120} - \frac{1}{24} \cdot \frac{20}{3} = \frac{4}{15} - \frac{20}{72} = \frac{4}{15} - \frac{5}{18}$ . Over the common denominator $90$ , $\frac{4}{15} = \frac{24}{90}$ and $\frac{5}{18} = \frac{25}{90}$ , so $C_{5} = - \frac{1}{90} \neq = 0$ . Hence $C_{0} = \dots = C_{4} = 0$ and $C_{5} \neq = 0$ : the order is $4 = r + 2$ with $r = 2$ even, the barrier value, attained with both roots on the unit circle. $□$

Proposition 4 (starting-error propagation under zero-stability). For a zero-stable $r$ -step method with power bound $∥ C^{n} ∥ \leq M$ , perturbing only the starting values by $η_{k} = u^{k} - \tilde{u}^{k}$ ( $0 \leq k \leq r - 1$ ) changes the solution at every later step by at most $max_{n} ∥ u^{n} - \tilde{u}^{n} ∥ \leq M^{'} max_{k} ∥ η_{k} ∥$ , with $M^{'}$ independent of $h$ .

Proof. With identical right-hand sides and no per-step perturbations, the difference $e^{n} = u^{n} - \tilde{u}^{n}$ satisfies the inhomogeneous companion recurrence $E^{n + 1} = C E^{n} + h B^{n}$ with $∥ B^{n} ∥ \leq Γ L max_{k \leq n + r} ∥ e^{k} ∥$ collecting the $σ$ -weighted Lipschitz $f$ -differences. Discrete variation of constants gives $E^{n} = C^{n} E^{0} + \sum_{m = 0}^{n - 1} C^{n - 1 - m} h B^{m}$ , so $∥ E^{n} ∥ \leq M ∥ E^{0} ∥ + M h Γ L \sum_{m = 0}^{n - 1} max_{k} ∥ e^{k} ∥$ . The stacked initial vector $E^{0}$ has $∥ E^{0} ∥ \leq r max_{k} ∥ η_{k} ∥$ . Setting $ϕ_{n} = max_{0 \leq i \leq n} ∥ e^{i} ∥$ , the bound reads $ϕ_{n} \leq M r max_{k} ∥ η_{k} ∥ + M h Γ L \sum_{m < n} ϕ_{m}$ , a discrete Gronwall inequality 43.10.01 whose solution is $ϕ_{N} \leq M r e^{M Γ L (T - t_{0})} max_{k} ∥ η_{k} ∥$ . Take $M^{'} = M r e^{M Γ L (T - t_{0})}$ , independent of $h$ since $N h \leq T - t_{0}$ . $□$

Connections Master

The linear multistep order theory of 43.10.02 supplies the polynomials $ρ, σ$ , the consistency conditions $ρ (1) = 0$ , $ρ^{'} (1) = σ (1)$ , and the error constants $C_{q}$ that this unit takes as input; that unit constructs the Adams, BDF, and predictor-corrector families and certifies their order but leaves convergence open, flagging precisely that a consistent method can diverge. This unit closes that gap by proving convergence equivalent to the root condition, and the first Dahlquist barrier stated there is proved here as the constraint zero-stability places on how high the order of a stable $ρ$ can reach.
The one-step convergence theorem of 43.10.01 is the structural template this unit generalises: there the global $O (h^{p})$ bound came from consistency plus a scalar Lipschitz/discrete-Gronwall stability factor; here the scalar amplification $1 + h Λ$ is replaced by the companion matrix $C$ of $ρ$ , and power-boundedness $∥ C^{n} ∥ \leq M$ — the root condition — is the multistep stability ingredient. The discrete Gronwall inequality of that unit is reused verbatim in the variation-of-constants estimate, and the Runge-Kutta starters that bootstrap a multistep recurrence are its instances.
The absolute-stability theory of 43.10.04 studies the same companion-matrix mechanism applied to the combined polynomial $ρ (ζ) - z σ (ζ)$ on the test equation $y^{'} = λ y$ at fixed $z = hλ$ : zero-stability is exactly the boundary case $z = 0$ , asking only that the roots of $ρ$ alone satisfy the root condition, while absolute stability asks the same of the perturbed roots for $z \neq = 0$ . The classification of spurious roots here (strong versus weak stability) is the input to the boundary-locus construction there.
The eigenvalue and characteristic-polynomial theory of 01.01.08 is the engine of the companion-matrix argument: the roots of $ρ$ are the eigenvalues of $C$ , the Jordan structure controls whether $C^{n}$ is power-bounded, and the non-derogatory property of companion matrices ties Jordan-block size to root multiplicity, which is why simplicity of boundary roots is exactly non-defectiveness there.
The Cauchy/Bolzano-Weierstrass boundedness machinery of 02.03.02 underlies the definition of zero-stability as uniform boundedness of the discrete solution operator as $h \to 0$ : the existence of a single constant $S$ controlling all refinements is a boundedness criterion on the family of solution operators, and the limiting arguments in the $(1) \Rightarrow (3)$ contrapositive use the divergence of $∣ ζ_{*} ∣^{1/ h}$ against a vanishing sequence.

Historical & philosophical context Master

The decisive synthesis is due to Germund Dahlquist, whose 1956 paper in Mathematica Scandinavica ^{[Dahlquist 1956]} introduced zero-stability through the root condition on the first characteristic polynomial and proved the equivalence of convergence with consistency-plus-stability for the general linear multistep method, establishing that accuracy and stability are independent requirements that together are necessary and sufficient. The same paper organised the order theory through the polynomials $ρ$ and $σ$ ; Dahlquist's 1963 paper ^{[Dahlquist 1963]} then proved the order barriers, the first bounding the order of a zero-stable $r$ -step method and the second bounding the order of an A-stable one. The root condition itself had a precursor in the stability analyses of Richardson and the difference-equation tradition, but Dahlquist gave it the clean polynomial form and the equivalence theorem.

The companion-matrix and difference-operator organisation of the proof was systematised by Peter Henrici in his 1962 monograph Discrete Variable Methods in Ordinary Differential Equations, which cast the stability analysis as power-boundedness of the companion matrix and is the source of the modern textbook treatment. The structural parallel with the Lax-Richtmyer equivalence theorem for finite-difference approximations of partial differential equations, published by Peter Lax and Robert Richtmyer in the same year 1956, was recognised early: both theorems assert that for a consistent scheme approximating a well-posed linear problem, stability and convergence are equivalent. The order-star technique that gives the sharpest modern proof of the Dahlquist barriers was introduced by Gerhard Wanner, Ernst Hairer, and Syvert Nørsett in 1978.

Bibliography Master

@article{dahlquist1956,
  author  = {Dahlquist, Germund},
  title   = {Convergence and stability in the numerical integration of ordinary differential equations},
  journal = {Mathematica Scandinavica},
  volume  = {4},
  year    = {1956},
  pages   = {33--53}
}

@article{dahlquist1963,
  author  = {Dahlquist, Germund},
  title   = {A special stability problem for linear multistep methods},
  journal = {BIT Numerical Mathematics},
  volume  = {3},
  number  = {1},
  year    = {1963},
  pages   = {27--43}
}

@book{henrici1962,
  author    = {Henrici, Peter},
  title     = {Discrete Variable Methods in Ordinary Differential Equations},
  publisher = {John Wiley \& Sons},
  year      = {1962}
}

@book{hnw1993,
  author    = {Hairer, Ernst and N\o{}rsett, Syvert P. and Wanner, Gerhard},
  title     = {Solving Ordinary Differential Equations I: Nonstiff Problems},
  edition   = {2},
  series    = {Springer Series in Computational Mathematics},
  volume    = {8},
  publisher = {Springer-Verlag},
  year      = {1993}
}

@book{sulimayers2003,
  author    = {S\"{u}li, Endre and Mayers, David F.},
  title     = {An Introduction to Numerical Analysis},
  publisher = {Cambridge University Press},
  year      = {2003}
}

@book{leveque2007fdm,
  author    = {LeVeque, Randall J.},
  title     = {Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2007}
}

@article{laxrichtmyer1956,
  author  = {Lax, Peter D. and Richtmyer, Robert D.},
  title   = {Survey of the stability of linear finite difference equations},
  journal = {Communications on Pure and Applied Mathematics},
  volume  = {9},
  number  = {2},
  year    = {1956},
  pages   = {267--293}
}

@article{wannerhairernorsett1978,
  author  = {Wanner, Gerhard and Hairer, Ernst and N\o{}rsett, Syvert P.},
  title   = {Order stars and stability theorems},
  journal = {BIT Numerical Mathematics},
  volume  = {18},
  number  = {4},
  year    = {1978},
  pages   = {475--489}
}

Prerequisites

43.10.02
43.10.01
01.01.08
02.03.02

Tier anchors

beginner: LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §6.3-6.4 (the zero-stability picture: the recurrence on the trivial problem $y'=0$ and why a parasitic root makes errors explode); Süli-Mayers 2003 *An Introduction to Numerical Analysis* (Cambridge) §12.9 (the root condition stated through the homogeneous recurrence)
intermediate: Süli-Mayers 2003 *An Introduction to Numerical Analysis* (Cambridge) §12.9-12.10 (zero-stability, the root condition on $\rho$, and the convergence theorem for linear multistep methods); LeVeque 2007 (SIAM) §6.3-6.4 (zero-stability, the root condition, and the statement that consistency plus zero-stability gives convergence)
master: Hairer-Nørsett-Wanner 1993 *Solving Ordinary Differential Equations I: Nonstiff Problems* 2e (Springer) §III.3-III.4 (the root/Wurzelbedingung condition, the stability theorem, and the first Dahlquist barrier with its order-star/order-bound proof); Henrici 1962 *Discrete Variable Methods in Ordinary Differential Equations* (Wiley) Ch. 5 §5.2-5.3 (the companion-matrix stability analysis and the equivalence theorem); Dahlquist 1956 *Convergence and stability in the numerical integration of ordinary differential equations* (Mathematica Scandinavica 4) (the original equivalence proof)

References

LeVeque, R. J. — Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems · SIAM 2007. §6.3 defines zero-stability of a linear multistep method as the requirement that the numerical solution of the homogeneous problem $y'=0$ stay bounded as $h\to0$ with the number of steps growing like $1/h$; this is shown to be exactly the root condition on the first characteristic polynomial $\rho(\zeta)$ — every root $\zeta_i$ satisfies $|\zeta_i|\le1$ and every root on $|\zeta|=1$ is simple. §6.4 states and sketches the convergence theorem: a consistent, zero-stable LMM is convergent, with global error order equal to the consistency order, and conversely a consistent convergent method is zero-stable; the unstable consistent example (a method whose $\rho$ has a root outside the disc) is exhibited diverging on a smooth problem.
Süli, E. & Mayers, D. F. — An Introduction to Numerical Analysis · Cambridge University Press 2003. §12.9 introduces zero-stability through the homogeneous difference equation $\sum_j \alpha_j u^{n+j}=0$, whose general solution is built from the roots of $\rho(\zeta)=\sum_j \alpha_j \zeta^j$; boundedness of every such solution sequence is the root condition (all roots in the closed unit disc, those on the unit circle simple). §12.10 proves the convergence theorem for the general $r$-step LMM: consistency ($\rho(1)=0$, $\rho'(1)=\sigma(1)$) plus zero-stability (the root condition) is necessary and sufficient for convergence, and under both the global error inherits the consistency order $p$. The Dahlquist first barrier capping the order of a zero-stable $r$-step method at $r+1$ ($r$ odd) or $r+2$ ($r$ even) is stated.
Hairer, E., Nørsett, S. P. & Wanner, G. — Solving Ordinary Differential Equations I: Nonstiff Problems · Springer, 2nd revised edition 1993. §III.3 packages the $r$-step recurrence as a one-step recurrence on $\mathbb{R}^{rd}$ through the companion matrix of $\rho$, proves that uniform power-boundedness of that matrix is the root condition, and derives the stability/convergence theorem $\max_n\|y(t_n)-u^n\|\le C(\|\text{starting errors}\|+\max_m\|\tau^m\|)$ via a discrete variation-of-constants formula. §III.4 gives the first Dahlquist barrier: a zero-stable $r$-step method has order at most $r+2$ ($r$ even) or $r+1$ ($r$ odd), with the bound proved through the analytic properties of $\rho(\zeta)/\log\zeta-\sigma(\zeta)$ and the constraint the root condition imposes on the location of the zeros of $\rho$.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m