TW776/876: Numeriese Metodes/Numerical Methods

TW776/876 (2016)

Numeriese Metodes Numerical Methods

Inligtingstukke Information Sheets

Information Sheet

Aankondigings Announcements

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)

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

JAC Weideman