Broyden's method update

293 Views Asked by At

One version of Broyden's method for systems of nonlinear equations updates the approximation of the Jacobian matrix as follows:

$$\mathbf{J}_n ⇽ \mathbf{J}_{n-1}+\frac{\mathbf{f}(\mathbf{x}_n)-\mathbf{f}(\mathbf{x}_{n-1})-\mathbf{J}_{n-1}(\mathbf{x}_n-\mathbf{x}_{n-1})}{||\mathbf{x}_n-\mathbf{x}_{n-1}||_2^2}(\mathbf{x}_n-\mathbf{x}_{n-1})^T$$

However, from the previous iteration, this solution method also uses $\mathbf{J}_{n-1}(\mathbf{x}_n-\mathbf{x}_{n-1})=-\mathbf{f}(\mathbf{x}_{n-1})$ such that the above update simplifies to

$$\mathbf{J}_n ⇽ \mathbf{J}_{n-1}+\frac{\mathbf{f}(\mathbf{x}_n)}{||\mathbf{x}_n-\mathbf{x}_{n-1}||_2^2}(\mathbf{x}_n-\mathbf{x}_{n-1})^T$$

The above simplified version is never mentioned in books as far as I know. Is there a mistake somewhere?

1

There are 1 best solutions below

4
On BEST ANSWER

No, there is no mistake. The second equation is found from considering Newton-Raphson equation: $$-J_{n-1}(x_n-x_{n-1})=f(x_{n-1})\tag{1}$$ And secant equation: $$J_{n}(x_n-x_{n-1})=f(x_n)-f(x_{n-1})\tag{2}$$ Adding the two equations yields: $$(J_{n}-J_{n-1})(x_n-x_{n-1})=f(x_n)\tag{3}$$ Solving for $(J_{n}-J_{n-1})$, assuming $(J_{n}-J_{n-1})(x_n-x_{n-1})^{\perp}=0$, yields: $$(J_{n}-J_{n-1})=\frac{f(x_n)}{\|x_n-x_{n-1}\|_2^2}(x_n-x_{n-1})^T\tag{4}$$ $$(J_{n}-J_{n-1})=\frac{f(x_n)-f(x_{n-1})+f(x_{n-1})}{\|x_n-x_{n-1}\|_2^2}(x_n-x_{n-1})^T\tag{5}$$ $$(J_{n}-J_{n-1})=\frac{f(x_n)-f(x_{n-1})-J_{n-1}(x_n-x_{n-1})}{\|x_n-x_{n-1}\|_2^2}(x_n-x_{n-1})^T\tag{6}$$ Let, $f(x_n)-f(x_{n-1})=y$ and $x_n-x_{n-1}=s$, then: $$J_{n}=J_{n-1}+\frac{y-J_{n-1}s}{s^Ts}(s)^T\tag{7}$$ which is the Broyden method.