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

-
I'm far from being a specialist in numerical analysis. But if I remember correctly, the rate of convergence of Gauss-Seidel and Jacobi are both quite sensitive to the problem at hand. Depending on the problem either one can be faster than the other. But this sounds more like homework than a research level question, so you should consider to head over to an alternative site, see mathoverflow.net/faq – Theo Buehler Dec 3 2010 at 2:24
I am not asking for making this, but I made it by myself, and I am confused because the convergence is the same, I am only asking whether it's possible for that kind of matrix. – vasilij8 Dec 3 2010 at 2:29

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.

-

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\ &\def&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.

-