Information Technology Reference
In-Depth Information
n1
X
D
1
2
.x
1
x
0
/f .x
0
/ C
1
f.x
i
/.x
iC1
x
i1
/ C
(6.9)
2
iD1
1
2
.x
n
x
n1
/f .x
n
/:
(6.10)
The corresponding pseudo code is given as Algorithm
6.7
. One still needs however,
to devise a strategy for choosing the unequal spacing, i.e., determine the values
of
x
0
;:::;x
n
. An intuitive approach is to cluster evaluation points where
f.x/
is
rapidly varying, perhaps in a way that makes the error approximately the same on
every interval
Œx
i1
;x
i
.
Algorithm 6.7
Optimized Trapezoidal Integration: Unequal Spacing.
trapezoidal
(
a
,
b
,
f
,
x
0
;:::;x
n
)
s D 0
for
i D 1;:::;n1
s s Cf.x
i
/.x
iC1
x
i1
/
end for
s s C f .a/.x
1
x
0
/ C f .b/.x
n
x
n1
/
return
0:5 s
The error when applying the trapezoidal rule on an interval
Œx
i1
;x
i
can be
showntobe
E D
1
12
.x
i
x
i1
/
3
f
00
./;
(6.11)
where
is some point in
Œx
i1
;x
i
. Using a finite difference to approximate
f
00
at
the midpoint of the interval,
f.x
i1
/ 2f .
1
2
.x
i1
C x
i
//C f.x
i
/
;
f
00
.
1
1
4.x
i
x
i1
/
2
2
.x
i1
C x
i
//
we can replace (6.11) by an approximate error quantity
2
.x
i1
C x
i
//C f.x
i
/
:
(6.12)
We could now start with an equally spaced coarse distribution
x
i
D aC
ih
,com-
pute the error in each interval, and divide an interval into two new equally spaced
segments if the error is greater than
,where
is the largest acceptable error on an
interval. This procedure can be repeated until no more refinement is necessary. Of
course, we should also stop the refinement if the number of points
x
i
becomes unac-
ceptably large. Algorithm
6.8
presents the pseudo code for one level of refinement.
We p r ov i d e
x
0
;:::;x
n
as input and obtain a new set of points
y
0
;y
1
;y
2
;:::
,where
each original interval is either preserved or divided into two new intervals.
f.x
i1
/ 2f .
1
E.x
i1
;x
i
;f/D
x
i
x
i1
48
