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.

Description of the method

Solving single-variable equation

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.

Solving a system of nonlinear equations

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{\mathrm{\Delta <!--\; \Delta \; -->}{\mathbf{x}}_n-<!--\; -\; -->{\mathbf{J}}_{n-<!--\; -\; -->1}^{}}{}}$Zdroj:https://en.wikipedia.org?pojem=Broyden's_method
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---