Background

    Newton's method can be used to solve systems of nonlinear equations.

Theorem (Newton-Raphson Method for 2-dimensional Systems).  To solve the non-linear system  ,  given one initial approximation  ,  and generating a sequence    which converges to the solution  ,  i.e.  .   Suppose that    has been obtained, use the following steps to obtain  .  

Step 1.     Evaluate the function   .

Step 2.  Evaluate the Jacobian   .  

Step 3.  Solve the linear system      for   .  

Step 4.  Compute the next approximation   .  

Proof  Nonlinear Systems  

More Background

    A drawback of Newton's method is the requirement that the Jacobian matrix be computed, which requires the calculation of    partial derivatives per iteration.  One obvious improvement is to use a finite difference approximation for the Jacobian matrix.  For two dimensions this is

        
where h is small.  Notice that this will require    function evaluations.  

Exploration

Broyden's Method

    Calculation of the Jacobian matrix requires    partial derivative evaluations and the approximate Jacobian matrix requires function evaluations.  Hence, a more computationally efficient method is desired.  Broyden's method is a least change secant update method or quasi-Newton method.  Recall the one-dimensional case of Newton's method for solving  . The secant method replaces the derivative    with the difference quotient  

          

          

The extension to higher dimensions is made by using the basic property of the Jacobian    to write the equation

        .  

Broyden's method starts initially with the Jacobian matrix  .  Then in successive iterations uses an update the approximate Jacobian with the matrix  :  

          for  .  

This equation is known as the quasi-Newton condition or secant condition.  Recall that two initial two values    are necessary to start the secant method.  In practice we are given one starting value and compute the Jacobian    and use Newton's method to get the first approximation  .  The following result gives the details of Broyden's method.

Theorem (Broyden's Method for 2-dimensional Systems).  To solve the non-linear system  ,  given one initial approximation  ,  and generating a sequence    which converges to the solution  ,  i.e.  .  

Step 0.     Compute the initial Jacobian matrix  

        .  

Use it to compute the first approximation using Newton's method  

        .  

For  .  Suppose that    has been obtained, use the following steps to obtain  .  

Step 1.     Evaluate the function   .

Step 2.  Update the approximate Jacobian using     and   

          

Step 3.  Solve the linear system      for   .  

Step 4.  Compute the next approximation   .  

Proof .

Improving Broyden's Method

    Matrix inversion requires    calculations.  Thus we seek a way to avoid this time consuming step.  A matrix inversion formula of Sherman and Morrison can facilitate in making a more efficient algorithm.  Except for , no matrix inverse or solution of a linear system computation is performed in the general step.  This is efficient when n is large.  

Theorem (Sherman-Morrison Formula).  If    is a nonsingular matrix and    are vectors such that  ,  then  

          
    or
        .  

Theorem (Broyden's Method for n-dimensional Systems).  To solve the non-linear system  ,  given one initial approximation  ,  and generating a sequence    which converges to the solution  ,  i.e.  .  Compute the initial Jacobian matrix  

        .  

Use it to compute the first approximation using Newton's method  

        .  

For  .  Suppose that    has been obtained, use the following steps to obtain  .  

Step 1.     Evaluate the function  .  

Step 2.  Update the approximate Jacobian using  ,  and  

        .   

Step 3.  Compute    using the Sherman-Morrison formula

          

Step 4.  Compute the next approximation   

        .  

Remark.

References

    The details regarding the proof are given in the articles below.

A Class of Methods for Solving Nonlinear Simultaneous Equations  
C. G. Broyden  
Mathematics of Computation, Vol. 19, No. 92. (Oct., 1965), pp. 577-593, Jstor.  

Software Libraries for Linear Algebra Computations on High Performance Computers  
Jack J. Dongarra; David W. Walker  
SIAM Review, Vol. 37, No. 2. (Jun., 1995), pp. 151-180, Jstor.  

(c) John H. Mathews 2005