Question

The linear system $$ \begin{aligned} &10 x_{1}+x_{2}+x_{3}=12 \\ &x_{1}+10 x_{2}+x_{3}=12 \\ &x_{1}+x_{2}+10 x_{3}=12 \end{aligned} $$ has the unique solution \(x_{1}=x_{2}=x_{3}=1\). Starting from \(\mathbf{x}_{0}=(0,0,0)^{T}\) perform \- two iterations using Jacobi; \- one iteration using Gauss-Seidel. Calculate error norms for the three iterations in \(\ell_{1}\). Which method seems to converge faster?

Short answer

Answer: The Gauss-Seidel method converges faster in this case, as the error norm after the first iteration is smaller compared to the error norm after the second iteration in the Jacobi method.

Step-by-step solution

Jacobi Method Iteration 1

In the given system of equations, we can rewrite each equation as: $$ \begin{aligned} x_{1} &= \frac{12 - x_{2} - x_{3}}{10} \\ x_{2} &= \frac{12 - x_{1} - x_{3}}{10} \\ x_{3} &= \frac{12 - x_{1} - x_{2}}{10} \end{aligned} $$ Starting from \(\mathbf{x}_{0}=(0,0,0)^{T}\), we can now compute the first iteration for the Jacobi method: $$ \begin{aligned} x_{1}^{(1)} &= \frac{12 - 0 - 0}{10} = 1.2\\ x_{2}^{(1)} &= \frac{12 - 0 - 0}{10} = 1.2\\ x_{3}^{(1)} &= \frac{12 - 0 - 0}{10} = 1.2 \end{aligned} $$ Now we have, \(\mathbf{x}^{(1)} = (1.2, 1.2, 1.2)^{T}\).

Jacobi Method Iteration 2

Using the values from \(\mathbf{x}^{(1)}\) for the second iteration of the Jacobi method: $$ \begin{aligned} x_{1}^{(2)} &= \frac{12 - 1.2 - 1.2}{10} = 0.96 \\ x_{2}^{(2)} &= \frac{12 - 1.2 - 1.2}{10} = 0.96 \\ x_{3}^{(2)} &= \frac{12 - 1.2 - 1.2}{10} = 0.96 \end{aligned} $$ Now we have, \(\mathbf{x}^{(2)} = (0.96, 0.96, 0.96)^{T}\).

Gauss-Seidel Method Iteration 1

For the Gauss-Seidel method, we can rewrite the equations using the same equations as Jacobi, but updating the values as soon as we have a new value. Using the initial \(\mathbf{x}_{0}=(0,0,0)^{T}\), we compute the first iteration for the Gauss-Seidel method: $$ \begin{aligned} x_{1}^{'} &= \frac{12 - 0 - 0}{10} = 1.2 \\ x_{2}^{'} &= \frac{12 - 1.2 - 0}{10} = 1.08 \\ x_{3}^{'} &= \frac{12 - 1.2 - 1.08}{10} = 0.972 \end{aligned} $$ Now we have, \(\mathbf{x}^{'} = (1.2, 1.08, 0.972)^{T}\).

Compute Error Norms in \(\ell_{1}\)

To determine which method converges faster, we will compute the error norms in \(\ell_{1}\) for each iteration. The exact solution is given by \(\mathbf{x} = (1,1,1)^{T}\). Error norm after 1st Jacobi iteration: $$ \|\mathbf{x}^{(1)} - \mathbf{x}\|_1 = \| (1.2-1,1.2-1, 1.2-1) \|_1 = 0.6 $$ Error norm after 2nd Jacobi iteration: $$ \|\mathbf{x}^{(2)} - \mathbf{x}\|_1 = \| (0.96-1,0.96-1, 0.96-1) \|_1 = 0.12 $$ Error norm after 1st Gauss-Seidel iteration: $$ \|\mathbf{x}^{'} - \mathbf{x}\|_1 = \| (1.2-1,1.08-1, 0.972-1) \|_1 = 0.252 $$

Results and Conclusions

Comparing the error norms, we can see that the Gauss-Seidel method has a smaller error after just one iteration than the Jacobi method after two iterations. As a result, we can conclude that the Gauss-Seidel method seems to converge faster in this case.

Key concepts

Jacobi Method

The Jacobi method is a classic iterative technique used to solve linear systems of equations. This method calculates each component of the solution vector independently at each iteration, making it particularly well-suited for parallel computing environments.

To apply the Jacobi method, you first begin by arranging your system of linear equations in a diagonal dominant form, where the coefficient of each variable in its respective equation is significantly larger than the other coefficients. From there, you solve each equation for its respective variable, as demonstrated in the given exercise.

In the context of the example, the initial guess \(\mathbf{x}_0=(0,0,0)^T\) is used to predict the next set of solutions \(\mathbf{x}^{(1)}\) and then \(\mathbf{x}^{(2)}\) by iteratively substituting the values into the adjusted equations. After two iterations using the Jacobi method, we observe that the values are converging towards the true solution.

Gauss-Seidel Method

The Gauss-Seidel method, another common iterative technique, differs from the Jacobi method primarily in its approach to using the most recent values. It sequentially updates each component of the solution vector, which potentially accelerates the convergence rate as the latest updates are utilized immediately in subsequent computations.

For the system provided, the Gauss-Seidel method starts with the same initial guess as the Jacobi method. But rather than calculating all variables independently, once the new value of \(x_1^{'}\) is found, it is directly used in the calculation of \(x_2^{'}\), and then both \(x_1^{'}\) and \(x_2^{'}\) are used for \(x_3^{'}\). This single iteration of the Gauss-Seidel method already shows a promising convergence, suggesting its effectiveness compared to the two iterations done by the Jacobi method.

Error Norms

Error norms are invaluable tools in numerical analysis to measure the accuracy of iterative methods. When approximating solutions, it's crucial to quantify how 'far' our estimates are from the actual values. One commonly used error norm is the \(\ell_1\) norm, which sums the absolute differences of the respective components of two vectors.

For our example, we compute the \(\ell_1\) norm after each iteration for both the Jacobi and Gauss-Seidel methods, using the exact solution \(\mathbf{x} = (1,1,1)^T\) for comparison. As shown in the step-by-step solution, the error decreases with each successive iteration. By examining the results of the error norms, it's evident that the Gauss-Seidel method, with a lower error after just one iteration compared to two iterations of the Jacobi method, demonstrates a faster rate of convergence, suggesting it may be the more efficient choice in certain cases.