# 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. Commented Apr 25, 2013 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
Commented Apr 25, 2013 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
Commented Apr 25, 2013 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
Commented Apr 26, 2013 at 4:03
• @hardmath, That's the one I have.
– jake
Commented Apr 26, 2013 at 4:10

The book is wrong.

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.

Therefore, Jacobi's method applied to your matrix converges.

See Applied Numerical Linear Algebra by James Demmel for details. In particular, see Chapter 6 and Theorem 6.2.

• Thanks. I was suspecting such. Probably listed in the book errata somewhere online.
– jake
Commented Apr 25, 2013 at 23:53