Overview

Broyden's method [14] approximates the Newton direction by using an approximation of the Jacobian (or its inverse), which is updated as the nonlinear iteration progresses. The cost of this updating in the modern implementation we advocate here is one vector for each nonlinear iteration. Contrast this cost to Newton-GMRES, where the storage is accumulated during a linear iteration. For a problem where the initial iterate is far from a solution and the number of nonlinear iterations will be large, this is a significant disadvantage for Broyden's method. Broyden's method, like the secant method for scalar equations, does not guarantee that the approximate Newton direction will be a descent direction for F and therefore a line search may fail. For these reasons, the Newton Krylov methods are now (2003) used more frequently than Broyden's method. Having said that, when the initial iterate is near the solution, Broyden's method can perform very well.

Broyden's method usually requires preconditioning to perform well, so the decisions you will make are the same as those for a Newton Krylov method.

Broyden's method is the simplest of the quasi-Newton methods. These methods are extensions of the secant method to several variables. Recall that the secant method approximates f ?( x _n) with

and then takes the step

One way to mimic this in higher dimensions is to carry an approximation to the Jacobian along with the approximation to x* and update the approximate Jacobian as the iteration progresses. The formula...