Richardson Extrapolation

Richardson Extrapolation is an idea which can often be used to improve the results of a numerical method: from a method of order O(hp) it gives us a method of order O(hp+1).

Suppose you want to approximate a quantity Q, and you have available approximations Q(h) for h > 0. Typically, you know that this approximation is of a certain order, say $\displaystyle Q = Q(h) + O(h^p)$. But often, more can be said: for some quantity A not depending on h,

Q = Q(h) + A hp + O(hp+1)

The idea of Richardson extrapolation is to take two different values of h, and eliminate the A term. Suppose we use h1 and h2, where h1 and h2 are of a similar order of magnitude (O(h)) but not too close together (so $\displaystyle1/(h_2^p -h_1^p) = O(1/h^p)$).

\begin{displaymath}\,\vcenter{\openup.7ex\mathsurround=0pt
\ialign{\strut\hfil$...
...(h^{p+1})\cr
Q &= Q(h_2) + A h_2^p + O(h^{p+1})\cr\crcr}}\,
\end{displaymath}

To eliminate the A term, multiply the first equation by h2p, the second by h1p and subtract.

\begin{displaymath}\,\vcenter{\openup.7ex\mathsurround=0pt
\ialign{\strut\hfil$...
...Q(h_1) - h_1^p Q(h_2)}{h_2^p - h_1^p} + O(h^{p+1})\cr\crcr}}\, \end{displaymath}

The Richardson extrapolation value for Q is

\begin{displaymath}Q_R = \frac{h_2^p Q(h_1) - h_1^p Q(h_2)}{h_2^p - h_1^p} \end{displaymath}

Its error, as an approximation to Q, should be O(hp+1). Typically, we take h1 = h and h2 = h/2. Then

\begin{displaymath}Q_R = \frac{(h/2)^p Q(h) - h^p Q(h/2)}{(h/2)^p - h^p} = \frac{2^p Q(h/2) - Q(h)}{2^p-1}
\end{displaymath}

For example, consider the approximation Q(h) = (1 + x h)1/h for $Q = \exp(x)$. As we saw , this has error A h + O(h2) for some A. Since p = 1, the Richardson approximation would be

QR = 2 Q(h/2) - Q(h) = 2 (1 + x h/2)2/h - (1+xh)1/h

Thus if we take x = 1 and h = 0.1, Q(.1) = 1.110 = 2.593742460 and Q(.05) = 1.0520 = 2.653297705. Neither of these is a very good approximation to $\exp(1) = 2.718281828$. But the Richardson approximation QR = 2.712852950 is considerably better.

Another use of this technique is to get an estimate of the error in the original approximation Q(h1) or Q(h2): this error should be approximately $\displaystyle Q_R - Q(h_1)$ or $\displaystyle Q_R - Q(h_2)$ respectively. We have the (presumably) much more accurate approximation $\displaystyle Q_R$, but we don't know how much more accurate! It won't hurt to use the approximation $\displaystyle Q_R$, but, to be conservative, still use $\displaystyle Q_R - Q(h_1)$ or $\displaystyle Q_R - Q(h_2)$ as an indication of the error. So in the above example, we can estimate the errors in Q(.1) and Q(.05) as about QR - Q(.1) = .119110490 and QR - Q(.05) = .059555245 respectively (the actual errors are .124539368 and .064984123), and we would expect the error in QR to be at most .059555245 as well (the actual error is .005428878).


 

Robert Israel
2002-01-29