MAT-51626
Matrix Algebra 2
Spring 2010
Lecturer: Robert Piché
Lectures Mondays 9-11 and Tuesdays 14-16 in Tb214
Textbook: James W. Demmel, Applied Numerical Linear Algebra, SIAM
1997, online,
errata
Course requirement: homework problems or take-home exam.
1. Introduction, norms, floating point arithmetic, backward
stability
Textbook chapter 1;
video, slides
Homework (due 9.3 at 14:15): chapter 1 questions 1, 3, 7, 10, 11, 14
part 2
(i.e. equivalence of
inf norm and 2-norm), 16 part 11.
2. Linear equations: gaussian elimination, SPD matrices
Textbook sections 2.3, 2.7.1;
video, slides
Homework: chapter 2 questions 1, 7, 11, 13 parts
1-2, 17, 19 bullet 2, 20 parts a-b.
3. Linear equations: perturbation analysis and backward stability
Textbook sections 1.3.2, 1.6, 2.2, 2.4.2;
video, slides
Homework: chapter 1 question 20; chapter 2
questions 9, 10 (n-by-n only), 12, 19 bullet 1 (using lemma 2.1) and
the following
simplified version of
question 14:
gecp implements gaussian
elimination with complete pivoting in Matlab.
Compare this algorithm with Matlab's lu function (which uses
gaussian elimination with partial pivoting) by testing single precision
matrices A of dimensions up to 30. Test well-conditioned matrices as
well as
ill-conditioned matrices; generate them either by following the advice
in Question 2.14 or by using Matlab's gallery('randsvd',...).
Report and discuss three indicators: the
pivot growth factors g, the
factorization backward error norm ||E||max=||P1*A*P2-L*U||max,
and
its
estimate
n*e*||abs(L)*abs(U)||max from section 2.4.2,
where
e=roundoff unit (=half of machine epsilon).
4. Linear equations: practical error bounds
Textbook sections 2.2, 2.4.3-4;
video, slides
Homework: pdf
5. Linear equations: blocking algorithms, banded and sparse matrices
Textbook sections 2.6 (except Strassen), 2.7.2-4;
video, slides
Homework: pdf
6. Least squares: normal equations, QR, backward stability
Textbook sections 3.1, 3.2 (except SVD), 3.4;
video, slides
Homework: chapter 3 questions 1, 3 parts 1&3, 4,
5, 6, 15 (except SVD)
7. SVD, perturbation analysis of LS, pseudoinverse, regularisation
Textbook sections 3.2.3, 3.3, 3.5 (up to defn 3.2); slides, demo1.m, demo2.m,
demo3.m
Homework: chapter 3 questions 3 part 2, 9, 11,
12, 14 (square A only), and redo p.114's table for
Matlab's gatlin.mat image
(note erratum: sigma_{k+1}/sigma_k
in the heading of column 2 should be sigma_{k+1}/sigma_1)
8. Eigenvalue problems, perturbation analysis
Textbook sections 4.2 & 4.3 (except Defn 4.4, Prop. 4.3, Thms 4.3,
4.6, 4.7);
video, slides
Homework: chapter 4 questions 2, 3, 9 (replace min by inf), 13, 14
9. Jacobi's method
Textbook sections 6.3 and 6.5 (except Gauss-Seidel, SOR, Chebyshev,
SSOR);
video, slides
Homework: pdf
, lap2d
10. Preconditioned Conjugate Gradient method
Textbook section 6.6;
video, slides
Homework: chapter 6 problems 11, 12 (Lanczos, replace
y1 by b), 13,
14, and redo question A3 of set 9 using the
conjugate gradient method and without forming A.