Romberg Nested Extrapolation

Worked Example

Let's consider integrating f(x) = x^4 from 0 to 1. The exact integral is 0.2. We compute the Romberg table up to refinement level 2.

1. For j=0 (1 panel, step size h=1):
   R_(0,0) = 1/2(f(0) + f(1)) = 1/2(0 + 1) = 0.5
2. For j=1 (2 panels, step size h=0.5):
   R_(1,0) = 1/2R_(0,0) + 0.5 f(0.5) = 0.25 + 0.5(0.0625) = 0.28125
3. For j=2 (4 panels, step size h=0.25):
   R_(2,0) = 1/2R_(1,0) + 0.25 (f(0.25) + f(0.75)) = 0.140625 + 0.25(0.00390625 + 0.31640625) = 0.220703125
4. Extrapolate k=1 (Simpson's rule equivalence):
   R_(1,1) = (4^1 R_(1,0) - R_(0,0))/(4^1 - 1) = (4(0.28125) - 0.5)/3 = (1.125 - 0.5)/3 = 0.208333...
   R_(2,1) = (4^1 R_(2,0) - R_(1,0))/(4^1 - 1) = (4(0.220703125) - 0.28125)/3 = (0.8828125 - 0.28125)/3 = 0.2005208333...
5. Extrapolate k=2 (Boole's rule equivalence):
   R_(2,2) = (4² R_(2,1) - R_(1,1))/(4² - 1) = (16(0.2005208333) - 0.208333...)/15 = (3.208333... - 0.208333...)/15 = 3.0/15 = 0.2

The value R_(2,2) precisely matches the exact integral 0.2, which is expected since x^4 is a polynomial of degree 4, and R_(j,2) integrates polynomials up to degree 5 exactly.

Experiment

You can reproduce this behavior in the interactive module.

1. Set the Function to Quartic.
2. Set the Refinement level to 2.
3. Set the Column to 2.
4. Observe that the Romberg value is exactly 0.2, while the raw trapezoid value is 0.220703125.
5. Change the Function to Sine and note how increasing the column progressively improves the Romberg value towards the exact integral.

Limitations

Romberg extrapolation is based on the Euler-Maclaurin formula, which requires the integrand to be sufficiently smooth. If the function has singularities, discontinuous derivatives, or is highly oscillatory, the formal error order O(h^(2k+2)) may not accurately describe the convergence, and extrapolation can even magnify errors. Furthermore, for very large refinement levels, catastrophic cancellation and floating-point roundoff can ruin the extrapolated values.

References

To read more about the mathematical derivation of Richardson extrapolation and its application to integration via the Romberg method, see thislecture notewhich covers the construction of the Romberg table and the corresponding error terms.