Motivation
A Runge–Kutta step evaluates several slopes inside one interval. A multistep method instead reuses values or slopes from earlier intervals. Once its history is available, an explicit method can advance with only one new function evaluation. This economy introduces a new mathematical issue: the algorithm has several independent modes, including modes that do not correspond to the differential equation. Their behavior as the step tends to zero is governed by a polynomial built from the method's left side.
It is therefore possible to write a formula whose exact-start defect tends rapidly to zero, yet whose repeated computation magnifies arbitrarily small errors. Consistency measures how well exact samples satisfy one formula. Zero stability measures the propagation mechanism remaining when the step size tends to zero. Both are needed for convergence over a fixed interval. Absolute stability, by contrast, tests the combined formula at a particular nonzero product .
We study constant-step, constant-coefficient methods. Variable-step formulas have changing coefficients and need their own stability analysis; the fixed polynomial proved here does not settle that problem.
Definitions
A -step linear multistep method is
The coefficients are fixed as . Define and . Multiplying both coefficient lists by the same nonzero constant changes neither method nor roots. If , the new value is explicit; otherwise an algebraic equation must be solved. A sufficient condition for a unique new value for globally -Lipschitz is , by contraction after rearranging.
For a smooth test curve , define its unscaled residual
The method has order if uniformly for sufficiently smooth curves. Consistency means at least order one. We use zero stability to mean a bound, uniform in the number of steps with , for the homogeneous difference equation in terms of its starting values. For fixed coefficients this is equivalent to the root condition: every root of lies in , and every root on the unit circle is simple.
Starting values are part of a multistep algorithm. To obtain global order , require . Merely listing a recurrence without specifying how its history is supplied leaves a practical solver incomplete.
Theorem/proposition
Theorem 4.1.1
(Consistency and the root condition)
A fixed-coefficient method is consistent exactly when
It is zero stable exactly when its characteristic polynomial satisfies the root condition. In that case there is a constant , independent of , such that the forced recurrence obeys
The roots need not all be strictly inside the disk: consistency requires the root .
Theorem 4.1.2
(Convergence with a quantified local residual)
Suppose the fixed method is zero stable and has uniform residual along an exact solution on . Suppose is uniformly state-Lipschitz with constant on a region containing the exact and numerical values, the implicit new values exist, and starting errors are . For sufficiently small constant , the global error on that interval is . For general convergent starting data, consistency and zero stability imply convergence. These are finite-time statements; they do not assert stable behavior for an arbitrarily large fixed step.
Concept lensAlgebraic
All order conditions in one exponential identity
Apply the residual to with : . The coefficient of in this expansion is , so the method has order exactly when . For AB2, and ; the difference recovers the residual constant.
Proof sketch or proof idea
Proof
(Taylor moments and bounded companion powers)
Taylor-expand about . The coefficient of in the residual is , and the coefficient of is . Both must vanish for a first-order residual. Conversely, if they vanish, Taylor's theorem gives for curves with bounded second derivative. Higher-order conditions are
together with . They provide a direct way to check an asserted order.
For the root condition, store consecutive errors as a vector . The homogeneous recurrence becomes , where is a companion matrix and its eigenvalues are the roots of . A Jordan block of size contributes terms proportional to , . If , these are bounded even for repeated roots, because geometric decay dominates a fixed polynomial. A unit-modulus root gives bounded powers exactly when its block has size one. A companion matrix has one Jordan block per distinct root, so simplicity is exactly the required condition there. Roots outside the disk produce unbounded geometric growth. This proves necessity and sufficiency for bounded powers of .
With forcing, iteration gives , where the fixed vector includes the factor . Taking norms and using bounded powers proves the forced estimate. It is the sum of residual magnitudes, rather than their maximum alone, that matters.
Proof
(Discrete Gronwall argument for convergence)
For the nonlinear error, subtract the exact and numerical formulas. Its forcing is a sum of times differences of , minus the residual. The forced estimate therefore yields, with constants independent of the mesh,
Each error occurs in at most a fixed number of stencil positions; their coefficient sum is absorbed into . Choose so and absorb the current term. The resulting inequality implies by induction and a geometric sum. This proves the convergence rate. With only consistency, replace in the preceding estimate by . This tends to zero for convergent starting data because consistency makes the accumulated residual tend to zero.
Proof X-ray
Why one order is lost when local defects accumulate
There are about residuals, each of size . The root condition bounds their response coefficients; it does not make the residuals cancel. Their absolute sum is therefore of size . This reasoning fails if the response coefficients themselves grow with the step number. The Lipschitz hypothesis enters only to turn differences of into multiples of times earlier errors, and the step restriction is what allows the current, possibly implicit, error to be moved to the left side. The discrete Gronwall step then converts a sum over at most steps into the mesh-independent factor . Consistency controls the inputs to the recurrence; zero stability controls its memory.
Zero stability is also necessary for convergence understood uniformly over all converging starting perturbations. For , a root outside the unit disk amplifies a vanishing initial perturbation geometrically. A repeated unit root produces a polynomial factor in ; choose a starting perturbation tending to zero slowly enough that its amplified value stays nonzero. Thus a statement about arbitrary convergent starts cannot discard the root condition. This necessity observation does not claim that every special exact initialization excites every parasitic mode.
Worked examples
Worked example 4.1.3
(AB2 from integrating an interpolated slope)
On , interpolate the known slopes at by a line. With , it is . Integrating from to gives
This is second-order Adams–Bashforth, AB2. Its polynomials are and . The roots satisfy the root condition. In this displayed stencil, is the middle node and the residual is under the earlier indexing; the middle node of would be . Taylor expansion gives residual , so the method has order two under the relevant smoothness bounds.
For , , take exact starts , . Then , compared with . One Euler step is also a valid second-order-accurate starter here: its error at is . A single starter's error requirement differs from the global order of the starter method over a whole fixed interval.
Worked example 4.1.4
(AM2 averages endpoint slopes implicitly)
Integrating the linear interpolant of slopes at gives
We call this AM2 to specify its order two: it is the one-step implicit trapezoidal Adams–Moulton formula. Naming conventions sometimes count steps instead of order, so the equation must accompany the label. Its residual is , and is zero stable.
On the factor is . At it is . The value alternates and loses magnitude only slowly, while the exact factor is negligible. A-stability prevents explosive scalar growth here but does not guarantee strong damping of unresolved fast decay. No part of the zero-stability proof predicts this large-step behavior.
Worked example 4.1.5
(BDF2 differentiates an interpolating polynomial)
Differentiate the quadratic through the three most recent values at the newest time. Its derivative is , giving
Thus BDF2 has roots and is zero stable. Expansion about the newest time gives residual , establishing order two. For , , and exact , its next value is , compared with .
BDF2 is also A-stable. If an amplification root had , put , so . Its test-equation relation would be , whose real part satisfies
Equality on the closed disk forces , hence . Thus every root is strictly inside the unit disk for and for nonzero purely imaginary ; at the roots satisfy the root condition. This proves the scalar multistep A-stability statement, including its boundary qualification.
A predictor is not an exact implicit solve
An explicit prediction can supply a convenient initial guess for an implicit step. For example, predict with AB2, then correct using the trapezoidal equation. Repeating the corrector amounts to fixed-point iteration . If , successive guesses contract, and the iteration converges to the uniquely defined trapezoidal value. Stopping after one correction produces a different explicit algorithm. It may retain a desired asymptotic order if the initial prediction is accurate enough, but it does not automatically inherit trapezoidal A-stability. Algebraic accuracy and discretization accuracy must be budgeted separately.
The forced-recurrence estimate provides that budget. If an inexact solve adds an unscaled equation residual , its total contribution is bounded by a constant times the sum of those residuals, with the nonlinear propagation factor included. To preserve a global order-two estimate on a fixed interval, a sufficient uniform residual target is per step. A fixed absolute solve tolerance independent of need not preserve a convergence rate under unlimited refinement. This statement concerns the equation's residual normalization; multiplying the equation by a constant or by the step changes the numerical tolerance representing the same residual.
The extra root of BDF2 explains a different phenomenon. On the zero differential equation a perturbation splits into a constant mode and a rapidly shrinking parasitic mode. The latter decays by each step, whereas the constant part persists. Thus zero stability does not promise that every starting error disappears; it promises bounded propagation. Improving the starting data improves the component that can remain throughout the interval. On variable meshes the corresponding propagation matrices change from step to step, so bounded powers of one companion matrix can no longer be used without an additional argument.
A residual estimate must also specify its starting index. A two-step formula does not apply before two history values exist. Counting a missing first recurrence as though it had zero residual silently inserts an undefined state. In a convergence proof, separate the finite starting block from the subsequent sum of actual recurrence defects; the forced estimate above is designed precisely for this separation. This also explains why the starting algorithm may differ from the recurrence, provided the values it supplies meet the required error bound.
Floating-point perturbations, on the other hand, need not shrink with the same power of as the truncation residual. If each step adds a perturbation of roughly fixed size, a crude worst-case sum can grow with the number of steps. Zero stability keeps the response coefficients bounded, but it does not remove errors that keep being added. When a refinement experiment eventually stops improving, check function evaluations, algebraic tolerances and floating-point scale, rather than interpreting every plateau as a failure of the theoretical order. This section does not assume independent random rounding, so it does not replace the deterministic sum by a square-root-of-steps count.
Common mistakes
Consistency and zero stability are independent requirements, and each fails without the other.
Counterexample mode
A consistent formula that does not converge
Claim: a consistent multistep formula with small local residual converges. The formula has and , so and : it passes the first-order consistency identities. Its double root violates the root condition. For , the starts , both approach the exact zero solution, yet the recurrence gives , so at the fixed time the computed value is while the exact value is . A small local residual cannot repair this memory instability; the root condition is the missing hypothesis.
Common mistake
(Taking zero stability for consistency)
Zero stability alone does not imply consistency: is zero stable but cannot approximate , since . Order conditions and root conditions answer independent questions.
Common mistake
(Confusing the roots of with those of )
Zero stability concerns the roots of alone. Absolute stability at a nonzero concerns the roots of . A zero-stable method such as AB2 can still have a root outside the unit disk at a large negative .
Common mistake
(Reusing fixed-step coefficients after a step change)
Using the same fixed-step coefficients after arbitrary step changes is a different algorithm; neither the interpolation derivations nor the theorem above justify it.
Summary
Multistep methods reuse history but introduce additional recurrence modes. Taylor moments determine consistency and order; the root condition determines bounded response to starts and forcing. Together with Lipschitz propagation and suitable starting values, they yield finite-time convergence. AB2, trapezoidal AM2 and BDF2 are all order two and zero stable, while their behavior for a particular stiff step can differ substantially.
Exercises
Quick check
(Derive the AB2 coefficient in its cubic residual by Taylor expansion about .)
Expand the previous slope as well as the new exact value.
Solution · Answer
The exact increment is . The integrated extrapolated slope is . Subtracting gives , with all derivatives at .
Quick check
(For , check zero stability and consistency.)
A favorable root polynomial does not settle the Taylor moments.
Solution · Answer
The root polynomial is , so it satisfies the root condition. But whereas . The method is inconsistent. For a nonzero constant derivative it advances at the wrong leading speed. Replacing the right side by repairs first-order consistency, although higher order would still require additional moment checks.
Quick check
(BDF2 is started with and one backward Euler step for . Show that the starting error is and compute when .)
The starter uses only one step, rather than a fixed time interval.
Solution · Answer
Backward Euler gives , while . Their difference is , meeting the order-two starting requirement. At , and . The starter changes the numerical value from the exact-start example, while preserving the asymptotic rate under the theorem's assumptions.
Quick check
(A root-condition-stable recurrence has residuals bounded by on and starting errors bounded by . What rate does the forced estimate guarantee before nonlinear propagation?)
Compare the accumulated residual with the starting contribution.
Solution · Answer
There are at most residuals, so their sum is at most . The total bound is . A third-order local-residual contribution does not remove the larger starting error. Nonlinear Lipschitz propagation multiplies this estimate by a mesh-independent finite-time factor and therefore retains the second-order guarantee.