Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 ยท Numerical Differentiation and Integration

Richardson Extrapolation and Romberg Integration

Combine two rough estimates into a much better one. Learn Richardson extrapolation for derivatives and the Romberg table for integrals, with code.

Many numerical methods have an error that follows a known pattern: it shrinks like h^p as the step h falls. If you know the pattern, you can run the method twice with different steps and combine the results so that the leading error term cancels. That is Richardson extrapolation, and it is one of the most useful ideas in numerical analysis because it turns cheap low-order methods into high-order ones almost for free.

This lesson applies it to a derivative first, then to the trapezoidal rule, which gives Romberg integration.

The idea

Suppose a method with step h returns A(h) = A + c h^p + higher terms, where A is the true value. Run it with h and h/2:

A(h) = A + c h^p A(h/2) = A + c h^p / 2^p

Eliminate c:

A ~ (2^p A(h/2) - A(h)) / (2^p - 1)

The leading error term is gone, so the new estimate is more accurate: its error starts at the next power of h. If p = 2 (central difference, trapezoid rule) the formula is (4 A(h/2) - A(h)) / 3.

Extrapolating a derivative

The central difference has error c2 h^2 + c4 h^4 + ..., so one extrapolation step removes h^2 and leaves an O(h^4) estimate.

Python One Richardson step on a central difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The extrapolated value is several orders of magnitude better than either input, from four function evaluations in total. (Note it equals the five-point stencil of the previous lesson.)

Repeated extrapolation

You can repeat the trick. Build a table: column 0 holds A(h), A(h/2), A(h/4), ...; each next column removes the next error term using factors 4^k:

R(i, k) = R(i, k-1) + (R(i, k-1) - R(i-1, k-1)) / (4^k - 1)

for the common case where the error has only even powers of h.

The trapezoidal rule and Romberg integration

The composite trapezoidal rule with n panels is T(h) = h * (f(a)/2 + f(a+h) + ... + f(b-h) + f(b)/2) with h = (b - a) / n. Its error expansion (the Euler-Maclaurin formula) contains only even powers: c2 h^2 + c4 h^4 + .... That is exactly the situation where the table works.

Romberg's method:

  1. Compute T with 1, 2, 4, 8, ... panels (reusing earlier evaluations: each doubling only needs the new midpoints).
  2. Fill the Richardson table to get R(i, i), the most accurate estimate of each row.
flowchart LR
  T["Trapezoid T(h), T(h/2), T(h/4)..."] --> R1["Extrapolate: removes h^2"]
  R1 --> R2["Extrapolate: removes h^4"]
  R2 --> R3["Extrapolate: removes h^6"]
Python Romberg integration from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 17 function evaluations the Romberg value is accurate to about machine precision, while the plain trapezoid rule is off in the fifth digit.

Look at the whole table to see convergence: the diagonal entries stabilize rapidly.

Python Print the Romberg table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When extrapolation fails

  • The error must follow a clean power law. Functions with singularities or kinks (sqrt(x) at 0, |x| at 0) break the assumption and Romberg gains little.
  • Noise defeats it: extrapolation amplifies random errors, since the combination weights are larger than 1 (4/3 and -1/3).
  • It is for smooth integrands; Gaussian and adaptive quadrature copes better with difficult ones.

For the underlying rules, see Newton-Cotes rules; Simpson's rule is actually the first Romberg column extrapolation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. If A(h) = A + c h^2 + ..., which combination cancels the h^2 term?

    With p = 2 the formula is (2^p A(h/2) - A(h)) / (2^p - 1) = (4 A(h/2) - A(h)) / 3.
  2. 2. Why does Romberg integration work well on the trapezoidal rule?

    The Euler-Maclaurin expansion contains only even powers, so each extrapolation step removes the next one cleanly.
  3. 3. When does Romberg extrapolation help little?

    A non-smooth function breaks the assumed power-law error pattern.
  4. 4. How many new function evaluations does doubling the panels of a trapezoid rule need?

    Previous nodes are reused, so only the new midpoints are evaluated.

Summary

  • Richardson extrapolation combines runs with steps h and h/2 to cancel the leading error term: (2^p A(h/2) - A(h)) / (2^p - 1).
  • Applied to the central difference it gives a fourth-order derivative.
  • Applied repeatedly to the trapezoidal rule it gives Romberg integration, with a table whose diagonal converges very fast for smooth integrands.
  • It needs clean power-law errors and low noise.

Next: Newton-Cotes rules