Introduction to Numerical Methods

Course Description

This course offers an advanced introduction to numerical linear algebra. Topics include direct and iterative methods for linear systems, eigenvalue decompositions and QR/SVD factorizations, stability and accuracy of numerical algorithms, the IEEE floating point standard, sparse and structured matrices, preconditioning, linear algebra software. Problem sets require some knowledge of MATLAB®.

Technical Requirements

Special software is required to use some of the files in this course:.m.

Lecture Notes

LEC #	LECTURE NOTES	SUPPLEMENTARY FILES
1	Introduction, Basic Linear Algebra (PDF) 6 slides per page (PDF)
2	Orthogonal Vectors and Matrices, Norms (PDF) 6 slides per page (PDF)	Vector Norms lec2mldemo1.m (M) Induced Matrix Norms lec2mldemo2.m (M)
3	The Singular Value Decomposition (PDF) 6 slides per page (PDF)
4	The QR Factorization (PDF) 6 slides per page (PDF)
5	Gram-Schmidt Orthogonalization (PDF) 6 slides per page (PDF)	Classical and Modified Gram-Schmidt lec5mldemo1.m (M) clgs.m (M) mgs.m (M)
6	Householder Reflectors and Givens Rotations (PDF) 6 slides per page (PDF)	Householder QR Factorization house.m (M) formQ.m (M)
7	Least Squares Problems (PDF) 6 slides per page (PDF)
8	Floating Point Arithmetic, The IEEE Standard (PDF) 6 slides per page (PDF)	Floating Point Arithmetic lec8mldemo1.m (M) num2bin.m (M)
9	Conditioning and Stability I (PDF) 6 slides per page (PDF)
10	Conditioning and Stability II (PDF) 6 slides per page (PDF)
11	Gaussian Elimination, The LU Factorization (PDF) 6 slides per page (PDF)	LU Factorization lec11mldemo1.m (M) lec11mldemo2.m (M) mkL.m (M) mkP.m (M)
12	Stability of LU, Cholesky Factorization (PDF) 6 slides per page (PDF)
13	Eigenvalue Problems (PDF) 6 slides per page (PDF)
14	Hessenberg / Tridiagonal Reduction (PDF) 6 slides per page (PDF)
15	The QR Algorithm I (PDF) 6 slides per page (PDF)
16	The QR Algorithm II (PDF) 6 slides per page (PDF)	Jacobi Algorithm lec16mldemo1.m (M) jacrot.m (M)
17	Other Eigenvalue Algorithms (PDF) 6 slides per page (PDF)	Method of Bisection lec17mldemo1.m (M) sturmcount.m (M) Divide-and-Conquer Algorithm lec17mldemo2.m (M)
18	The Classical Iterative Methods (PDF) 6 slides per page (PDF)
19	The Conjugate Gradients Algorithm I (PDF) 6 slides per page (PDF)	Conjugate Gradients cg.m (M) cg_stats.m (M)
20	The Conjugate Gradients Algorithm II (PDF) 6 slides per page (PDF)	Conjugate Gradients lec20mldemo1.m (M) steep.m (M) conjdir.m (M) conjgrad.m (M)
21	Sparse Matrix Algorithms (PDF) 6 slides per page (PDF)	Elimination Movie lec21mldemo1.m (M) realmmd.m (M)
22	Preconditioning, Incomplete Factorizations (PDF) 6 slides per page (PDF)
23	Arnoldi / Lanczos Iterations (PDF) 6 slides per page (PDF)	Arnoldi Iteration arnoldi.m (M)
24	GMRES, Other Krylov Subspace Methods (PDF) 6 slides per page (PDF)
25	Linear Algebra Software (PDF) 6 slides per page (PDF)

Assignments

Special software is required to use some of the files in this section: .m.

This course has 6 homework assignments which are collectively worth 60% of the grade.

Collaboration on the homeworks is encouraged, but each student must write his/her own solutions, understand all the details of them, and be prepared to answer questions about them.

The assignments are due in the lectures listed.

LEC #	ASSIGNMENTS	SUPPLEMENTARY FILES
5	Homework 1 (PDF)
9	Homework 2 (PDF)
12	Homework 3 (PDF)
16	Homework 4 (PDF)	Banded Cholesky bandtest.m (M)
21	Homework 5 (PDF)	Linear Elasticity Utilities assemble.m (M) elmatrix.m (M) mkmodel.m (M) qdplot.m (M) qdanim.m (M)
25	Homework 6 (PDF)