Why a small local error may not stay small
A multistep method reuses several previous values. That saves work, but it also gives an error several possible patterns in which to evolve. A good approximation of one step is therefore only half the story: we must also know whether those patterns remain bounded when the number of steps grows as on a fixed time interval.
Consider the constant-coefficient -step formula
with characteristic polynomial . Starting values are required for . We assume all coefficients are fixed as varies. For an implicit formula we additionally assume the step equation has been solved on the relevant branch; local existence and uniqueness for sufficiently small follow, for example, from a uniform Lipschitz bound on .
Definition 8.5.1
(Root condition and zero-stability)
The polynomial satisfies the root condition if every root has modulus at most one and every root on the unit circle is simple. A method whose satisfies it is zero-stable. Roots strictly inside the unit disk give the decaying parasitic modes of the method.
Theorem 8.5.2
(Boundedness of the homogeneous recurrence)
The homogeneous recurrence has all solutions uniformly bounded in in terms of their initial values if and only if satisfies the root condition.
Proof
(Basis solutions and bounded powers)
A nonzero root of multiplicity contributes the independent solutions ; the statement follows from the standard constant-coefficient recurrence decomposition, or equivalently the Jordan form of its companion matrix. If , every polynomial times is bounded. If , boundedness requires . A root with produces an exponentially growing solution. At a zero root, the corresponding Jordan block is nilpotent, so its contribution vanishes after finitely many powers. Conversely, with the stated roots every basis solution is bounded. The solution space has dimension , and its coefficients depend linearly on the initial values; thus for a constant independent of .
This theorem tests perturbations when , not absolute stability for a fixed nonzero value of . A simple extra unit root is allowed by zero-stability but may leave an alternating or oscillating component that does not decay.
How the root condition controls accumulated defects
Theorem 8.5.3
(Global error bound for zero-stable methods)
Suppose is globally Lipschitz in its second argument on and satisfies the root condition. Let be the vector of successive errors and the unscaled residual of the exact solution in the method. For sufficiently small, depending on the method and the Lipschitz constant,
The constant may depend on the method, the Lipschitz constant and , but not on . In particular, if the unscaled residual is per step and every starting error is , the global error is on .
Proof
(Unrolling the error recurrence)
Subtracting the two formulas gives
where is the companion matrix of , for a constant independent of , and contains the unscaled residual inserted by the comparison sequence. Choose an induced matrix norm in which the root condition gives . Unrolling the recurrence and writing and , we obtain
The sum contains itself because of the implicit term. For it is absorbed to the left, so . The discrete Grönwall inequality gives for , which is (1) with . With the stated orders, the sum has terms of size , so it is .
Proof X-ray
Four hypotheses, four roles
Each hypothesis does one job in the unrolled recurrence. The root condition is used only through the single constant bounding all powers ; this is what prevents the residuals from being amplified when they are repeated. The Lipschitz condition turns the new error into a term proportional to the errors already present, and the smallness of is what allows the implicit part to be absorbed. The Grönwall step then costs the factor , independent of . The one non-obvious move is that the residuals are summed with weight and no factor : there are of them, and this count is what turns a per-step order into a global order . Without the root condition grows with and no constant exists.
Consistency supplies the small residual; zero-stability prevents its repeated amplification. Neither property alone implies the conclusion. It also explains why a high-order starter matters.
Common mistake
(Truncation error is not the unscaled residual)
Some books divide the residual by and call that quantity the local truncation error. With that convention order means a defect , while the actual forcing in the recurrence is times that defect. Estimate (1) uses the unscaled residual ; inserting the scaled defect in its place loses a factor and understates the accuracy.
Two formulas with very different error memories
Worked example 8.5.4
(Two-step Adams–Bashforth: a zero root)
For the two-step Adams–Bashforth formula
. Its roots are and , so the method is zero-stable. When , the recurrence copies forward; a difference in the older starting value disappears after one step. With a second-order starter and sufficient solution smoothness, the method has second-order global accuracy on a fixed interval.
Worked example 8.5.5
(Leapfrog: an alternating unit root)
For the leapfrog formula , . The two simple roots satisfy the root condition. However, for an initial mismatch in the two interleaved sequences persists: , . Zero-stability permits the alternating component; it does not promise that every perturbation decays.
Worked example 8.5.6
(Two-step backward differentiation formula: a decaying parasitic mode)
The formula has , so the roots are and and the root condition holds. Take , and . The general solution is ; the starting values give and , so and . The parasitic part decays, and the perturbation settles at : it is amplified by the bounded factor but does not grow with .
Counterexample mode
Consistency cannot rescue a double unit root
Consider
It is consistent: , , and , . Nevertheless, with , and the numerical sequence is . Both starting values approach the exact solution as , yet at the error approaches . The double root creates a linearly growing mode and the method is not zero-stable.
Zero-stability is not absolute stability
For the scalar test equation , the amplification factors solve
where . Using the root-condition convention, absolute stability at a given asks for the root condition of this new polynomial, with its degree intact. A stricter convention requires all roots to have modulus strictly less than one. Zero-stability checks the special limiting recurrence ; at , consistency gives the root , representing the exact constant solution, and zero-stability additionally requires this root to be simple.
Common mistake
(Zero-stability does not give stability at a chosen step)
A zero-stable method can still be unstable at a particular . Explicit Euler is zero-stable, since , but its amplification factor equals at , so the numerical solution of grows although the exact solution decays.
Practice with solutions
Quick check
(Decide whether satisfies the root condition. What happens to its parasitic mode?)
List the roots and their moduli.
Solution · Answer
Yes; both roots lie in the closed unit disk and the unit root is simple. The mode decays.
Quick check
(Decide the same for .)
Look at the multiplicity of each root on the unit circle.
Solution · Answer
No: is a repeated unit root and is unbounded.
Quick check
(A zero-stable order-three method has unscaled residual , but its starting errors are only . What does (1) guarantee?)
Add the two contributions on the right of (1).
Solution · Answer
The bound gives ; the starter limits the guaranteed order.
Quick check
(For leapfrog with , find the solution when and . Why is it bounded but not necessarily convergent to the constant solution as time advances at fixed ?)
Use .
Solution · Answer
Even terms equal and odd terms equal . The discrepancy stays bounded but does not decay unless .