Broyden's Method

The extension to higher dimensions is made by using the basic property of the Jacobianto 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 valuesare necessary to start the secant method.In practice we are given one starting value and compute the Jacobianand 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 sequencewhich 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 thathas been obtained, use the following steps to obtain.

Step 1.Evaluate the function.

Step 2.Update the approximate Jacobian usingand



Step 3.Solve the linear systemfor.

Step 4.Compute the next approximation.

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

Improving Broyden's Method

Matrix inversion requirescalculations.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 ).Ifis a nonsingular matrix andare 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 sequencewhich converges to the solution,i.e..Compute the initial Jacobian matrix

.

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

.

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

Step 1.Evaluate the function.

Step 2.Update the approximate Jacobian using,and

.

Step 3.Computeusing the Sherman-Morrison formula



Step 4.Compute the next approximation

.

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