3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I checked it and find the same results as you do. $\endgroup$ – Dr_Sam Apr 25 '13 at 6:40
  • $\begingroup$ 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? $\endgroup$ – hardmath Apr 25 '13 at 14:09
  • $\begingroup$ @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). $\endgroup$ – jake Apr 25 '13 at 15:23
  • $\begingroup$ That preview is for the 2nd edition. Is it the same as yours, or perhaps you have an earlier edition/printing? $\endgroup$ – hardmath Apr 26 '13 at 4:03
  • $\begingroup$ @hardmath, That's the one I have. $\endgroup$ – jake Apr 26 '13 at 4:10
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I was suspecting such. Probably listed in the book errata somewhere online. $\endgroup$ – jake Apr 25 '13 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.