ERRATUM for
An Introduction to the Conjugate Gradient Method Without the Agonizing Pain
Jonathan Shewchuk
Page iv, line 2: On some early copies, the IP address of the FTP server is
listed as 128.2.218.42. Unfortunately, one week after I publicized the report,
the IP address was changed to 128.2.222.79.
Page 5, paragraph beginning "The fact that f(x) is...", last sentence: "The
value of y determines..." should read "The values of b and c determine...".
Page 10, line 1: "If B is nonsingular..." should read "If B is symmetric,
and often if B is not...". There are matrices that do not have a set of n
linearly independent eigenvectors. Matrices that do have n independent
eigenvectors are said to be "diagonalizable"; there is no relationship between
diagonalizability and singularity. For matrices that are not diagonalizable,
convergence also depends upon the spectral radius - Jacobi iterations are
guaranteed to converge if and only if the spectral radius is less than one -
but the reasons why are not as simple as the reasoning in the text.
Page 11, inequality at the bottom of the page: This inequality is only true
for normal matrices - matrices with a full set of orthogonal eigenvectors.
This includes all symmetric matrices. However, the matrices associated with
Jacobi's Method are, in general, not normal. For general matrices, it is true
that the error term will converge to zero as i approaches infinity, but not as
cleanly as the inequality would lead one to believe.
Page 13, last line: "It is proven in Appendix C2 that if A is nonsingular
and symmetric..." should read "It is proven in Appendix C2 that if A is
symmetric...". Singularity is irrelevant.
Page 20, paragraph beginning "Inequality 27 is plotted in Figure 20.":
This paragraph is misleading, as it implied that a matrix is defined to be
"ill-conditioned" if it converges slowly under Steepest Descent. In fact,
the term "ill-conditioned" means that a matrix is close to being singular
(in a well-defined mathematical sense).
Page 32, paragraph beginning "We also find that CG converges...": The phrase
"evenly distributed" is misleading. "Randomly distributed" might be more
appropriate.
Page 37, paragraph beginning "We can circumvent this difficulty...": The
matrices M^-1 A and E^-1 A E^-T have the same eigenvalues, but do not
necessarily have the same condition number, because M^-1 A is not generally
symmetric, and the condition number of a nonsymmetric matrix is defined
differently than on page 20.
Page 52, Appendix C2, first line: "Suppose that A is nonsingular" should read
"Suppose that A is symmetric".
A new, corrected version of the article will be available soon. Email
jrs@cs.cmu.edu for details.