AMS 526: Numerical Analysis I

AMS 526: Numerical Analysis I (Numerical Linear Algebra)
Fall 2011

Time: Monday & Friday 12:50 pm - 2:10 pm
Location: Physics P125

Instructor: Prof. Xiangmin (Jim) Jiao
Email: xiangmin.jiao@stonybrook.edu Phone: 631-632-4408
Office hours: Mon. & Fri., 2:20pm-3:40pm
Office: Math Tower 1-115

TA: Vladimir Dyedov
Email: vladimir@ams.sunysb.edu
Office hours: Tue. & Thur. 3pm-4pm
Office: Math Tower S-250

Announcements (back to top)

Class for 8/29 was cancelled due to Hurricane Irene.

Course Description (back to top)

Direct methods for solving simultaneous linear equations. Matrix factorization, conditioning, stability, and efficiency. Computation of eigenvalues and eigenvectors. Singular value decomposition.

Prerequisite/Co-requisite: AMS 510, AMS 595 (co-requisite for students without programming experience in C).

Required Textbook

Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III, SIAM, 1997, ISBN 0-89871-361-7.

Reference Book (not required)

Matrix Computations, 3rd edition, by Gene H. Golub and Charles F. Van Loan, John Hopkins University Press, 1996, ISBN 0-8018-5414-8.

Course Outline (back to top)

Outline

Matrix fundamentals, orthogonality, norms, and SVD (2.5 weeks).
QR factorization, projectors, Gram-Schmidt algorithm, Householder triangulation, least squares problems (2 weeks).
Conditioning and stability (2.5 weeks).
Solution of linear system of equations, Gaussian elimination, pivoting, Cholesky factorization (2 weeks).
Eigenvalue problems, Hessenberg tridiagonalization, Rayleigh quotient, inverse power method, QR algorithm, Computing SVD (3 weeks).
Overview of iterative methods; Arnoldi/Lanczos iteration (1.5 week).
Linear algebra software (1 week).

Course Policy (back to top)

Assignments

Homework assignments are due in class typically two weeks after they are assigned. You are allowed to discuss course materials and homework problems in small groups, but limited to discussion of general ideas only. You must write your solutions completely independently. Under no circumstances may you copy solutions from any source, including but not limited to other students solutions, official solutions distributed in past terms, and solutions from courses taught at other universities. Violation of these rules may result in disciplinary actions.

Exams

The exams (including two tests and the final exam) are closed-book, but you are allowed to bring a single-sided, one-page, letter-size cheat sheet, which you must prepare by yourself.

Attendance

All students are expected to attend all the lectures and exams.

Grading

Assignments: 30%
Two tests: 40%
Final exam: 30%

Homework and Sample Tests (back to top)

For the computing assignments, you are encouraged to use the Linux machines in the Mathlab SINC Site at Math Tower S-235. You can remotely log onto the Linux computer compute.mathlab.sunysb.edu using ssh. Before you can login, you may need to go to Math Tower S-235 to activate your account. You may use your own computer if it runs a UNIX system (such as Linux or Mac OS X), has a C compiler (such as gcc) and debugger (such as gdb and ddd), and has octave, gnuplot, and gv (for plotting).

Assignments

Homework 1 (due September 19). Sample solution.
Homework 2 (due October 3) and code template. Sample solution.
Homework 3 (due October 21) and code template. Sample solution.
Homework 4 (due November 4) and code template. Sample solution.
Homework 5 (due November 21) and code template. Sample solution.
Homework 6 (due December 9). Sample solution.

Sample Tests

Class Schedule (back to top)

Important: All schedules are tentative and are subject to change.

Week	Date	Topic	Slides	Reading	Notes
1	Mon 8/29	Class cancelled due to Hurricane Irene
	Fri 9/2	Course overview; matrix-vector multiplication	Lecture 1	§I.1
2	Mon 9/5	No class (Labor Day observed)			HW1 out
	Fri 9/9	Orthogonal vectors and matrices; Vector norm	Lecture 2	§I.2-3
3	Mon 9/12	Matrix norms; Singular value decomposition	Lecture 3	§I.3-4
	Fri 9/6	More on singular value decomposition	Lecture 4	§I.4-5
4	Mon 9/19	Projectors, QR factorization	Lecture 5	§II.6-7	HW1 due; HW2 out
	Fri 9/23	Gram-Schmidt orthogonalization; Householder triangularization	Lecture 6	§II.8
5	Mon 9/26	More on Householder triangularization; Least squares problems	Lecture 7	§II.10-11
	Wed 9/28	Floating-point arithmetic; condition numbers	Lecture 8	§III.12-13	Correction Day
6	Mon 10/3	Accuracy and stability; Review for test 1	Lecture 9	§III.14-15	HW2 due
	Fri 10/7	Test 1 (covers Part I and Part II of text book)			HW3 out
7	Mon 10/10	Stability of Householder QR and back substitution	Lecture 10	§III.16-17
	Fri 10/14	Conditioning of least squares problems	Lecture 11	§III.18-19
8	Mon 10/17	Gaussian elimination and LU factorization	Lecture 12	§IV.20-21
	Fri 10/21	Stability of LU; Cholesky factorization	Lecture 13	§IV.22-23	HW3 due; HW4 out
9	Mon 10/24	Linear algebra software; eigenvalue problems	Lecture 14	§V.24-25	example.c
	Fri 10/28	Reduction to Hessenberg form	Lecture 15	§V.26
10	Mon 10/31	Rayleigh quotient iteration	Lecture 16	§V.27
	Fri 11/4	QR algorithm without shifts; Review for test 2	Lecture 17	§V.28	HW4 due
11	Mon 11/7	Test 2 (covers material up to 10/31)			HW5 out
	Fri 11/11	QR algorithm and simultaneous iteration	Lecture 18
12	Mon 11/14	QR algorithm with shifts	Lecture 19	§V.29
	Fri 11/18	Other eigenvalue algorithms	Lecture 20	§V.30-31
13	Mon 11/21	Overview of iterative methods	Lecture 21	§VI.32,33,36	HW5 due; HW6 out
	Fri 11/25	No class (Thanksgiving break)
14	Mon 11/28	Conjugate gradient method	Lecture 22	§VI.38
	Fri 12/2	GMRES and other Krylov subspace methods	Lecture 23	§VI.35,39
15	Mon 12/5	Preconditioning; multigrid methods	Lecture 24	§VI.40
	Fri 12/9	Review	review		HW6 due
16	Thur 12/15	Final exam (2:15-4:45pm, Physics P125)

References (back to top)

References on C Programming

For students who are not familiar with C, you are encouraged to read some books on C programming. There are some free online books linked at this "C Programming Language" page. Among these, the following book might be most appropriate.

M. Banahan, D. Brady and M. Doran, The C Book, second edition, Addison Wesley, 1991.

Another good starting point is the community-written C book is

C Programming, Wikibooks.

If you want to purchase a C book, a classical one is

B.W. Kernighan, D.M. Ritchie, C Programming Language (2nd Edition). Prentice Hall, 1988.

References on Iterative Methods

Anne Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, 1997.
Yousef Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003.
William L. Briggs, Van Emden Henson, Steve F. McCormick, A Multigrid Tutorial, SIAM, 2000.

Links (back to top)

Netlib contains a collection mathematical software. Some particularly useful software for numerical linear algebra include BLAS, LAPACK, ScaLAPACK, etc.
Jonathan R. Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, 1994. PDF (58 pages)