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

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  .  

Remark.  An efficient computation for is the following equivalent procedure:

      
    
    for    .

Proof

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.  

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  

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  

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.  

Bisection Method Part of Brent's Method

    The following portions of the Mathematica code in  BrentMethod  will perform one step of the Bisection Method.

The next part of the subroutine in this thread is:
If     evaluates true, then

The next part of the subroutine in this thread is:
If     evaluates true, then    evaluates as    

Regula Falsi or Linear Interpolation part of Brent's Method

    The following portions of the Mathematica code in  BrentMethod  will perform one step of the Regula-Falsi Method.

Inverse Quadratic Interpolation Part of Brent's Method

    Brent's method uses a slightly different, computation.  Using the notation  ,  we use Mathematica to establish that it is equivalent.  The following portions of the Mathematica code in  BrentMethod  will perform one step of the Inverse Quadratic Interpolation Method.

References

    The details regarding the proof and the original ALGOL 60 procedure are given in the book and article below.

1. An algorithm with guaranteed convergence for finding a zero of a function
   R. P. Brent
   Computer Journal, 14 (1971) 422-425.
2. Algorithms for Minimization Without Derivatives  
   Brent, R.  
   Prentice-Hall, 1973.

(c) John H. Mathews 2005