Marks: Current marks (excluding Test 2 and Assignment 6) can be found here. Please send Email if you see mistakes.
Second Test: Friday, May 20, 09:00-11:00 (room M301). Covers the material of Weeks 7-13 (see below). Sample test.
Assignment 5: Has been marked and can be collected from a blue folder on the table outside A310. Solutions below.
Assignment 6: Solutions below.
Class room demo (10 May): CG and PCG demo
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