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  

Computer Programs  Nonlinear Systems  

Mathematica Subroutine (Newton's Method for Systems in n-Dimensions).

Example 1.  Use Newton's method to solve the nonlinear system  

            

Solution 1.

Exercise 2.  Observe that the subroutine NewtonSystem involves vector functions and is not dependent on the dimension.
Use the subroutine NewtonSystem to solve the nonlinear system in 3D space:  

           
          
          
    
Hint.  There are four solutions.  Good starting vectors are  .  

Solution 2.

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

Mathematica Subroutine (PseudoNewton's Method for Systems in n-Dimensions).

Example 3.  Use the Pseudo-Newton's method to solve the nonlinear system  

            

Solution 3.

Exercise 4.  Observe that the subroutine PseudoNewtonSystem involves vector functions and is not dependent on the dimension.
Use the subroutine NewtonSystem to solve the nonlinear system in 3D space:  

           
          
          
    
Hint.  There are four solutions.  Good starting vectors are  .  

Solution 4.

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 Broyden's Method  

Computer Programs Broyden's Method  

Mathematica Subroutine (Broyden's Method for Systems in n-Dimensions).

Example 5.  Use the Broyden's method to solve the nonlinear system  

            

Solution 5.

Exercise 6.  Observe that the subroutine Broyden involves vector functions and is not dependent on the dimension.
Use the subroutine Broyden to solve the nonlinear system in 3D space:  

           
          
          
    
Hint.  There are four solutions.  Good starting vectors are  .  

Solution 6.

Exercise 7.  Observe that the subroutine Broyden involves vector functions and is not dependent on the dimension.
Use the subroutine Broyden to solve the nonlinear system in 4D space:  

           
          
           
          
    
Hint.  There is one real solutions.  A good starting vectors is  .  

Solution 7.

Improving Broyden's Method

    Matrix inversion requires    calculations.  Thus we seek a way to avoid this time consuming step each time an iteration is performed.  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   

        .  

Proof Broyden's Method  

Mathematica Subroutine (Improved Broyden's Method for Systems in n-Dimensions).

Example 8.  Use the improved Broyden's method to solve the nonlinear system  

            

Solution 8.

Exercise 9.  Observe that the subroutine ImprovedBroyden involves vector functions and is not dependent on the dimension.
Use the subroutine ImprovedBroyden to solve the nonlinear system in 3D space:  

           
          
          
    
Hint.  There are four solutions.  Good starting vectors are  .  

Solution 9.

Exercise 10.  Observe that the subroutine ImprovedBroyden involves vector functions and is not dependent on the dimension.
Use the subroutine ImprovedBroyden to solve the nonlinear system in 4D space:  

           
          
           
          
    
Hint.  There is one real solutions.  A good starting vectors is  .  

Solution 10.

Research Experience for Undergraduates

Broyden's Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Broyden's Method

(c) John H. Mathews 2005