Study guide for Exam 3

Here is a non-exhaustive list of questions you should be able to answer as you prepare for the third midterm. The exam will focus on Chapter 4, including the material through QR iteration, together with introductory coverage of Krylov subspaces and the Arnoldi and Lanczos methods. Concepts from earlier chapters remain relevant where they are used in eigenvalue problems. 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.

Eigenvalue Problems

  • What are an eigenvalue, a right eigenvector, a left eigenvector, and an eigenspace? How does scaling an eigenvector affect its eigenvalue?
  • What is the characteristic polynomial? Why can a real matrix have complex eigenvalues, and how are those eigenvalues paired?
  • What are the algebraic and geometric multiplicities of an eigenvalue? When are eigenvectors linearly independent? What makes a matrix diagonalizable or defective, and why do repeated eigenvalues not necessarily make a matrix defective?
  • What is the eigenvalue decomposition $A=XDX^{-1}$? How can it be used to compute $A^k$ and describe the action of $A^k$ on an initial vector?
  • For a matrix of transition probabilities whose rows sum to one, how is a stationary probability vector characterized as a left eigenvector? How should it be normalized?
  • What are real symmetric, Hermitian, and normal matrices? What can you say about their eigenvalues and the existence of an orthonormal eigenvector basis?
  • How do the SVD and eigenvalue decomposition differ? How are singular values related to eigenvalues of $A^H A$? For which matrix classes are the singular values the absolute values of the eigenvalues? What is the spectral radius, and how does it compare with $\|A\|_2$?
  • What is a similarity transformation? What happens to eigenvalues and eigenvectors under $B=X^{-1}AX$? How do you recover eigenvectors after a sequence of similarity transformations?
  • Why are orthogonal or unitary similarity transformations useful in eigenvalue algorithms? What do they preserve besides eigenvalues?
  • What are the Jordan form and the complex Schur form? What kinds of similarity transformations are used to obtain these forms, and what can you read from their diagonal entries? Why does a defective matrix still have a Schur form?
  • What are the eigenvalues of a triangular matrix? For a small triangular matrix, how can you compute an eigenvector and recover an eigenvector of the original matrix from its Schur factorization?

Conditioning of Eigenvalue Problems

  • For a diagonalizable matrix $A=XDX^{-1}$, how does $\kappa_2(X)$ affect the sensitivity of the eigenvalues to small perturbations in $A$? How does this differ from the role of $\kappa_2(A)$ in solving a linear system, and why are normal matrices' eigenvalues well conditioned in an absolute sense?
  • Why can individual eigenvectors be sensitive when eigenvalues are close, even for a real symmetric matrix?

Computing One Eigenpair

  • Given an approximate eigenvector $x$, what is the Rayleigh quotient? How do you compute it, and why does it minimize $\|Ax-\mu x\|_2$ over the scalar $\mu$?
  • What are power iteration and normalized power iteration? How do you identify the dominant eigenvalue by magnitude and carry out a step? Why is normalization useful, and what does convergence of the eigenvector direction mean?
  • For a diagonalizable matrix, what conditions on the eigenvalues and the starting vector's eigenbasis expansion ensure that power iteration approaches the dominant eigenvector direction? What may happen when these conditions fail?
  • Under these convergence assumptions, how do the magnitudes of the two leading eigenvalues determine the asymptotic convergence factor of power iteration? How would you use that factor to compare convergence or estimate how many additional iterations are needed?
  • How do shifting and inversion change eigenvalues and eigenvectors? What are inverse iteration and shifted inverse iteration, and which eigenvalue does each target when it converges? How do you carry out a step by solving a linear system?
  • In shifted inverse iteration, how do the distances from the shift to the desired and competing eigenvalues determine the convergence factor? How can a good shift accelerate convergence, and when is the shifted system singular?
  • What are the costs of power iteration and inverse iteration for a dense matrix? For a fixed shift, what factorization can be reused, and what is the cost of each subsequent solve? How can sparsity make matrix-vector products less expensive?
  • What is Rayleigh quotient iteration, and how does its shift change? How does its local convergence near a simple eigenpair of a real symmetric or Hermitian matrix compare with fixed-shift inverse iteration? How does changing the shift affect the work required at each iteration?

Computing Multiple Eigenpairs

  • What is deflation? For a Hermitian matrix and a known eigenpair $(\lambda,x)$ with $\|x\|_2=1$, how does $A-\lambda xx^H$ change the eigenvalues? How can the remaining eigenpairs be sought in the orthogonal complement of $x$?
  • What are simultaneous iteration and orthogonal iteration? Why can repeated multiplication without orthonormalization produce an increasingly poor basis, and which invariant subspace does orthogonal iteration seek?
  • How does QR iteration use a factorization $A_k=Q_kR_k$ to obtain $A_{k+1}$? Why are successive iterates similar? How is QR iteration related to orthogonal iteration?
  • When QR iteration converges, what form is sought for a general matrix and for a real symmetric or Hermitian matrix? What do the accumulated orthogonal or unitary factors represent? When do their columns give eigenvectors directly? Why can real QR iteration approach a form with $2\times2$ diagonal blocks when eigenvalues are nonreal?
  • What is an upper Hessenberg matrix? How can Householder similarity transformations reduce a matrix to this form? Why does the reduction give a tridiagonal matrix in the real symmetric or Hermitian case?
  • What is the cost of the initial reduction of a dense matrix to Hessenberg or tridiagonal form? When computing eigenvalues only, what is the work per QR iteration for a dense, an upper Hessenberg, and a symmetric tridiagonal matrix? Why is the reduced structure preserved during QR iteration?
  • How is a shift incorporated into QR iteration, and why is it added back after reversing the factors? How can shifts improve convergence?
  • How can a zero or sufficiently small subdiagonal entry in Hessenberg or tridiagonal form identify a split into smaller eigenvalue problems? How is this used for deflation during QR iteration?

Krylov Subspace Methods

Coverage of these methods will emphasize their purpose, the spaces and matrix structures involved, and interpretation of a supplied small eigenvalue problem. Detailed recurrences, convergence proofs, and restarting strategies are not expected.

  • What is the Krylov subspace $\mathcal K_k(A,x_0)$? How is it built using matrix-vector products, and why is it useful for finding a few eigenpairs of a large sparse matrix?
  • At a high level, how does Arnoldi construct an orthonormal basis for this subspace? How does Lanczos specialize it for real symmetric or Hermitian matrices, and what structures do the resulting small matrices have?
  • Given an orthonormal basis $Q_k$ and small matrix $H_k=Q_k^HAQ_k$, what are Ritz values and Ritz vectors? If $H_ky=\theta y$, how do you obtain an approximate eigenpair of $A$? Why can an exact solution of the small problem give only an approximate eigenpair of $A$?