Math 270A (Numerical Linear Algebra)

Course Topics: Numerical Linear Algebra
Instructor: Prof. Michael Holst (5739 AP&M, mholst@math.ucsd.edu; Regular Office Hours: Mon 3-4:30pm)
Term: Fall 2014
Lecture: 12:00p-12:50p MWF, 5402 AP&M
TA: Shi (Fox) Cheng (5768 AP&M, scheng@math.ucsd.edu; Office Hours: Thu 3-4pm)
Discussion: None
Main Class Webpage: http://ccom.ucsd.edu/~mholst/teaching/ucsd/270a_f14/index.html
Textbook(s): L. Trefethen and D. Bau, Numerical Linear Algebra.
Printable Syllabus: Can be found [ here ].

CATALOG DESCRIPTION: 270A. Numerical Linear Algebra (4)
Error analysis of the numerical solution of linear equations and least squares problems for the full rank and rank deficient cases. Error analysis of numerical methods for eigenvalue problems and singular value problems. Iterative methods for large sparse systems of linear equations. Prerequisites: Graduate standing or consent of instructor.

COURSE INFORMATION: Many of the advances of modern science have been made possible only through the sophisticated use of computer modeling. The mathematical foundation of the computer modeling techniques now used in all areas of mathematics, engineering, and science is known as numerical analysis (sometimes referred to as computational mathematics, numerical mathematics, or scientific computing). The Math 270ABC series at UCSD provides a graduate level overview of some of the foundation topics in numerical analysis. The Math 270ABC sequence covers all of the material that appears on one of our core written qualifying examinations for the mathematics doctoral program at UCSD.

Math 270A deals with various aspects of numerical linear algebra, including direct methods for solving systems of equations involving dense and sparse matrices, iterative methods for solving linear systems, and methods for solving eigenvalue problems. Math 270B focuses on numerical methods for solving nonlinear equations and optimization problems, and on classical and modern approximation theory as needed for analyzing numerical methods. Math 270C concentrates on bringing the tools from 270A and 270B together to develop numerical methods for solving initial value problems (IVPs) and boundary value problems (BVPs) in ordinary differential equations (ODEs). The topics in 270A and the first half of 270B may be viewed as preparation for Math 271ABC (numerical optimization), whereas the topics in the entire series, with emphasis on the topics in the second half of 270B and the topics in 270C, may be viewed as preparation for 272ABC (numerical PDE) and 273ABC (advanced techniques in computational and applied mathematics).

GRADES, HOMEWORKS, EXAMS, AND IMPORTANT DATES: Course information, such as any homework assignments given out, exam dates, and so forth, will be maintained on this course webpage. Note that I sometimes make changes to the lecture schedule and homework assignments as the quarter progresses, depending on how far I get each week in the lectures. Therefore, check this webpage regularly. I will periodically (about every 2-4 weeks) give out homeworks to help you prepare for the final exam. The last week I will finish any remaining material, and then focus mostly in the last lecture on reviewing the material from the class for the final exam. The final exam will be based on the material I cover in class (a subset of the textbook), supplemented with some background material I will lecture on at the beginning of the course (most of which is also in the textbook), and some material on iterative methods at the end (I will post my notes on that material).

Important dates:

 First lecture: FRI 10/03 Last lecture: FRI 12/12 Finals week: MON-FRI, 12/15-12/19 GUEST LECTURE: WED 10/22 (Prof. Bank; Gaussian Elimiation and LU Factorization) NO LECTURE: FRI 10/24 (Holst at IMA in Minnesota) Holiday: FRI 11/28 (Thanksgiving Break -- NO LECTURE) Final Exam: THU 12/18, 11:30am-2:30pm, 5402 APM

Homeworks: I will give out some homework problems that will be very similar to problems that will appear on the final exam (and later the qual exam). The TA will be available to help you work the problems in the weekly discussion sessions, and by appointment as needed. We will collect and mark some of the homework problems to give you feedback, but your grade for the course will be based only on your final examination at the end of the quarter. (The idea is to give you a practice run at 1/3 of the 270ABC qual exam.)

Turning in the homeworks: Please just do not give all of your homeworks to the TA toward the end of the quarter; he will not have time to give you any feedback before the final. To make best use of his help, try to do the homeworks within a couple of weeks of their posting, and then give the homeworks to the TA; he will then be able to give you some marked versions back within a week.

COURSE MATERIAL 1 of 3: Fundamentals, Gaussian Elimination, and Conditioning/Stability
Relevant Book Material: Parts 1 and 4, and Part 3--Lectures 12-15
Homework 1 Exercises:
• Part 1, Lecture 1: 1.1
• Part 1, Lecture 2: 2.3, 2.4, 2.5, 2.6
• Part 1, Lecture 3: 3.1, 3.2, 3.3, 3.4
• Part 1, Lecture 4: 4.1, 4.4, 4.5
• Part 1, Lecture 5: 5.3

• Part 3, Lecture 12: 12.1, 12.3
• Part 3, Lecture 13: 13.3, 13.4
• Part 3, Lecture 14: 14.1, 14.2
• Part 3, Lecture 15: 15.1

• Part 4, Lecture 20: 20.1, 20.2, 20.3
• Part 4, Lecture 21: 21.1, 21.2, 21.6
• Part 4, Lecture 22: 21.1
• Part 4, Lecture 23: 23.1 (Can wait until until we cover Part 2 below)

COURSE MATERIAL 2 of 3: QR Factorization, Eigenvalues, and More Conditioning/Stability
Relevant Book Material: Parts 2 and 5, and Part 3--Lectures 16-19
Homework 2 Exercises:
• Part 2, Lecture 6: 6.1, 6.3, 6.4, 6.5
• Part 2, Lecture 7: 7.1, 7.4, 7.5
• Part 2, Lecture 8: 8.1, 8.3
• Part 2, Lecture 10: 10.1, 10.4
• Part 2, Lecture 11: 11.1

• Part 5, Lecture 24: 24.1, 24.2, 24.4
• Part 5, Lecture 25: 25.1, 25.2, 25.3
• Part 5, Lecture 26: 26.1, 26.3
• Part 5, Lecture 27: 27.1, 27.2, 27.5
• Part 5, Lecture 28: 28.2

• Part 3, Lecture 16: 16.1
• Part 3, Lecture 17: 17.1, 17.2
• Part 3, Lecture 18: 18.1, 18.2, 18.4
• Part 3, Lecture 19: 19.1

COURSE MATERIAL 3 of 3: Iterative Methods
Relevant Book Material: Part 6 (First section and section on CG; rest of material is from lecture.)
Homework 3 Exercises:
• The third set of homework problems can be found [ here ].
• Notes on iterative methods (from my book) which I lectured from are [ here ].

FINAL EXAM: Here are some things to help you prepare for the final.

Homework Solution Key/Hints: Fox (our TA) has put together hints for homeworks relevant to five of the six final questions; the hints are [ here ].

Special Office Hours/Review: Fox will hold special "final exam preparation" office hours on Wednesay Dec 17 from 3-4pm. I will also have regular office hours that day from 1:30-2:30pm.

Outline of the Final Exam:
1. Question 1: Basic abstract linear algebra (Book sections: Lectures 1-5)
• Basic ideas about linear systems and eigenvalue problems
• Basic ideas about eigenvalue problems
• Existence and properties of the SVD
2. Question 2: QR Decomposition and Least Squares Problems (Book sections: Lectures 6-11)
• Projections, QR Decomposition, Gram-Schmidt
• Householder Reflections, and Least-Squares Problems
• Storage and computational complexity of algorithms
3. Question 3: Gaussian Elimination and LU Factorization (Book sections: Lectures 20-23)
• Gaussian Elimination, Gauss Transforms,
• LU Factorization, forward/backward subsitition
• Storage and computational complexity of algorithms
4. Question 4: Conditioning and Stability (Book sections: Lectures 12,14,16-19)
• Condition of a problem, condition number of a matrix
• Condition of matrix multiplication, system of equations
• Stability of a problem, stability of an algorithm
• Backward stable algorithm, backward error analysis
• Stability of algorithms: GE/LU, backsubstition, QR, LS
5. Question 5: Eigenvalue Problems (Book sections: Lectures 24-29)
• Similarity, orthogonal and unitary transformations
• Existence of Schur Decomposition
• Existence of spectral decomposition
• Two-stage QR algorithm for diagionalizing a matrix
• Stage 1: QR-based reduction to upper-Hessenberg form
• Stage 2: QR iteration
• Raleigh quotient, power, and inverse power iterations
• Storage and computational complexity of algorithms
• Stability of algorithms: QR (phases 1 and 2)
6. Question 6: Iterative Methods for Linear Systems (Book sections: Posted notes from Holst textbook)
• Derivation of the Basic Linear Method (BLM)
• Convergence and complexity properties of the BLM
• Storage and computational complexity of algorithms
• Properties of A-self-adjoint operators, preconditioners
• Derivation of CG as sequential orthogonal projection
• Convergence and complexity properties of CG