Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say we have a $2\times 2$ matrix $A$:

$$A=\begin{pmatrix} 1&2 \\ 3&1\end{pmatrix}$$

What is the spectral radius of $A$?

So I get the eigenvalues of $A$, and the maximum eigenvalue (absolute VALUE) = spectral radius?

And for the linear system $Ax = b$ where $b = (1, 0)^{t}$, to define the Jacobi Method, I see we need to bring in $x^{k}$, and an $A$, but I need help in making it iterative.

Also, does the Jacobi method converge to any initial guess $x_0$ in this example?

share|improve this question
    
@Git: whoops. Got confused with the operator norm. –  Qiaochu Yuan Mar 8 '13 at 7:06
    
Generally you need diagonal dominance, or similar, to use Jacobi methods... $A$ above is not diagonally dominant. –  copper.hat Mar 8 '13 at 7:09

1 Answer 1

You are correct for the spectral radius:

$$\rho (A) = max |\lambda|,$$

where $\lambda$ is an eigenvalue of $A$.

To write the Jacobi iteration, we solve each equation in the system as:

$E1: x_1 = -2x_2 + 1$

$E2: x_2 = -3x_1 + 0$

This is typically written as, $Ax = (D - L - U)x = b$,

where $D$ is the diagonal, $-L$ is the lower triangular and $-U$ is the upper triangular. Solving this system results in:

$x = D^{-1}(L + U)x + D^{-1}b$ and the matrix form of the Jacobi iterative technique is:

$x_{k} = D^{-1}(L + U)x_{k-1} + D^{-1}b, k = 1, 2, \ldots$

Writing these out, gives:

$$A = \begin{pmatrix} 1&2 \\ 3&1\end{pmatrix} = D - L - U = \begin{pmatrix} 1&0 \\ 1&0\end{pmatrix} - \begin{pmatrix} 0&0 \\ -3&0\end{pmatrix} -\begin{pmatrix} 0&-2 \\ 0&0\end{pmatrix}.$$

This results in an iteration formula of (compare this to what I started with with $E1$ and $E2$ above):

$$x_{k} = D^{-1}(L + U)x_{k-1} + D^{-1}b = \begin{pmatrix} 0&-2 \\ -3&0\end{pmatrix}x_{k-1} + \begin{pmatrix} 1 \\ 0\end{pmatrix}$$

This can also be written in a component-wise form.

We know the solution here is $\displaystyle x = (-\frac{1}{5}, \frac{3}{5})$, but no initial $x_{0}$ choice will give convergence here because $A$ is not diagonally dominant (it is easy to manually crank tables for different starting $x_0's$ and see what happens).

Note: See the nice comment below from Elmar Zander, which is an oversight on my part! Thanks Elmar!

Regards

share|improve this answer
    
Can you input in the L and U and make this a little more complete? Also, the question has x sub zero, not x^0. Thanks! –  mary Mar 8 '13 at 7:49
    
@mary: See updated response. Regards –  Amzoti Mar 8 '13 at 15:32
    
Diagonal dominance is sufficient but not necessary for convergence, so it's not quite right to draw the conclusion as you do here. However, the spectal radius of the iteration matrix $D^{-1}(L+U)$ is clearly larger than one, so the conclusion itself is correct. –  Elmar Zander Mar 8 '13 at 16:40
    
@ElmarZander: thanks for the clarification - I even updated the answer to point to it and a silly oversight on my part! Regards –  Amzoti Mar 8 '13 at 16:46
    
@Amzoti That's what I like so much about SE: unlike in "real life", if you spot some mistake and point it out, people here are not offended but rather say thanks. That makes discussions here really constructive and nice. –  Elmar Zander Mar 8 '13 at 16:54

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.