21-344 Numerical Linear Algebra

Instructor: Zecheng Zhang.

Office: Wean Hall 7216.

Email: zechengz@andrew.cmu.edu.

Office hour: MF (03:50 pm to 04:50 pm)

Course information

The syllabus (tentative) is available here.
I will post the homewrok in Gradescope in Canvas.
Class notes

I will upload the class notes in this section.
  • The first 2 lectures, matrix multiplication, subspace, column space, row space.
  • Jan 23, rank, Rank theorem, rank factorization.
  • Jan 25, projection, orthogonal.
  • Jan 27, orthogonal matrix, orthogonal complement, orthogonal projection.
  • Jan 30, construction of orthogonal projector, orthogonal projector given non-orthonormal basis, best approximation theorem.
  • Feb 1 (updated on Feb 3) diagonalizable, unitary diagonalizable, Schur Theorem.
  • Feb 3 (updated on Feb 5) unitary matrix, unitary equivalent, normal matrix (normal implies unitary diagonalizable).
  • Feb 6 Hermitian matrix, equivalent theorem for Hermitian (x^*Ax is real).
  • Feb 8 equivalent theorem for Hermitian, Spetral theorem, Hermitian form theorem, Rayleigh Ritz theorem.
  • Feb 10 construction of SVD, full SVD.
  • Feb 13 Theorem: row(A) = V_p and co(A) = U_p, comparison of SVD and Schur.
  • Feb 15 SVD examples, A^TA eigenvalues are non-negative and the second definition of SVD.
  • Feb 17 L2 and F norm, Courant Fisher Theorem.
  • Feb 22 uniquenss of singular value, Courant Fisher Theorem, low rank approximation A_k and its rank.
  • Feb 24 midterm questions, Eckart-Young low-rank approximation theorem for L2 norm.
  • Feb 27 Weyl's inequality for singular values.
  • Mar 1 Eckart-Young for F-norm, POD. This file contains all updated SVD notes without my writing.
  • Mar 3 review of GS algorithm, QR, and modified QR.
  • Mar 13 preview. Done Modified GS for QR (from the projection perspective, I corrected the index mistake in class), flops and operation counts.
  • Mar 15 operation count of the modified GS for QR, construction of Q_k (of the Household reflector), Household triangularization.
  • Mar 17 Householder algorithm, implicit computation of Q^*b and Qx
  • Mar 20 least square problems, normal equation, QR to compute least square, SVD and least square
  • Mar 22 least square problem examples, relative conditioning number, examples of well/ ill-conditioned problem, polynomial root finding is ill-conditioned.
  • Mar 27 conditioning of Ax given perturbation in x (special case when A is square invertiable, A is rectangle but has full col rank), conditioning of Ax = b given perturbation in A.
  • Mar 29 midterm 2 summary, floating point, machine epsilon
  • Mar 31 algorithm accuracy, backward stability, condition plus bw stable = accuracy, sin(x) when x = \pi/2-\delta.
  • April 3 backward error and numerical verification of QR backward stability. The kaggle code of the class is here: QR.
  • April 5 proof of backward stability of QA where Q is an unitary matrix.
  • April 7 complete notes of conditioning and backward stability.
  • April 7 backward stability of solving Ax = b by QR (I corrected a small error I made in the first page of the handwritten notes), and the algorithm accuracy.
  • April 10 Rayleigh quotient, power iteration (from eigenvector approx to eigenvalue by Rayleigh quotient), inverse iteration for eigenvalue problems.
  • April 12 Rayleigh quotient iteration, reduction to Hessenberg form.
  • April 17 QR iteration for eigenvalue, proof of A^k = Q^{(k)}R^{(k)}
  • April 19 connection of QR with Power iteration, shifted QR, preprocessing.
  • April 24 preview

    • Useful Links