Question

Continuing Exercise 3 : (a) Show that Jacobi's method will converge for this matrix regardless of the starting vector \(\mathbf{x}_{0}\) (b) Now apply two Jacobi iterations for the problem $$ \begin{aligned} &2 x_{1}+5 x_{2}+5 x_{3}=12 \\ &5 x_{1}+2 x_{2}+5 x_{3}=12 \\ &5 x_{1}+5 x_{2}+2 x_{3}=12 \end{aligned} $$ starting from \(\mathbf{x}_{0}=(0,0,0)^{T}\). Does the method appear to converge? Explain why.

Short answer

Provide the results of two Jacobi iterations starting from the initial vector \(\mathbf{x}_{0}=(0,0,0)^{T}\). Answer: The Jacobi's method does not converge for the given matrix because the spectral radius of the iteration matrix H is greater than 1. When applying two Jacobi iterations starting from the initial vector \(\mathbf{x}_{0}=(0,0,0)^{T}\), we obtain the following results: 1. First iteration: \(\mathbf{x}_{1}=(6, 6, 6)^{T}\) 2. Second iteration: \(\mathbf{x}_{2}=(-\frac{27}{2}, -\frac{27}{2}, -\frac{27}{2})^{T}\) The components of the computed vector \(\mathbf{x}_{2}\) become more negative, indicating that the method does not appear to converge.

Step-by-step solution

(a) Convergence of Jacobi's method

(To show that Jacobi's method will converge for this matrix regardless of the starting vector, we need to check whether the matrix is diagonally dominant, that is, if the absolute value of the diagonal element of each row is greater than the sum of absolute values of other elements in that row. If the matrix is diagonally dominant, the method will converge for any initial vector. The given matrix can be written as a sum of a diagonal matrix (D) and the remaining matrix (R): $$ A = \begin{pmatrix} 2 & 5 & 5 \\ 5 & 2 & 5 \\ 5 & 5 & 2 \end{pmatrix} = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix} + \begin{pmatrix} 0 & 5 & 5 \\ 5 & 0 & 5 \\ 5 & 5 & 0 \end{pmatrix} = D + R $$ Now, we can check for diagonal dominance for each row: $$ |2| > |5| + |5|, |2| > |5| + |5|, |2| > |5| + |5| $$ This condition is false, so we must use another approach to show the convergence of Jacobi's method. Recall the spectral radius (\(\rho\)) and its relation to the convergence of Jacobi's method: The method will converge if the spectral radius of the iteration matrix (\(\rho(H)\)) is less than 1. The iteration matrix H can be found using the following formula: $$ H = -D^{-1} R. $$ Calculating the inverse of the diagonal matrix D and the resulting matrix H: $$ D^{-1} = \begin{pmatrix} 1/2 & 0 & 0 \\ 0 & 1/2 & 0 \\ 0 & 0 & 1/2 \end{pmatrix}, \quad H = - \frac{1}{2} \begin{pmatrix} 0 & 5 & 5 \\ 5 & 0 & 5 \\ 5 & 5 & 0 \end{pmatrix} = \begin{pmatrix} 0 & -5/2 & -5/2 \\ -5/2 & 0 & -5/2 \\ -5/2 & -5/2 & 0 \end{pmatrix}. $$ Computing the eigenvalues of H, we find that $$ \lambda(H) = \{- \frac{5}{2}, 0, \frac{5}{2} \}. $$ Now, we compute the spectral radius of H, $$ \rho(H) = \max\{|\lambda(H)|\} = \frac{5}{2}. $$ Since \(\rho(H) > 1\), the Jacobi's method will not converge for this matrix regardless of the starting vector.

(b) Applying two Jacobi iterations

(We now apply two Jacobi iterations to the given problem starting from the initial vector \(\mathbf{x}_{0}=(0,0,0)^{T}\), and then discuss whether the method appears to converge. To do this, we will rewrite the system of linear equations in the canonical form for Jacobi's iterations: $$ x_{1}^{(k+1)}=\frac{1}{2}(12-5 x_{2}^{(k)}-5 x_{3}^{(k)}), $$ $$ x_{2}^{(k+1)}=\frac{1}{2}(12-5 x_{1}^{(k)}-5 x_{3}^{(k)}), $$ $$ x_{3}^{(k+1)}=\frac{1}{2}(12-5 x_{1}^{(k)}-5 x_{2}^{(k)}). $$ Now, we perform the first iteration starting from \(\mathbf{x}_{0}=(0,0,0)^{T}\): $$ x_{1}^{(1)}=\frac{1}{2}(12-5 \cdot 0-5 \cdot 0)=6, $$ $$ x_{2}^{(1)}=\frac{1}{2}(12-5 \cdot 0-5 \cdot 0)=6, $$ $$ x_{3}^{(1)}=\frac{1}{2}(12-5 \cdot 0-5 \cdot 0)=6. $$ We get the result of the first iteration as \(\mathbf{x}_{1}=(6, 6, 6)^{T}\). Now let's perform the second iteration using \(\mathbf{x}_{1}\): $$ x_{1}^{(2)}=\frac{1}{2}(12-5 \cdot 6-5 \cdot 6)=-\frac{27}{2}, $$ $$ x_{2}^{(2)}=\frac{1}{2}(12-5 \cdot 6-5 \cdot 6)=-\frac{27}{2}, $$ $$ x_{3}^{(2)}=\frac{1}{2}(12-5 \cdot 6-5 \cdot 6)=-\frac{27}{2}, $$ and, as a result, we obtain \(\mathbf{x}_{2}=(-\frac{27}{2}, -\frac{27}{2}, -\frac{27}{2})^{T}\). We can see that the method does not appear to converge, as the components of the computed vector \(\mathbf{x}_{2}\) become more and more negative, diverging away from their true values. The explanation for this behavior can be found in our conclusion from part (a): since the spectral radius of the iteration matrix H is greater than 1, the Jacobi's method will not converge for this matrix.

Key concepts

Spectral Radius

The spectral radius is a crucial concept in understanding the convergence of iterative methods like Jacobi's method. The term refers to the largest absolute value among the eigenvalues of a matrix. Mathematically, for a given square matrix A with eigenvalues \( \lambda_i \), the spectral radius \( \rho(A) \) is defined as \( \rho(A) = \max_i |\lambda_i| \).

In the context of iterative methods for solving linear systems, the spectral radius helps determine whether an iterative method will converge. Specifically for Jacobi's method, if the spectral radius of the iteration matrix, \( H \), is less than 1, convergence is guaranteed. However, if \( \rho(H) > 1 \), the method will diverge, meaning that as the iterations continue, the solution will not get closer to the true answer.

To calculate the spectral radius in a given problem, one would start by determining the eigenvalues of the iteration matrix and then finding the maximum absolute value among those. In the exercise provided, the eigenvalues of matrix H are \( \{- \frac{5}{2}, 0, \frac{5}{2} \} \) and therefore, the spectral radius is \( \frac{5}{2} \) which indicates that Jacobi's method will not converge for this specific matrix, regardless of the starting vector.

Diagonal Dominance

Diagonal dominance is another key factor that influences the convergence of numerical methods for solving systems of linear equations. A matrix is diagonally dominant if, for each row, the magnitude of the diagonal entry in the row is greater than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row.

Mathematically, a matrix \( A \) is said to be diagonally dominant if for every row \( i \) the following condition holds: \( |a_{ii}| \geq \sum_{j eq i} |a_{ij}| \) where \( a_{ii} \) is a diagonal element and \( a_{ij} \) are the off-diagonal elements of \( A \).

Diagonal dominance is a desirable property because it often ensures the convergence of iterative methods such as Jacobi's method, even if the spectral radius criterion is not met. Unfortunately, in our textbook exercise, the given matrix lacks diagonal dominance as the condition \( |2| > |5| + |5| \) doesn't hold for any of the rows, highlighting one potential reason why Jacobi's method fails to converge in this scenario.

Numerical Iterations

Numerical iterations are a fundamental concept in numerical analysis, used for approximating solutions to mathematical problems through a process of iteration. This approach involves generating a sequence of approximations, hoping that the sequence will converge to the actual solution.

In the given exercise, Jacobi's method performs numerical iterations to find the solution to a system of linear equations. It does so by isolating each variable in the equations and then using an initial guess to compute a sequence of increasingly accurate approximations for each variable.

The method requires an initial vector, \( \mathbf{x}_{0} \), and updates it using a specified iteration formula. After each iteration, the updated values become the input for the next round. The convergence of these iterations is closely linked to the properties of the matrix, specifically its spectral radius and diagonal dominance.

However, as shown in the exercise, if the method diverges, the values obtained after each iteration move further away from the solution. The divergence observed in the textbook problem, with the vector components drastically increasing in magnitude, underscores the importance of the convergence criteria—such as having a spectral radius smaller than 1—for the success of numerical iterative methods.