7
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Dominique
    Commented Nov 30, 2012 at 17:46
  • $\begingroup$ 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. $\endgroup$
    – Honza Brabec
    Commented Nov 30, 2012 at 21:31
  • $\begingroup$ Have you considered using weighted jacobi iteration instead? $\endgroup$
    – Dan
    Commented Jan 24, 2013 at 0:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dan
    Commented Jan 25, 2013 at 17:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dan
    Commented Jan 25, 2013 at 17:48

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Honza Brabec
    Commented Jan 25, 2013 at 10:39
  • $\begingroup$ @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). $\endgroup$
    – David Ketcheson
    Commented Jan 27, 2013 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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