Brent's Method

Module

for

Background

We start by reviewing the secant method and then extend it to the inverse quadratic interpolation method. Mueller's proposed a method using successive bisection and inverse quadratic interpolation which was extended by Brent's and others. It uses a combination of the bisection, regula falsi, and inverse quadratic interpolation methods.

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





for    will converge to for certain initial approximations  .

Proof Brent's Method

Algorithm (Secant Method). Find a root of given two initial approximations using the iteration

for .

Computer Programs Secant Method

Mathematica Subroutine (Secant Method).

Example 1. Use the secant method to find the three roots of the cubic polynomial .
Show details of the computations for the starting value .

Solution 1.

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





for    will converge to for certain initial approximations  .

Proof Brent's Method

Algorithm (Inverse Quadratic Method).  Find a root of    given three initial approximations    using the iteration



for    .

Mathematica Subroutine (Inverse Quadratic Method).

The computation of is 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 of    given three initial approximations    iteration.  When the code in the above subroutine is executed the computation of    is seen to require 13 function evaluations.   (because occurs 13 times).  The number of function evaluations can by using the following scheme.

     [Graphics:Images/BrentMethodMod_gr_90.gif]

    for    .

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

Example 2. Use the inverse quadratic method to find the three roots of the cubic polynomial .
Show details of the computations for the starting value .

Solution 2.

Example 3. Compare the secant method with the inverse quadratic method for finding the roots of the cubic polynomial .

3 (a) Investigate fast convergence at the simple root .

Solution 3 (a).

3 (b) Investigate slow convergence at the double root .

Solution 3 (b).

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,      .

Proof Bisection Method

Computer Programs Bisection Method

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,      .

Proof False Position or Regula Falsi Method

Computer Programs False Position or Regula Falsi Method

Mathematica Subroutine (Regula Falsi Method).

Brent's Method

    The secant method and inverse quadratic interpolation method can be used to find a root    of 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 root    provided that    have opposite signs.  At a typical step we have three points    such that  ,  and the point  a  may coincide with the point  c.  The points    change during the algorithm, and the root always lies in either    or  .  The value  b  is the best approximation to the root and  a  is the previous value of  b.  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 root    of the function    in the interval    to within a tolerance    where    is a positive tolerance and  .

Algorithm (Brent's Method). Find a root p of given initial bracketing interval where must have opposite signs. At a typical step we have three points such that , and a may coincide with c. The points change during the algorithm, and the root always lies in either or . The value b is the best approximation to the root and a is the previous value of b. The iteration uses a combination of techniques: