Errors in the book

"Applied Numerical Linear Algebra"

by James Demmel

Updated Fall 2020

I will continue to post errors and clarifications that I or others find in this location, as well as the source.

  • Page 22, Lemma 1.7, part 2: This is imprecise on which norms I mean. There are 3 norms in the inequality "||A*B|| <= ||A|| * ||B||", and not every choice of 3 norms makes sense. The easiest case is when A and B are square, and you use the same vector norm in the numerator and denominator of definition 1.9 for all 3 norms. This is all I wanted you to prove for Question 1.16. (Hyounjin Kim)

    The result is more generally true as long as you use the same norm for the vectors in the domain space of A*B and B, the same norm for vectors in the range space of B and the domain space of A, and the same norm for vectors in the range space of A*B and the range of A. In other words, you can choose three different vector norms.

  • Page 23, Lemma 1.7, part 7: The notation "lambda_max (A* A)" means "the largest eigenvalue of the matrix conjugate-transpose(A) times A".
  • Page 23, Lemma 1.7, Part 13: "|| A ||_1 <= || A ||_F" should be "(1/sqrt(n)) * || A ||_1 <= || A ||_F". (Hyounjin Kim)
  • Page 23, Lemma 1.7, proof: "q^T A^T A q = q^T lambda q" should be "q* A* A q = q* lambda q".
  • Page 23, Lemma 1.7, proof: In a denominator of a the second displayed equation, "|| Q* x ) ||" should be "|| Q* x ||".
  • Page 24, Question 1.2: It should be specified that vectors a and b are both nonzero. (Nicholas Knight)
  • Page 24, Question 1.7: y^H should be y*. Both are acceptable notations for the conjugate transpose of y. (Gerardo Lafferriere)
  • Page 26, Question 1.16: See the comments on pages 22 and 23 above.
  • Page 27, Question 1.18: In the first numbered fact, "s1 - a" and "(s1 - a) - b" should be "a - s1" and "(a - s1) + b". (Matt Podolsky)
  • Page 29, Question 1.20, part 2: "perturbed eigenvalues" should be "perturbed roots" in the next to last line. (Gerardo Lafferriere)
  • Page 29, Question 1.20, part 3: p'(r(i)) means the derivative of the polynomial p, evaluated at r(i).
  • Page 32, Section 2.2, line 2: "Ax=B" should be "Ax=b". (JD)
  • Page 37, Equation (2.8): "|| x ||" should be "|| x hat ||" in the denominator. (Gerardo Lafferriere)
  • Page 52, displayed equation near middle: the not-equal sign should be an equal sign. (Rich Vuduc)
  • Page 67, Table 2.1: The defintion of matrix multiplication should contain "b_{kj}", not "b_{jk}". (Rich Vuduc)
  • Page 68, line 4 from the bottom: q = 2n^3/(n^2 + 3n^2) should be q = 2n^3/(n^3 + 3n^2). (Eric Hallman)
  • Page 72, line 3 of Algorithm 2.9: U should be n-by-n, not m-by-m. (Maksim Oks)
  • Page 73 and 74: Change U_{21} and U_{31} to U_{12} and U_{13}, respectively, in the displayed factorizations of the matrix A.
  • Page 80, Prop. 2.3: The space needed is "n(bL + bU + 1)", not "bL + bU + 1". (Rich Vuduc)
  • Page 95, question 2.10. Assume A is n-by-n, not n-by-m. Also assume A is real, or else replace A^T by A^H. Assume M is real symmetric (or complex Hermitian, also replacing L^T by L^H). The question about A is correct as stated, but we will not define condition numbers for rectangular matrices until Chapter 3. (Tsuyoshi Koyama)
  • Page 95, question 2.11. Assume i is not equal to j. (Tsuyoshi Koyama)
  • Page 95, question 2.13, parts 2 and 3: The intent is to suppose that you have already done Gaussian elimination on A to get its L and U factors, so that solving Ax=b is fast (costs just O(n^2)), and then to exploit this to solve By=c in O(n^2), rather than O(n^3), which is what Gaussian elimination on B would cost. (Matt Podolsky)
  • Page 98, question 2.18 part 1. Assume that the first k steps of Gaussian elimination without pivoting succeed, i.e. do not try to divide by 0. (Tsuyoshi Koyama)
  • Page 114, Table in the middle of the page: "sigma_{k+1}/sigma_k" in the heading of column 2 should be "sigma_{k+1}/sigma_1".
  • Page 118, line 2: There is an extra closing parenthesis at the end of the line. (Matt Podolsky)
  • Page 119, last line: tilde_u should equal x + sign(x_1)*norm(x)*e_1, not x + sign(x_1)*e_1. (Matt Podolsky)
  • Page 122: The displayed matrix R(i,j,theta) differs from the identity matrix only in rows and columns i and j, whose entries are cos(theta) and +-sin(theta). (Matt Podolsky)
  • Page 127, 4th paragraph: "b = A^{-1} * x" should be "x = A^{-1} * b", and "b = A^{+} * x" should be "x = A^{+} * b". (Guenter Gramlich)
  • Page 127, Definition 3.2: "A^+ = V^T Sigma^+ U " should be "A^+ = V Sigma^+ U^T".
  • Page 135, Question 3.9: It should be specified that A has full column rank. (Nicholas Knight)
  • Page 137, Question 3.17: The question says A is m-by-n, so the vectors u(i) in Part 1 should be of length m, not n, and the loop in Part 2 should be "for i=1:min(m-1,n)", not "for i=1:m". (RuoChen Liang)
  • Page 145, Definition 4.4: "R^n" should be "R^n or C^n".
  • Page 147, line 4: "P^* A_22 P = T^tilde" should be "P^* A^tilde_22 P = T^tilde". (Tongge Wu)
  • Pages 165-166, Algorithm 4.6: The line of code updating Q should be Q(i+1:n,2:n) = P_i * Q(i+1:n,2:n). Also, the operation count of 14*n^3/3 on page 166 assumes the P_i are multiplied in the opposite order as in Algorithm 4.6, exploiting the special structure of P_i. (Casper Beentjes and Matteo Croci)
  • Page 188, Question 4.4, Part 4: "earlier subdiagonals" should be "earlier superdiagonals". (Yulong Dong)
  • Page 191, Question 4.15: In the fourth line of Matlab, " diag((1.5*ones(1,5)).\verb+^+(0:4)) + " should be " diag((1.5*ones(1,5)).^(0:4)) + " The "\verb+ +" is a latex error.
  • Page 192, Question 4.16, line 23: Numterm(2,1) should be NumTerms(2,1). (William De Meo)
  • Page 229: In the equation at the bottom of the page, matrix entry "a_n" should be "a_n - z". (Tongge Wu)
  • Page 259, proof of Corollary 5.4: The last displayed equation should be "(d/dt) T(-t) = -(d/dt) T at -t = + pi_0(F(T))*T - T*pi_0(F(T)) at -t"; the first term on the right has the wrong sign. (Emile Sahouria)
  • Page 260, Question 5.4. It should be stated that B and C are real-valued. (Nicholas Knight)
  • Page 275, line 1: "X and C" should be "X".
  • Page 280, proof of Lemma 6.5: In the 5th line of the displayed equation, " = max_i | lambda_i | + eps " should be " <= max_i | lambda_i | + eps "
  • Page 292, last line of text: "consistent ordering" should be "consistently ordered"
  • Page 296, Lemma 6.7, bullet 3: T_m(x) = cosh(m*arccosh(x)) if x >= 1, not if |x| >= 1
  • Page 304, 5th line of text: "q_j yields q_j A q_j" should be "q_j^T yields q_j^T A q_j".
  • Page 317, First line of Theorem 6.9: "A^hat = M^{-1/2}AM^{1/2}" should be "A^hat = M^{-1/2}AM^{-1/2}". (Zexuan Liu)
  • Page 342, equation (6.56): x^(i-1) should be d^(i-1).
  • Page 357, Question 6.5, Part 1: The expression for the eigenvectors should be: "z_ij, where z_ij = kron(y_j, x_i) whose ((l-1)*m+k)th entry is x_i(k)*y_j(l)" {using Matlab notation kron() for the Kronecker product}
  • Page 358, Question 6.5, Part 3: "(km+l)th entry" should be "((k-1)*m+l)th" entry.
  • Page 358, Question 6.5, Part 3: Equation (6.64) should be "(A kron B)(X kron Y) = (X kron Y)(Lambda_A kron Lambda_B)", although (6.64) is also mathematically correct. (Mathias Weiden)