Topic 12.3: Richardson Extrapolation (Theory)

Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple

One significant problem with approximating a derivative is subtractive cancellation. In the formula (f(x + h) − f(x − h))/(2 h), for very small values of h, the two function evaluations f(x + h) and f(x − h) will be approximately equal, and therefore subtractive cancellation will occur. Therefore, it would be undesirable, and dangerous, to use ever smaller values of h.

Instead of using a smaller value of h, suppose we are attempting to approximate an exact value e with an approximation a(h). In this case, e is the derivative f⁽¹⁾(x) and the approximation is a(h) = (f(x + h) − f(x − h))/(2 h). Suppose now that the error of the approximation is defined by a Taylor series of the form:

e = a(h) + K hⁿ + o(hⁿ)

Consider now the approximation using h/2:

e = a(h/2) + K (h/2)ⁿ + o((h/2)ⁿ)
= a(h/2) + K/2ⁿ hⁿ + o(hⁿ)

Multiplying this second expression by 2ⁿ and subtracting off the first equation yeilds

2ⁿe − e = 2ⁿa(h/2) − a(h) + K/2ⁿ hⁿ − K hⁿ + o(hⁿ)

Note that the hⁿ term cancels and we are left with

(2ⁿ − 1)e = 2ⁿa(h/2) − a(h) + o(hⁿ)

If we look at the full Taylor series for the centred divided-difference formula, we note that the error terms are of the form K_nhⁿ:

We can write this as:

where K₁ = −1/6 f⁽³⁾(x)h², etc.

This is not the case if you use the backward divided-difference formula, which is of the form:

To convince yourself of this, you may look at this Maple worksheet which demonstrates this fact.

For the centred divided-difference formula, this is identical to the pattern for the composite trapezoidal rule, and therefore, we can use Richardson extrapolation to get a better answer. Note, for integration, applying Richardson extrapolation to the results of the composite trapezoidal rule is termed Romberg integration. There is no special name for Richardson extrapolation as applied to derivative formula.