# Jacobi Iteration diverges?

I'm working through a problem in a textbook as follows:

"Consider the $d \times d$ Toeplitz matrix $$A = \left[ \begin{array}{ccccc} 2 & 1 & 0 & \cdots & 0 \\ -1 &2 &1&\ddots&\vdots\\ 0&\ddots&\ddots&\ddots&0 \\ \vdots &\ddots&-1&2&1\\ 0&\cdots&0&-1&2 \end{array} \right].$$

Find explicitly all the eigenvalues of the Jacobi iteration matrix $B$. Conclude that this iterative scheme diverges."

Deriving the matrix $B$ as

$$B = \left[ \begin{array}{ccccc} 0 & -\frac{1}{2} & 0 & \cdots & 0 \\ \frac{1}{2} &0 &-\frac{1}{2}&\ddots&\vdots\\ 0&\ddots&\ddots&\ddots&0 \\ \vdots &\ddots&\frac{1}{2}&0&-\frac{1}{2}\\ 0&\cdots&0&\frac{1}{2}&0 \end{array} \right]$$

and solving for the eigenvalues using the difference equation $q_{k+1} +2 \lambda q_k - q_{k-1} = 0$, I found the set of eigenvalues to be $$\lambda_{j} = i \cos(\frac{j\pi}{d+1}), \quad \quad j = 1,2, \dots, d$$

I then confirmed this fact using the eig function in Matlab.

However, this leads to the conclusion that $\rho(B) = \max|\lambda_j| = |i\cos(\frac{\pi}{d+1})| < 1$, in which case the Jacobi Iteration should definitely converge (although maybe not very quickly). Why, then, does the textbook think that I should conclude the opposite?

• I checked it and find the same results as you do. – Dr_Sam Apr 25 '13 at 6:40
• Which textbook and exercise are you asking about? Is it possible the phrase "this iterative scheme diverges" refers not to Jacobi iteration but to some alternative outlined previously in the exercise set? – hardmath Apr 25 '13 at 14:09
• @hardmath, It's from "A First Course in Numerical Analysis of Differential Equations", by Arieh Iserles. Its Exercise 12.10 on p. 289 (which is unfortunately not part of the preview available on Google Books). – jake Apr 25 '13 at 15:23
• That preview is for the 2nd edition. Is it the same as yours, or perhaps you have an earlier edition/printing? – hardmath Apr 26 '13 at 4:03
• @hardmath, That's the one I have. – jake Apr 26 '13 at 4:10

There is another way to see this, using somewhat more heavy machinery. There is a theorem that states that if a matrix $A$ is irreducible and weakly row diagonally dominant, then Jacobi's method converges. Here weakly diagonally row dominant means $|a_{ii}| \geq \sum_{j\neq i} |a_{ij}|$ for all $i$ and irreducible means that there is no permutation matrix $P$ such that $$PAP^T = \left[\begin{array}{cc} A_{11} & A_{12} \\ 0 & A_{22}\end{array}\right]$$
Clearly your matrix is weakly diagonally row dominant. It can be shown that a matrix $A$ is irreducible if and only if its directed graph is strongly connected. Since your matrix's sparsity pattern is identical to that of the one-dimensional Laplacian matrix, and the directed graph of the one-dimensional Laplacian matrix is strongly connected, it follows that the directed graph of your matrix is strongly connected as well and thus your matrix is irreducible.