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
.
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
).
To eliminate the A term, multiply the first equation by h2p, the second by h1p and subtract.
The Richardson extrapolation value for Q is
Its error, as an approximation to Q, should be
O(hp+1).
Typically, we take h1 = h and h2 = h/2. Then
For example, consider the approximation
Q(h) = (1 + x h)1/h for
.
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
.
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
or
respectively.
We have the (presumably) much more accurate approximation
,
but
we don't know how much more accurate! It won't hurt to use the
approximation
,
but, to be conservative, still use
or
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