Richardson Extrapolation

Section C.1 Richardson Extrapolation

There are many approximation procedures in which one first picks a step size

h

and then generates an approximation

A (h)

to some desired quantity

A .

For example,

A

might be the value of some integral

\int_{a}^{b} f (x) d x .

For the trapezoidal rule with

n

steps,

Δ x = \frac{b - a}{n}

plays the role of the step size. Often the order of the error generated by the procedure is known. This means

\begin{matrix} (E1) & A = A (h) + K h^{k} + K_{1} h^{k + 1} + K_{2} h^{k + 2} + \dots \end{matrix}

🔗

with

k

being some known constant, called the order of the error, and

K, K_{1}, K_{2}, \dots

being some other (usually unknown) constants. If

A (h)

is the approximation to

A = \int_{a}^{b} f (x) d x

produced by the trapezoidal rule with

Δ x = h,

then

k = 2 .

If Simpson’s rule is used,

k = 4 .

🔗

Let’s first suppose that

h

is small enough that the terms

K^{'} h^{k + 1} + K^{″} h^{k + 2} + \dots

in (E1) are small enough

Typically, we don’t have access to, and don’t care about, the exact error. We only care about its order of magnitude. So if

h

is small enough that

K_{1} h^{k + 1} + K_{2} h^{k + 2} + \dots

is a factor of at least, for example, one hundred smaller than

K h^{k},

then dropping

K_{1} h^{k + 1} + K_{2} h^{k + 2} + \dots

would not bother us at all.

that dropping them has essentially no impact. This would give

\begin{matrix} (E2) & A = A (h) + K h^{k} \end{matrix}

🔗

Imagine that we know

k,

but that we do not know

A

K,

and think of (E2) as an equation that the unknowns

A

and

K

have to solve. It may look like we have one equation in the two unknowns

K,

A,

but that is not the case. The reason is that (E2) is (essentially) true for all (sufficiently small) choices of

h .

If we pick some

h,

say

h_{1},

and use the algorithm to determine

A (h_{1})

then (E2), with

h

replaced by

h_{1},

gives one equation in the two unknowns

A

and

K,

and if we then pick some different

h,

say

h_{2},

and use the algorithm a second time to determine

A (h_{2})

then (E2), with

h

replaced by

h_{2},

gives a second equation in the two unknowns

A

and

K .

The two equations will then determine both

A

and

K .

🔗

To be more concrete, suppose that we have picked some specific value of

h,

and have chosen

h_{1} = h

and

h_{2} = \frac{h}{2},

and that we have evaluated

A (h)

and

A (h / 2) .

Then the two equations are

\begin{aligned} (E3a) & A & = A (h) + K h^{k} \\ (E3b) & A & = A (h / 2) + K (\frac{h}{2})^{k} \end{aligned}

🔗

It is now easy to solve for both

K

and

A .

To get

K,

just subtract (E3b) from (E3a).

\begin{aligned} (E3a) - (E3b) : & 0 = A (h) - A (h / 2) + (1 - \frac{1}{2^{k}}) K h^{k} \\ (E4a) & ⟹ & K = \frac{A (h / 2) - A (h)}{[1 - 2^{- k}] h^{k}} \end{aligned}

🔗

To get

A

multiply (E3b) by

2^{k}

and then subtract (E3a).

\begin{aligned} 2^{k} (E3b) - (E3a) : & [2^{k} - 1] A = 2^{k} A (h / 2) - A (h) \\ (E4b) & ⟹ & A = \frac{2^{k} A (h / 2) - A (h)}{2^{k} - 1} \end{aligned}

🔗

The generation of a “new improved” approximation for

A

from two

A (h)

’s with different values of

h

is called Richardson

Richardson extrapolation was introduced by the Englishman Lewis Fry Richardson (1881--1953) in 1911.

Extrapolation. Here is a summary

🔗

Equation C.1.1. Richardson extrapolation.

🔗

Let

A (h)

be a step size

h

approximation to

A .

A = A (h) + K h^{k}

🔗

then

K = \frac{A (h / 2) - A (h)}{[1 - 2^{- k}] h^{k}} A = \frac{2^{k} A (h / 2) - A (h)}{2^{k} - 1}

🔗

This works very well since, by computing

A (h)

for two different

h

’s, we can remove the biggest error term in (E1), and so get a much more precise approximation to

A

for little additional work.

Example C.1.2. Richardson extrapolation with the trapezoidal rule.

Applying the trapezoidal rule (1.11.6) to the integral

A = \int_{0}^{1} \frac{4}{1 + x^{2}} d x

with step sizes

\frac{1}{8}

and

\frac{1}{16}

(i.e. with

n = 8

and

n = 16

) gives, with

h = \frac{1}{8},

A (h) = 3.1389884945 A (h / 2) = 3.1409416120

So (E4b), with

k = 2,

gives us the “new improved” approximation

\frac{2^{2} \times 3.1409416120 - 3.1389884945}{2^{2} - 1} = 3.1415926512

We saw in Example 1.11.3 that

\int_{0}^{1} \frac{4}{1 + x^{2}} d x = π,

so this new approximation really is “improved”:

$A (1 / 8)$ agrees with $π$ to two decimal places,
$A (1 / 16)$ agrees with $π$ to three decimal places and
the new approximation agrees with $π$ to eight decimal places.

Beware that (E3b), namely

A = A (h / 2) + K (\frac{h}{2})^{k},

is saying that

K (\frac{h}{2})^{k}

is (approximately) the error in

A (h / 2),

not the error in

A .

You cannot get an “even more improved” approximation by using (E4a) to compute

K

and then adding

K (\frac{h}{2})^{k}

to the “new improved”

A

of (E4b) — doing so just gives

A + K (\frac{h}{2})^{k},

not a more accurate

A .

Example C.1.3. Example 1.11.16 revisited.

Suppose again that we wish to use Simpson’s rule (1.11.9) to evaluate

\int_{0}^{1} e^{- x^{2}} d x

to within an accuracy of

10^{- 6},

but that we do not need the degree of certainty provided by Example 1.11.16. Observe that we need (approximately) that

| K | h^{4} < 10^{- 6},

so if we can estimate

K

(using our Richardson trick) then we can estimate the required

h .

A commonly used strategy, based on this observation, is to

first apply Simpson’s rule twice with some relatively small number of steps and
then use (E4a), with $k = 4,$ to estimate $K$ and
then use the condition $| K | h^{k} \leq 10^{- 6}$ to determine, approximately, the number of steps required
and finally apply Simpson’s rule with the number of steps just determined.

Let’s implement this strategy. First we estimate

K

by applying Simpson’s rule with step sizes

\frac{1}{4}

and

\frac{1}{8} .

Writing

\frac{1}{4} = h^{'},

we get

A (h^{'}) = 0.74685538 A (h^{'} / 2) = 0.74682612

so that (E4a), with

k = 4

and

h

replaced by

h^{'},

yields

K = \frac{0.74682612 - 0.74685538}{[1 - 2^{- 4}] (1 / 4)^{4}} = - 7.990 \times 10^{- 3}

We want to use a step size

h

obeying

| K | h^{4} \leq 10^{- 6} ⟺ 7.990 \times 10^{- 3} h^{4} \leq 10^{- 6} ⟺ h \leq \sqrt[4]{\frac{1}{7990}} = \frac{1}{9.45}

like, for example,

h = \frac{1}{10} .

Applying Simpson’s rule with

h = \frac{1}{10}

gives

A (1 / 10) = 0.74682495

The exact answer, to eight decimal places, is

0.74682413

so the error in

A (1 / 10)

is indeed just under

10^{- 6} .

Suppose now that we change our minds. We want an accuracy of

10^{- 12},

rather than

10^{- 6} .

We have already estimated

K .

So now we want to use a step size

h

obeying

\begin{aligned} | K | h^{4} \leq 10^{- 12} & ⟺ 7.99 \times 10^{- 3} h^{4} \leq 10^{- 12} \\ ⟺ h \leq \sqrt[4]{\frac{1}{7.99 \times 10^{9}}} = \frac{1}{299.0} \end{aligned}

like, for example,

h = \frac{1}{300} .

Applying Simpson’s rule with

h = \frac{1}{300}

gives, to fourteen decimal places,

A (1 / 300) = 0.74682413281344

The exact answer, to fourteen decimal places, is

0.74682413281243

so the error in

A (1 / 300)

is indeed just over

10^{- 12} .

Prev Top Next