Proving that Gauss-Jacobi iterations always converge when a system is strictly diagonally dominant.

Question

Consider a system $A\mathbf x=\mathbf b$ where $A=[a_{ij}]_{n\times n}$ is a coefficient matrix, $\mathbf b$ is the constant vector $(b_1,b_2,\ldots,b_n)^T$ and $\mathbf x$ is the solution vector $(x_1,x_2,\ldots,x_n)^T$.

Recall that we start off with an initial guess $\mathbf x^{(0)}=(x_1^{(0)},x_2^{(0)},\ldots,x_n^{(0)})^T$ and generate every iterate recursively as follows: $$\displaystyle x_{i}^{( k+1)} =\frac{1}{a_{ii}}\left( b_{i} -\sum _{j\ \neq \ i} a_{ij} \ x_{j}^{( k)}\right)\\ \Leftrightarrow \mathbf{x}^{( k+1)}=D^{-1}\left(\mathbf{b} -( A-D)\mathbf{x}^{( k)}\right) $$ where $D=\text{diag}(a_{11},a_{22},\ldots,a_{nn})$ and $D^{-1}=\text{diag}\left(\frac{1}{a_{11}},\frac{1}{a_{22}},\ldots,\frac{1}{a_{nn}}\right)$.

Let $H=I-D^{-1}A$ and $\mathbf c=D^{-1}\mathbf b$, we get: $$\mathbf x^{(k+1)}=H\mathbf x^{(k+1)}+\mathbf c$$

I have understood everything up to this from the notes I have. Then it goes on to claim that: $$ \color{red}{\text{$A$ is strictly diagonally dominant}\iff ||H||<1}\implies \mathbf x^{(k)} \text{ converges}$$

The second implication is obvious to me because $\rho(H)<||H||$ and $\rho(H)<1$ is a necessary and sufficient condition for convergence.

I don't know how to prove the first one (which is in red). I would appreciate any hint or help.

Answer 1

Being strictly diagonally dominant is just a sufficient condition for convergence. If $H$ is strictly diagonally dominant, then $\|H\|_{\infty} < 1$, which implies that the iteration is convergent with the infinity norm. Since in finite-dimensional spaces, all norms are equivalent, the iteration will be convergent in any norm.

The spectral norm $\rho(H)$ is beside the point here.

Answer 2

I followed a textbook later and my doubts are clear now.

Claim:

$$\color{red}{\text{$A$ is strictly diagonally dominant}\\ \iff \lVert H\rVert_{\infty}<1}$$

Proof:

$\begin{align} & \lVert H\rVert_{\infty}<1\\ \iff & \lVert I-D^{-1}A\rVert_{\infty} <1\\ \iff & \left|-\frac{1}{|a_{ii}|}\sum_{ j\neq i}|a_{ij}|+\left|1-\frac{a_{ii}}{a_{ii}}\right|\right|<1\tag{01} \\& \quad\quad \text{ for each row $i$}\\ \iff & \frac{1}{|a_{ii}|}\sum_{j\neq i}|a_{ij}|<1\\ \iff & \sum_{j\neq i}|a_{ij}|<|a_{ii}|\\ \iff & \text{$A$ is strictly diagonally dominant}\end{align}$

(1) Left multiplying by a diagonal matrix has the effect of "scaling" the rows. Each row $i$ is scaled by the factor $1/a_{ii}$. Adding with identity matrix increases each diagonal entry by $1$. $I-D^{-1}A=\displaystyle \begin{pmatrix}0 & -\frac{a_{12}}{a_{11}} & \ldots & -\frac{a_{1n}}{a_{11}}\\ -\frac{a_{21}}{a_{22}}& 0 &\ldots & -\frac{a_{2n}}{a_{22}}\\ \vdots& \vdots&\ddots & \vdots\\ -\frac{a_{n1}}{a_{nn}}&-\frac{a_{n2}}{a_{nn}} & \ldots&0\end{pmatrix}\tag*{}$

This completes the proof that strict diagonal dominance is a sufficient condition for the G-J iterations to converge, however, it is not necessary.

The iteration scheme $\mathbf x^{(k+1)}=H\mathbf x^{(k)}+\mathbf c$ may sometimes converge even if $\lVert H\rVert_{\infty}\geq 1$ i.e., the system is not strictly diagonally dominant.

However, the condition $\rho(H)<1$ is both necessary and sufficient for convergence.