BROYDEN'S METHOD

In mathematics, 'Broyden's method' is a quasi-Newton method for the numerical solution of nonlinear equations in more than one variable. It was originally described by C. G. Broyden in 1965.^[1]
Newton's method for solving the equation $displaystyle\; f(x)\; =\; 0$ uses the Jacobian $displaystyle\; J$ at every iteration. However, computing this Jacobian is a difficult and expensive operation. The idea behind Broyden's method is to compute the whole Jacobian only at the first iteration, and to do a rank-one update at the other iterations.
In 1979 Gay proved that when Broyden's method is applied to a linear system, it
terminates in ''2n'' steps ^[2].

Contents

Description of the method

See also

References

External links

Description of the method

Broyden's method is a generalization of the secant method to multiple dimensions. The secant method replaces the first derivative $displaystyle\; f\text{'}(x\_n)$ with the finite difference approximation:
:
and proceeds in the Newton's direction:
:
Broyden gives a generalization of this formula to a system of equations $displaystyle\; F(x)=0$, replacing the derivative $displaystyle\; f\text{'}$ with the Jacobian $displaystyle\; J$. The Jacobian is determined using the 'secant equation' (using the finite different approximation):
:$J\_n\; cdot\; (x\_n-x\_\{n-1\})simeq\; F(x\_n)-F(x\_\{n-1\}).$
However this equation is under determined in more than one dimension. Broyden suggests using the current estimate of the Jacobian $displaystyle\; J\_\{n-1\}$ and improving upon it by taking the solution to the secant equation that is a minimal modification to $J\_\{n-1\}$:
:
then proceeds in the Newton's direction:
:$x\_\{n+1\}=x\_n-J\_n^\{-1\}F(x\_n).$
Broyden also suggested using the Sherman-Morrison formula to upgrade directly the inverse of the Jacobian
(bad Broyden's method):
:
Many other quasi-Newton schemes have been suggested in optimization, where one seeks a maximum or minimum by finding the root of the first derivative (gradient in multi dimensions). The Jacobian of the gradient is called Hessian and is symmetric, adding further constraints to its upgrade.

See also

★ Secant method

★ Newton's method

★ Quasi-Newton method

★ Newton's method in optimization

References

1. A Class of Methods for Solving Nonlinear Simultaneous Equations, , C. G., Broyden, Mathematics of Computation,
2. Some convergence properties of Broyden's method, , D.M., Gay, SIAM Journal of Numerical Analysis,

External links

★ Module for Broyden's Method by John H. Mathews