Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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 '10 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. –  user11277 Dec 3 '10 at 2:29
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

sufficient condition for convergence

II c II < 1 .

This II C II is some matrix norm, this norm can be find using 3 methods

  1. frobineus norm

    II C II = √(∑(j=1)^n▒∑(k=1)^n▒C)JK2

  2. column “sum” norm II C II = maxk ∑_(j=1)^n▒〖I C〗JK I OR greatest of the sums of the I CJK I in a column of C

  3. row “sum” norm II C II = maxj ∑_(k=1)^n▒〖I C〗JK I OR greatest of the sums of the I CJK I 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.

share|improve this answer
1  
Hi, there seems to be something strange in your math display (in particular the appearance of ▒). Please consider editing your answer to make use of the MathJax capability of this website. –  Willie Wong Jun 26 '13 at 10:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.