Study guide for Exam 2
Here is a non-exhaustive list of questions you should be able to answer as you prepare for the second midterm. The exam will cover the later parts of Chapter 2 (special linear systems and Sherman-Morrison) and the material in Chapter 3 through Gram-Schmidt, Givens, and Householder QR. This includes Lectures 8-9 and the following lecture on QR algorithms. Concepts from Exam 1 remain relevant, but questions will focus on new material. The midterm will be 50 minutes in length and will consist of questions similar to the multiple-choice and short-entry questions on the quizzes. You will have access to a RELATE code submission box with numpy/scipy functions available, for use as a calculator.
Linear Systems
- What defines a symmetric positive definite (SPD) matrix? Why are its diagonal blocks and Schur complements SPD? Why does strict column diagonal dominance also permit elimination without pivoting?
- What are the Cholesky and $LDL^T$ factorizations? When can they be used and what are their advantages? Why can symmetric indefinite matrices require permutations and $2\times2$ pivots in an $LDL^T$ factorization?
- How can we take advantage of tridiagonal or banded structure in solving a linear system? Which entries can change in a Schur-complement update, and what are the factorization and solve costs?
- What is the cost of reusing a stored factorization to solve additional systems, e.g. with multiple right-hand sides?
- How can changes to a row or column be written as a rank-1 update $uv^T$?
- How can we solve a rank-1 perturbed problem via the Sherman Morrison formula? When is the formula valid, and how can stored factors be used without forming $A^{-1}$?
Linear Least Squares
- How can polynomial fitting be expressed as a linear least-squares problem? What condition on the residual characterizes a least-squares solution?
- How can you solve a least-squares problem using the SVD?
- Given an SVD of the matrix and a right-hand side, how would you find the 2-norm of the residual of a least-squares problem?
- What is the pseudoinverse, what are the Moore-Penrose conditions, and how is it constructed from the SVD? How does it treat zero versus small nonzero singular values?
- How can you solve a rank-deficient linear least squares problem? What is the minimum-norm solution, and is it unique?
- How can least squares problems be solved via the normal equations? What are the advantages and disadvantages of that? When is $A^TA$ SPD, and how does its condition number compare with that of $A$?
- What are the costs of forming and solving the normal equations? What work can be reused for additional right-hand sides?
- On what factors does the conditioning of a linear least-squares problem depend on? For perturbations in $b$ with $A$ fixed, how do singular values and the relative residual enter the bound?
- What is an orthogonal matrix? How does a rectangular matrix with orthonormal columns differ in its norm-preservation properties?
- What is a projection matrix? Which subspaces do $AA^+$ and $A^+A$ project onto?
- What is QR factorization, when does it exist and is it unique? How do full and reduced QR differ?
- How does one solve linear least squares problems using a QR factorization? How do you obtain the residual norm, and how are the singular values of $R$ related to those of $A$?
- What is Cholesky QR and how is it used for solving a linear least squares problem?
- What are the classical and modified Gram-Schmidt processes? What can you say about their stability? What is their computational cost?
- What is a Householder reflector matrix, what properties does it have and how is it computed?
- What is the Householder QR factorization algorithm, and what can you say about its stability?
- How many Householder iterations are needed for a QR factorization and what is the total cost?
- What is a Givens rotation matrix, what properties does it have and how is it computed?
- How can Givens rotations be used to factorize a sparse matrix?