Brent's Method

Brent's method is 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 is implemented in the Wolfram Language as the undocumented option Method -> Brent in FindRoot[eqn, x, x0, x1].

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 , , and , Brent's method fits as a quadratic function of , then uses the interpolation formula

(1)

Subsequent root estimates are obtained by setting , giving

(2)

where

			(3)
			(4)

with

			(5)
			(6)
			(7)

(Press et al. 1992).

Wolfram Web Resources