| Oorsig | Overview |
|---|---|
| Die module fokus op numeriese metodes vir matriksbewerkings. Ons kyk na die effektiewe oplos van vierkantige lineêre stelsels, kleinste-kwadrate probleme, en die eiewaarde probleem. Direkte sowel as iteratiewe metodes word behandel, met die klem op yl matrikse en matrikse met struktuur. Slaggate soos numeriese onstabiliteit en sleg-geaardheid word uitgewys. Ons beskou modelprobleme uit parsiële differensiaalvergelykings en beeldverwerking. Teorie, algoritmiese aspekte en toepassings word in gelyke mate beklemtoon. | The module focuses on numerical methods for matrix computations. We look at the effective solution of square linear systems, least squares problems, and the eigenvalue problem. We consider direct as well as iterative methods, with special attention to sparse matrices and structured matrices. Pitfalls such as numerical instability and ill-conditioning are pointed out. Model problems are drawn from partial differential equations and image processing. Theory, algorithmic aspects, and applications are emphasised in equal measure. |
Dosente / Lecturers
| Dosent / Lecturer | Kantoor / Office | E-pos / Email |
|---|---|---|
| Prof. André Weideman | A315 | weideman at sun |
| Stéfan van der Walt | A314 | stefan at sun |
Test: 29 March
Test 1 is scheduled for 29 March, 09:00-11:00 and will count 20 percent of your final mark. Closed book, closed notes, all calculators allowed (but no laptops).
The test covers all material discusssed in class up to March 9 (inclusive). This is essentially Chapter 1 of Saad (excluding sections 1.10 and 1.12) plus the material that was added in class to supplement the textbook.
Problems will be a mixture of theory and hand calculation on small matrices. It will not be expected of you to prove theorems but you should understand the key point of the most important theorems and know how to apply it. (These important theorems include Thm 1.1, 1.4, 1.7, 1.9, and 1.10.) Be able to do operation counts for the most important algorithms. Know the vocabulary!
To prepare for the test, be sure you can do all non-software computations that were part of the first four assignments. In addition, some extra exercises to help you prepare can be found here, here and here. These exercises were copied from the book of B.N. Datta (on reserve at the desk of the Engineering Library.)
Lectures
| Date | Topic |
|---|---|
| Previous lectures | |
| 11/03 | Video lecture on direct methods for large sparse Ax = b: the minimum degree algorithm. |
| 26/01 | Model problem: Finite difference modelling of partial differential equations, Saad p. 47. One-dimensional case, p. 51. Two-dimensional case, p.54. |
| 28/01 | Revision: Gaussian elimination, leading to LU factorisation. Improving numeric stability by row interchanges (partial pivoting). Solving for multiple right-hand sides, using Ly=Pb, Ux=y. See handout. |
| 01/02 | LU Growth factor. Revision: complex matrices, square matrices, and eigenvalues (Saad, p. 3). |
| 02/02 | Eigenvectors and values of a tri-diagonal matrix with constant values on each diagonal. Assignment hand-out. |
| 04/02 | Revision of vocabulary (Saad, 1.3). Matrix structures: banded, upper Hessenberg, Toeplitz, Hankel, circulant, etc. Inner product and norms (Saad, 1.4). |
| 08/02 | Matrix norms, induced vector norms. Note that the definition of (Saad, 1.5) is more general than commonly used. Derivation of 1-norm (equation 1.9). Example 1.1, p.9 shows that the spectral radius is not a suitable matrix norm. |
| 09/02 | Orthogonal and orthonormal sets; introduction to Gram-Schmidt (Saad, p. 10-11). |
| 11/02 | The Reduced QR-factorisation (Saad, Alg. 1.1). |
| 16/02 | QR factorisation based on Householder reflections. |
| 18/02 | Least Squares using QR factorisation |
| 22/02 | Least Squares example. Operations count for Gaussian elimination. |
| 23/02 | Operations count for Gram-Schmidt and Householder. Canonical forms: similar matrices, Saad 1.8. |
| 25/02 | Diagonalisable Matrices (Saad 1.8). Examples from handout. Briefly mentioned Jordan Canonical Form, Schur form. Applications of powers of matrices (matrix iterations) (Saad 1.8.4) |
| 01/03 | Singular Value Decomposition (not in Saad), singular values are the square roots of the eigenvalues of AHA. Normal & Hermitian matrices (Saad, 1.9). Theorem 1.7: normal <=> A=QDQH. Theorem 1.9: A Hermitian matrix has real eigenvalues. |
| 02/03 | Attributes of positive definite matrices. Cholesky factorisation. Note: No pivoting required for Cholesky. A=LDLT avoids taking square roots. |
| 04/03 | Perturbation theory (1.13.2). Condition number of a matrix. Computer examples at hand of the Hilbert matrix, illustrating loss of precision. |
| 08/03 | Condition number in terms of singular values; conditioning of the model problems; connection between singularity of the matrix and its conditioning; inadequacy of the determinant to decide on singularity in floating-point arithmetic. |
| 09/03 | The size of the residual may not be a good indication of the accuracy of an approximate solution to Ax = b. Direct vs iterative methods for large sparse Ax = b. |
Assignments
| Nr | Topic | Hand-in |
|---|---|---|
| 1 | Discretisation of PDEs, red-black ordering, Gaussian elimination, LU factorisation | 11 February |
| 2 | Numerical stability of Gaussian elimination, matrix norms, orthogonalisation | 23 February |
| 3 | Least Squares and Householder reflections | 4 March |
| 4 | Operation counts, canonical forms, normality of circulant matrices, ill-conditioned linear systems. (With corrected Problem 3(b)). | 23 March |
Golden Rules of Numerical Linear Algebra
- Never compute the matrix inverse.
- Never compute a determinant using co-factors.
- Never compute eigenvalues using the characteristic polynomial.
- Never compute QR using straight Gram-Schmidt (i.e., without modification).
- Never compute ATA when solving least squares problems.
- Never compute the eigenvalues of A to determine whether it is symmetric positive definite. Rather compute the Cholesky factorisation; if successful, A is s.p.d.
- Never compute det(A) to decide if A is approximately singular.
