MATH/APPM 4650
Class notes, February 20

Richardson's extrapolation

Most of today's notes will be on the board. Here are the basic ideas.

Main idea:
Suppose we are trying to approximate a derivative numerically.
[-f(5+2h) + 4 f(5+h) - 3 f(5)] / [2h] = f'(5) - f'''(5) h2/3 - fiv(5) h3/4 - . . .
or more generally, approximate any number M by some formula N(h) depending on a small parameter h.
N(h) = M + K1 h + K2 h2 + K3 h3 + . . .


It's actually easier to work with the more general formula.

If we know N(0.2) is 5.92 and N(0.1) is 5.41, what's the best estimate for M?

We know
N(0.2) = 5.92 = M + 0.2 K1 + . . .
N(0.1) = 5.47 = M + 0.1 K1 + . . .
We don't know K1 but we can eliminate it.

2 * 5.47 - 5.92 = 2M - M = M,
so the best approximation for M is
M = 5.02
and the error in this approximation is O(h2), i.e., probably about 0.05 or so.

If we had three approximations for three different values of h, we could eliminate the error terms up to h2.
Then the approximation would be accurate to order O(h3).


It's a simple trick, but we can make it more systematic by supposing we keep cutting h in half and deriving a general formula.


General formula (derivation on board):
If N1(h) = N(h) is the basic formula, then we generate better approximations via
Nj(h) = Nj-1(h/2) + [ Nj-1(h/2)-Nj-1(h) ] / [ 2j-1 - 1 ].


The technique can be used to generate better derivative formulas with less computation.

It also gets used especially in numerical integration and in solving differential equations.

The nice thing about it is that it works based on how we do things in real life: successively generate better values by reducing h, until results stop changing. But then it incorporates all those computed values to generate a much better approximation than any individual one.

We can also use this technique more generally.
  1. We don't need to cut h in half; we could consider other shrinking algorithms too.
  2. If we happen to know some terms in the Taylor series for the error are zero, we can skip ahead.


Only thing to worry about is if h shrinks too much. Then we may get roundoff error.



Explicit example: