Marks: All marks (now including Test 2 and Assignment 6) can be found here. (Note that Test 2 marks were adjusted so that it counts out of 50. Note also that these marks are tentative and subject to change pending the outcome of an external moderation.) Please send Email ASAP if you see mistakes.
Assignments 5 and 6: Have been marked and can be collected from a blue folder on the table outside A310.
Supplementary reading: Additional notes on the CG method (sections 2.6.3 and 2.6.4 are compulsory reading), and the derivation of the minmax error bound (compulsory reading).
Supplementary reading: Computing the optimal SOR parameter for the model problem (optional but recommended reading)
Chapter 1; Lecture Slides 1 (Background Material = Recommended Reading)
Chapter 2; Lecture Slides 2 (Linear Systems)
Chapter 3; Lecture Slides 3 (Least Squares)
Chapter 4; Lecture Slides 4 (Eigenvalues)
Chapter 11 (pp.335-350); Lecture slides 11 (long) (short) (Direct and Iterative Methods for Sparse Systems)
Week 1 (Feb 2&4): Linear systems; existence and uniqueness of solutions; vector and matrix norms; intro to conditioning of linear systems. Undergraduate slides: English Afrikaans
Week 2 (Feb 9&11): Conditioning (cont); the A = LU and PA = LU factorizations.
Week 3 (Feb 16&18): Instability of GE and the growth factor; Complexity of matrix computations; Sherman-Morrison formula
Week 4 (Feb 23&25): Symmetric positive definite systems; Cholesky factorization; Review of the least squares problem; Normal equations. Undergraduate notes on least squares English Afrikaans
Week 5 (Mar 1&3): Least squares problem (cont); Orthogonal matrices; QR factorization with Gram-Schmidt.
Week 6 (Mar 8&10): Gram-Schmidt; Solving the LS problem with Householder. Geometry of a Householder transformation diagram. Intro to the eigenvalue problem.
Test week & Easter break
Week 7 (Mar 29&31): Eigenvalues: similarity, power iterations, Rayleigh-Quotient iteration. Properties of symmetric/Hermitian matrices
Week 8 (Apr 5&7): QR iteration. Lanczos & Arnoldi algorithms.
Week 9 (Apr 12&14): PDE model problem. Related undergraduate notes. Direct methods for sparse matrices: reordering and bandwidth reducing algorithms. Intro to iterative methods.
Week 10 (Apr 19&21): Jacobi, Gauss-Seidel, SOR, Incomplete Cholesky iterations. Convergence rates and complexity for the 2D model problem.
Week 11 (Apr 26&28): Convergence rates and complexity (cont). Quadratic forms. Solving s.p.d. systems with minimization methods. Method of steepest descents.
Week 12 (May 3; no class on May 5): Conjugate gradient method (CG).
Week 13 (May 10 & 12): Preconditioned CG method. Error estimates for CG. Nonsymmetric variants of CG.
Assignment 1 (handed in on Feb 18)
Assignment 2 (handed in on March 1) solutions
Assignment 3 (handed in on March 10) solutions
Assignment 4 (handed in on April 12) (Additional reading) solutions
Assignment 5 (handed in on April 26) solutions
Assignment 6 (handed in on May 13) solutions
Fitting a circle to data in the (x,y)-plane: class room
on 25 Feb
Solving the least squares problem if QR factors are known: class room demo on March 1.
Reordering algorithms for direct methods for sparse systems: class room demo on March 12
Iteration methods for solving sparse Ax = b: class room demo on April 19
Steepest descent for Ax = b: class room demo and plot on 28 April
CG and PCG demo: class room demo on May 10