Make each new sample count
Suppose a function is expensive to evaluate and we want to approximate , where . For equal panels of width , write
Halving the panel width does not require reevaluating all the old nodes. The new points lie halfway between adjacent old nodes, so in exact arithmetic
To check the coefficients, old interior values have weight in and old endpoints have weight ; each new midpoint has weight . These are exactly the coefficients on the right. Store the old values if evaluation cost matters. Rounding in the accumulated sum, in node construction, and in the function values is separate from the exact identities below.
A table that removes successive powers
Definition 6.5.1
(Romberg table)
Start with and set for . Once column is available on two successive grids, define
The triangular array of the numbers , , is the Romberg table.
The denominator changes with the column: using in every column would not perform the same cancellation. The first column compares steps and and removes an term; the second compares estimates whose leading remaining term is proportional to , and so on.
Theorem 6.5.2
(Extrapolation under a stated expansion)
Let . Fix an integer and suppose, as ,
with constants independent of . Then, for each fixed ,
This is a statement about a fixed column and sufficiently fine grids. It is not an error certificate for an individual table entry.
Proof of cancellation
Proof
(Induction on the column index)
The base column has the assumed expansion. Suppose column has an expansion through whose first possible nonzero term is , with coefficients independent of and remainder . The coarser entry uses , so its corresponding term is . Multiplying the fine entry by and subtracting the coarse entry cancels this term. The denominator is nonzero. Remaining even powers retain grid-independent coefficients, and the remainder stays of order because is fixed. Induction proves the result.
Proof X-ray
An expansion is more than a single error bound
The single move in the proof is the cancellation of between two grids. It works only because the coefficient is the same number on both grids; that is where the hypothesis that the constants are independent of is spent. A bound alone does not say that the signed errors on successive grids share the same leading coefficient. The table cancels a common term in an expansion; it does not cancel an arbitrary error merely because that error is bounded by a multiple of .
Two smaller points close the induction. A term with becomes , again with a coefficient independent of , so the new column has an expansion of the same form. The remainder is multiplied by at most , a constant only because is fixed; the theorem says nothing uniform about going down the diagonal .
For sufficiently smooth functions the Euler–Maclaurin formula supplies such even-power expansions. For instance, if , it gives
Thus the theorem applies with . The displayed coefficients are consequences of that formula, not a bound inferred from the table alone. If a derivative difference vanishes, a leading coefficient may be zero, making convergence faster in that particular case. Piecewise smoothness, endpoint singularities, or oscillations missed by the sample grid require separate analysis; increasing the table depth alone does not verify the expansion.
The recurrence has a second, equivalent reading that explains the weights.
Concept lensAlgebraic
Romberg as polynomial extrapolation to zero step
Put and , so . Let be the polynomial of degree at most in that takes the value at for . Neville's recurrence for interpolating polynomials, evaluated at , reads
This is exactly the Romberg recurrence, so : each entry fits a polynomial in through computed trapezoid values and reads off its value at the unattainable step . The expansion hypothesis is the statement that , viewed as a function of , is well approximated by such polynomials.
The first extrapolated column also has a familiar name.
Proposition 6.5.3
(The first column is composite Simpson)
For every , equals the composite Simpson rule on the panels of width , where . In particular is composite Simpson with panels.
Proof
(Comparing weights node by node)
Index the fine nodes by , , and write . In each endpoint has weight and every other fine node has weight . In the endpoints have weight , even interior nodes have weight , and odd nodes do not appear. Subtracting, endpoints get , odd nodes and even interior nodes . Dividing by gives
which is composite Simpson with step .
Worked table for a quartic
Worked example 6.5.4
(Exact table for )
Take on , so . The trapezoid values are , and . For instance, the refinement identity gives
The first extrapolated column is composite Simpson on the fine grid, by the proposition above. Here we place the values in the full table:
| 0 | — | — | |
| 1 | — | ||
| 2 |
For example, , and . The equality with the integral is special to this polynomial and the exact arithmetic used here. In general, additional terms remain after any finite number of cancellations.
Further worked examples
Worked example 6.5.5
(Observed rates for )
On take , with . Exactly,
Then , and . To six decimals:
| error | error | error | ||||
|---|---|---|---|---|---|---|
| 0 | — | — | — | — | ||
| 1 | — | — | ||||
| 2 |
The trapezoid errors shrink by factors and , approaching the factor of an term. The first column improves by a factor of about in one halving, on its way to the factor of an term. Here is smooth on and , so the leading coefficient really is present and the theorem describes the trend; it still does not bound any single entry.
Worked example 6.5.6
(Edge case: a periodic integrand and a coarse first grid)
Take on , so . All derivatives of agree at and , so every Euler–Maclaurin coefficient vanishes. The samples give (both endpoints have value ), while and are exact. Extrapolation then gives
The entries that reach back to are worse than the finest trapezoid value they use, which is already exact. The single panel is too coarse to resolve one period: its error is aliasing, not the leading term of an expansion. This is consistent with the theorem, which is asymptotic in , and shows why entries built from pre-asymptotic grids can mislead.
Agreement is not a proof of accuracy
Counterexample mode
Every sampled value can miss the integral
Let on . It is continuous, nonnegative, and positive between its finitely many zeros, so its integral is positive. Yet every sample on the first three grids, with one, two and four panels, is zero. The entire displayed triangular table is zero, and adjacent entries agree exactly. The table alone cannot distinguish this function from the zero function. It therefore cannot certify an error tolerance without additional information such as a justified derivative bound.
The difference between successive entries can be useful as a practical indicator when an error expansion is justified and its leading term dominates. Near cancellation, pre-asymptotic grids, evaluation error or rounding can make it misleading. A robust implementation also detects repeated floating-point nodes, nonfinite values and resource limits; a stopping rule should report an estimate as an estimate unless a separate error bound has been established.
Common mistake
(Using the factor in every column)
The weight is right only for column . Applying to the quartic table gives , still in error by about , whereas the correct gives . In column the term being removed is proportional to , and doubling multiplies it by .
Common mistake
(Extrapolating across an endpoint singularity)
For on the derivative is unbounded at and the trapezoid error is not an even-power expansion: it contains a term proportional to . Numerically, successive trapezoid errors shrink by factors close to , and so do the first-column errors , , , instead of the factor the table is designed for. Remove the singularity first, for example with , before using Romberg weights.
Practice with solutions
Quick check
(With on , write the new points needed for .)
New points lie halfway between adjacent old nodes.
Solution · Answer
The old nodes are ; the new midpoints are . Thus .
Quick check
(Suppose , , and . Compute , , and .)
Use denominator in column and in column .
Solution · Answer
They are , , and . This agreement does not by itself prove that .
Quick check
(If the first unremoved error term in column is , why is the factor ?)
Compare the term on the grids with steps and .
Solution · Answer
Doubling multiplies that term by . Multiplication of the fine estimate by the same factor makes its leading term equal to the coarse one, so subtraction removes it.
Quick check
(Does alone prove ?)
Try errors whose sign alternates with .
Solution · Answer
No. For a sequence with errors , the bound holds, but the fine and coarse signed coefficients differ: . The extrapolated error remains a nonzero multiple of . An even-power expansion with common coefficients supplies the missing hypothesis.