Broyden's method

In numerical analysis, Broyden's method is a quasi-Newton method for finding roots in k variables. It was originally described by C. G. Broyden in 1965. In numerical analysis, Broyden's method is a quasi-Newton method for finding roots in k variables. It was originally described by C. G. Broyden in 1965. Newton's method for solving f(x) = 0 uses the Jacobian matrix, 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 rank-one updates at other iterations. In 1979 Gay proved that when Broyden's method is applied to a linear system of size n × n, itterminates in 2 n steps, although like all quasi-Newton methods, it may not converge for nonlinear systems. In the secant method, we replace the first derivative f′ at xn with the finite-difference approximation: and proceed similar to Newton's method: where n is the iteration index. Consider a system of k nonlinear equations where f is a vector-valued function of vector x: For such problems, Broyden gives a generalization of the one-dimensional Newton's method, replacing the derivative with the Jacobian J. The Jacobian matrix is determined iteratively, based on the secant equation in the finite-difference approximation: