Are Gauss-Seidel and Jacobi Methods Guaranteed to Converge on Certain Matrices?

[evinda]

Hello :)
Could you tell me,why both of the Gauss-Seidel and Jacobi method,when we apply them at the tridiagonal matrix with the number 4 at the main diagonal and the number 1 at the first diagonal above the main and also the number 1 at the first diagonal under the main diagonal converge,but they do not converge ,when we apply them at the Hilbert matrix and also at the tridiagonal matrix with the number 2 at the main diagonal and the number -1 at the 2 other diagonals?

 

[evinda]

The fact that the methods do not converge for the Hilbert matrix,has it to with the fact that this matrix is ill-conditioned?And what's with the other two matrices?

 

[I like Serena]

Hello :)
Could you tell me,why both of the Gauss-Seidel and Jacobi method,when we apply them at the tridiagonal matrix with the number 4 at the main diagonal and the number 1 at the first diagonal above the main and also the number 1 at the first diagonal under the main diagonal converge,but they do not converge ,when we apply them at the Hilbert matrix and also at the tridiagonal matrix with the number 2 at the main diagonal and the number -1 at the 2 other diagonals?

The fact that the methods do not converge for the Hilbert matrix,has it to with the fact that this matrix is ill-conditioned?And what's with the other two matrices?

Hi! (Smile)

From the Gauss-Seidel method on wiki we can see that Gauss-Seidel is known to converge if either:

• A is symmetric positive-definite,
• A is strictly or irreducibly diagonally dominant.

The Gauss–Seidel method sometimes converges even if these conditions are not satisfied.

Note that it will still only converge if the rounding errors made by the computer are within small enough bounds.Your 4-1 band matrix is easily strictly diagonally dominant, so it converges.

Your 2-(-1) band matrix is not strictly diagonally dominant, so it is an edge case.
Combined with large enough matrices and rounding errors, it will probably diverge.
I checked that with a 4x4 matrix A and some choices for b and the initial guess, Gauss-Seidel was actually convergent.

Your Hilbert matrix is symmetric positive-definite, so it will converge if the matrix is small enough.
Thanks to Opalg we already know that large Hilbert matrices have a determinant of near-zero, making it ill-conditioned, meaning that the rounding errors will become too large if the matrix is large enough.
Another check with a 4x4 Hilbert matrix and some choices for b and the initial guess showed that Gauss-Seidel was convergent.

 

[evinda]

Hi! (Smile)

From the Gauss-Seidel method on wiki we can see that Gauss-Seidel is known to converge if either:

• A is symmetric positive-definite,
• A is strictly or irreducibly diagonally dominant.

The Gauss–Seidel method sometimes converges even if these conditions are not satisfied.

Note that it will still only converge if the rounding errors made by the computer are within small enough bounds.Your 4-1 band matrix is easily strictly diagonally dominant, so it converges.

Your 2-(-1) band matrix is not strictly diagonally dominant, so it is an edge case.
Combined with large enough matrices and rounding errors, it will probably diverge.
I checked that with a 4x4 matrix A and some choices for b and the initial guess, Gauss-Seidel was actually convergent.

Your Hilbert matrix is symmetric positive-definite, so it will converge if the matrix is small enough.
Thanks to Opalg we already know that large Hilbert matrices have a determinant of near-zero, making it ill-conditioned, meaning that the rounding errors will become too large if the matrix is large enough.
Another check with a 4x4 Hilbert matrix and some choices for b and the initial guess showed that Gauss-Seidel was convergent.

Is the 4-1 band matrix also symmetric positive-definite or not??
Also,do these two method converge/diverge for the same reasons or for different ones?

 

[I like Serena]

Is the 4-1 band matrix also symmetric positive-definite or not??
Also,do these two method converge/diverge for the same reasons or for different ones?

Yes, the 4-1 band matrix is positive definite, since it is symmetric, strictly diagonally dominant, and has positive real entries on its diagonal (see wiki).

I'd say that the other 2 matrices diverge for different reasons.
The Hilbert matrix is supposed to converge, but big matrices won't due to being ill-conditioned.
The 2-(-1) band matrix is an edge case for Gauss-Seidel to begin with. Its conditioned well enough, but certainly with rounding errors it may not converge.

 

[evinda]

Yes, the 4-1 band matrix is positive definite, since it is symmetric, strictly diagonally dominant, and has positive real entries on its diagonal (see wiki).

I'd say that the other 2 matrices diverge for different reasons.
The Hilbert matrix is supposed to converge, but big matrices won't due to being ill-conditioned.
The 2-(-1) band matrix is an edge case for Gauss-Seidel to begin with. Its conditioned well enough, but certainly with rounding errors it may not converge.

So,the Jacobi method won't converge for the 2-(-1) band matrix because it is not strictly dominant??And why could the Gauss-Seidel method converge for it?

 

[evinda]

Also,is the Hilbert matrix strictly dominant,so that the Jacobi methodi would converge,but it doesn't because of the fact that the matrix is ill-conditioned??Or isn't it strictly dominant?

 

[I like Serena]

So,the Jacobi method won't converge for the 2-(-1) band matrix because it is not strictly dominant??And why could the Gauss-Seidel method converge for it?

It is more accurate to say that the 2-(-1) band matrix might converge for both the Jacobi and the Gauss-Seidel method, but based on the strictly diagonally dominant criterium, it is not known to be.

Furthermore, the 2-(-1) band matrix is not symmetric positive-definite, so the Gauss-Seidel is not known to be convergent based on that criterium.

However, I believe the iterative matrix of the 2-(-1) band matrix ($D^{-1}R$) has a spectral radius smaller than 1, making the Jacobi method convergent.

 

[evinda]

It is more accurate to say that the 2-(-1) band matrix might converge for both the Jacobi and the Gauss-Seidel method, but based on the strictly diagonally dominant criterium, it is not known to be.

Furthermore, the 2-(-1) band matrix is not symmetric positive-definite, so the Gauss-Seidel is not known to be convergent based on that criterium.

However, I believe the iterative matrix of the 2-(-1) band matrix ($D^{-1}R$) has a spectral radius smaller than 1, making the Jacobi method convergent.

Yes,I also noticed that the iterative matrix of the 2-(-1) band matrix ($D^{-1}R$) has a spectral radius smaller than 1 for all the dimensions I checked,but I get as result that the methods do not converge..Why does this happen??

 

[I like Serena]

Also,is the Hilbert matrix strictly dominant,so that the Jacobi methodi would converge,but it doesn't because of the fact that the matrix is ill-conditioned??Or isn't it strictly dominant?

The Hilbert matrix is not strictly diagonally dominant.
You may want to look up the definition if you want to use it in your work.

Yes,I also noticed that the iterative matrix of the 2-(-1) band matrix ($D^{-1}R$) has a spectral radius smaller than 1 for all the dimensions I checked,but I get as result that the methods do not converge..Why does this happen??

How large is your matrix?
Is it perhaps convergent for matrices, say, up to 10x10?

 

[evinda]

The Hilbert matrix is not strictly diagonally dominant.
You may want to look up the definition if you want to use it in your work.

So,doesn't the Jacobi method converge because of the fact that the matrix is not strictly dominant and bacause it is also ill conditioned..Or for an other reason?

How large is your matrix?
Is it perhaps convergent for matrices, say, up to 10x10?

No,I have checked it for 50<=dimension<=1000..and I found the spectral radious p:
0.9962<=p<=1..But the methods do not converge

 

[I like Serena]

No,I have checked it for 50<=dimension<=1000..and I found the spectral radious p:
0.9962<=p<=1..But the methods do not converge

Note that the spectral radius approaches 1 when the matrix becomes large enough.
At that point the Jacobi method will converge very slowly.
Then even small rounding errors will throw the method off to diverge.

Perhaps you want to try if for dimensions up to 10?
You might want to do the same thing for the Hilbert matrix.

 

[evinda]

Note that the spectral radius approaches 1 when the matrix becomes large enough.
At that point the Jacobi method will converge very slowly.
Then even small rounding errors will throw the method off to diverge.

Perhaps you want to try if for dimensions up to 10?
You might want to do the same thing for the Hilbert matrix.

I think I am not able to do this,because I haven't get taught how to do this in MATLAB So,if I am asked to tell why the methods do not converge,is the right answer that they would converge because the spectral radious is smaller or equal to one,but they don't because of the rounding errors??or because of the precision of the digits??

 

[I like Serena]

I think I am not able to do this,because I haven't get taught how to do this in MATLAB

Huh? I do not understand.
If you can do it for 50 and 1000, it seems to me you should also be able to do it for 10.

So,if I am asked to tell why the methods do not converge,is the right answer that they would converge because the spectral radious is smaller or equal to one,but they don't because of the rounding errors??or because of the precision of the digits??

Yes.
But note that for the Jacobi method, the Hilbert matrix diverges because the spectral radius of the iteration matrix is larger than 1.

Btw, it is the lack of precision of the digits is the reason for the rounding errors.
If we had infinitely many significant digits, there wouldn't be any rounding errors.

 

[I like Serena]

Here's my result for n=5 for the Hilbert matrix.
(This is the output of MathCAD instead of Matlab. ;))View attachment 1748

 

[evinda]

Huh? I do not understand.
If you can do it for 50 and 1000, it seems to me you should also be able to do it for 10.
Yes.
But note that for the Jacobi method, the Hilbert matrix diverges because the spectral radius of the iteration matrix is larger than 1.

Btw, it is the lack of precision of the digits is the reason for the rounding errors.
If we had infinitely many significant digits, there wouldn't be any rounding errors.

Oh,sorry!I thought you meant that I should change the precision of the digits..

So,the Hilbert matrix diverges because the spectral radius of the iteration matrix is larger than 1,and the the 2-(-1) band matrix bacause of the rounding errors??

- - - Updated - - -

Here's my result for n=5 for the Hilbert matrix.
(This is the output of MathCAD instead of Matlab. ;))View attachment 1748

I found the max eigenvalue 3.4441 using the Jacobi method,and 1.0000,using the Gauss-Seidel method..

 

[I like Serena]

Oh,sorry!I thought you meant that I should change the precision of the digits..

That explains it. (Drunk)

So,the Hilbert matrix diverges because the spectral radius of the iteration matrix is larger than 1,and the the 2-(-1) band matrix because of the rounding errors??

That would be for the Jacobi method yes.

Now that I have made the calculations for the Hilbert matrix with the Gauss-Seidel method, I can see that the iteration matrix for the Hilbert matrix has a spectral radius approaching 1, meaning it also diverges due to rounding errors.

I found the max eigenvalue 3.4441 using the Jacobi method,and 1.0000,using the Gauss-Seidel method..

Looks like the same result then! (Cool)

 

[evinda]

That explains it. (Drunk)
That would be for the Jacobi method yes.

Now that I have made the calculations for the Hilbert matrix with the Gauss-Seidel method, I can see that the iteration matrix for the Hilbert matrix has a spectral radius approaching 1, meaning it also diverges due to rounding errors.
Looks like the same result then! (Cool)

I also found that the spectral radius is approaching 1 with the Gauss Seidel,and >= 42.6769 with the Jacobi method..Have you found the same result? :)

 

[I like Serena]

I also found that the spectral radius is approaching 1 with the Gauss Seidel,and >= 42.6769 with the Jacobi method..Have you found the same result? :)

That's what I have for a dimension of 50 for the Hilbert matrix.
With dimension 500, I get 1 respectively 435.661.

 

[I like Serena]

Btw, it still only means that the methods might diverge.
It still depends on the actual b vector and the initial guess what will happen.
The best we can say is that they are not guaranteed to converge.
Only the 4-1 band matrix is guaranteed to converge.

For the 4-1 band matrix I get a spectral radius of 0.249 for Gauss-Seidel and 0.499 for Jacobi. ;)

 

[evinda]

That's what I have for a dimension of 50 for the Hilbert matrix.
With dimension 500, I get 1 respectively 435.661.

I get the same result! :)

- - - Updated - - -

Btw, it still only means that the methods might diverge.
It still depends on the actual b vector and the initial guess what will happen.
The best we can say is that they are not guaranteed to converge.
Only the 4-1 band matrix is guaranteed to converge.

For the 4-1 band matrix I get a spectral radius of 0.249 for Gauss-Seidel and 0.499 for Jacobi. ;)

I understand!Thank you very much! :D