Convergence of classical iterative methods

Recall the key iterative step in splitting methods:

$$M{x}^{(k+1)}=b+N{x}^{(k)}$$

The exact solution to $Ax=b$ satisfies

$$Mx=b+Nx$$

since $A=M-N$. Let’s define the error as:

$$e^{(k)}\stackrel{def}{=}{x}^{(k)}-x$$

From the equations above, we get:

$$\begin{array}{c}M{e}^{(k+1)}=N{e}^{(k)}\\ e^{(k)}=M^{-1}N{e}^{(k-1)}=(M^{-1}N{)}^k{e}^{(0)}\end{array}$$

This leads to the following theorem.

Theorem §

These iterative schemes converge for any initial guess $x^{(0)}$ and $b$ if and only if $\rho (M^{-1}N)<1$.

$\rho$ denotes the largest eigenvalue in magnitude for a matrix.

Proof §

Denote by $G=M^{-1}N$.

$\rho (G)\ge 1$ implies no convergence when $e^{(0)}=$ eigenvector associated with the eigenvalue that is greater than 1.

Assume that $\rho (G)<1$

If $G$ is diagonalizable, then

$$G^k{e}_0=X{\Lambda }^k{X}^{-1}{e}_0$$

and ${\Lambda }^k\to 0.$

When $G$ is not diagonalizable, the argument is a little more complex. Consider $Z$ a non-singular matrix, then we can define the following vector norm:

$$\Vert x{\Vert }_Z=\Vert Zx{\Vert }_{\infty }$$

We can define $\Vert G{\Vert }_Z$ as the induced operator norm, and we can prove that

$$\Vert G{\Vert }_Z=\Vert ZG{Z}^{-1}{\Vert }_{\infty }$$

Consider now the Schur decomposition of $G$:

$$G=QT{Q}^H$$

We define the following diagonal scaling matrix $D$:

$$d_{ii}={\delta }^{-i}$$

for some $\delta >0$. We find that

$$[DT{D}^{-1}{]}_{ij}=t_{ij}{\delta }^{j-i},j\ge i,$$

and 0 otherwise. Therefore:

$$\Vert DT{D}^{-1}{\Vert }_{\infty }\le \underset{i}{\max }\{|t_{ii}|+n\underset{j>i}{\max }\{|t_{ij}|{\delta }^{j-i}\}\}$$

We can choose $\delta$ sufficiently small such that

$$\Vert DT{D}^{-1}{\Vert }_{\infty }\le \rho (G)+ϵ<1$$

since the eigenvalues of $G$ are equal to $t_{ii}$. Define $Z=D{Q}^H$. We have proved that

$$\Vert G{\Vert }_Z=\Vert ZG{Z}^{-1}{\Vert }_{\infty }\le \rho (G)+\epsilon <1$$

Then

$$\Vert G^k{\Vert }_Z\le \Vert G{\Vert }_Z^k\to 0$$

since $\Vert G{\Vert }_Z<1$.

$\square$

• $\rho (M^{-1}N)<1$ is required for convergence.
• In practice though, numerical convergence may be slow.
• These methods are often used in combination with other techniques (e.g., multigrid) as accelerators.
• Their main advantage is that they can be very cheap to apply and therefore very fast.