Eigenvalue algorithms approximate invariant directions and spectra. The symmetric case is far better behaved than the general non-normal case.
Eigenvalue problem
Definition. The eigenvalue problem asks for \((\lambda,v)\) with \(Av=\lambda v\) and \(v\ne0\). The numerical problem may seek one eigenpair, a few extreme eigenpairs, or a Schur form containing all eigenvalues.
Power method
Proposition. If \(A\) has a dominant eigenvalue separated in modulus from the rest and the starting vector has a component in its eigenvector direction, normalized powers \(A^k x\) converge to the dominant invariant direction.
QR algorithm
Theorem. The QR algorithm repeatedly factors \(A_k=Q_kR_k\) and sets \(A_{k+1}=R_kQ_k\). With shifts and preliminary Hessenberg reduction, it is the standard stable method for dense eigenvalue computation.
Symmetric perturbation
Proposition. For symmetric matrices, eigenvalues are Lipschitz in operator norm: \(\max_j |\widehat\lambda_j-\lambda_j|\le \|E\|_2\) after suitable ordering. Eigenvectors require eigenvalue gaps for stability.
Pseudospectra
Remark. For non-normal matrices, eigenvalues can be much more sensitive than the norm of the perturbation suggests. Pseudospectra visualize where eigenvalues of nearby matrices may lie and are often more informative than the spectrum alone.
Power and inverse iteration
If \(A\) is diagonalizable with \(|\lambda_1|>|\lambda_2|\ge\cdots\) and the starting vector has a nonzero component in \(v_1\), normalized power iteration converges in direction at rate \[ O\!\left(\left|\frac{\lambda_2}{\lambda_1}\right|^k\right). \] Inverse iteration on \(A-\mu I\) targets the eigenvalue nearest the shift \(\mu\). Factoring once and solving repeatedly is more stable than explicitly forming the inverse.
Rayleigh quotients
Proposition. For symmetric \(A\), the Rayleigh quotient \[ \rho(x)=\frac{x^\top Ax}{x^\top x} \] satisfies \[ \lambda_{\min}\le\rho(x)\le\lambda_{\max}, \] and its stationary points on the unit sphere are eigenvectors.
Proof. Expand \(x=\sum_ic_iv_i\) in an orthonormal eigenbasis: \[ \rho(x)=\frac{\sum_i\lambda_i|c_i|^2}{\sum_i|c_i|^2}, \] a convex combination of eigenvalues. Lagrange stationarity of \(x^\top Ax\) under \(x^\top x=1\) gives \(Ax=\lambda x\).
QR iteration
Unshifted QR factors \[ A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k=Q_k^\top A_kQ_k. \] Thus every iterate is orthogonally similar to \(A\). For symmetric matrices, preliminary Householder reduction to tridiagonal form costs \(O(n^3)\), while each implicit shifted QR step costs \(O(n)\). Wilkinson shifts accelerate deflation and usually give cubic convergence near a simple eigenvalue.
Symmetric perturbation
Theorem (Weyl). For symmetric \(A,E\), ordered eigenvalues satisfy \[ |\lambda_i(A+E)-\lambda_i(A)|\le\|E\|_2. \]
Proof. The Courant--Fischer min--max formula and \(|x^\top Ex|\le\|E\|_2\|x\|^2\) give upper and lower inequalities for each ordered eigenvalue.
Invariant subspaces
Individual eigenvectors are unstable when eigenvalues are clustered, but the invariant subspace for an isolated cluster can be stable. Davis--Kahan gives, schematically, \[ \|\sin\Theta(\widehat U,U)\|_2 \le\frac{\|E\|_2}{\operatorname{gap}}, \] where the denominator separates the target cluster from the rest of the spectrum. Statistical PCA error bounds are instances of this theorem.
Nonnormal matrices
Schur factorization \(A=QTQ^*\) is always available and stable, whereas an eigenvector matrix may be ill conditioned. For nonnormal problems, pseudospectra and Schur vectors are often more meaningful than raw eigenvectors. A small backward error in \(A\) can still produce a large eigenvalue forward error.