Broyden's Method

Definition

Solve $f(x)=0$ using Newton’s Method with approximation of Jacobian Matrix

Algorithm

The essence of Broyden’s method is to approximate Jacobian Matrix of Newton’s Method using the average rate of change

Replace derivative $f^{\prime }(x_n)\simeq \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$ or gradient with an approximation ${\nabla }^{2}f({\mathbf{x}}_n)\simeq J_n$ Then, $J_n\cdot ({\mathbf{x}}_n-{\mathbf{x}}_{n-1})\simeq f({\mathbf{x}}_n)-f({\mathbf{x}}_{n-1})$

Define ${\mathbf{f}}_n:=f({\mathbf{x}}_n)$ $\Delta {\mathbf{f}}_n:={\mathbf{f}}_n-{\mathbf{f}}_{n-1}$ $\Delta {\mathbf{x}}_n:={\mathbf{x}}_n-{\mathbf{x}}_{n-1}$ $J_n\simeq {\nabla }^{2}f(x)$

Then, ${\mathbf{J}}_{\mathbf{n}}\Delta {\mathbf{x}}_n\simeq \Delta {\mathbf{f}}_n$

We want to find $A$ satisfying the following expression $J_n=J_{n-1}+A$ $\Rightarrow \Delta {\mathbf{f}}_n=(J_{n-1}+A)\Delta {\mathbf{x}}_n=J_{n-1}\Delta {\mathbf{x}}_n+A\Delta {\mathbf{x}}_n\Rightarrow \Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n=A\Delta {\mathbf{x}}_n$ by above approximation

To ensure stability of update, take a minimum modification $J_{n-1}$ In other words, solve the minimization problem using method of Lagrange multipliers $\min ||A|{|}_F=||J_n-J_{n-1}|{|}_F$ subject to $\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n=A\Delta {\mathbf{x}}_n$

Then, the solution is $A=\frac{\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n}{||\Delta {\mathbf{x}}_n||}\Delta {\mathbf{x}}_n^{⊺}$ and $J_n$ is calculated by $J_{n-1}$ $J_n=J_{n-1}+\frac{\Delta {\mathbf{f}}_n-J_{n-1}\Delta {\mathbf{x}}_n}{||\Delta {\mathbf{x}}_n||}\Delta {\mathbf{x}}_n^{⊺}$

Now updating formula become ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-J_n^{-1}\mathbf{f}({\mathbf{x}}_n)$

Where $J_n^{-1}$ can be easily calculated by Sherman–Morrison Formula

$J_n^{-1}=J_{n-1}^{-1}+\frac{\Delta {\mathbf{x}}_n-J_{n-1}^{-1}\Delta {\mathbf{f}}_n}{\Delta {\mathbf{x}}_n^{\mathrm{T}}{J}_{n-1}^{-1}\Delta {\mathbf{f}}_n}\Delta {\mathbf{x}}_n^{\mathrm{T}}{J}_{n-1}^{-1}$ and ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-J_n^{-1}\mathbf{f}({\mathbf{x}}_n)$