Information Technology Reference
In-Depth Information
1
2
.x
a/
2
g
00
.a/
g.x/
D
g.a/
C
.x
a/g
0
.a/
C
(1.41)
1
nŠ
.x
a/
n
g
.n/
.a/
C
Q
nC1
CC
where
Q
nC1
D
1
.n
C
1/Š
.x
a/
nC1
g
.nC1/
./
for some in the interval bounded by x and a. This can again be written more
compactly as
n
X
.x
a/
m
mŠ
g
.m/
.a/
C
Q
nC1
:
g.x/
D
(1.42)
mD0
1.7.2
Derive Other Methods for Numerical Integration
The purpose of this project is to derive other methods of numerical integration. Since
we argued above that the error of the trapezoidal scheme is O.h
2
/, it is reasonable to
ask why we should need any other schemes. It is correct that the trapezoidal rule is
accurate and a good approximation can be achieved if we choose sufficiently many
grid points. Essentially, the trapezoidal scheme requires about n arithmetic opera-
tions and n function evaluations. For any reasonable function, we can evaluate the
integral using, say, n
D
10
6
in less than a second with a fairly modern computer. So
why do we need anything else? There are several reasons. First, there are situations
where we need to compute millions of integrals and we need them fast. One million
seconds is more than 11 days and that's a long time to wait for the result of a compu-
tation. So even if the trapezoidal scheme is accurate, there are situations where we
want to be able to compute an accurate solution more quickly. Second, the methods
discussed here also have multidimensional counterparts. In three dimensions, using
n
D
10
6
grid points in each coordinate direction would lead to 10
18
function eval-
uations for a method similar to the trapezoidal scheme. On a very fast computer,
one arithmetic operation takes about 10
9
s and thus such a grid is not feasible
with today's technology. We may circumvent this difficulty by using more accurate
methods or parallel computers. In this project we will concentrate on developing
two methods that are more accurate than the trapezoidal scheme. But more impor-
tant is that by completing this project, you will understand the principle of how such
a method is derived.
The problem is to compute an approximation of the integral
Z
b
f.x/dx:
a
One way of doing this is to find a function p
0
.x/ such that
