# Jacobi's Method for a matrix

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?

-
@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

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

-
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