Solution. The iteration is \begin {align*} x_1^{(k)} &= \tfrac {1}{10}x_2^{(k-1)}-\tfrac 15x_3^{(k-1)}+\tfrac 35,\\ x_2^{(k)} &= \tfrac 1{11}x_1^{(k-1)}+\tfrac 1{11}x_3^{(k-1)}-\tfrac 3{11}x_4^{(k-1)}+\tfrac {25}{11},\\ x_3^{(k)} &= -\tfrac 15x_1^{(k-1)}+\tfrac 1{10}x_2^{(k-1)}+\tfrac 1{10}x_4^{(k-1)}-\tfrac {11}{10},\\ x_4^{(k)} &= -\tfrac 38x_2^{(k-1)}+\tfrac 18x_3^{(k-1)}+\tfrac {15}8 . \end {align*}

After \(10\) iterations the relative change is below \(10^{-3}\) and every component is within \(2.3\times 10^{-4}\) of the solution.

Solution.

Five Gauss–Seidel iterations do the work of ten Jacobi iterations. For instance \(x_2^{(1)} = \frac {1}{11}(0.6000)+\frac {25}{11} = 2.3273\) already uses the new \(x_1^{(1)}\).

Proof. If \(\rho (T)<1\), then \(1\) is not an eigenvalue of \(T\), so \(I-T\) is invertible and \(\mathbf x = T\mathbf x+\mathbf c\) has a unique solution. Subtracting it from (5.4), the error \(\mathbf e^{(k)} = \mathbf x^{(k)}-\mathbf x\) satisfies \(\mathbf e^{(k)} = T\mathbf e^{(k-1)} = \dots = T^k\mathbf e^{(0)}\), which tends to \(\mathbf 0\) for every \(\mathbf e^{(0)}\) by Theorem 5.2.4. Conversely, if \(\rho (T)\geq 1\), choose \(\mathbf x^{(0)}\) so that \(\mathbf e^{(0)}\) is an eigenvector for an eigenvalue with \(|\lambda |\geq 1\); then \(\mathbf e^{(k)} = \lambda ^k\mathbf e^{(0)}\) does not tend to \(\mathbf 0\). The bounds follow exactly as in the proof of the Fixed-Point Theorem 2.3.7, with \(|g'|\leq k\) replaced by \(\|T\|<1\). □

Proof. Jacobi. The \(i\)th row of \(T_j\) has entries \(-\frac {a_{ij}}{a_{ii}}\) (\(j\neq i\)) and \(0\) on the diagonal, so its absolute row sum is \(\frac {1}{|a_{ii}|}\sum _{j\neq i}|a_{ij}|<1\). Hence \(\rho (T_j)\leq \|T_j\|_\infty <1\).

Gauss–Seidel. Let \(\lambda \) be an eigenvalue of \(T_g\) with eigenvector \(\mathbf v\), scaled so that \(\|\mathbf v\|_\infty = 1\), and let \(|v_k| = 1\). From \(U\mathbf v = \lambda (D-L)\mathbf v\), the \(k\)th component reads \[-\sum _{j>k}a_{kj}v_j = \lambda \left (a_{kk}v_k+\sum _{j<k}a_{kj}v_j\right ).\] Taking absolute values and using \(|v_j|\leq 1\), \[|\lambda |\left (|a_{kk}|-\sum _{j<k}|a_{kj}|\right )\leq \sum _{j>k}|a_{kj}| .\] By strict diagonal dominance, \(|a_{kk}|-\sum _{j<k}|a_{kj}|>\sum _{j>k}|a_{kj}|\geq 0\), so \(|\lambda |<1\). Hence \(\rho (T_g)<1\). □

Solution. Here \(T_j = \begin {pmatrix}0&-2\\-3&0\end {pmatrix}\), with eigenvalues \(\pm \sqrt 6\), so \(\rho (T_j) = 2.449>1\). From \(\mathbf 0\) the iterates are \((3,4), (-5,-5), (13,19), (-35,-35),\dots \), moving away from the solution \((1,1)\). Interchanging the equations gives \(3x_1+x_2 = 4\), \(x_1+2x_2 = 3\), which is strictly diagonally dominant, and now \(T_j = \begin {pmatrix}0&-\frac 13\\-\frac 12&0\end {pmatrix}\) has \(\rho = \frac 1{\sqrt 6} = 0.408\): the iteration converges.