5.6 Practice Problems
Problem 5.6.1. Find \(\|\mathbf x\|_1\), \(\|\mathbf x\|_2\) and \(\|\mathbf x\|_\infty \) for \(\mathbf x = (3,-4,0,12)^T\), and \(\|A\|_\infty \), \(\|A\|_1\) for \(A = \begin {pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end {pmatrix}\).
Show solution
Solution. \(\|\mathbf x\|_1 = 19\), \(\|\mathbf x\|_2 = \sqrt {9+16+144} = 13\), \(\|\mathbf x\|_\infty = 12\). For \(A\) the absolute row sums are \(3, 4, 3\) and, \(A\) being symmetric, so are the column sums: \(\|A\|_\infty = \|A\|_1 = 4\).
Problem 5.6.2. Perform three iterations of the Jacobi and Gauss–Seidel methods for \(3x_1+x_2 = 5\), \(x_1+2x_2 = 5\) from \(\mathbf 0\). Compare with the exact solution.
Show solution
Solution. Jacobi: \(x_1^{(k)} = \frac {5-x_2^{(k-1)}}{3}\), \(x_2^{(k)} = \frac {5-x_1^{(k-1)}}{2}\) gives \((1.6667,2.5)\), \((0.8333,1.6667)\), \((1.1111,2.0833)\). Gauss–Seidel uses the new \(x_1\) at once: \((1.6667,1.6667)\), \((1.1111,1.9444)\), \((1.0185,1.9907)\). The solution is \((1,2)\). Here \(\rho (T_j) = \frac 1{\sqrt 6} = 0.408\) and \(\rho (T_g) = \frac 16\), and the Gauss–Seidel errors indeed shrink by a factor of \(6\) per step.
Problem 5.6.3. Show that \(\rho (T_g) = \rho (T_j)^2\) for every \(2\times 2\) matrix with non-zero diagonal.
Show solution
Solution. For \(A = \begin {pmatrix}a&b\\c&d\end {pmatrix}\), \(T_j = \begin {pmatrix}0&-b/a\\-c/d&0\end {pmatrix}\) has eigenvalues \(\pm \sqrt {\frac {bc}{ad}}\), so \(\rho (T_j)^2 = \left |\frac {bc}{ad}\right |\). Gauss–Seidel gives \(x_1^{(k)} = \frac {b_1-bx_2^{(k-1)}}{a}\) and \(x_2^{(k)} = \frac {b_2-cx_1^{(k)}}{d}\), so \(T_g = \begin {pmatrix}0&-\frac ba\\0&\frac {bc}{ad}\end {pmatrix}\), with eigenvalues \(0\) and \(\frac {bc}{ad}\). Hence \(\rho (T_g) = \rho (T_j)^2\): Gauss–Seidel converges exactly when Jacobi does, and twice as fast in terms of digits per iteration.
Problem 5.6.4. For \(A = \begin {pmatrix}1&2\\1.0001&2\end {pmatrix}\), compute the solution of \(A\mathbf x = \mathbf b\) for \(\mathbf b = (3,3.0001)^T\) and for the slightly changed \(\mathbf b' = (3,3.0002)^T\). Explain the result using \(K_\infty (A)\).
Show solution
Solution. The first solution is \((1,1)\). For \(\mathbf b'\), \(\mathbf x' = A^{-1}\mathbf b' = (-30000+30002,\ 15001.5-15001)^T = (2,0.5)^T\). A relative change of \(3.3\times 10^{-5}\) in \(\mathbf b\) has changed the solution by \(100\%\) (in \(\|\cdot \|_\infty \)): an amplification of about \(3\times 10^4\), of the order of \(K_\infty (A) = 60002\), as Theorem 5.5.3 allows.
Problem 5.6.5. Explain why the SOR method with \(\omega = 2.1\) cannot converge for any system, and compute \(\omega _{\text {opt}}\) for a positive definite tridiagonal matrix with \(\rho (T_j) = 0.9\). By what factor is the convergence faster than Gauss–Seidel?
Show solution
Solution. By Theorem 5.4.1(i), \(\rho (T_\omega )\geq |1-\omega | = 1.1>1\). For \(\rho (T_j) = 0.9\), \(\omega _{\text {opt}} = \frac {2}{1+\sqrt {0.19}} = 1.393\) and \(\rho (T_{\omega _{\text {opt}}}) = 0.393\), against \(\rho (T_g) = 0.81\). Gauss–Seidel gains \(-\log _{10}0.81 = 0.092\) decimal digits per iteration and SOR \(-\log _{10}0.393 = 0.41\): about \(4.4\) times as fast.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.