Module

for

Broyden's Method

 

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  [Graphics:Images/BroydenMethodMod_gr_1.gif],  given one initial approximation  [Graphics:Images/BroydenMethodMod_gr_2.gif],  and generating a sequence  [Graphics:Images/BroydenMethodMod_gr_3.gif]  which converges to the solution  [Graphics:Images/BroydenMethodMod_gr_4.gif],  i.e.  [Graphics:Images/BroydenMethodMod_gr_5.gif].   Suppose that  [Graphics:Images/BroydenMethodMod_gr_6.gif]  has been obtained, use the following steps to obtain  [Graphics:Images/BroydenMethodMod_gr_7.gif].  

Step 1.     Evaluate the function   [Graphics:Images/BroydenMethodMod_gr_8.gif].

Step 2.  Evaluate the Jacobian   [Graphics:Images/BroydenMethodMod_gr_9.gif].  

Step 3.  Solve the linear system   [Graphics:Images/BroydenMethodMod_gr_10.gif]   for   [Graphics:Images/BroydenMethodMod_gr_11.gif].  

Step 4.  Compute the next approximation   [Graphics:Images/BroydenMethodMod_gr_12.gif].  

Proof Nonlinear Systems  

 

Computer Programs  Nonlinear Systems  

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

[Graphics:Images/BroydenMethodMod_gr_13.gif]

 

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

        [Graphics:Images/BroydenMethodMod_gr_14.gif]    

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:  

        [Graphics:Images/BroydenMethodMod_gr_41.gif]   
        [Graphics:Images/BroydenMethodMod_gr_42.gif]  
        [Graphics:Images/BroydenMethodMod_gr_43.gif]  
    
Hint.  There are four solutions.  Good starting vectors are  [Graphics:Images/BroydenMethodMod_gr_44.gif].  

Solution 2.

 

More Background

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

        [Graphics:Images/BroydenMethodMod_gr_72.gif]
where h is small.  Notice that this will require  [Graphics:Images/BroydenMethodMod_gr_73.gif]  function evaluations.  

Exploration

 

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

[Graphics:Images/BroydenMethodMod_gr_88.gif]

 

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

        [Graphics:Images/BroydenMethodMod_gr_89.gif]    

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:  

        [Graphics:Images/BroydenMethodMod_gr_115.gif]   
        [Graphics:Images/BroydenMethodMod_gr_116.gif]  
        [Graphics:Images/BroydenMethodMod_gr_117.gif]  
    
Hint.  There are four solutions.  Good starting vectors are  [Graphics:Images/BroydenMethodMod_gr_118.gif].  

Solution 4.

 

Broyden's Method

    Calculation of the Jacobian matrix requires  
[Graphics:Images/BroydenMethodMod_gr_178.gif]  partial derivative evaluations and the approximate Jacobian matrix requires [Graphics:Images/BroydenMethodMod_gr_179.gif] 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  [Graphics:Images/BroydenMethodMod_gr_180.gif]. The secant method replaces the derivative  [Graphics:Images/BroydenMethodMod_gr_181.gif]  with the difference quotient  

        
[Graphics:Images/BroydenMethodMod_gr_182.gif]  

        [Graphics:Images/BroydenMethodMod_gr_183.gif]  

The extension to higher dimensions is made by using the basic property of the Jacobian  [Graphics:Images/BroydenMethodMod_gr_184.gif]  to write the equation

        [Graphics:Images/BroydenMethodMod_gr_185.gif].  

Broyden's method starts initially with the Jacobian matrix  
[Graphics:Images/BroydenMethodMod_gr_186.gif].  Then in successive iterations uses an update the approximate Jacobian with the matrix  [Graphics:Images/BroydenMethodMod_gr_187.gif]:  

        
[Graphics:Images/BroydenMethodMod_gr_188.gif]  for  [Graphics:Images/BroydenMethodMod_gr_189.gif].  

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

 

Theorem (Broyden's Method for 2-dimensional Systems).  To solve the non-linear system  [Graphics:Images/BroydenMethodMod_gr_194.gif],  given one initial approximation  [Graphics:Images/BroydenMethodMod_gr_195.gif],  and generating a sequence  [Graphics:Images/BroydenMethodMod_gr_196.gif]  which converges to the solution  [Graphics:Images/BroydenMethodMod_gr_197.gif],  i.e.  [Graphics:Images/BroydenMethodMod_gr_198.gif].  

Step 0.     Compute the initial Jacobian matrix  

        
[Graphics:Images/BroydenMethodMod_gr_199.gif].  

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

        [Graphics:Images/BroydenMethodMod_gr_200.gif].  

For  [Graphics:Images/BroydenMethodMod_gr_201.gif].  Suppose that  [Graphics:Images/BroydenMethodMod_gr_202.gif]  has been obtained, use the following steps to obtain  [Graphics:Images/BroydenMethodMod_gr_203.gif].  

Step 1.     Evaluate the function   [Graphics:Images/BroydenMethodMod_gr_204.gif].

Step 2.  Update the approximate Jacobian using   [Graphics:Images/BroydenMethodMod_gr_205.gif]  and   [Graphics:Images/BroydenMethodMod_gr_206.gif]

        [Graphics:Images/BroydenMethodMod_gr_207.gif]  

Step 3.  Solve the linear system   [Graphics:Images/BroydenMethodMod_gr_208.gif]   for   [Graphics:Images/BroydenMethodMod_gr_209.gif].  

Step 4.  Compute the next approximation   [Graphics:Images/BroydenMethodMod_gr_210.gif].  

Proof Broyden's Method  

 

Computer Programs Broyden's Method  

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

[Graphics:Images/BroydenMethodMod_gr_211.gif]

[Graphics:Images/BroydenMethodMod_gr_212.gif]

 

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

        [Graphics:Images/BroydenMethodMod_gr_213.gif]    

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:  

        [Graphics:Images/BroydenMethodMod_gr_242.gif]   
        [Graphics:Images/BroydenMethodMod_gr_243.gif]  
        [Graphics:Images/BroydenMethodMod_gr_244.gif]  
    
Hint.  There are four solutions.  Good starting vectors are  [Graphics:Images/BroydenMethodMod_gr_245.gif].  

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:  

        [Graphics:Images/BroydenMethodMod_gr_286.gif]   
        [Graphics:Images/BroydenMethodMod_gr_287.gif]  
        [Graphics:Images/BroydenMethodMod_gr_288.gif]   
        [Graphics:Images/BroydenMethodMod_gr_289.gif]  
    
Hint.  There is one real solutions.  A good starting vectors is  [Graphics:Images/BroydenMethodMod_gr_290.gif].  

Solution 7.

 

Improving Broyden's Method

    Matrix inversion requires  [Graphics:Images/BroydenMethodMod_gr_634.gif]  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 [Graphics:Images/BroydenMethodMod_gr_635.gif], 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  [Graphics:Images/BroydenMethodMod_gr_636.gif]  is a nonsingular matrix and  [Graphics:Images/BroydenMethodMod_gr_637.gif]  are vectors such that  [Graphics:Images/BroydenMethodMod_gr_638.gif],  then  

        [Graphics:Images/BroydenMethodMod_gr_639.gif]  
    or
        [Graphics:Images/BroydenMethodMod_gr_640.gif].  

 

Theorem (Broyden's Method for n-dimensional Systems).  To solve the non-linear system  [Graphics:Images/BroydenMethodMod_gr_641.gif],  given one initial approximation  [Graphics:Images/BroydenMethodMod_gr_642.gif],  and generating a sequence  [Graphics:Images/BroydenMethodMod_gr_643.gif]  which converges to the solution  [Graphics:Images/BroydenMethodMod_gr_644.gif],  i.e.  [Graphics:Images/BroydenMethodMod_gr_645.gif].  Compute the initial Jacobian matrix  

        
[Graphics:Images/BroydenMethodMod_gr_646.gif].  

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

        [Graphics:Images/BroydenMethodMod_gr_647.gif].  

For  [Graphics:Images/BroydenMethodMod_gr_648.gif].  Suppose that  [Graphics:Images/BroydenMethodMod_gr_649.gif]  has been obtained, use the following steps to obtain  [Graphics:Images/BroydenMethodMod_gr_650.gif].  

Step 1.     Evaluate the function  [Graphics:Images/BroydenMethodMod_gr_651.gif].  

Step 2.  Update the approximate Jacobian using  [Graphics:Images/BroydenMethodMod_gr_652.gif],  and  [Graphics:Images/BroydenMethodMod_gr_653.gif]

        [Graphics:Images/BroydenMethodMod_gr_654.gif].   

Step 3.  Compute  [Graphics:Images/BroydenMethodMod_gr_655.gif]  using the Sherman-Morrison formula

        [Graphics:Images/BroydenMethodMod_gr_656.gif]  

Step 4.  Compute the next approximation   

        [Graphics:Images/BroydenMethodMod_gr_657.gif].  

Proof Broyden's Method  

 

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

[Graphics:Images/BroydenMethodMod_gr_658.gif]

[Graphics:Images/BroydenMethodMod_gr_659.gif]

 

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

        [Graphics:Images/BroydenMethodMod_gr_660.gif]    

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:  

        [Graphics:Images/BroydenMethodMod_gr_683.gif]   
        [Graphics:Images/BroydenMethodMod_gr_684.gif]  
        [Graphics:Images/BroydenMethodMod_gr_685.gif]  
    
Hint.  There are four solutions.  Good starting vectors are  [Graphics:Images/BroydenMethodMod_gr_686.gif].  

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:  

        [Graphics:Images/BroydenMethodMod_gr_718.gif]   
        [Graphics:Images/BroydenMethodMod_gr_719.gif]  
        [Graphics:Images/BroydenMethodMod_gr_720.gif]   
        [Graphics:Images/BroydenMethodMod_gr_721.gif]  
    
Hint.  There is one real solutions.  A good starting vectors is  [Graphics:Images/BroydenMethodMod_gr_722.gif].  

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