### Aankondigings / Announcements

Summary of semester marks (now including Assignment 6 and Test 02 marks ). Please send Email if you see mistakes. Note that these marks are tentative and subject to moderation. Final marks will be made available on the university system in due course. If you have not received email from either lecturer then you are not eligible for any second opportunity tests.

Marked Assignment 6 available in the alphabetical boxes on the 4th floor

### Dosent / Lecturer

- Dr Nick Hale
- Office: A410
- Email nickhale@sun.ac.za

- Prof. JAC Weideman
- Office: A315
- Email weideman@sun.ac.za

### Rooster / Timetable

- Tuesday 13:00 @ M203
- Wednesday 10:00 @ M203
- Thursday 10:00 @ M203

### Inligtingstukke / Information Sheets

Information Sheet

### 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)

(Undergraduate notes on least squares: English /Afrikaans)

Chapter 4; Lecture Slides 4 (Eigenvalues)

Chapter 11 (pp.335-350); Lecture slides 11 (long) / (short) (Direct and Iterative Methods for Sparse Systems)

### Opdragte / Assignments

- Assignment 1 & Solutions 1
- Assignment 2 & Solutions 2
- Assignment 3 & Solutions 3
- Assignment 4 (Supplementary notes for Problem 4.) & Solutions 4
- Assignment 5 & Solutions 5
- Assignment 6 & Solutions 6

### 2017 Skedule / Schedule (tentative)

** Week 1** (Jan 31, Feb 1,2):

- Fundamentals (Undergraduate slides: eng1, eng2 / afr1, afr2)
- Linear systems
- Existence and uniqueness of solutions
- Vector and matrix norms
- Intro to conditioning of linear systems. (Undergraduate slides: eng / afr)

** Week 2** (Feb 7,8,9):

- Solving linear systems
- Elimination
- LU factorization
- Gaussian elimination

** Week 3** (Feb 14,15,16):

- Instability and error growth factor
- Pivoting
- Algorithmic complexity
- Sherman-Morrison formula

** Week 4** (Feb 21,22,23):

- Special types of linear systems
- Cholesky factorization
- Chapter 3: Least squares
- Normal equations

** Week 5** (Feb 28, Mar 1,2):

- Conditioning of LS problem
- QR Factorization
- Householder transformation
- Givens rotations

** Week 6** (Mar 7,8,9):

- Gram-Schmidt
- Singular value decomposition (SVD)

Term break

** Week 7** (Mar 22, 23):

- Review of eigenvalues, eigenvectors, diagonalization (Undergraduate slides: eng / afr)
- Review continued

** Week 8** (Mar 28, 29, 30) (no live lectures)

- Similarity transformations, power iteration and its variants (video lectures Lecture 1a Lecture 1b)
- Rayleigh-quotient iteration, QR iteration (video lectures Lecture 2a Lecture 2b)
- Some implementation details of QR iteration, Hessenberg factorization (video lectures Lecture 3a Lecture 3b )

** Week 9** (Apr 4, 5, 6)

- Arnoldi and Lanczos algorithms
- Arnoldi & Lanczos continued
- Model problem, sparse matrices PDE model problem. Related undergraduate notes.

** Week 10** (Apr 18, 19, 20)

- Direct methods for sparse systems; reordering (classroom demo)
- Iterative methods for Ax = b: splitting methods; convergence
- Jacobi, Gauss-Seidel, SOR iterations (classroom demo).

** Week 11** (Apr 25, 26; no class on 27)

- Jacobi, Gauss-Seidel, SOR iterations (continued)
- Rate-of-convergence for the 2D Model Problem

** Week 12** (May 2, 4; no class on 3)

- Minimization methods for Ax = b when A is s.p.d.
- Method of steepest descent (Figure) (Implementation)

** Week 13** (May 9, 10; 11)

- Method of conjugate gradients (Implementation)
- Pre-conditioned conjugate gradient method. (Clustering Demo) (Convergence of all methods)

### MATLAB Kodes / MATLAB Codes

- decode_ieee.m - Decodes an IEEE 754 double-precision value.
- cos_demo.m - Demonstrate cancellation error.
- myhouseholder.m - Inefficient Householder.
- myhouseholder2.m - Efficient Householder.
- myhouseholder3.m - Efficient Householder in loop form.
- myhouseholder4.m - Efficient Householder storing v.
- mygivens.m - Inefficient Givens for a vector.
- mygivens2.m - Inefficient Givens for a matrix example (interactive).
- mygivens3.m - Efficient Givens for matrix example.

### 2016 Skedule / Schedule (for reference)

** 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).

** Test week & Easter break **

** Week 7** (Mar 29&31):
Eigenvalues: intro, 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.