Back to Nonlinear Equations.

Recall that a potential shortcoming of Newton's method for nonlinear equations is that the derivatives required for the Jacobian may not be available or may be difficult to calculate. *Secant methods*, also known as *quasi-Newton* methods, do not require the calculation of the Jacobian; they construct an approximation to the matrix, which is updated at each iteration, so that it behaves similarly to the true Jacobian along the step. *Broyden's method* is the most successful secant-method for solving systems of nonlinear equations.

Let \(B_k\) be the Jacobian approximation at iteration \(k\) and let \(s_k = x_{k+1} - x_k\). Then, the updated Jacobian approximation \(B_{k+1}\) must satisfy the *secant equation*

\[B_{k+1} \, s_k = f(x_{k+1}) - f(x_k). \quad(1) \,\]

Given an initial matrix \(B_0\) (often a finite-difference approximation to the Jacobian matrix), Broyden's method generates subsequent matrices by the update formula

\[B_{k+1} = B_k + \frac{(y_k - B_k s_k)s_k^T} {\|s_k\|_2^2 }, \quad(2) \,\]

where \(y_k = f(x_{k+1}) - f(x_k) \,\).

The remarkable feature of Broyden's method is that it is able to generate a reasonable approximation to the Jacobian matrix with no additional evaluations of the function. This feature is partially explained by noting that, because of equation (1), the updated \(B_{k+1}\) mimics the behavior of the true Jacobian along the line joining \(x_k\) to \(x_{k+1}\).

*Last updated: October 10, 2013*