Page 175 - Compact Numerical Methods For Computers

164 Compact numerical methods for computers
finding, we prefer to require the user to provide an interval in which at least one root exists and
upon which the function is defined. The driver program DR1618.PAS on the software diskette is
in tended to allow users to approximately localise roots of functions using grid search, ,followed by
a call to algorithm 18 to refine the position of a suspected root.

Example 13.2. A test of root-finding algorithms
In order to test the algorithm above it is useful to construct a problem which can
be adapted to cause either the bisection or the False Position methods some
relative difficulty. Therefore, consider finding the root of
f(b)=z*[tanh(y) +w ] (13.28)
where
y=s* (b- t) (13.29)
which has a root at
b*=t+ln[(l-w)/(l+w)]/(2s). (13.30)
Note that z is used to provide a scale for the function, s scales the abscissa while t
translates the root to right or left. The position of the root is determined by w to
within the scaling s. Suppose now that s is large, for example s=100. Then the
function f(b) will change very rapidly with b near the root, but otherwise will be
approximated very well by

(13.31)

In fact using the grid search procedure (algorithm 16) we find the values in table
13.1 given t=0·5, z=100, s=100 and w=0·99. (The results in the table have
been computed on a Data General NOVA having 23-bit binary arithmetic.)
The consequences of such behaviour can be quite serious for the False Position
algorithm. This is because the linear approximation used is not valid, and a typical
step using u = 0, 2, v = 1 gives
b=1·00001/200=5·00005E-3.
Since the root is near 0·473533, the progress is painfully slow and the method
requires 143 iterations to converge. Bisection, on the other hand, converges in 24
iterations (nbis=1 in the algorithm above). For nbis=2, 25 iterations are
required, while for nbis=5, which is the suggested value, 41 iterations are
needed. This may indicate that bisection should be a permanent strategy. How-
ever, the function (13.28) can be smoothed considerably by setting w=0·2 and
s=1, for which the root is found near 0·297268. In this case the number of
iterations needed is again 24 for nbis=1 (it is a function only of the number of
bits in the machine arithmetic), 6 for nbis=5 and also 6 if nbis is set to a large
number so no bisections are performed. Figure 13.1 shows plots of the two
functions obtained on a Hewlett-Packard 9830 calculator.