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)

No comments: