Stationary iterations and relaxation

Put $d=\mathbf{1}-C\mathbf{1}$. Telescoping gives $\mathbf{1}-C^n\mathbf{1}={\sum }_{k=0}^{n-1}{C}^{k}d$, since $(I-C){\sum }_{k=0}^{n-1}{C}^k=I-C^n$. Each summand is coordinatewise nonnegative by [A1].

For each $i$, choose by [A2] a path of length $s_i\le n-1$ from $i$ to $r$. The product of the positive edge weights along it is a positive term of $(C^{s_i}{)}_{ir}$; for $s_i=0$ this entry is $1$. Hence $(C^{s_i}d{)}_i\ge (C^{s_i}{)}_{ir}{d}_r>0$. Step 1.1 then gives $(C^n\mathbf{1}{)}_i<1$ for every $i$.

Let $q:={\max }_i(C^n\mathbf{1}{)}_i<1$. Since $C^s\mathbf{1}\le \mathbf{1}$ for $0\le s<n$, nonnegativity gives $C^{kn+s}\mathbf{1}\le q^k\mathbf{1}$ for all $k\ge 0$ and $0\le s<n$. Therefore ${\sum }_{j=0}^{\mathrm{\infty }}{C}^j\mathbf{1}$ converges coordinatewise and its sum $v$ satisfies $v\ge \mathbf{1}>0$.

Multiplying the convergent series by $C$ shifts its terms, so $Cv=v-\mathbf{1}<v$ coordinatewise.

By [A1], every $a_{ii}\mathrm{\ne }0$. Thus $D$ and the lower-triangular matrix $D-L$ have nonzero diagonal, so the solves in [F1] and [F2] are uniquely defined by [L2].

By [F1]–[F2] and [L3], the iteration matrices are $G_J=D^{-1}(L+U)$ and $G_G=(D-L{)}^{-1}U$.

For each row $i$, set $q_i={\sum }_{j\mathrm{\ne }i}\mathrm{\mid }{a}_{ij}\mathrm{\mid }\mathrm{/}\mathrm{\mid }{a}_{ii}\mathrm{\mid }$ and $q_J={\max }_i{q}_i<1$. Since $L_{ij}=-a_{ij}$ below the diagonal and $U_{ij}=-a_{ij}$ above it, ${\sum }_j\mathrm{\mid }(G_J{)}_{ij}\mathrm{\mid }=q_i$. Hence for any eigenpair $G_{J}z=\lambda z$ with $z\mathrm{\ne }0$, choose $i$ with $\mathrm{\mid }{z}_i\mathrm{\mid }={\max }_j\mathrm{\mid }{z}_j\mathrm{\mid }$; the row equation gives $\mathrm{\mid }\lambda \mathrm{\mid }\mathrm{\mid }{z}_i\mathrm{\mid }\le q_i\mathrm{\mid }{z}_i\mathrm{\mid }\le q_J\mathrm{\mid }{z}_i\mathrm{\mid }$, so $\mathrm{\mid }\lambda \mathrm{\mid }<1$ and $\rho (G_J)<1$.

Let $G_{G}z=\lambda z$ with $z\mathrm{\ne }0$, and choose $i$ with $\mathrm{\mid }{z}_i\mathrm{\mid }={\max }_j\mathrm{\mid }{z}_j\mathrm{\mid }=:R$. The equation $Uz=\lambda (D-L)z$ in row $i$ is ${\sum }_{j>i}{U}_{ij}{z}_j=\lambda (a_{ii}{z}_i-{\sum }_{j<i}{L}_{ij}{z}_j)$, so $\mathrm{\mid }\lambda \mathrm{\mid }\mathrm{\mid }{a}_{ii}{z}_i-{\sum }_{j<i}{L}_{ij}{z}_j\mathrm{\mid }\le {\sum }_{j>i}\mathrm{\mid }{U}_{ij}\mathrm{\mid }\mathrm{\mid }{z}_j\mathrm{\mid }$. By the reverse triangle inequality and [A1], the left factor is at least $\mathrm{\mid }\lambda \mathrm{\mid }(\mathrm{\mid }{a}_{ii}\mathrm{\mid }-{\sum }_{j<i}\mathrm{\mid }{a}_{ij}\mathrm{\mid })R$, while the right side is at most ${\sum }_{j>i}\mathrm{\mid }{a}_{ij}\mathrm{\mid }R$. Therefore $\mathrm{\mid }\lambda \mathrm{\mid }\le {\max }_i\frac{{\sum }_{j>i}\mathrm{\mid }{a}_{ij}\mathrm{\mid }}{\mathrm{\mid }{a}_{ii}\mathrm{\mid }-{\sum }_{j<i}\mathrm{\mid }{a}_{ij}\mathrm{\mid }}<1$; the denominators are positive and each strict inequality follows from [A1]. Thus $\rho (G_G)<1$.

The bounds in steps 3.1 and 3.2 and [L4] imply that both methods converge to the unique solution of $Ax=b$ for every $b$ and every initial vector.

If $n>1$ and $a_{ii}=0$, [A1] forces every off-diagonal entry in row $i$ to vanish, contradicting strong connectivity. If $n=1$, the strict-row hypothesis forces $\mathrm{\mid }{a}_{11}\mathrm{\mid }>0$. Hence every diagonal entry is nonzero, and the Jacobi and lower-triangular Gauss–Seidel solves are defined by [L5].

Define $C_{ii}=0$ and $C_{ij}=\mathrm{\mid }{a}_{ij}\mathrm{\mid }\mathrm{/}\mathrm{\mid }{a}_{ii}\mathrm{\mid }$ for $i\mathrm{\ne }j$. Its row sums are at most $1$, one is strictly below $1$, and its positive-entry graph is the graph in [A1]. By [L2], choose $v>0$ with $Cv<v$, and set $q_J={\max }_i(Cv{)}_i\mathrm{/}{v}_i<1$.

By [F1], $\mathrm{\mid }{G}_J\mathrm{\mid }=C$ entrywise. For $\mathrm{\parallel }z{\mathrm{\parallel }}_v:={\max }_i\mathrm{\mid }{z}_i\mathrm{\mid }\mathrm{/}{v}_i$, nonnegativity gives $\mathrm{\mid }{G}_{J}z\mathrm{\mid }\le C\mathrm{\mid }z\mathrm{\mid }\le \mathrm{\parallel }z{\mathrm{\parallel }}_{v}Cv\le q_J\mathrm{\parallel }z{\mathrm{\parallel }}_{v}v$. Thus every eigenvalue $\lambda$ of $G_J$ satisfies $\mathrm{\mid }\lambda \mathrm{\mid }\le q_J<1$, so $\rho (G_J)<1$.

Set $B_L=\mathrm{\mid }D{\mathrm{\mid }}^{-1}\mathrm{\mid }L\mathrm{\mid }$ and $B_U=\mathrm{\mid }D{\mathrm{\mid }}^{-1}\mathrm{\mid }U\mathrm{\mid }$. Then $C=B_L+B_U$, $B_L$ is strictly lower triangular, and $(I-B_L{)}^{-1}={\sum }_{r=0}^{n-1}{B}_L^r\ge I$. Thus $H:=(I-B_L{)}^{-1}{B}_U={\sum }_{r=0}^{n-1}{B}_L^r{B}_U\ge 0$. Since $(I-B_L)v-B_{U}v=(I-C)v>0$, multiplying by $(I-B_L{)}^{-1}\ge I$ gives $Hv<v$. Consequently $q_G:={\max }_i(Hv{)}_i\mathrm{/}{v}_i<1$.

Because $D-L=D(I-D^{-1}L)$ and $D^{-1}L$ is strictly lower triangular, $(D-L{)}^{-1}U={\sum }_{r=0}^{n-1}(D^{-1}L{)}^r{D}^{-1}U$. Entrywise absolute values obey $\mathrm{\mid }XY\mathrm{\mid }\le \mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$, so $\mathrm{\mid }{G}_G\mathrm{\mid }\le H$. The same weighted-vector estimate as in step 3.1 yields $\mathrm{\parallel }{G}_{G}z{\mathrm{\parallel }}_v\le q_G\mathrm{\parallel }z{\mathrm{\parallel }}_v$; hence $\rho (G_G)<1$.

By [L3]–[L4], the two spectral-radius bounds imply convergence to the unique solution of $Ax=b$ for every right-hand side and every initial vector.

By [A1] and [F1], $M_{\omega }$ is lower triangular with diagonal $a_{ii}\mathrm{/}\omega \mathrm{\ne }0$, hence invertible by [L5]. Also $A=M_{\omega }-N_{\omega }$ by [L1], so [L2] applies with iteration matrix $G_{\omega }$. The matrix $N_{\omega }$ is upper triangular with diagonal entries $({\omega }^{-1}-1)a_{ii}$. Thus [L6]–[L7] give $\det (M_{\omega })={\omega }^{-n}{\prod }_i{a}_{ii}$ and $\det (N_{\omega })=({\omega }^{-1}-1{)}^n{\prod }_i{a}_{ii}$. From $M_{\omega }{G}_{\omega }=N_{\omega }$ and multiplicativity, $\det (G_{\omega })=\det (N_{\omega })\mathrm{/}\det (M_{\omega })=(1-\omega {)}^n$.

For sufficiency, suppose $A$ is positive definite and $0<\omega <2$. Then $Q:=M_{\omega }+M_{\omega }^{\ast }-A=(2\mathrm{/}\omega -1)D$ is positive definite. For an eigenpair $G_{\omega }v=\lambda v$ with $v\mathrm{\ne }0$, one has $\lambda \mathrm{\ne }1$ since $Av=(1-\lambda )M_{\omega }v$ and $A$ is invertible. Put $a=v^{\ast }Av>0$. Then $v^{\ast }{M}_{\omega }v=a\mathrm{/}(1-\lambda )$, so $v^{\ast }Qv=a(2\mathrm{Re}\frac{1}{1-\lambda }-1)=a\frac{1-\mathrm{\mid }\lambda {\mathrm{\mid }}^2}{\mathrm{\mid }1-\lambda {\mathrm{\mid }}^2}>0$. Therefore $\mathrm{\mid }\lambda \mathrm{\mid }<1$ for every eigenvalue and $\rho (G_{\omega })<1$.

If SOR converges for every right-hand side and start, [L3] gives $\rho (G_{\omega })<1$. By [L8]–[L9], $\mathrm{\mid }\det (G_{\omega })\mathrm{\mid }={\prod }_{j=1}^n\mathrm{\mid }{\lambda }_j\mathrm{\mid }\le \rho (G_{\omega }{)}^n<1$. Step 1.1 therefore gives $\mathrm{\mid }1-\omega \mathrm{\mid }<1$, which for real $\omega$ is equivalent to $0<\omega <2$.

Assume now that SOR converges for every right-hand side and start. Then $\rho (G_{\omega })<1$ by [L3], so $1$ is not an eigenvalue of $G_{\omega }$ and $I-G_{\omega }$ is invertible. By [L2], $A=M_{\omega }(I-G_{\omega })$ is invertible. For $b=0$, its unique solution is $x_{\ast }=0$. For arbitrary nonzero $e^{(0)}:=x^{(0)}$, set $e^{(k)}:=x^{(k)}-x_{\ast }=x^{(k)}$ and ${\delta }_k=e^{(k+1)}-e^{(k)}$. The homogeneous SOR recurrence gives $M_{\omega }{e}^{(k+1)}=N_{\omega }{e}^{(k)}$, hence $A{e}^{(k)}+M_{\omega }{\delta }_k=0$. Expanding the Hermitian quadratic form gives $(e^{(k)}{)}^{\ast }A{e}^{(k)}-(e^{(k+1)}{)}^{\ast }A{e}^{(k+1)}={\delta }_k^{\ast }(M_{\omega }+M_{\omega }^{\ast }-A){\delta }_k=(2\mathrm{/}\omega -1){\delta }_k^{\ast }D{\delta }_k$. The last equality follows from [L1] and [F1].

By step 2.1, $c:=2\mathrm{/}\omega -1>0$. Summing the identity in step 2.2 from $k=0$ to $N-1$ and taking $N\to \mathrm{\infty }$ (the error tends to $0$ by the assumed convergence) gives $(e^{(0)}{)}^{\ast }A{e}^{(0)}=c{\sum }_{k=0}^{\mathrm{\infty }}{\delta }_k^{\ast }D{\delta }_k$. Moreover ${\delta }_0\mathrm{\ne }0$: otherwise step 2.2 implies $A{e}^{(0)}=0$, contrary to invertibility of $A$. Since $D$ has positive diagonal, the first summand is strictly positive and all others are nonnegative. Thus $(e^{(0)}{)}^{\ast }A{e}^{(0)}>0$ for every nonzero $e^{(0)}$, so [L4] gives that $A$ is positive definite.

By [L3], $\rho (G_{\omega })<1$ implies convergence to the unique solution for every right-hand side and every initial vector. Steps 2.1 and 3.1 prove the reverse implication.