TW776/876: Numeriese Metodes/Numerical Methods

TW776/876 (2016)

Numeriese Metodes Numerical Methods

Inligtingstukke Information Sheets

Information Sheet

Aankondigings Announcements

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)

Notas Notes

MATLAB Intro and accompanying lecture slides Afrikaans English

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)

Skedule Schedule

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.

Opdragte Assignments

Assignment 1 (handed in on Feb 18) solutions
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 demo 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

JAC Weideman