Broyden's method

From Wikipedia, the free encyclopedia

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].

1 Description of the method
2 See also
3 References
4 External links

[edit] 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'(x_n)$ with the finite difference approximation:

$f'(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'(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'$ 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$ :

$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.

[edit] See also

[edit] References

^ Broyden, C. G. (October 1965). "A Class of Methods for Solving Nonlinear Simultaneous Equations". Mathematics of Computation 19 (92): 577–593. American Mathematical Society. doi:10.2307/2003941.
^ Gay, D.M. (August 1979). "Some convergence properties of Broyden's method". SIAM Journal of Numerical Analysis 16 (4): 623–630. SIAM. doi:10.1137/0716047.