MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

closed as off-topic by Ricardo Andrade, Jeremy Rouse, S. Carnahan Oct 6 '14 at 1:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Ricardo Andrade, Jeremy Rouse, S. Carnahan
If this question can be reworded to fit the rules in the help center, please edit the question.

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 – 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
up vote 4 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|cite|improve this answer

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.

share|cite|improve this answer
dranxo, in place of $$\rho(R_{\text{Gauss}}) \leq \rho(R_{\text{Jacobi}})$$ shouldn't be $$\|R_{\text{Gauss}}\|_{\infty} \leq \|R_{\text{Jacobi}}\|_{\infty}$$ ? – Shamisen Oct 5 '14 at 21:56
Counterexample to $$ \rho(R_{\text{Gauss}}) \leq \rho(R_{\text{Jacobi}}).$$ Considering $$ A=\begin{bmatrix}1 & 2 & -2\\ 1 & 1 & 1\\ 2 & 2 & 1 \end{bmatrix}, $$ one has that $\rho(R_{\text{Gauss}})=2$ and $\rho(R_{\text{Jacobi}})=0$. – Shamisen Oct 6 '14 at 2:19

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|cite|improve this answer
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

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