NextUpPrev

Appendix C
Richardson Extrapolation

Digital computers cannot, in general, evaluate values with infinite precision and thus need to rely on approximations. It is, of course, among the goals of any scheme resulting in such an approximate value to have as little an error as possible. Numerical schemes to reduce this error, such as the Richardson extrapolation presented here, are therefore of great interest.

The Richardson extrapolation scheme assumes that a function f can be expanded around a point of evaluation depending on a parameter h in a form

1- 2 f(h) = f (0 ) + c1h + 2 c2h + ..., (C .1)
such that the point of evaluation corresponds to the parameter h = 0 . Expanding the function at two different values of the parameter h and hs gives
1- 2 f(h ) = f (0) + c1h + 2c2h + ... (C.2a) h 1 1 1 f(--) = f (0) + c1-h +-c2 -2h2 + .... (C.2b) s s 2 s

Multiplying Equation  by s and subtracting Equation  allows to eliminate the terms of order h

sf(h-) − f (h) = (s − 1 )f(0) − 1c2-1 h2 + .... (C.3) s 2 s2
Reordering this expression shows the approximation for f (0 ) explicitly as
h sf(s)-−-f(h)- ′ 2 f (0 ) = s − 1 + c2h + .... (C.4)
An approximation which now is of order 2 h instead of the original order h . This procedure can be applied repeatedly to further increase the quality of the approximation.

Applications using digital computers usually utilize factors s corresponding to powers of 2 . This allows the following settings

R (i,0) = f(h-) (C .5a) 2i sjR(i,j − 1) − R(i − 1,j − 1) R (i,j) = -------------i---------------, (C .5b) 2 − 1

which further illustrate the recursive nature of the procedure.


NextUpPrev