info prev up next book cdrom email home

Brent's Method

A Root-finding Algorithm which combines root bracketing, bisection, and Inverse Quadratic Interpolation. It is sometimes known as the van Wijngaarden-Deker-Brent Method.


Brent's method uses a Lagrange Interpolating Polynomial of degree 2. Brent (1973) claims that this method will always converge as long as the values of the function are computable within a given region containing a Root. Given three points $x_1$, $x_2$, and $x_3$, Brent's method fits $x$ as a quadratic function of $y$, then uses the interpolation formula

$x={[y-f(x_1)][y-f(x_2)]x_3\over [f(x_3)-f(x_1)][f(x_3)-f(x_2)]}+{[y-f(x_2)][y-f(x_3)]x_1\over [f(x_1)-f(x_2)][f(x_1)-f(x_3)]}$
$ +{[y-f(x_3)][y-f(x_1)]x_2\over [f(x_2)-f(x_3)][f(x_2)-f(x_1)]}.\quad$ (1)
Subsequent root estimates are obtained by setting $y=0$, giving

\begin{displaymath}
x=x_2+{P\over Q},
\end{displaymath} (2)

where
$\displaystyle P$ $\textstyle =$ $\displaystyle S[R(R-T)(x_3-x_2)-(1-R)(x_2-x_1)]$ (3)
$\displaystyle Q$ $\textstyle =$ $\displaystyle (T-1)(R-1)(S-1)$ (4)

with
$\displaystyle R$ $\textstyle \equiv$ $\displaystyle {f(x_2)\over f(x_3)}$ (5)
$\displaystyle S$ $\textstyle \equiv$ $\displaystyle {f(x_2)\over f(x_1)}$ (6)
$\displaystyle T$ $\textstyle \equiv$ $\displaystyle {f(x_1)\over f(x_3)}$ (7)

(Press et al. 1992).


References

Brent, R. P. Ch. 3-4 in Algorithms for Minimization Without Derivatives. Englewood Cliffs, NJ: Prentice-Hall, 1973.

Forsythe, G. E.; Malcolm, M. A.; and Moler, C. B. §7.2 in Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Van Wijngaarden-Dekker-Brent Method.'' §9.3 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 352-355, 1992.




© 1996-9 Eric W. Weisstein
1999-05-26