= Broyden's method
{c}
{title2=$B_{k+1}=B_k+(y_k-B_ks_k)s_k^{\mathsf T}/(s_k^{\mathsf T}s_k)$}
{wiki}
A secant-updating method for a vector equation $F(x)=0$, named for <Charles George Broyden>. Solve $B_kd_k=-F(x_k)$, choose $x_{k+1}=x_k+\alpha_kd_k$, and form $s_k=x_{k+1}-x_k$, $y_k=F(x_{k+1})-F(x_k)$. For a nonzero step the displayed “good Broyden” update satisfies $B_{k+1}s_k=y_k$, learning the <Jacobian matrix> action along the observed step rather than evaluating a new full <Jacobian matrix>.
The update also has a least-change characterization in the <Frobenius norm>. Write $u=y_k-B_ks_k$. Any correction $E$ satisfying $Es_k=u$ has squared row norms bounded below by $u_i^2/\|s_k\|^2$, by the <Cauchy-Schwarz inequality>. Summing these bounds gives $\|E\|_F^2\ge\|u\|^2/\|s_k\|^2$, with equality for $E=us_k^{\mathsf T}/\|s_k\|^2$. This proves the rank-one correction is the least-change update satisfying the secant constraint. <Superlinear convergence> needs local regularity and suitable initialization; it is not a global consequence of this algebraic identity.<A Class of Methods for Solving Nonlinear Simultaneous Equations by Charles George Broyden>[pp. 577–581, motivation and Jacobian-updating construction.]{ref}
Back to article page
