Broyden's method

In numerical analysis, Broyden's method is a quasi-Newton method for the root-finding algorithm in k variables. It was originally described by C. G. Broyden in 1965.

Newton's method for solving the equation $\displaystyle f(x) = 0$ uses the Jacobian matrix and determinant, $\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 of size n x n, it terminates in 2n steps.

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 similar to Newton's Method:

$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 difference 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}$ (minimal in the sense of minimizing the Frobenius norm $\displaystyle \|J_{n} - J_{n-1}\|_{F}$):

$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 direction:

$x_{n+1}=x_n-J_n^{-1}F(x_n).$

In the formula above $\displaystyle x_n=(x_1[n],...,x_k[n])$ and $\displaystyle F_n(x)=(f_1(x_1[n],...,x_k[n]),...,f_k(x_1[n],...,x_k[n]))$ are vector-columns with $k$ elements for a system with k-dimensions. This way:

$\Delta x_n=\begin{bmatrix} x_1[n]-x_1[n-1]\\ ...\\ x_k[n]-x_k[n-1] \end{bmatrix} \quad \text{and} \quad \Delta F_n=\begin{bmatrix} f_1(x_1[n],...,x_k[n])-f_1(x_1[n-1],...,x_k[n-1])\\ ...\\ f_k(x_1[n],...,x_k[n])-f_k(x_1[n-1],...,x_k[n-1]) \end{bmatrix}.$

Broyden also suggested using the Sherman-Morrison formula to update 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}$ (which minimizes $\displaystyle \|J^{-1}_{n} - J^{-1}_{n-1}\|_{F}$ instead); this yields the so-called "bad Broyden's method" (but see ):

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

See also

• Secant method
• Newton's method
• Quasi-Newton method
• Newton's method in optimization
• Davidon-Fletcher-Powell formula
• Broyden-Fletcher-Goldfarb-Shanno (BFGS) method

External links

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