Removing a predictable error
A numerical approximation can be inaccurate in a structured way. If a quantity has approximations
where and the same constant applies to both step sizes, then has leading error . A suitable linear combination of and removes it.
Definition 7.11.1
(Richardson extrapolation)
Given approximations of whose leading error is with the same at every step size, the extrapolated value is
The weights and sum to one, which retains , and the weighted leading errors sum to zero. The calculation depends on an actual asymptotic expansion, not just on two approximations being close.
Theorem 7.11.2
(Cancellation of the leading error)
Suppose with and for . Then for ,
Proof
(Substituting the expansion into the combination)
Since , the expansion applies at both step sizes:
The bracket is . Dividing by gives , and
Proof X-ray
Cancellation needs a shared coefficient
The only step that uses the structure of the error is the vanishing bracket, and it vanishes because the same multiplies at and at . Everything else is the triangle inequality. Suppose instead we knew only . The same computation then gives , which is no better in order than the bound we started with: unrelated errors at the two step sizes need not cancel. The weights summing to one are used once, to keep in the combination with coefficient .
Worked example 7.11.3
(Extrapolating a central difference)
For sufficiently smooth ,
so and . Take at . Then , in agreement with and . For and we get and , so
The result is exact here because the expansion of a cubic stops after the term; for a general only the term is removed and an error remains.
These conclusions describe truncation error in exact arithmetic. Subtracting nearby values and combining approximations may amplify floating-point errors, so endlessly halving need not improve the computed answer.
A table for the trapezoidal rule
Let be the composite trapezoidal approximation of on a uniform grid of spacing . For a sufficiently smooth fixed , the Euler–Maclaurin expansion has even powers:
The amount of smoothness required increases with the number of terms used; this expansion is a hypothesis here, not a consequence of continuity alone. With , the repeated halving of the step suggests applying extrapolation column by column.
Definition 7.11.4
(Romberg table)
Put for and, for ,
The triangular array of the numbers is the Romberg table; column is the -th extrapolation of the trapezoidal values.
Why does the factor change with the column? The factor is with , the order of the term being removed in column . The next result makes this precise.
Theorem 7.11.5
(Accuracy of the Romberg columns)
Assume the expansion of above holds for every , with coefficients that do not depend on and a remainder bounded by . Then for and ,
with and . In particular .
Proof
(Induction on the column)
For this is the hypothesis, with . Assume it for column , where . Because , we have , and the coefficients are the same in and . In the coefficient of is therefore , and appears with total weight . Dividing by gives the displayed coefficients. For the factor is zero, so the sum starts at . The remainders satisfy
which is again a constant times . If the first surviving term is of order ; for the sum is empty and the error is .
The first extrapolation is Simpson's rule on a single pair of panels:
Worked example 7.11.6
(One extrapolation for a quadratic)
Integrate on . The one-panel trapezoid is , and two panels give . Extrapolation gives
which equals the exact integral. This happens because the trapezoidal error for this quadratic is exactly proportional to (here ); one example does not make the first extrapolation exact for every integrand.
Worked example 7.11.7
(A three-row Romberg table for )
Integrate on , where . The trapezoidal values are , and, from ,
Column 1 uses the factor :
Column 2 uses the factor :
| 0 | 1 | 1/2 | ||
| 1 | 1/2 | 9/32 | 5/24 | |
| 2 | 1/4 | 113/512 | 77/384 | 1/5 |
The entries and are Simpson's rule with two and four panels. The last entry is exact because the Euler–Maclaurin series of a polynomial terminates: here , which has only the two terms that column 2 removes. For a non-polynomial integrand the entry would still carry an error.
When a grid misses the structure
Counterexample mode
A zero difference can hide a nonzero error
On , take . Its values at , and are all zero, so both approximations and their extrapolation are zero; the true integral is . Two equal approximations alone therefore provide no universal error bound. The next grid resolves this particular oscillation: . The integrand is smooth; the first two grids are simply too coarse to reveal its structure.
A stopping criterion based on successive table entries is an indicator unless additional assumptions bound the remainder. Sharp peaks, unresolved oscillations, and endpoint singularities may invalidate the assumed expansion or hide structure between nodes. Even when the expansion applies, rounding eventually competes with truncation. Inspect the integrand and the stability of the table, and use an error theorem appropriate to the problem before treating an indicator as a guarantee.
Common mistakes
Common mistake
(Using the wrong power in the weights)
If , the correct combination has . Applying the formula instead gives : the error is still of order , with its sign reversed. The weights must match the exponent that actually appears in the error.
Common mistake
(Reusing one factor in every column)
In the table for , the second column needs the factor . Using the column-1 factor again gives , not . The weights then sum to one but do not cancel the term.
Practice and solutions
Quick check
(Suppose exactly. Find .)
Substitute and collect the powers of .
Solution · Answer
Substitution gives : the term cancels, but the fourth-order term remains.
Quick check
(Why do the weights in extrapolation add to one?)
What happens to the target in the combination?
Solution · Answer
This preserves the common target rather than scaling it: appears with coefficient .
Quick check
(Compute the one-panel trapezoid and first Romberg entry for on .)
Both trapezoidal values come from the same straight line.
Solution · Answer
Here and , so . The trapezoidal rule integrates an affine function exactly.
Quick check
(If two table entries agree to machine precision, must the exact integral agree with them?)
Recall the integrand on .
Solution · Answer
No. The function above gives equal zero approximations while its integral is .