Exam 2 Study Guide/Practice Aid

Content

The exam covers content from LU factorization through Schur form. Roughly in terms of subsections, that is

What is the LU factorization? What are the shapes and properties of $L$ and $U$?
Can I carry out LU factorization on a small matrix by hand?
What is the one failure mode of LU without pivoting? Given a matrix, can I determine whether LU without pivoting exists?
What is partial pivoting? What is complete pivoting? What are the trade-offs?
What does a pivoted LU factorization look like? (i.e. $PA = LU$)
Given an LU factorization $PA = LU$, can I outline the solve process for $A\boldsymbol x = \boldsymbol b$?
What is the computational cost of LU factorization? Of forward/backward substitution? Of solving multiple right-hand sides? In special cases, such as banded matrix?
What are the BLAS levels, and why do they matter for the constant in the $O(n^3)$ cost?
What is the Schur complement? How does block Gaussian elimination produce it? Can I rederive the formula if needed?
How does round-off error in LU behave with and without pivoting? Can I trace through the $2\times 2$ example with $\epsilon < \epsilon_\text{mach}$?

What is the Cholesky factorization? For what class of matrices does it apply?
Why does Cholesky require no pivoting to guarantee existence for SPD matrices?
What is the relationship (if any) between the LU and Cholesky factorizations of an SPD matrix?
How do the singular values of $A$ relate to the diagonal of $L$ in $A = LL^T$?
What is the cost advantage of Cholesky over LU?

What is the SVD $A = U\Sigma V^T$? What are the shapes and properties of the factors?
How does the 2-norm of a matrix relate to its singular values?
How is $\text{cond}_2(A)$ expressed in terms of the singular values?
Given the SVD of a matrix, can I compute its condition number?
What is the Frobenius norm? Is it an induced norm? How does it relate to the SVD?

Can I set up the matrix for a function fitting problem? In one dimension? In multiple dimensions?
What is the least squares problem $A\boldsymbol x \cong \boldsymbol b$? When does it arise?
What are the normal equations? How are they derived?
What is the geometric interpretation of the least squares solution? (orthogonal projection, residual $\perp$ column space of $A$)
Given vectors $\boldsymbol b$, $\boldsymbol y = A\boldsymbol x$, and the angle $\theta$ between $\boldsymbol b$ and $\text{colspan}(A)$, can I interpret $\|\boldsymbol b\|_2 \cos\theta$?
What is an orthogonal projector? What conditions characterize one?
Can I verify that $P = A(A^TA)^{-1}A^T$ is an orthogonal projector onto $\text{colspan}(A)$?
What is the pseudoinverse $A^+$ of a full-column-rank matrix?

What is the conditioning bound for the least squares solution when $\boldsymbol b$ is perturbed? [ \frac{|\Delta\boldsymbol x|_2}{|\boldsymbol x|_2} \leq \kappa(A) \frac{1}{\cos\theta} \frac{|\Delta\boldsymbol b|_2}{|\boldsymbol b|_2} ]
Can I apply this bound to compute a numerical answer?
Which values of $\theta$ make the least squares problem ill-conditioned? Why?
How does the sensitivity depend on both $A$ and $\boldsymbol b$ (unlike for square linear systems)?

What is the QR factorization? How does it reduce a least squares problem to a triangular one?
How can a QR factorization be used to solve least squares problems?
How can Gram-Schmidt be used to calculate QR? What is modified Gram-Schmidt? How does Gram-Schmidt fall short numerically?
How does a Householder reflector $H = I - 2\frac{\boldsymbol v \boldsymbol v^T}{\boldsymbol v^T \boldsymbol v}$ zero out entries below the first in a vector?
Can I compute the first Householder reflector for a given matrix, and apply it to find $H_1 A$?
Which sign choice for $\boldsymbol v = \boldsymbol a \mp \|\boldsymbol a\|_2 \boldsymbol e_1$ minimizes cancellation?
What are Givens rotations? How do they produce zeros one at a time? In what order are they applied to a $3\times 3$ matrix?
What is economical/reduced QR? How does it factor into LSQ solutions?
What is rank-revealing QR (column pivoting)? What factorization does it produce?

What are the shapes of the factors in the full vs.\ economical SVD for an $m\times n$ matrix with $m > n$?
What does the SVD reveal about the nullspace, rank, and numerical rank of a matrix?
What is the Eckart-Young-Mirsky theorem? Given a truncated SVD $A_k$, what is $\|A - A_k\|_2$? What aobut the Frobenius norm?
How is the minimum-norm least squares solution expressed via the pseudoinverse $A^+ = V\Sigma^+ U^T$?
Can I compare the cost of solving least squares via normal equations (Cholesky), Householder QR, and SVD?

What is an eigenvalue? An eigenvector? The spectrum? The spectral radius?
What is the characteristic polynomial? Why does it not yield a practical algorithm for $n \geq 5$? Why is it numerically not useful?
What are algebraic and geometric multiplicity? What does it mean for a matrix to be defective?
What does it mean for a matrix to be diagonalizable? Can I write $A = XDX^{-1}$ given the eigenvectors?

What does it mean for two matrices to be similar?
What properties are shared by similar matrices? (eigenvalues/spectral radius, diagonalizability, characteristic polynomial)
What properties are not necessarily shared? (singular values, symmetry, orthogonality of eigenvectors)
Can I verify whether a given statement about similar matrices must be true or false?

Given $A\boldsymbol x = \lambda \boldsymbol x$, what are the eigenvalues of:
- $A - \sigma I$ (shift)
- $A^{-1}$ (inversion)
- $A^k$ (power)
- $p(A)$ for a polynomial $p$ (polynomial)
- $T^{-1}AT$ (similarity)
Can I compute a specific eigenvalue of a transformed matrix given an eigenvalue of the original?