NLA MT25, Eigenvalue problems
Other relevant general content is covered in:
- Notes - Numerical Analysis HT24, EigenvaluesU
- Notes - Linear Algebra II HT23, Eigenvectors and eigenvaluesU
Flashcards
@State the general setup of a generalised eigenvalue problem.
Suppose:
- $A, B \in \mathbb C^{n \times n}$
We want to find $x \ne 0$ and $\lambda \in \mathbb C$ such that
\[Ax = \lambda B x\]Bite-sized
Standard eigenvalue problem: given a square $A \in \mathbb R^{n \times n}$, find $\lambda \in \mathbb C$ and $x \ne 0$ such that $A x = $ $\lambda x$.
Why is no finite-step algorithm possible for the eigenvalue problem when $n \ge 5$?
Eigenvalues are the roots of $\det(\lambda I - A) = 0$, a degree-$n$ polynomial. Conversely, every polynomial $p$ is the characteristic polynomial of its companion matrix, so a finite-step eigenvalue algorithm would yield a finite-step root-finder for arbitrary polynomials of degree $n \ge 5$ — contradicting Abel-Galois. Hence eigenvalue algorithms are necessarily iterative and approximate.
The computational goal for $Ax = \lambda x$ is the Schur decomposition $A = U T U^*$ with $U$ unitary and $T$ upper triangular: eigenvalues are then read off as $\mathrm{eig}(A) = $ $\mathrm{diag}(T)$.
For a generalised eigenvalue problem $Ax = \lambda B x$ with $A = A^\top$, $B \succ 0$, how is it reduced to a standard symmetric eigenproblem?
Compute Cholesky $B = R^\top R$. Substitute $y = Rx$: the problem becomes $A R^{-1} y = \lambda R^\top y$, i.e. $R^{-\top} A R^{-1} y = \lambda y$. The transformed matrix $\tilde A := R^{-\top} A R^{-1}$ is symmetric (since $A$ is), so the standard symmetric QR algorithm applies — eigenvalues are therefore all real. Recover eigenvectors via $x = R^{-1} y$.
Why not just premultiply by $B^{-1}$? $B^{-1}A$ has the same eigenvalues (it is similar to $\tilde A$ via $R$: $R(B^{-1}A)R^{-1} = R^{-\top}AR^{-1} = \tilde A$), but it is not symmetric in general, since $(B^{-1}A)^\top = AB^{-1} \ne B^{-1}A$ unless $A$ and $B$ commute. Premultiplying therefore forfeits the symmetric eigensolver: you would need the general nonsymmetric QR ($\approx 25 n^3$ vs $\tfrac{4}{3} n^3$), lose the guaranteed real eigenvalues and orthogonal eigenvectors, and the eigenvalues can become ill-conditioned when $B$ is (the eigenvector matrix of $B^{-1}A$ is $R^{-1}Q$, with $\kappa _ 2(R) = \sqrt{\kappa _ 2(B)}$). The congruence $A \mapsto R^{-\top} A R^{-1}$ preserves symmetry, keeping all of that, plus Weyl-well-conditioned eigenvalues.
For a general (non-symmetric, $B$ possibly indefinite) generalised eigenproblem $Ax = \lambda B x$, the QZ algorithm finds unitary $Q, Z$ such that both $QAZ$ and $QBZ$ are upper triangular; eigenvalues are then $\mathrm{diag}(QAZ) / \mathrm{diag}(QBZ)$. Cost $\approx 50 n^3$.
Eigenvalues of nonsymmetric matrices can be highly ill-conditioned. Take the $n \times n$ Jordan block $J$ (eigenvalue $1$, repeated) and its perturbation $J + E$ with $\epsilon$ placed in the bottom-left $(n, 1)$ corner:
\[J = \begin{bmatrix} 1 & 1 & & & \\ & 1 & \ddots & & \\ & & \ddots & \ddots & \\ & & & 1 & 1 \\ & & & & 1 \end{bmatrix} \in \mathbb R^{n \times n}, \qquad J + E = \begin{bmatrix} 1 & 1 & & & \\ & 1 & \ddots & & \\ & & \ddots & \ddots & \\ & & & 1 & 1 \\ \epsilon & & & & 1 \end{bmatrix}\]Then $\lambda(J) = 1$ ($n$ copies), but the perturbation moves them by $ \vert \lambda(J + E) - 1 \vert \approx$ $\epsilon^{1/n}$. With $n = 100$, a perturbation of $10^{-100}$ moves the eigenvalues by $0.1$.
Why $\epsilon^{1/n}$: the corner $\epsilon$ shifts only the constant term of the characteristic polynomial, turning $\det(\lambda I - J) = (\lambda - 1)^n$ into $(\lambda - 1)^n = \epsilon$. The roots are $\lambda = 1 + \epsilon^{1/n} e^{2\pi i j / n}$, all at distance $\epsilon^{1/n}$ from $1$. The $n$-th root is the blow-up: an $n$-fold (defective) eigenvalue, bumped by a constant $\epsilon$, splits into $n$ simple eigenvalues at radius $\epsilon^{1/n} \gg \epsilon$.