Brent’s method is an algorithm in numerical analysis for finding a zero of a real-valued function within an interval whose endpoints have opposite function signs. It combines the reliability of the bisection method with the speed of the secant method and inverse quadratic interpolation. Interpolation proposes a potentially fast step; safeguards reject unsuitable proposals and replace them with bisection. The method requires function evaluations but no derivatives.
The name also refers to a distinct, closely related algorithm for one-dimensional minimization, which combines parabolic interpolation with golden-section search. Unless the context is optimization, “Brent’s method” usually means the root-finding algorithm.
Root-finding problem and assumptions
The root-finding problem is to determine a number satisfying
Brent’s root-finding method starts with an interval such that is a continuous function on the interval and
By the intermediate value theorem, this interval contains at least one root. If an endpoint already satisfies , it can be returned immediately.
The initial interval is called a bracket. The method preserves a sign-changing bracket as it proceeds, providing an enclosure for at least one root even when interpolation gives poor predictions. It does not require the function to be monotonic or the root to be unique. When several roots lie within the bracket, however, the method does not generally specify which one will be found.
Continuity is essential to the existence guarantee. A discontinuous function can change sign without vanishing: for example, has opposite signs at and , but has no zero between them and is undefined at the origin.
The component methods
Bisection
Bisection evaluates the midpoint
and retains whichever half-interval still brackets a root. After bisection steps, an initial interval of width has width
This reduction is predictable and does not depend on the local shape of the function. Its limitation is that it does not use function magnitudes to accelerate convergence.
Secant interpolation
Given two points with unequal function values, the secant method proposes
This is the zero of the straight line through the two sampled points. Near a sufficiently smooth simple root, secant steps can converge faster than bisection. Used alone, however, they need not remain inside a root bracket and can fail to converge.
Inverse quadratic interpolation
With three points whose function values are distinct, inverse quadratic interpolation fits a quadratic approximation to as a function of . Evaluating that approximation at gives
This is an application of interpolation in which the roles of argument and function value are reversed. Unlike ordinary quadratic interpolation of , it does not require choosing between two roots of a fitted quadratic.
Under suitable smoothness and nondegeneracy assumptions near a simple root, standalone inverse quadratic interpolation has an asymptotic order of convergence of approximately . This describes favorable local behavior of the interpolation process, not an unconditional rate for every run of Brent’s safeguarded algorithm.
How the root-finding algorithm works
Implementations differ in notation and bookkeeping, but the central structure is consistent.
The algorithm maintains:
- two points whose function values have opposite signs;
- a preferred approximation, normally the bracket endpoint with the smaller absolute function value;
- a previous point and information about recent step sizes.
Each iteration proceeds conceptually as follows:
- Check termination. Stop if a function value is zero or the remaining bracket is sufficiently small.
- Construct an interpolation proposal. Use inverse quadratic interpolation when three suitable, distinct function values are available; otherwise use a secant step.
- Apply safeguards. Reject a proposal that is outside the permitted part of the bracket, is too large relative to recent steps, or fails the algorithm’s progress tests.
- Bisect if necessary. When interpolation is rejected, use the bracket midpoint.
- Evaluate the new point. Update the sign-changing bracket and rearrange the stored points as required.
The safeguards are more restrictive than simply requiring the proposed point to lie inside the bracket. An interior proposal can still make almost no progress—for example, by repeatedly landing very close to one endpoint. Brent’s acceptance rules use recent step lengths to prevent such stagnation and force bisection when necessary.
Thus, Brent’s method is not merely an arbitrary alternation between bisection and interpolation. Its defining feature is the controlled acceptance of fast steps within a bracketing framework.
Convergence and stopping criteria
For a continuous function with a valid initial bracket, the safeguarded method converges in exact arithmetic without requiring a good initial approximation to a particular root. This is often called global convergence, meaning convergence from an admissible bracket, not the ability to discover every root or to start from any pair of numbers.
Its speed depends on the function:
- Near a smooth simple root, accepted interpolation steps often produce superlinear convergence.
- When interpolation is unreliable, bisection restores dependable interval reduction.
- Flat, nonsmooth, or poorly resolved functions can cause more frequent fallback steps.
Brent’s method therefore combines a bracketing guarantee with favorable local acceleration. This does not mean that every iteration halves the bracket, or that every implementation always uses no more evaluations than pure bisection.
A common stopping rule combines absolute and relative tolerances, schematically as
The exact constants and interpretation vary between software libraries. If a root remains bracketed, the bracket width supplies a direct bound on positional uncertainty: any point in the bracket is at most its full width from at least one enclosed root, while its midpoint is at most half the width away.
A small residual, , is not by itself a universal guarantee of a small root error. Near a differentiable simple root ,
Consequently, a small derivative can make the root location sensitive even when the residual is small. This connects stopping criteria to the conditioning of the root-finding problem.
Numerical implementation
Several details matter in floating-point arithmetic:
- Sign comparisons: explicitly forming may overflow or underflow. Implementations can instead handle zero values and compare signs directly.
- Interpolation denominators: equal or nearly equal function values can make interpolation undefined or numerically unreliable.
- Representable movement: a proposed increment may be too small to change the current floating-point number. Implementations need a minimum effective step or an appropriate termination test.
- Nonfinite values: infinities and undefined numerical results require explicit handling; the usual convergence assumptions do not cover them.
- Evaluation reuse: storing previously computed function values avoids unnecessary calls, which can dominate the cost of the calculation.
Stable implementations often evaluate algebraically rearranged interpolation expressions rather than the displayed inverse-quadratic formula. Mathematical equivalence does not imply identical numerical stability.
Example
Consider
Since
the interval brackets a root. A secant proposal from these endpoints is
At this point,
so evaluating the proposal gives a narrower sign-changing bracket,
As additional points become available, inverse quadratic interpolation can propose more accurate estimates. Safeguards retain the ability to bisect if those proposals are unsuitable. The root in the original interval is approximately
Exact trial points and iteration counts depend on the implementation and stopping tolerances.
Brent’s minimization method
The optimization algorithm also called Brent’s method seeks a local minimum of a scalar objective function without derivatives. It combines:
- Parabolic interpolation, which fits a quadratic through sampled points and proposes its minimizer;
- Golden-section search, which reduces an interval without relying on an accurate parabolic model.
A typical minimum bracket consists of three ordered points with
A parabolic step is accepted only when its geometry and size satisfy suitable safeguards. Otherwise, the algorithm takes a golden-section step.
This differs fundamentally from root finding: opposite function signs play no role. Bracketing a minimum also does not establish that it is the global minimum over a larger domain. Unimodality—having a single minimum within the search interval—provides the standard setting for reliable interval reduction toward the desired minimizer.
Brent’s minimization method is used in one-dimensional searches and in line searches within larger optimization algorithms. Noise, multiple local minima, and nearly flat objective functions can weaken the usefulness of parabolic interpolation.
History, uses, and limitations
Richard P. Brent developed the root-finding algorithm from earlier hybrid bracketing and interpolation work associated with Theodorus Dekker. Brent described the improved algorithm in a 1971 paper and treated both root finding and derivative-free minimization in his 1973 book Algorithms for Minimization Without Derivatives.
The root-finding method is widely used in scientific software. Examples include SciPy’s brentq and the GNU Scientific Library’s Brent solver. Related routines can use different interpolation formulas or acceptance rules, so the name alone does not specify an identical evaluation sequence.
Typical applications include solving scalar nonlinear equations, inverting monotonic functions, determining threshold crossings, and obtaining distribution quantiles from cumulative probabilities. Compared with Newton’s method, Brent’s method avoids derivative calculations and preserves a root bracket; Newton’s method can be faster locally when accurate derivatives and a suitable initial approximation are available.
Important limitations include:
- A suitable sign-changing bracket must first be found.
- Roots of even multiplicity usually do not change the function’s sign and therefore cannot generally be detected by sign bracketing alone.
- A bracket containing several roots does not identify a particular one.
- Discontinuities can invalidate the root-existence guarantee.
- Noisy or inaccurate function evaluations can corrupt both sign decisions and interpolation.
- The standard method solves a scalar real problem, not a system of nonlinear equations or a general complex root-finding problem.