Quadratic Convergence of Newton's Method for Matrix Inverse Calculation

Question

This discussion centers on Newton's method as an iterative approach for computing the matrix inverse. Let $A$ be a non-singular $n \times n$ matrix, and consider the non-linear function $f(X) = A - X^{-1}$. If $f(X^*) = 0$, then $X^* = A^{-1}$. The Newton iteration to solve $f(X) = 0$ is given by:

$$X_{k+1} = 2X_k - X_kAX_k$$

The objective is to demonstrate that the Newton method for calculating the matrix inverse exhibits quadratic convergence when all singular values of $AX_0 - I$ are smaller than $1$.

Attempted Proof:

To establish quadratic convergence, we aim to show the existence of a positive constant $c < 1$ such that:

$$\|X_{k+1} - X^*\| \leq c\|X_k - X^*\|^2$$

Define $Y_k = AX_k - I$, then:

$$Y_{k+1} = -(AX_k - I)^2 = -Y_k^2$$

Since $X^* = A^{-1}$, we can express $X_k - X^*$ as $A^{-1}Y_k$. Therefore,

$$\begin{align*} \|X_{k+1} - X^*\| = \|A^{-1}Y_{k+1}\| &= \|A^{-1}Y_k^2\|\\ &=\|A^{-1}Y_kAA^{-1}Y_k\| \leq \|A\|\|A^{-1}Y_k\|^2\\ &= \|A\|\|X_k - A^{-1}\|^2 = \|A\|\|X_k - X^*\|^2 \end{align*} $$

However, this inequality implies that $\|A\|$ must be less than $1$. Since the Euclidean norm of a matrix is its largest singular value, we conclude that the singular values of $A$ should be smaller than $1$.

To complete the proof, we seek to establish a result of the form:

$$\|X_{k+1} - X^*\| \leq c^\prime\|Y_0\|\|X_k - X^*\|^2$$

At this point, further progress is unclear, and assistance is requested to reach the desired result. Any insights or guidance would be highly appreciated.

Answer 1

Let $V$ be a normed space and let $\{x_n\}_{n=1}^\infty \subseteq V$ be convergent with limit $x$.

1. We say that the convergence has order $p>1$ if there exists $c>0$ such that $$\frac{\|x-x_{n+1}\|}{\|x-x_n\|^p} \rightarrow c, \quad n \rightarrow \infty, \quad n \in \mathbb{N}.$$
2. We say that the convergence has order $p=1$ if there exists $c \in (0,1)$ such that $$\frac{\|x-x_{n+1}\|}{\|x-x_n\|} \rightarrow c, \quad n \rightarrow \infty, \quad n \in \mathbb{N}.$$

In general, these definitions are not particular easy to apply in practice and it is convenient to apply a weaker concept.

3. We say that the convergence has order at least $p\ge 1$ if there exist as majorizing sequence $\{\epsilon_n\}_{n=1}^\infty \subset (0,\infty)$ such that $$ \|x - x_n\| \leq \epsilon_n \rightarrow 0, \quad n \rightarrow \infty, \quad n \in \mathbb{N},$$ and order $p$ convergence.

For the residual given by $$R_n = I - AX_n$$ you have already established that $$ R_{n+1} = R_n^2.$$ It follows automatically that $$ R_n = R_0^{2^n}$$ and $$ \|R_n\| \leq \|R_0\|^{2^n.}$$ You assumption is that $\|R_0\| < 1$, so convergence is assured. For the error $E_n = A^{-1} - X_n$ you have already noted that $$ AE_n = R_n$$ or equivalently $$ E_n = A^{-1} R_n$$ so $$ \|E_n\| \leq \epsilon_n: = \|A^{-1}\| \|R_0\|^{2^n}$$ It is straightforward to verify that the sequence $\{\epsilon_n\}_{n=1}^\infty$ tends to $0$ with order of convergence $p=2$. Hence $\{X_n\}_{n=1}^\infty$ tends to $A^{-1}$ with an order of convergences that is at least $p=2$.