Why compare two meshes?
A second-order method halves its typical error by about a factor of four when the mesh width is halved. If the leading error on both meshes has the same coefficient, we can do better than simply choose the finer answer: a suitable weighted average cancels that coefficient. This is Richardson extrapolation. Its usefulness rests on a statement stronger than an error bound. A bound says the error is no bigger than a multiple of ; an expansion identifies the same leading term on the two meshes.
We prove such an expansion for a concrete boundary-value problem. The result concerns values at shared nodes, with exact data and exact algebraic solves.
The grid problem and the cancellation
Definition 3.3.1
(Nested grid solutions and the Richardson extrapolant)
Let solve on , with and . For , , write and let solve
The refined grid has width ; is its node . Define
Suppose for a moment that uniformly in , where the same function applies at every mesh width. The fine-grid error is , so . Division by three leaves a fourth-order approximation. Negative weight matters: this is an extrapolation, not a convex average.
Theorem 3.3.2
(Uniform expansion and extrapolation)
Assume and the grid equations and boundary values are solved exactly. Let be the solution of with . There is a constant , independent of and , such that
The constant may differ between the two inequalities. This is a statement at the coarse nodes, not an assertion about interpolation between them.
Proof: from local defect to global expansion
Let denote the centered second difference. The proof rests on one stability fact for the zero-boundary grid problem.
Lemma 3.3.3
(Maximum-norm bound for the zero-boundary grid problem)
Let satisfy and for . If for every interior , then
Proof
(Comparison with a quadratic barrier)
Set . The centered difference is exact on quadratics, so at every interior node and . The vector satisfies with zero ends. If had a positive maximum, it would be attained at an interior node , and means , so both neighbors attain the same maximum. Propagating reaches an endpoint, where , a contradiction. Hence . The same argument applied to gives . Finally .
Proof
(From local defect to global expansion)
Taylor's theorem, with bounded sixth derivative, gives uniformly at interior nodes
The sign is easiest to check from the equation: for ,
The solution has four continuous derivatives because and . Thus uniformly. With , the two leading terms cancel and
The lemma turns this residual into , uniformly in , which is the first inequality. Applying it on the grid of width at the node gives , and then , which is the second. The boundary data are essential: they ensure both and the correction vanish at the endpoints.
Proof X-ray
Why one function serves every mesh
The cancellation in needs more than an error of size : it needs the same coefficient on both grids. The proof produces that coefficient by a continuous problem, with zero ends, which mentions no mesh at all. This is the key move. The local defect is matched by a global correction instead of being bounded crudely.
Two hypotheses are used at definite points. The sixth derivative of makes the defect expansion valid to ; it also gives , which is needed so that applied to is itself accurate to . The Dirichlet data give , which the lemma requires. The argument closes because the lemma converts an residual into an error with a constant independent of . Nested grids enter only at the end, when the same expansion is read at the shared node of the fine grid.
Worked examples
Worked example 3.3.4
(A sine forcing on two nested meshes)
Take , so and both boundary values vanish. The sampled sine is a discrete eigenvector:
Uniqueness therefore gives with . At , the coarse and fine values for and are and . Hence , compared with the exact value . The fine solution alone is approximately . Extrapolation has canceled much of its leading error, though the remaining error is not zero.
Worked example 3.3.5
(A quartic solution where the expansion is exact)
Let , , , so . Here and , so the Taylor expansion of the defect terminates: exactly. The correction solves with zero ends, so . The error satisfies with , and the sampled quadratic satisfies the same equations exactly. By uniqueness,
At this gives and ; solving the three fine-grid equations directly gives , in agreement. Then . The remainder term is zero here, so extrapolation is exact, while each grid alone carries the full error.
Worked example 3.3.6
(An error indicator and what it estimates)
If the expansion holds, then at a common node
Thus adding this signed correction to the fine solution produces , and its magnitude estimates the fine-grid error to leading order. It is not a rigorous upper bound: if the leading coefficient is small, the remainder may dominate. With three grids one can compare successive differences; ratios near four support, but do not prove, that the term is dominant.
When cancellation is not justified
Counterexample mode
An order-two bound does not justify extrapolation
The tempting claim is that any method whose error is becomes fourth order after Richardson extrapolation. Consider the abstract error sequence on the dyadic widths . It satisfies , an bound, but its coefficient changes with . Substitution gives
Each interval on which has length , so infinitely many give . For those the extrapolated error is at least , still second order. The repair is the hypothesis proved in the theorem: an expansion with a mesh-independent . The sequence is abstract; it is not claimed to arise from the smooth Dirichlet problem above.
Boundary approximations, nonsmooth solutions and unaligned meshes can spoil the common expansion. Solver and data errors matter too: if each grid solution has a perturbation bounded by , its extrapolated effect can be as large as . Refining until truncation error is below solver or rounding errors may make the observed ratio misleading. If the target is a non-grid point, interpolation error must be analyzed separately.
Common mistake
(Using the weights and for a method of another order)
The weights and cancel an term only. If the leading error is , the same combination leaves , still first order. For leading order on a halved mesh, the canceling combination is , and it is valid only when an expansion of that order has been established.
Common mistake
(Reading the correction as a certified error bound)
The difference estimates the fine-grid error only to leading order. If is small or zero at the node, the remainder dominates, and the indicator can underestimate the actual error or carry the wrong sign. It is an estimate, not a bound.
Practice with solutions
Quick check
(For , find and .)
Check whether the centered difference is exact on this solution.
Solution · Answer
Here , and the centered second difference differentiates a quadratic exactly. The sampled satisfies the grid equations and boundary conditions; uniqueness gives on both grids. Consequently exactly. The leading coefficient vanishes, so a ratio of successive errors is undefined, not four.
Quick check
(Suppose at a shared node and the analogous expansion holds at width . Compute .)
Replace by term by term before combining.
Solution · Answer
Substitution yields and therefore . The fourth-order coefficient is not simply the coefficient in the original fine-grid error.
Quick check
(A computed fine-grid value is and the coarse-grid value at the same node is . Find the extrapolated value and the signed estimate of the fine-grid error, assuming the expansion applies.)
Use the definition of and the error indicator.
Solution · Answer
The extrapolated value is . The correction is , an estimate of exact value minus fine value. It is not a certified error bound.
Quick check
(A coarse solution has algebraic error and the fine solution has algebraic error at a shared node. What error does extrapolation introduce from these solves?)
The extrapolant is linear in the two grid values.
Solution · Answer
Linearity gives . This reaches the worst-case magnitude bound for two errors bounded by and illustrates why linear-solver tolerances must be chosen alongside mesh widths.