## 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