Exercise 1
Consider the linear system of equations \(A\mathbf{x}=\mathbf{b}\), with
\[\begin{split}
A = \begin{bmatrix}
2 & -1 & 1 \\
1 & a & 2 \\
-1 & -1 & 3
\end{bmatrix},
\quad \mathbf{b} = \begin{bmatrix}
2 \\
0 \\
0
\end{bmatrix}
\end{split}\]
a) Determine all values of \(a\) for which the Jacobi method is guaranteed to converge.
Solution:
The Jacobi method leads to the following iteration:
\[
\mathbf{x}^{k+1} = M\mathbf{x}^k + \mathbf{c}, \quad k = 0,1,\ldots,
\]
where
\[\begin{split}
M = - \begin{bmatrix}
0 & \displaystyle -\frac{1}{2} & \displaystyle \frac{1}{2} \\
\displaystyle \frac{1}{a} & 0 & \displaystyle \frac{2}{a} \\
\displaystyle -\frac{1}{3} & \displaystyle -\frac{1}{3} & 0
\end{bmatrix}.
\end{split}\]
The 1-norm of \(M\) is
\[\begin{split}
\begin{aligned}
\lVert M \rVert_1 &= \max \limits_j \sum \limits_{i=1}^3 \lvert M_{ij} \rvert \\
&= \max \left( \frac{1}{|a|} + \frac{1}{3}, \; \frac{1}{2} + \frac{1}{3},\; \frac{1}{2} + \frac{2}{|a|} \right).
\end{aligned}
\end{split}\]
The iteration is guaranteed to converge if \(\lVert M \rVert_1 <1\), which is equivalent to \(|a|>4\).
b) Let \(a=3\) and \(\mathbf{x}^0 = (0,0,0)^T\). Compute \(\mathbf{x}^2\) without explicitly computing \(\mathbf{x}^1\).
Solution:
We have
\[
\mathbf{x}^2 = M\mathbf{x}^1 + \mathbf{c} = M\left( M\mathbf{x}^0 + \mathbf{c} \right) + \mathbf{c} = M^2 \mathbf{x}^0 + M\mathbf{c} + \mathbf{c}.
\]
With the initial guess \(\mathbf{x}^0 = \mathbf{0}\), we obtain
\[\begin{split}
\mathbf{x}^2 = M\mathbf{c} + \mathbf{c} = -
\begin{bmatrix}
0 & -\frac{1}{2} & \frac{1}{2} \\
\frac{1}{3} & 0 & \frac{2}{3} \\
-\frac{1}{3} & -\frac{1}{3} & 0
\end{bmatrix}
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix} +
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix} =
\begin{bmatrix}
1 \\
-\frac{1}{3} \\
\frac{1}{3}
\end{bmatrix}
\end{split}\]
c) Consider the following iterative method: Given \(\mathbf{x}^0\), set
\[
\mathbf{x}^{k+1} = M\mathbf{x}^k + \mathbf{c}, \quad k=0,1,\ldots,
\]
where
\[
M = I -\frac{1}{3}A, \quad \mathbf{c} = \frac{1}{3}\mathbf{b}.
\]
If \(a=1\), will the method converge?
Solution:
We have
\[\begin{split}
\begin{aligned}
M = I - \frac{1}{3}A &= \frac{1}{3}\begin{bmatrix}
3-2 & 1 & -1 \\
-1 & 3-1 & -2 \\
1 & 1 & 3-3
\end{bmatrix}\\
&=
\frac{1}{3}\begin{bmatrix}
1 & 1 & -1 \\
-1 & 2 & -2 \\
1 & 1 & 0
\end{bmatrix}.
\end{aligned}
\end{split}\]
The 1-norm and \(\infty\)-norm of \(M\) are
\[
\lVert M \rVert_1 = \max \limits_j \sum \limits_{i=1}^3 \lvert M_{ij} \rvert = \frac{4}{3}.
\]
\[
\lVert M \rVert_\infty = \max \limits_i \sum \limits_{j=1}^3 \lvert M_{ij} \rvert = \frac{5}{3}.
\]
Both norms are greater than 1, so the iteration might not converge. To know for sure, we need to compute the spectral radius of \(M\). In this case it is easy to compute the eigenvalues, since \(M\) is only 3-by-3. We find that
\[
\rho(M) \approx 0.7013
\]
which shows that the iteration will actually converge!
