Graphics Programs Reference
In-Depth Information
5.3
Richardson Extrapolation
Richardson extrapolationis a simple method forboosting the accuracy of certain
numerical procedures, including finite difference approximations(we will also use it
later in numerical integration).
Suppose that wehave an approximate meansofcomputing somequantity
G
.
Moreover, assumethat the result dependson a parameter
h
.Denoting the approxi-
mationby
g
(
h
), wehave
G
E
(
h
), where
E
(
h
) represents the error. Richardson
extrapolation can remove the error, provided that ithas the form
E
(
h
)
=
g
(
h
)
+
ch
p
,
c
and
p
=
being constants.Westart by computing
g
(
h
) with some valueof
h
,say
h
=
h
1
. In that
case wehave
ch
1
G
=
g
(
h
1
)
+
(i)
Thenwe repeat the calculationwith
h
=
h
2
,
so that
ch
2
G
=
g
(
h
2
)
+
(j)
Eliminating
c
and solving for
G
, weobtain fromEqs. (i) and (j)
h
2
)
p
g
(
h
2
)
(
h
1
/
−
g
(
h
1
)
G
=
(5.9a)
(
h
1
/
h
2
)
p
−
1
which is the
Richardsonextrapolation formula
. It iscommonpractice to use
h
2
=
h
1
/
2
,
in which case Eq. (5.9a) becomes
2
p
g
(
h
1
/
2)
−
g
(
h
1
)
G
=
(5.9b)
2
p
−
1
Let us illustrate Richardson extrapolationbyapplying it to the finite difference
approximation of (
e
−
x
)
at
x
1. We work with six-digit precision and utilize the
results in Table 5.4.Since the extrapolationworks only on the truncation error, we
must confine
h
to values that produce negligible roundoff.Choosing
h
1
=
=
64 and
letting
g
(
h
) be the approximation of
f
(1)obtainedwith
h
, we get from Table 5.4
0
.
g
(
h
1
)
=
0
.
380 610
g
(
h
1
/
2)
=
0
.
371 035
The truncation errorinthe central difference approximationis
E
(
h
)
=
O
(
h
2
)
=
c
1
h
2
+
c
2
h
4
c
3
h
6
+
+···
.
Therefore, wecan eliminate the first (dominant) error term if we
substitute
p
=
2 and
h
1
=
0
.
64 in Eq. (5.9b). The result is
2
2
g
(0
.
32)
−
g
(0
.
64)
4(0
.
371 035)
−
0
.
380 610
G
=
=
=
0
.
367 84 3
2
2
−
1
3
which is an approximation of (
e
−
x
)
with the error
(
h
4
). Note that it is as accurate as
the best result obtainedwith eight-digitcomputations in Table 5.4.
O
Search WWH ::
Custom Search