Richardson extrapolation

Section 12.4 Richardson extrapolation

Richardson extrapolation is a method that allows one to reduce the error of an approximate formula, provided that the order of this error is known. The idea is to use two different step sizes, for example \(h\) and \(2h\text{.}\) If the order of error is \(n\text{,}\) then the second approximation will have an error that is about \(2^n\) times greater. How can we use this information?

🔗

Let \(Q\) be the quantity we want to find. Using step size \(h\) we get an approximation \(A_1\) with error term \(E_1\text{,}\) meaning that

\begin{equation} Q = A_1 + E_1\tag{12.4.1} \end{equation}

Using step size \(2h\) we get an approximation \(A_2\) with error term \(E_2\text{,}\) meaning that

\begin{equation} Q = A_2 + E_2\tag{12.4.2} \end{equation}

Since we know that \(E_2\) is close to \(2^n E_1\text{,}\) we can try to cancel out the error terms: multiply (12.4.1) by \(2^n\) and subtract (12.4.2). The result is

\begin{equation*} (2^n-1) Q = 2^n A_1 - A_2 + [2^n E_1 - E_2] \end{equation*}

Since the error terms should almost cancel each other, the new approximation

\begin{equation} Q \approx \frac{2^n A_1 - A_2}{2^n-1}\tag{12.4.3} \end{equation}

should be much more accurate than the original approximation (12.4.1). The formula (12.4.3) expresses the method of Richardson extrapolation. This idea is not specific to numerical differentiation; it can be used any time a computed quantity has an error proportional to a known power of step size.

🔗

Example 12.4.1. Apply Richardson extrapolation to the symmetric formula for \(f'\).

Use Richardson extrapolation to improve the accuracy of the symmetric difference formula (12.3.1).

🔗

Solution.

Recall from Example 12.3.1 that the symmetric difference formula has error of order 2. Therefore, in the equation (12.4.3) we have \(2\text{.}\) The approximation \(A_1\) is the original formula

\begin{equation*} A_1 = \frac{f(x+h)-f(x-h)}{2h} \end{equation*}

To get \(A_2\) we replace \(h\) by \(2h\text{:}\)

\begin{equation*} A_2 = \frac{f(x+2h)-f(x-2h)}{4h} \end{equation*}

The formula (12.4.3) now tells us that

\begin{equation} f'(x) \approx \frac{4 A_1 - A_2}{3} = 2\frac{f(x+h)-f(x-h)}{3h} - \frac{f(x+2h)-f(x-2h)}{12h}\tag{12.4.4} \end{equation}

which is the extrapolated approximation to \(f'(x)\text{.}\)

🔗

Prev Top Next