\(\star\)E9.1. For the matrices \(T\) corresponding to the Jacobi and Gauss–Seidel iteration in exercise E9.3, determine the spectral radius \(\rho(T)\). Which of the iterations converge?

\(\star\)E9.2. Suppose that \(T\) is a \(d\times d\) matrix with \(\|T\|_{\mathrm{op}}<1\), for some operator norm \(\|T\|_{\mathrm{op}}\) with respect to a vector norm \(\|\vec x\|\).

  1. Let \(I\) denote the \(d\times d\) identity matrix. Given that the expansion of the inverse matrix \((I-T)^{-1}=I+T+T^2+\dots+\) converges, prove that \[\|(I-T)^{-1}\|_{\mathrm{op}} \le \frac{1}{1-\|T\|_{\mathrm{op}}}.\]

  2. For a vector \(\vec c \in \mathbb{R}^n\), let \(\vec x\in \mathbb{R}^n\) satisfy \(\vec x= T \vec x+\vec c\) and consider the iteration \(\vec x_{n+1}=T \vec x_n+\vec c\). Show that \[\|\vec x_n -\vec x\|% \le \frac{\|T\|_{\mathrm{op}}^n}{1- \|T\|_{\mathrm{op}}} \|\vec x_1 - \vec x_0\|.\qquad \qquad {(\star)}\] Hint: use the following estimate from class: \[\|\vec x_n-\vec x\| \le \|T\|_{\mathrm{op}}^n \|\vec x_0-\vec x\|.\qquad \qquad {(\dagger)}\]

  3. Why is \((\star)\) more useful in applications that \((\dagger)\)?

E9.3. Let \(A=D+L+U\) be split into diagonal and lower- and upper-triangular parts. Let \(T_{\mathrm J}\) denote the Jacobi iteration matrix and \(T_{\mathrm {GS}}\) the Gauss–Seidel iteration matrix.

  1. Show that \(\lambda\) is an eigenvalue of \(T_{\mathrm J}\) if and only if \(\det|-\lambda D -L -U|=0\).

  2. Show that \(\lambda\) is an eigenvalue of \(T_{\mathrm {GS}}\) if and only if \(\det|-\lambda (D+L) -U|=0\).

  3. Assume that, for \(a,b\ne 0\), \[\det|aD-L-U|% =\det|a D-b^{-1} L- b U|.\qquad\qquad (*)\] Show that \(\lambda\) is an eigenvalue of \(T_{\mathrm GS}\) if and only \(\lambda^{1/2}\) is an eigenvalue of \(T_{\mathrm {J}}\).

E9.4. Formulate the Jacobi iteration as \(\vec x_{k+1}=T \vec x_k + \vec c\) for the \(d\times d\) finite-difference matrix \[A= \begin{bmatrix} 2 & -1 & & & \\ -1 & 2 & -1 & \\ & -1 & \ddots & \ddots & \\ & & & &-1\\ & & & -1& 2 \end{bmatrix}.\]

  1. Show that \(\vec u_k=(\sin k\pi h, \sin 2 k\pi h,\dots,\sin d k\pi h)^\top\), for \(h=1/(d+1)\) and \(k=1,\dots,d\), is an eigenvector of \(T\). Use this to prove the Jacobi iteration converges for this class of matrices.

  2. Show that \((*)\) holds for the finite-difference matrix \(A\).

  3. Which of the iterations (Jacobi and Gauss-Seidel) would converge faster for this matrix?