NLA MT25, Lanczos algorithm
Flashcards
What is the Lanczos algorithm used for?
Solving symmetric eigenvalue problems
\[Ax = \lambda x\]Describe the Rayleigh-Ritz @algorithm.
Given a symmetric $A$ and orthonormal $Q$, find approximate eigenpairs in the subspace spanned by $Q$:
- Compute $Q^\top A Q$
- Find the eigenvalue decomposition $Q^\top A Q = V \hat \Lambda V^\top$
- Approximate eigenvalues $\text{diag}(\hat \Lambda)$ (Ritz values) and eigenvectors $QV$ (Ritz vectors).
Describe the Lanczos @algorithm for solving symmetric eigenvalue problems $Ax = \lambda x$.
- Perform Lanczos iterations to obtain $AQ _ k = Q _ k T _ k + q _ {k+1} [0, \ldots, 0, h _ {k+1, k}]$
- Compute the eigenvalue decomposition of $T _ k = V _ k \hat \Lambda V _ k^\top$ (Rayleigh-Ritz with subspace $Q _ k$)
- $\text{diag}(\hat \Lambda)$ are the approximate eigenvalues (Ritz values), and the columns of $Q _ k V _ k$ are the approximate eigenvectors (Ritz vectors)
The ∆lanczos-algorithm for solving symmetric eigenvalue problems $Ax = \lambda x$ does iterations of the form:
- Perform Lanczos iterations to obtain $AQ _ k = Q _ k T _ k + q _ {k+1} [0, \ldots, 0, h _ {k+1, k}]$
- Compute the eigenvalue decomposition of $T _ k = V _ k \hat \Lambda V _ k^\top$ (Rayleigh-Ritz with subspace $Q _ k$)
- $\text{diag}(\hat \Lambda)$ are the approximate eigenvalues (Ritz values), and the columns of $Q _ k V _ k$ are the approximate eigenvectors (Ritz vectors)
The ∆rayleigh-ritz-algorithm calculates $Q _ k^\top A Q _ k = T _ k$. Why is it particularly simple in this case?
The Lanczos iteration for a symmetric matrix gives a tridiagonal output, so we only have to solve a tridiagonal eigenproblem.
The ∆lanczos-algorithm for solving symmetric eigenvalue problems $Ax = \lambda x$ does iterations of the form:
- Perform Lanczos iterations to obtain $AQ _ k = Q _ k T _ k + q _ {k+1} [0, \ldots, 0, h _ {k+1, k}]$
- Compute the eigenvalue decomposition of $T _ k = V _ k \hat \Lambda V _ k^\top$ (Rayleigh-Ritz with subspace $Q _ k$)
- $\text{diag}(\hat \Lambda)$ are the approximate eigenvalues (Ritz values), and the columns of $Q _ k V _ k$ are the approximate eigenvectors (Ritz vectors)
Can you @justify why the convergence of this algorithm is good for extremal eigenpairs?
We have
\[\begin{aligned} \lambda _ \max(A) &\ge \max _ {x \in \mathcal K _ k(A, b)} \frac{x^\top A x}{x^\top x} \\ &\ge \frac{v^\top A v}{v^\top v}, \quad v = A^{k-1}b \end{aligned}\]and similarly for $\lambda _ \min$.