Page 171 - Compact Numerical Methods For Computers

160 Compact numerical methods for computers
inaccuracy in the derivative has, in my experience, appeared to upset the
performance of either the inverse interpolation or the convergence test.

13.3. REAL, ROOTS OF FUNCTIONS OF ONE VARIABLE
The linear search problem may, as mentioned, be approached by finding the roots
of the derivative of the function to be minimised. The problem of finding one or
more values b for which f(b) is zero arises directly in a variety of disciplines.
Formally the problem may be stated:
find the (real) value or values b such that f(b) = 0 .
However, in practice there is almost always more information available about
the roots other than that they are real. For instance, the roots may be restricted to
an interval [u, v] and the number of roots in this interval may be known. In such
cases, a grid search may be used to reduce the length of the interval in which the
roots are to be sought. Choosing some integer n to define a step
h = (v - u) / (n + 1) (13.15)
gives a grid upon which function values

f (u + jh) j = 0, 1, 2, . . . ,(n + 1) (13.16)
can be computed. If
f (u + jh)*f(u +(j + 1)h) < 0 (13.17)
then the interval [u + jh, u +(j +1)h] contains at least one root and the search can
be repeated on this smaller interval if necessary. Roots which occur with
f(b) = 0 f'(b) = 0 (13.18)

simultaneously are more difficult to detect, since the function may not cross the b
axis and a sign change will not be observed. Grid searches are notoriously
expensive in computer time if used indiscriminately. As in the previous section,
they are a useful tool for discovering some of the properties of a function by
‘taking a look’, particularly in conjunction with some plotting device. As such, the
grid parameter, n, should not be large; n < 10 is probably a reasonable bound.
Unfortunately, it is necessary to caution that if the inequality (13.17) is not
satisfied, there may still be an even number of roots in [u + jh,u +(j + 1)h].
Suppose now that a single root is sought in the interval [u, v] which has been
specified so that
f(u) * f(u) < 0. (13.19)

Thus the function has at least one root in the interval if the function is continuous.
One possible way to find the root is to bisect the interval, evaluating the function
at
b = (u + v)/2. (13.20)
If
f (u) * f(b) < 0 (13.21)