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.^[1]

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 at most 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, it terminates in 2 n steps,^[2] although like all quasi-Newton methods, it may not converge for nonlinear systems.

In the secant method, we replace the first derivative f′ at x_n with the finite-difference approximation:

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},}$

and proceed similar to Newton's method:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}}$

where n is the iteration index.

Consider a system of k nonlinear equations

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

where f is a vector-valued function of vector x:

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

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:

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),}$

where n is the iteration index. For clarity, let us define:

${\displaystyle \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},}$

so the above may be rewritten as

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

The above equation is underdetermined when k is greater than one. Broyden suggests using the current estimate of the Jacobian matrix J_n−1 and improving upon it by taking the solution to the secant equation that is a minimal modification to J_n−1:

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.}$

This minimizes the following Frobenius norm:

${\displaystyle \|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.}$

We may then proceed in the Newton direction:

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).}$

Broyden also suggested using the Sherman–Morrison formula to update directly the inverse of the Jacobian matrix:

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

This first 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 a second method, the so-called "bad Broyden's method" (but see^[3]):

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

This minimizes a different Frobenius norm:

${\displaystyle \|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.}$

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 multiple dimensions). The Jacobian of the gradient is called Hessian and is symmetric, adding further constraints to its update.

In addition to the two methods described above, Broyden defined a whole class of related methods.^[1]: 578 In general, methods in the Broyden class are given in the form^[4]: 150 $${\displaystyle \mathbf {J} _{k+1}=\mathbf {J} _{k}-{\frac {\mathbf {J} _{k}s_{k}s_{k}^{T}\mathbf {J} _{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{T}\mathbf {J} _{k}s_{k}\right)v_{k}v_{k}^{T},}$$ where ${\displaystyle y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),}$ ${\displaystyle s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},}$ and $${\displaystyle v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right],}$$ and ${\displaystyle \phi _{k}\in \mathbb {R} }$ for each ${\displaystyle k=1,2,...}$. The choice of ${\displaystyle \phi _{k}}$ determines the method.

Other methods in the Broyden class have been introduced by other authors.

• The Davidon–Fletcher–Powell (DFP) method is the only member of this class being published before the two methods defined by Broyden.^[1]: 582 For the DFP method, ${\displaystyle \phi _{k}=1}$.^[4]: 150
• Schubert's or sparse Broyden algorithm – a modification for sparse Jacobian matrices.^[5]
• Klement (2014) – uses fewer iterations to solve many equation systems.^[6][7]

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

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN 0-13-627216-9.
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5.

• Simple basic explanation: The story of the blind archer