Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I have a $4\times 4$ matrix and I want to use Jacobi iteration on it. Right now the spectral radius is higher than $1$. I know that the method is guaranteed to converge if the matrix is diagonally dominant. I can't do any reordering that would make the matrix diagonally dominant. Is it sensible to try to get as close as possible to diagonally dominant matrix and if the spectral radius is still greater than $1$, I can state that I can not use Jacobi iteration? Or is it possible that there can still exist some reordering of the columns and rows, that would have spectral radius lesser than $1$?

Edit: In other words, is there some correlation between some of the matrix parameters and the size of the spectral radius?

share|improve this question

migrated from math.stackexchange.com Jan 23 '13 at 15:50

This question came from our site for people studying math at any level and professionals in related fields.

1  
If I understand well, you're wondering if the spectral radius may be less than 1 even though the matrix is not diagonally dominant. The answer is yes, it may, because the spectral radius is bounded above by the $\ell_{\infty}$-norm. That your coefficient matrix is diagonally dominant guarantees that the $\ell_{\infty}$-norm of the Jacobi operator $D^{-1} (L+U)$ is less than 1. This in turn guarantees that $\rho(D^{1} (L+U)) \leq \|D^{-1} (L+U)\|_{\infty} < 1$. But it could be that for some reordering $\rho(D^{-1} (L+U)) < 1 \leq \|D^{-1} (L+U)\|_{\infty}$. –  Dominique Nov 30 '12 at 17:46
    
Actually I knew that the spectral radius can be lesser than 1 even if the matrix is not diagonally dominant. I was just wondering if there is some corellation of some of the matrix parameters and the spectral radius that would help me in optimizing the spectral radius without brute force. –  Honza Brabec Nov 30 '12 at 21:31
    
Have you considered using weighted jacobi iteration instead? –  Dan Jan 24 '13 at 0:36
1  
@Honza Brabec: Super-relaxation (also called Successive Over-Relaxation or SOR) and weighted Jacobi are different methods. Weighted Jacobi converges slower than Jacobi, but will converge for some matrices that Jacobi iteration won't converge for. –  Dan Jan 25 '13 at 17:39
1  
@Honza Brabec: Basically you just multiply the iteration matrix by some $0< \epsilon< 1$, this reduces the absolute value of every eigenvalue by a factor of $\epsilon$, with a corresponding drop in the spectral radius. –  Dan Jan 25 '13 at 17:48
show 1 more comment

1 Answer 1

Reordering will not ever change whether a matrix is diagonally dominant, nor will it change the spectral radius.

share|improve this answer
    
IMO reordering can change spectral radius for example ((1,2),(3,4)) has radius 5.37 and ((3,4),(1,2)) has radius 4.56 –  Honza Brabec Jan 25 '13 at 10:39
    
@HonzaBrabec You're reordering rows without reordering columns. That will change the solution of your linear system (which apparently matters to the OP, since he is interested in using Jacobi iteration). –  David Ketcheson Jan 27 '13 at 8:36
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.