EXPLANATION FILE OF PROGRAM ZBRENT
==================================
Purpose: Find a real root of a real function Y = F(x)
-------
The Van Wijngaarden-Dekker-Brent Method
---------------------------------------
While secant and false position formally converge faster than bisection, one
finds in practice pathological functions for which bisection converges more
rapidly. These can be choppy, discontinuous functions, or even smooth functions
if the second derivative changes sharply near the root. Bisection always halves
the interval, while secant and false position can sometimes spend many cycles
slowly pulling distant bounds closer to a root. Is there anything we can do to
get the best of both worlds?
Yes. We can keep track of whether a supposedly superlinear method is onverging
the way it is supposed to, and, if it is not, we can intersperse bisection steps
so as to guarantee at least linear convergence. This kind of super-strategy
requires attention to bookkeeping detail, and also careful consideration of how
roundoff errors can affect the guiding strategy. AIso, we must be able to
determine reliably when convergence has been achieved.
An excellent algorithm that pays close attention to these matters was developped
in the 1960s by van Wijngaarden, Dekker, and others at the Mathematical Center
in Amsterdam, and later improved by Brent (reference below). For brevity, we refer
to the final form of the algorithm as Brent 's method. The method is guaranteed
(by Brent) to converge, so long as the function can be evaluated within the initial
interval known to contain a root.
Brent's method combines root bracketing, bisection, and inverse quadratic inter-
polation to converge from the neighborhood of a zero crossing. While the false
position and secant methods assume approximately linear behavior between twO prior
root estimates, inverse quadratic interpolation uses three prior points to fit an
inverse quadratic function (x as a quadratic function of y) whose value at y = 0
is taken as the next estimate of the root x.
Of course one must have contingency plans for what to do if the root falls outside
brackets. Brent's method takes care of all that. If the three point are
[a, f(a)], [b, f(b)], [e, f(e)] then the interpolation formula (cf. equation 3.1.1)
is
[y - f(a)][y - f(b)]c [y - f(b)][y - f(c)]a
x = -------------------------- + --------------------------
[f(c) - f(a)][f(c) - f(b)] [f(a) - f(b)][f(a) - f(c)]
(9.3.1)
[y - f(c)][y - f(a)]b
+ --------------------------
[f(b) - f(c)][f(b) - f(a)]
Setting y to zero gives a result for the next root estimate, which written as
x=b+P/Q (9.3.2)
where, in terms of
R == f(b)/ f(e), S == f(b)/ f(a), T == f(a)/ f(e) (9.3.3)
we have
P = S [T(R - T)(c - b) - (1- R)(b - a)] (9.3.4)
Q = (T - l)(R - l)(S - 1) (9.3.5)
ln practice b is the current best estimate of the root and P / Q ought to be
a "small" correction. Quadratic methods work well only when the function
behaves smoothly; they run the serious risk of giving very bad estimates of the
next root or causing machine failure by an inappropriate division by a very
small number (Q ~ 0). Brent's method guards against this problem by maintaining
brackets on the root and checking where the interpolation would land before
carrying out the division. When the correction P / Q would not land within the
bounds, or when the bounds are not collapsing rapidly enough, the algorithm takes
a bisection step. Thus, Brent's method combines the sureness of bisection with
the speed of a higher-order method when appropriate. We recommend it as the method
of choice for general one-dimensional root finding where a function's values only
(and not its derivative or functional form) are available.
From [BIBLI 08].
-------------------------------------------------------------
End of file Zbrent.txt