The Convergence of Jacobi and Gauss-Seidel Iteration [closed]

Question

Hi All!

I was supposed to find a solution of Ax=b using Jacobi and Gauss-Seidel method. The A is 100x100 symetric, positive-definite matrix and b is a vector filled with 1's. I am iterating(k = 1,2,....) those methods until the norm of (x(k+1) - x(k)) < precision which means that x is not changing and it is senseless to iterate more. Both methods ends with the same k(changed precision and k is still the same). So is it possible that the convergence of Jacobi and Gauss-Seidel is the same?

I will appreciate every resposne.

Answer 1

There are several important cases where it is proved that $\rho(G)<\rho(J)$, with $G$ and $J$ the iteration matrices associated to the Gauss-Seidel and Jacobi methods. See for instance my book Matrices. GTM 216, Springer-Verlag. For instance, in the tridiagonal case, $\rho(G)=\rho(J)^2$ thus G-S is twice faster as Jacobi.

What means twice faster (or just $k$-times faster) ? These are order one methods, in the sense that a fixed number of exact digits are gained at each step. This number is $\tau=-\log_{10}\rho$. A method is twice faster than an other if the ratio $\tau_{one}/\tau_{other}$ equals $2$. Thus you should see a significant difference between both methods. If not, there might be two reasons. Either you are in an exceptional case where $\rho(G)=\rho(J)$, or something is wrong in your code.

In general, I do not recommend Jacobi and G-S. They are good examples in a course to beginners. But a slight change of G-S yields the relaxation method. With an optimal parameter, it is much faster. This is because $\rho(G)$ is very close to $1$ when $n$ is large, and thus $\tau$ is very small.

Answer 2

You need to be careful how you define rate of convergence. For Gauss-Seidel and Jacobi you split $A$ and rearrange \begin{eqnarray} Ax & = & b \\ M-K & = & b \\ \implies x & = & M^{-1}Kx + M^{-1}b \\ & \triangleq & Rx + c \\ \end{eqnarray} Giving the iteration $x_{m+1} = Rx_m + c$. We (Demmel's book) define the rate of convergence as the increase in the number of correct decimal places per iteration $$ r = -\log_{10}( \rho(R)) $$ where $\rho(R)$ is the spectral radius of $R$. It can be shown that for $A$ strictly row diagonally dominant that $$ \rho(R_{\text{Gauss}}) \leq \rho(R_{\text{Jacobi}}) < 1 $$ indicating that the rate of convergence for Gauss Seidel is greater than that of Jacobi.

However I have never seen a significant difference in speed between the two methods.

Answer 3

Sufficient condition for convergence:

$$ \| C \| < 1 . $$

This $\|C\|$ is some matrix norm, this norm can be find using 3 methods

1. frobineus norm

   $$ \| C \| = \sqrt{\sum_{j=1}^n\sum_{k=1}^n |C_{j,k}|^2} $$

2. column "sum" norm $$ \| C \| = \max_k \sum_{j=1}^n| C_{j,k} |$$ OR greatest of the sums of the $| C_{j,k} |$ in a column of $C$

3. row “sum” norm $$ \| C \| = \max_j \sum_{k=1}^n| C_{j,k} |$$ OR greatest of the sums of the $| C_{j,k} |$ in a row of $C$.

These are the most frequently used matrix norms in numerics. In most cases the choice of one of these norms is a matter of computational convenience.