Study guide for Examlet 4

Here is a non-exhaustive list of questions you should be able to answer as you prepare for the examlet.

Past chapters

See the

(Recall from the course policies that our examlets are cumulative.)

What criteria does a vector norm have to satisfy?
What is the triangle inequality?
What are the $p$-norms?
What is the "unit ball" of a norm?
What is a matrix norm? submultiplicativity?
How can the matrix norm of a diagonal matrix be computed?
What is special about matrix norms of orthogonal matrices?
What is the condition number of solving a linear system? matrix-vector multiplication?
What is the condition number of a matrix?
How can the condition number of a diagonal matrix be calculated?
How does a condition number affect the number of accurate digits in a result?
How can the norm/condition number of a matrix $A$ be found from the plot of $A\mathbf{x}$ for $\|\mathbf x\|=1$?

What do forward/backward substitution accomplish? How? At what computational cost?
What is LU factorization? How does it work? What is its computational cost?
How does arithmetic with block matrices work? What is the Schur complement update?
What is the asymptotic cost of LU factorization? How do you apply it to estimate factorization time?

Does the LU factorization always exist? Why is pivoting needed?
What is partial pivoting? What is its purpose? How does it work?
What is a permutation matrix? How does it help realize partial pivoting?
What is the form of an LU factorization with pivoting? (can be $PA=LU$ or $A=\bar PLU$--note that $\bar P=P^T$)
What is the cost of LU factorization with pivoting?

How is LU factorization used to solve a linear system of equations $A\mathbf x=\mathbf b$?
How is LU factorization used to solve many linear systems of equations $A\mathbf{x_i}=\mathbf{b_i}$ with many different right-hand sides?
How is LU factorization used to solve a matrix equation $AX=B$?
Be able to (write down algorithms to) solve more complicated matrix equations involving triangular/orthogonal/other matrices.

What is an eigenvector? an eigenvalue of a matrix? (i.e. know the definition)
When are eigenvectors linearly independent?
What is power iteration?
What can be obtained using power iteration?
What is normalized power iteration? What problem does it address?
Given an approximate eigenvector, how can you estimate eigenvalues? What is the Rayleigh Quotient?