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. [cite journal
last = Broyden
first = C. G.
title = A Class of Methods for Solving Nonlinear Simultaneous Equations
journal = Mathematics of Computation
volume = 19
issue = 92
pages = 577–593
publisher = American Mathematical Society
date = October 1965
url = http://links.jstor.org/sici?sici=0025-5718%28196510%2919%3A92%3C577%3AACOMFS%3E2.0.CO%3B2-B
accessdate = 2007-04-29
month = Oct
year = 1965
doi = 10.2307/2003941 ]

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 [cite journal
last = Gay
first = D.M.
title = Some convergence properties of Broyden's method
journal = SIAM Journal of Numerical Analysis
volume = 16
issue = 4
pages = 623–630
publisher = SIAM
date = August 1979
doi = 10.1137/0716047] .

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::$f\text{'}(x\_n)\; simeq\; frac\; \{f(x\_n)-f(x\_\{n-1\})\}\{x\_n-x\_\{n-1\}\; \},$ and proceeds in the Newton's direction::$x\_\{n+1\}=x\_n-frac\{1\}\{f\text{'}(x\_n)\}\; f(x\_n)\; .$ 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 $displaystyle\; J\_\{n-1\}$::$J\_n=J\_\{n-1\}+frac\{Delta\; F\_n-J\_\{n-1\}\; Delta\; x\_n\}\{||Delta\; x\_n||^2\}\; Delta\; x^T\_n$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::$J\_n^\{-1\}=J\_\{n-1\}^\{-1\}+frac\{Delta\; x\_n-J^\{-1\}\_\{n-1\}\; Delta\; F\_n\}\{Delta\; x\_n^T\; J^\{-1\}\_\{n-1\}Delta\; F\_n\}\; (Delta\; x\_n^T\; J^\{-1\}\_\{n-1\})$This method is commonly known as the "good Broyden's method". A similar technique can be derived by using a slightly different modification to $J\_\{n-1\}$ ; this yields the so-called "bad Broyden's method"::$J\_n^\{-1\}=J\_\{n-1\}^\{-1\}+frac\{Delta\; x\_n-J^\{-1\}\_\{n-1\}\; Delta\; F\_n\}\{Delta\; F\_n^T\; Delta\; F\_n\}\; Delta\; F\_n^T$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.

ee also

*Secant method
*Newton's method
*Quasi-Newton method
*Newton's method in optimization

References

External links

* [http://math.fullerton.edu/mathews/n2003/BroydenMethodMod.html Module for Broyden's Method by John H. Mathews]