1
$\begingroup$

I'm talking about the Newton-Raphson method for finding square roots of matrices: $$\begin{cases} X_{k+1} &= \frac{1}{2}\big(X_k + X_k^{-1}A\big)\\ X_0 &= A \end{cases}$$ as a "solution" to the equation $f(X)=X^2-A=O$.
For normal functions $f(x)=x^2-a=0$ it makes sense why sometimes the method does not converge. But I don't know how to intuitively explain or even understand why the matrix-version sometimes diverges.
For example: compared to the Denman-Beavers method, the Newton-Raphson method is pretty bad since it often does not converge.
So how do we explain these divergences?

$\endgroup$

1 Answer 1

0
$\begingroup$

One possible way to see what you ask:

Newton's method to solve an equation $$f(u)=0$$ is given by a minimization direction procedure to solve the problem $$\min_u\frac{1}{2}\|f(u)\|^2.$$

You can see this as the initial value problem $$\tag{1}\frac{du}{dt}=-[Jf(u)]^{-1}u,\quad u(0)=u_0,$$ because this implies that
$$\frac{d}{dt}\left(\frac{1}{2}\|f(u)\|^2\right)=-\|f(u)\|^2\leq 0.$$

If you use Euler method to solve (1) numerically, with step size equal $1$, you find Newton's method $$\left\{\begin{array}{rll}J{ f}({ u}_j) { w}_j&=&- { f}({ u}_j)\\ { u}_{j+1}&=&{ u}_j+{ w}_j\end{array}\right.$$

Now, if you let $$f(X)=X^2-A,$$ where $A$ and $X$ are matrix, you find that $$J{ f}({ X}_j) { W}_j=X_jW_j+W_jX_j.$$ This is, in general, not iqual to $2X_jW_j$. But it holds if you choose $X_0=A$.

You can find details on matrix derivative seraching for "(\frac{dX^2}{dX}) matrix derivative" on SearchOnMath.

Remark: If you follows a decreasing direction, you can arrive at a local minimum or a saddle point to $\frac{1}{2}\|f(u)\|^2$. And this can explain some non convergence of Newton's method to a desired root of $f(u)=0$.

On the other side, since you are doing the approximation $u_n\approx u(n)$, in which $u(t)$ is given by equation (1). You can have bad approximation, if $u_0$ is far from one root of $f(u)=0$, and "lost" the curve you intend to follows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.