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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
