Computational linear algebra — intensive review
Worked through Lectures 9–16 using the original course handouts, created understanding-first reference sheets, applied the ideas to Assignment 4, and consolidated the material into a four-sheet exam reference.
Learning outcome
Built a connected understanding of iterative SPD solvers, Conjugate Gradient, least squares, QR construction, Householder and Givens transformations, eigenvalue iterations, practical QR algorithms, and SVD—with attention to why each method works, the structure it exploits, and its computational cost.
Lecture 9 — Steepest Descent
- Reframed solving Ax = b for symmetric positive definite A as minimizing the quadratic F(x) = ½xᵀAx − bᵀx.
- Connected the gradient Ax − b with the residual b − Ax, making the residual the negative-gradient direction.
- Worked through exact line search, the step length, residual recurrence, geometric zig-zag behaviour, the A-norm error viewpoint, and how conditioning controls convergence.
Lecture 10 — Conjugate Directions & Conjugate Gradient
- Studied why steepest descent can revisit directions and why Euclidean orthogonality is not the right geometry for an SPD system.
- Learned the A-inner product, A-norm, and A-orthogonal—or conjugate—directions.
- Built conjugate directions using Gram–Schmidt in the A-inner product and followed the simplifications leading to the Conjugate Gradient algorithm.
- Connected finite-step convergence in exact arithmetic to having at most n independent conjugate directions.
Lecture 11 — Least Squares
- Studied overdetermined systems and minimizing the squared residual norm.
- Understood geometrically why the optimal residual is perpendicular to the range of A.
- Derived the normal equations and connected them to the pseudoinverse in the full-column-rank setting.
- Compared normal-equation and QR approaches and used reduced QR to obtain a triangular least-squares solve.
Lecture 12 — Gram–Schmidt QR
- Interpreted A = QR columnwise: Q stores orthonormal directions and upper-triangular R stores reconstruction coefficients.
- Worked through classical Gram–Schmidt projection subtraction and normalization.
- Studied Modified Gram–Schmidt and why its ordering improves floating-point orthogonality.
- Reviewed QR construction and the computational cost of Gram–Schmidt.
Lecture 13 — Householder & Givens QR
- Studied Householder reflections as orthogonal triangularization by repeatedly zeroing entries below the diagonal.
- Connected reflection geometry to projection onto a hyperplane and worked through explicit by-hand constructions.
- Understood why implementations store reflector vectors instead of full Q and how Q or Qᵀ can be applied implicitly.
- Studied Givens rotations for zeroing selected entries and their role in structured QR and Hessenberg computations.
Lecture 14 — Eigenvalues, Eigenvectors & Iterative Methods
- Reviewed eigendecomposition for real symmetric matrices and why numerical methods avoid explicitly solving the characteristic polynomial.
- Studied Gershgorin disks as eigenvalue-location bounds and the Rayleigh quotient as an eigenvalue estimate.
- Studied power iteration, inverse iteration, shifting, Rayleigh quotient iteration, complexity, and the basic QR iteration idea.
Lecture 15 — Practical QR Iteration
- Extended power iteration to simultaneous or block iteration to recover several eigen-directions.
- Understood why QR orthonormalization is inserted at every step to preserve a stable basis for the evolving subspace.
- Studied the equivalence between simultaneous iteration and QR iteration.
- Followed the practical two-phase strategy: reduce to Hessenberg or tridiagonal form, then run cheaper QR sweeps.
Lecture 16 — Singular Value Decomposition
- Motivated SVD as a diagonalization-like factorization for rectangular as well as square matrices.
- Interpreted right singular vectors as input directions, left singular vectors as output directions, and singular values as stretch factors.
- Distinguished reduced and full SVD and linked right singular vectors to eigenvectors of AᵀA.
- Studied rank, fundamental subspaces, matrix norms, conditioning, symmetric and SPD cases, and best low-rank approximation.
Assignment 4 — applied problem solving
- Proved a projection matrix is idempotent and used Householder properties to establish orthogonality.
- Adapted Householder QR ideas to derive a QL factorization with lower-triangular L.
- Analyzed QR factorization of a symmetric tridiagonal matrix, including sparsity, recovered structure, and local 2×2 Householder complexity.
- Practised Householder QR and reduced SVD by hand.
- Used known SVD factors to solve square systems and tall least-squares problems without explicitly constructing inverses.
Study method & evidence of work
- Used the original lecture material as the source of truth.
- Used ChatGPT interactively to unpack notation, proofs, algorithms, and assignment-style questions rather than only reading final formulas.
- Produced lecture-specific deep-understanding sheets preserving theory, derivations, algorithms, examples, explanations, and key formulas.
- Consolidated the covered material into an optimized four-sheet, font-8 final-exam reference.
- Applied the concepts to Assignment 4 problems involving Householder matrices, QR structure, tridiagonal matrices, complexity, and SVD.
Resources & source material
- CS475 lecture handouts for Lectures 12–16
- CS475 Assignment 4
- Deep-understanding and complete cheatsheets for Lectures 9–16
- cs475C1 consolidated notes
- Lecture 16 LaTeX source
- CS475 Final — four optimized font-8 reference sheets
- Interactive ChatGPT study and problem-solving sessions