Richardson Extrapolation

A technique that combines approximations at different step sizes to cancel leading error terms and gain accuracy for free.

Turning known error structure into accuracy

Many numerical approximations have an error that is a known power of the step size h: for example, a result A(h) that equals the true value plus a term proportional to h-squared, plus higher-order terms. Richardson extrapolation exploits this structure. By combining the approximations at two step sizes, the leading error term can be canceled algebraically, producing a much more accurate estimate without evaluating any new derivatives.

The formula

If the error goes as h to the power p, then combining A(h) and A(h/2) as [2^p times A(h/2) minus A(h)] divided by [2^p minus 1] cancels the leading term, leaving an error of higher order. Repeating this with a sequence of step sizes builds a triangular table, each column canceling the next error term, converging rapidly to the true value.

def richardson(A, h, p, levels):
    # A(h) is a function returning the approximation at step h
    T = [[0.0]*(levels) for _ in range(levels)]
    for i in range(levels):
        T[i][0] = A(h / 2**i)
    for j in range(1, levels):
        for i in range(j, levels):
            f = 2.0**(p*j)
            T[i][j] = (f * T[i][j-1] - T[i-1][j-1]) / (f - 1)
    return T[levels-1][levels-1]

Named instances

• Romberg integration: Richardson extrapolation applied to the trapezoidal rule, yielding high-order quadrature
• The Bulirsch-Stoer ODE solver: extrapolation of the midpoint rule to very high accuracy
• Estimating discretization error by comparing solutions on successively refined grids

Uses and cautions

Beyond boosting accuracy, Richardson extrapolation is a primary tool for error estimation: the difference between successive extrapolants estimates the remaining error, which drives adaptive quadrature and mesh adaptivity. The catch is that it assumes the error truly follows the expected power law; if the solution lacks the required smoothness (near singularities or shocks), the extrapolation can be worse than the raw estimate. Verifying the observed order of convergence guards against this.