The Convergence of Jacobi and Gauss-Seidel Iteration 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.   
 A: 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. 
A: 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.
A: Sufficient condition for convergence:
$$ \| C \| < 1 . $$
This $\|C\|$   is some matrix norm, this norm can be find using 3 methods


*

*frobineus norm
$$ \| C \|   =  \sqrt{\sum_{j=1}^n\sum_{k=1}^n |C_{j,k}|^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$

*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.
