Numerical Eigenvalue Calculation

Methods for One Eigenvalue or the Full Spectrum

An eigenpair of a square matrix $A$ satisfies

Av=\lambda v,\qquad v\ne0

For a small symbolic matrix, one can solve $\det(A-\lambda I)=0$ . Numerical software usually $avoids forming and rooting the characteristic polynomial$ because its coefficients can be sensitive to rounding. When only part of the spectrum of a large sparse matrix is needed, Krylov methods use matrix-vector products without forming that polynomial. Dense algorithms for the complete spectrum instead work with matrix factorizations.

The required part of the spectrum and the matrix structure determine the algorithm:

Power iteration estimates one eigenvalue of largest magnitude.
Shifted inverse iteration targets an eigenvalue near a chosen shift.
The $\mathrm{QR}$ algorithm computes the complete spectrum of a dense matrix.
Lanczos and Arnoldi methods target a small part of the spectrum of a large sparse matrix.

Power Iteration

The formulas below use real matrices and real iterates. For complex iterates, replace the transpose in the Rayleigh quotient by the conjugate transpose. If $z_k=0$ , normalization is impossible. Check whether the previous vector is an eigenvector for zero.

Choose a nonzero starting vector $q_0$ and normalize it. Repeat

z_k=Aq_{k-1}

The scalar $\mu_k$ is the Rayleigh quotient. For a diagonalizable matrix with a $unique dominant magnitude$ ,

|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|

If the displayed inequality holds and the starting vector has a nonzero component in the dominant eigendirection, $q_k$ approaches that eigendirection. The asymptotic error commonly shrinks in proportion to

\left|\frac{\lambda_2}{\lambda_1}\right|^k

This explains two failure modes. Equal dominant magnitudes can prevent convergence to one vector, while a zero coefficient in the dominant direction of the eigenbasis prevents convergence to that direction. For symmetric matrices, this is equivalent to orthogonality to the dominant eigenvector. For nonnormal matrices, the eigenbasis need not be orthogonal, so the coefficient must be checked in that basis.

Stop with the Residual

Do not stop only because consecutive eigenvalue estimates look similar. Check the eigenpair residual

r_k=Aq_k-\mu_kq_k

A scale-aware condition is

\|r_k\|_2\le \tau\bigl(\|A\|_2+|\mu_k|\bigr)

Here, $\tau$ is the requested tolerance. A small residual certifies that $the computed pair nearly satisfies the eigenvalue equation$ , although it does not by itself identify which nearby eigenvalue was found.

Worked Power Iteration Example

Consider

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

The first step gives

z_1=Aq_0=\begin{pmatrix}2\\1\end{pmatrix}

The second step gives

q_2=\frac{1}{\sqrt{41}}\begin{pmatrix}5\\4\end{pmatrix}

The iterates approach

q_*=\frac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix},\qquad \lambda_*=3

The other eigenvalue is $1$ , so the $expected convergence factor$ is $|1/3|$ per iteration after the asymptotic regime is reached.

Iteration	Rayleigh estimate	Residual norm
1	$14/5$	$3/5$
2	$122/41$	$9/41$

Shifted Inverse

Choose a shift that is $not an eigenvalue$ . Convergence to one eigendirection requires a uniquely closest eigenvalue and a nonzero coefficient in its eigenbasis direction. A tie in distance can prevent convergence to one direction. Iteration

Power iteration favors the largest magnitude. To target an eigenvalue near a shift $\sigma$ , repeat

(A-\sigma I)z_k=q_{k-1}

The eigenvalues of $(A-\sigma I)^{-1}$ are $1/(\lambda_i-\sigma)$ , so the eigenvalue closest to $\sigma$ becomes dominant. Never form the inverse explicitly. $Factor$ $A-\sigma I$ and solve a linear system at each iteration. A fixed shift allows the factorization to be reused.

If $\sigma$ is extremely close to an eigenvalue, the shifted system is ill conditioned. Accurate linear solves and residual checks are therefore essential.

QR Algorithm for the Full Spectrum

Start with $A_0=A$ . At iteration $k$ , compute

A_k=Q_kR_k

Every step is an $orthogonal similarity transformation$ , so it preserves the eigenvalues. Practical $\mathrm{QR}$ algorithms first reduce a dense matrix to Hessenberg form, use shifts, and deflate converged blocks. For a real nonsymmetric matrix, the limit is generally a real Schur form with $1\times1$ and $2\times2$ diagonal blocks. A symmetric matrix reduces to tridiagonal form and converges to a diagonal matrix.

Choosing the Right Method

Goal and matrix structure	Suitable method	Important check
One dominant eigenpair	Power iteration	unique dominant magnitude and nonzero starting component
Eigenpair near $\sigma$	Shifted inverse iteration	stable solves with $A-\sigma I$
Several extreme eigenpairs of a large symmetric sparse matrix	Lanczos	loss of orthogonality and residuals
Several eigenpairs of a large nonsymmetric sparse matrix	Arnoldi	subspace size, restarts, and residuals
Complete spectrum of a dense matrix	Shifted $\mathrm{QR}$ to Schur form	converged diagonal or quasi-diagonal blocks

The final acceptance test is always tied to the requested eigenpairs: $verify residuals$ , preserve complex conjugate pairs for real matrices, and avoid claiming an eigenvector is accurate merely because an eigenvalue estimate has stabilized.