Brent's Method

Mathematica Subroutine (Secant Method).

Theorem (Inverse Quadratic Method).Assume that and there exists a number , where .If , then there exists a such that the sequence defined by the iteration





forwill converge to for certain initial approximations.

Algorithm ( Inverse Quadratic Method ).Find a root ofgiven three initial approximationsusing the iteration



for.

Mathematica Subroutine (Inverse Quadratic Method).

The computation ofis seen to require 12 function evaluations (because occurs 13 times).This number can be reduced to 3 function evaluations per iteration by using the following "algebraic trick."

Algorithm ( Inverse Quadratic Method ).Find a root ofgiven three initial approximationsiteration.When the code in the above subroutine is executed the computation ofis seen to require 13 function evaluations.(because occurs 13 times).The number of function evaluations can by using the following scheme.



for.

Mathematica Subroutine (Inverse Quadratic Method).Efficient version that uses only 3 function evaluations per iteration.

More Background

We will now review some root bracketing methods.The regula falsi method usually converge faster than the bisection method bisection.However, examples can be found when the bisection method converges faster.To speed things up, Brent included inverse quadratic interpolation and his method combines the root bracketing methods: bisection, regula falsi; and inverse quadratic interpolation methods.

Theorem ( Bisection Method ). Assume that and that there exists a number such that .If have opposite signs, and represents the sequence of midpoints generated by the bisection process, then

for,

and the sequence converges to the zero.

That is,.

Mathematica Subroutine (Bisection Method).

Theorem ( Regula Falsi Method ). Assume that and that there exists a number such that .
If have opposite signs, and



represents the sequence of points generated by the Regula Falsi process, then the sequence converges to the zero.

That is,.

Mathematica Subroutine (Regula Falsi Method).

Brent's Method

The secant method and inverse quadratic interpolation method can be used to find a rootof the function.Combining these methods and making variations which include inverse interpolation have been presented by A. van Wijngaarden, J. A. Zonneveld and E. W. Dijkstra (1963), J. H. Wilkinson (1967), G. Peters and J. H. Wilkinson (1969), T. J. Dekker (1969) and were improved by R. P. Brent (1971).

Brent's method can be used to find a rootprovided thathave opposite signs.At a typical step we have three pointssuch that,and the pointamay coincide with the pointc.The pointschange during the algorithm, and the root always lies in eitheror.The valuebis the best approximation to the root andais the previous value ofb.The method uses a combination of three methods: bisection, regula falsi, and inverse quadratic interpolation.It is difficult to see how each of these ideas are incorporated into the subroutine.To assist with locating the lines that must be used in logical sequence some of the lines have been color coded.But some lines are used in more than one method so look carefully at the subroutine and the portions listed below.

The Brent subroutine will find the rootof the functionin the intervalto within a tolerancewhereis a positive tolerance and.

Algorithm (Brent's Method).Find a rootpofgiven initial bracketing intervalwhere must have opposite signs.At a typical step we have three pointssuch that,andamay coincide withc.The points change during the algorithm, and the root always lies in eitheror.The valuebis the best approximation to the root andais the previous value ofb.The iteration uses a combination oftechniques:

(i)The Bisection Method

,or

(ii)Regula Falsi Method

,or

(iii) Quadratic Interpolation

Mathematica Subroutine (Brent's Method).