Information Technology Reference
In-Depth Information
Mathematical Pseudo Code
As we have learned, the mathematical description of the method in (6.3) should
first be turned into a mathematical pseudo algorithm. Then we can proceed with
translating the algorithm into computer language. With our recent experience in
writing algorithms for the trapezoidal rule, it should be quite easy to come up with
Algorithm
6.3
. Note that we have not used the notation
x
i1
,
x
i
2
,and
x
i
,but
x
,
x
,and
x
C
instead. This is due to the fact that mathematical symbols with indices,
such as
x
i
, are often translated to arrays in computer codes. In the present case, we
do not need to store the
x
i
values in an array, we just need to compute the
x
value
inside the loop and then call
f.x/
. Therefore, to avoid indices, we work with
x
,
x
,and
x
C
. In a computer code these variables could be given names such as
xm
,
x
,
and
xp
.
Algorithm 6.3
Simpson's Rule
.
Simpson
(
a
,
b
,
f
,
n
)
h D
ba
n
s D 0
for
i D 1;:::;n
x
D a C .i 1/h
x
C
D a C
ih
x D
2
.x
Cx
C
/
s s C
6
f.x
/C
6
f.x/C
6
f.x
C
/
end for
s hs
return
s
Algorithm
6.3
and a computer implementation that follows the algorithm line
by line using similar symbols represent a safe development from description (6.3)
of the numerical method. It should not be difficult to get things right and obtain
working code.
Optimization of the Algorithm
The downside of Algorithm
6.3
is that we perform more evaluations of the func-
tion
f.x/
than necessary. Computing
f.x/
is probably the most expensive part of
such algorithms, so avoiding too many function evaluations will have a significant
impact on CPU time. Even very intelligent compilers will probably have a hard time
detecting that we are performing too many function evaluations, so this is work for
a human programmer.
The main observation is that we evaluate
f.x
i1
/
and
f.x
i
)inthe
i
th term of
the sum in (6.3) and recalculate
f.x
i
/
in the next term of the sum (where we need
f.x
i
/
and
f.x
iC1
//
. We should avoid the recalculation of
f.x
i
/
. How to do this is
