AMES 526: Numerical Analysis I (Numerical Linear Algebra)
Fall 2007
Time: Tue, Thu 12:50 pm - 2:10 pm Location: P-124 Physics Building


Instructor: Prof. Xiangmin (Jim) Jiao
Email: xjiao@sunysb.edu Phone: 2-4408
Office Hours: Tue, Thu, 2:15pm-3:30pm
Office: Math Tower 1-115 		TA/Grader: Peng Zhang
Email: penzhang@ams
Office Hours: Mon. 11am-12pm, Fri. 10-11
Office: 016 Herriman Hall


[ Announcements | Course Description | Course Outline | Homework and Project Information | Class Schedule  | Links ]

Announcements (back to top)
 
Course Description (back to top)


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

Prerequisite/Co-requisite: AMES 505, Elementary programming skills

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, multiplications, orthogonality, norms, and SVD (2.5 weeks).
  • QR factorization, projectors, Gram-Schmidt algorithm, Householder triangulation (2 weeks).
  • Conditioning and stability (1.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 (2.5 weeks).
  • Iterative methods, Arnoldi/Lanczos iteration, conjugate gradients, GMRES  (2 weeks).
Course Policy (back to top)


Assignments

Homework assignments are due in class typically one week 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 (5 highest scores out of 6): 35%
  • Two tests: 40%
  • Final exam: 25%

Note: The lowest score of your homework assignments will be dropped.

 
Class Schedule (back to top)
 
  • All schedules are tentative and are subject to change.

Week Date Topic Lecture Notes Reading Notes
1 Tue 9/4 Course overview; matrix-vector multiplication Slides §I.1

Thu 9/6 Orthogonal matrices Slides §I.2  
2 Tue 9/11 Norms Slides §I.3  

Thu 9/13 No class (Rosh Hashanah Observed)      
3 Tue 9/18 Singular value decomposition Slides §I.4 HW1 out; solutions

Thu 9/20 More on SVD continued Slides §II.5-6  
4 Tue 9/25 Projectors, QR factorization Slides §II.6-7 HW1 due

Thu 9/27 Gram-Schmidt orthogonalization Slides §II.8  
5 Tue 10/2 Householder triangularization Slides §II.10 HW2 out; solutions, code

Thu 10/4 Givens rotation, least squares problems Slides §III.11  
6 Tue 10/9 floating-point arithmetic, condition numbers Slides §III.12-13 HW2 due

Thu 10/11 Stability of algorithms Slides §III.14-15  
7 Tue 10/16 Test 1 (covers material up to 10/04) sample questions & solutions   HW3 out; solution

Thu 10/18 Stability of Householder QR Slides §III.16-17  
8 Tue 10/23 Questions-and-answers session      

Thu 10/25 Gaussian elimination and LU factorization Slides §IV.20-21 HW3 due
9 Tue 10/30 LU factorization with pivoting, stability of LU Slides §IV.21-22 HW4 out; solutions, code

Thu 11/1 Cholesky factorization; software Slides §IV.23  
10 Tue 11/6 Stability of Cholesky factorization; eigenvalue problems Slides §V.23-24  

Thu 11/8 eigenvalue problems Slides §V.24 HW4 due
11 Tue 11/13 Test 2 (covers material between 10/09 and 11/06) sample questions & solutions  

Thu 11/15 Reduction to Hessenberg form Slides §V.25-26 HW5 out; solutions
12 Tue 11/20 QR algorithm without shifts Slides §V.27-28  

Thu 11/22 No class (Thanksgiving recess)      
13 Tue 11/27 QR algorithm with shifts Slides §V.29  

Thu 11/29 Other eigenvalue algorithms; computing SVD Slides §VI.30-31 HW5 due; HW6 out
14 Tue 12/4 Guest lecture on applications of eigenvalue problems; overview of iterative methods Slides §VI.32

Thu 12/6 Arnoldi/Lanczos iterations Slides §VI.33,36  
15 Tue 12/11 Conjugate gradients Slides §VI.38, painless CG

Thu 12/13 More on CG; Other Krylov subspace methods; Review Slides §VI.35 HW6 due;  solutions, codes

 

16 Thu 12/20 Final exam (11:00-1:30pm, P-124 Physics Building) sample questions & solutions    

Links (back to top)
 
  • The World’ s Largest Matrix Computation: Google's PageRank
     
  • Matlab summary and tutorial
     
  • Matlab tutor
     
  • GNU Octave: A free computer program for numerical computations mostly compatible with MATLAB.
     
  • Netlib contains a collection mathematical software. Some particularly useful software for numerical linear algebra include BLAS, LAPACK, ScaLAPACK, etc.
     
  • For the programming part, you are suggested to use MATLAB on the computers at SINC SITES (e.g., Math Towner S-235, with limited opening hours). Alternatively, you may use Octave, which is installed on all the Linux computers in the AMS's computer labs (e.g., Harriman 010).
     
  • Jonathan R. Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, 1994. PDF (58 pages)