Jacobi Iteration diverges?

Question

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?

Answer 1

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.