Information Technology Reference
In-Depth Information
Of course, hand coding of such an optimization would make the implementation
valid for only a specific function. Calling
f.x/
instead makes the implementation
valid for any
f
.
Testing the computational efficiency of integrating
f
1
.x/ D e
x
2
log
.1Cx
sin
x/
and
f
2
.x/ D 1Cx
shows that Algorithm
6.4
clearly runs faster than Algorithm
6.3
.
The difference depends on the amount of compiler optimization and the complexity
of
f.x/
. With full optimization and
f
2
.x/
, Algorithm
6.4
reduced the CPU time by
about 20% in comparison with Algorithm
6.3
. The theoretical saving is 33%, since
we reduce the number of function evaluations from
3n
to
2nC 1
.
Computer implementation and debugging can often be very time consuming.
When preparing a problem in scientific computing for implementation, one should
start with the simplest version of the algorithm. Smart rewriting and hand optimiza-
tions in the code can easily result in hunting errors for hours. On the other hand,
training the ability to rewrite algorithms in more efficient forms is an important
part of scientific computing. Real-life applications of numerical computing in sci-
ence and technology make such harsh demands on computer power that serious
work with optimization is crucial. The bottom line is that such optimization work
should be performed
after
safe and easy-to-understand algorithms are implemented
and thoroughly tested. Thinking “constantly” of optimization when carrying out the
mathematics and programming has been a tradition in scientific computing, and we
believe the result has been too many codes that compute wrong numbers simply
because the “smart” expressions increased the complexity of the problem and the
code at too early a stage in the development.
6.1.5
Adaptive Integration Rules
A basic problem when applying the trapezoidal or Simpson's rule is to find a suitable
value of
n
. Two factors influence the choice of
n
: the desired accuracy of the integral
and the shape of
f
. A simple strategy is to apply the integration rule for a sequence
of
n
increasing values, say,
n
0
,
n
1
,
n
2
,
:::
, and stop when the difference between two
consecutive integral values becomes negligible. This is called an
adaptive
algorithm,
because the number of points will adapt to the desired accuracy and the shape of
f
.
Define
I.a; b; f; n/
as an approximation to
R
b
a
f.x/dx
using a specific numerical
integration rule with
n
points, and let
be some specified tolerance. The following
pseudo code expresses adaptive integration:
r D I.a; b; f; n
0
/
for
n D n
1
;n
2
;n
3
;:::
s D I.a; b; f; n/
if
js rj
then
return
s
else
r D s
end if
end for
