Broyden's Method Algorithm

Broyden's method is a quasi-Newton algorithm for finding the roots of a system of several nonlinear equations at once, built to avoid the expense of calculating a full Jacobian matrix, the matrix of all the system's partial derivatives, at every single iteration. Instead, it computes the Jacobian exactly at most once, at the very first step, and then updates an approximation of it on each later iteration using a cheap rank-one adjustment derived from how the function's output changed between steps. Charles Broyden first described the method in 1965 as a practical middle ground between Newton's method, which is accurate but expensive per iteration, and cruder approximation schemes; a later result proved by Gay in 1979 showed that when applied to a genuinely linear system of a given size, Broyden's method is guaranteed to converge in at most twice that many steps.