## AMS 526: Numerical Analysis I (Numerical Linear Algebra for Computational and Data Sciences) Fall 2019Time: Monday & Wednesday 4:00--5:20pm Location: Earth & Space 181 Lecture Schedule and Slides

 Instructor: Prof. Xiangmin (Jim) Jiao Email: Sorry, you need Javascript on to email me. Phone: 631-632-4408 Office hours: Tue. 10:00am-11:30am &                       Wed. 11:30am-1:00pm Office: Math Tower 1-117 TA: Hyeji Choi Email: Sorry, you need Javascript on to email me. Office hours: Tue. & Thur. 4--5pm Office: Harriman Hall 132

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

Required Textbook

Prerequisite/Co-requisite

• AMS 510 (linear algebra portion) or equivalent undergraduate-level linear algebra course. Familiarity of the following concepts is assumed: Vector spaces, Gaussian elimination, Gram-Schmidt orthogonalization, and eigenvalues/eigenvectors.
• AMS 595 (co-requisite for students without programming experience).

Learning Objectives

The objective of this course is to introduce the key concepts and algorithms in numerical linear algebra, including direct and iterative methods for solving simultaneous linear equations, least squares problems, computation of eigenvalues and eigenvectors, and singular value decomposition. The key learning outcomes include the following:

1. Master concepts and numerical methods for solving systems of linear equations
• Gaussian elimination and its variants
• Cholesky and LDL' factorizations
2. Master concepts of orthogonality and numerical methods for linear least squares problems
• Orthogonal matrices, projectors, and linear least squares
• QR factorization using Gram-Schmidt orthogonalization, Householder reflectors, and Givens rotation
3. Build fundamental understanding of conditioning and stability
• Norms, condition numbers, and effect of rounding errors
• Stable and backward stable algorithms
• Backward error analysis of fundamental algorithms
4. Master concepts and analyses based on eigenvalues and singular values and their numerical computations
• Singular value decomposition and eigenvalue decomposition
• Power method and similarity transformations
• Reduction to Hessenberg and tridiagonal forms
5. Build fundamental understanding of iterative methods for solving large sparse linear systems and computing eigenvalues
• Conjugate gradient method, GMRES, and other Krylov subspace methods
• Lanczos and Arnoldi iterations
• Preconditioners for iterative methods
6. Demonstrate programming skills for numerical methods using the abstractions of linear algebra

Outline

• Fundamentals (matrix notation and basic operations; vector spaces; algorithmic considerations; norms and condition numbers; decomposition of matrices)
• Linear systems (triangular systems; Gaussian elimination; accuracy and stability; Cholesky factorization; sparse linear systems)
• QR factorization and least squares (Gram-Schmidt orthogonalization; QR factorization with Householder reflection; updating QR factorization with Givens rotation; stability of QR factorization; least squares problems; rank-revealing QR factorization; SVD and low-rank approximations)
• Eigenvalue problems (eigenvalues and invariant spaces; classical eigenvalue methods; QR algorithms; two-stage methods; Arnoldi and Lanczos iterations)
• Iterative Methods for linear systems (basic iterative methods; conjugate gradient methods; minimal residual style methods; bi-Lanczos iterations; preconditioners)
• Special topics (multigrid methods; under-determined linear systems etc., if time permits)

## Lecture Schedule and Slides

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.

• Assignments: 30%

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

You are encouraged to typeset your homework solutions using LaTeX or using LyX (a very easy-to-use document processor, using LaTeX in the backend). (However, Microsoft Word alike are not recommended because of the equations.) Hand-written homework is due in class on the due date. Homework typeset using LaTeX or LyX is due at 11:59pm on the due date, through email submission of the PDF file to the TA.

All programming part of the homework are also due at 11:59pm on the due date, through email submission of the source code and the report to the TA.

Assignments

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.

Sample Tests

### References on Undergraduate-Level Linear Algebra

The following is an excellent text for reviewing fundamental concepts and some applications of linear algebra.

• Gilbert Strang, Linear Algebra and Its Applications, 4th Edition, Brooks Cole, 2006.

### Other References on Numerical Linear Algebra

The following books are graduate-level textbooks on numerical linear algebra, similar to the main textbook for this course.

• James W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997.

### References on Iterative Methods and Multigrid Methods

The following books are for additional readings on iterative methods and multigrid methods, which are increasingly important but not covered in this course due to time constraint.

• 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, 2nd edition, SIAM, 2000.

### References on Technical Writing

You can find some tips on using LyX etc. at here.

### References on C Programming

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.

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