SC-08

Course 8

Eigenvalue Problems

Compute eigenvalues and eigenvectors numerically. From the simple power method to sophisticated algorithms, learn to solve the fundamental problem $Ax = \lambda x$ .

Learning Objectives

Implement the power method for dominant eigenvalues
Use inverse power method with shifts for specific eigenvalues
Apply Gershgorin circles for eigenvalue localization
Understand Jacobi rotations for symmetric matrices
Learn the principles of the QR algorithm
Apply deflation techniques for multiple eigenvalues

1. Power Method

The power method finds the dominant eigenvalue (largest in absolute value) and its eigenvector.

Algorithm Power Method

Input: Matrix $A$ , initial vector $x^{(0)}$ , tolerance $\epsilon$

Normalize: $x^{(0)} \leftarrow x^{(0)} / \|x^{(0)}\|$
For $k = 0, 1, 2, \ldots$ :
Compute $y^{(k+1)} = A x^{(k)}$
Normalize $x^{(k+1)} = y^{(k+1)} / \|y^{(k+1)}\|$
Estimate eigenvalue: $\lambda^{(k+1)} = (x^{(k+1)})^T A x^{(k+1)}$ (Rayleigh quotient)
Stop if $|\lambda^{(k+1)} - \lambda^{(k)}| < \epsilon$

Theorem 8.1: Convergence of Power Method

\lambda^{(k)} \to \lambda_1, \quad x^{(k)} \to v_1 \text{ (eigenvector)}

Convergence rate: $O\left(\left|\frac{\lambda_2}{\lambda_1}\right|^k\right)$

Example: Power Method

For $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ with $x^{(0)} = (1, 0)^T$ :

$k$	$x^{(k)}$	$\lambda^{(k)}$
1	(0.894, 0.447)	2.8
2	(0.745, 0.667)	2.96
5	(0.707, 0.707)	3.00

Converges to $\lambda_1 = 3$ , $v_1 = (1, 1)^T/\sqrt{2}$ .

Note:

Special cases: If the dominant eigenvalue has multiplicity > 1, or if there are complex conjugate dominant eigenvalues, modified approaches are needed.

2. Inverse Power Method

Definition 8.1: Inverse Power Method

Apply power method to $A^{-1}$ : since $A^{-1}v = \frac{1}{\lambda}v$ , the smallest eigenvalue of $A$ becomes dominant for $A^{-1}$ .

Each iteration solves $Ay^{(k+1)} = x^{(k)}$ instead of computing $A^{-1}$ explicitly.

Definition 8.2: Shifted Inverse Power Method

To find eigenvalue closest to shift $\mu$ , apply inverse power to $(A - \mu I)^{-1}$ :

(A - \mu I)y^{(k+1)} = x^{(k)}

The eigenvalue of $A$ closest to $\mu$ becomes dominant.

Remark:

Rayleigh quotient iteration: Use the current eigenvalue estimate as the shift: $\mu^{(k)} = R(x^{(k)})$ . This achieves cubic convergence near the eigenvalue.

3. Eigenvalue Localization

Theorem 8.2: Gershgorin Circle Theorem

Every eigenvalue of $A$ lies in at least one Gershgorin disk:

D_i = \left\{ z \in \mathbb{C} : |z - a_{ii}| \leq \sum_{j \neq i} |a_{ij}| \right\}

Furthermore, if $k$ disks form a connected region disjoint from other disks, exactly $k$ eigenvalues lie in that region.

Example: Gershgorin Disks

For $A = \begin{pmatrix} 4 & 1 & 0 \\ 1 & 5 & 1 \\ 0 & 0 & 2 \end{pmatrix}$ :

$D_1$ : center 4, radius 1 → $[3, 5]$
$D_2$ : center 5, radius 2 → $[3, 7]$
$D_3$ : center 2, radius 0 → $\{2\}$ (isolated)

Thus $\lambda_3 = 2$ exactly, and other eigenvalues lie in $[3, 7]$ .

Remark:

Gershgorin circles provide initial estimates for shifts in shifted inverse iteration, making convergence faster.

4. Jacobi Method for Symmetric Matrices

Definition 8.3: Jacobi Rotation

A Jacobi rotation (Givens rotation) $J(p, q, \theta)$ is an orthogonal matrix that differs from identity only in positions $(p,p), (p,q), (q,p), (q,q)$ :

J = \begin{pmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{pmatrix} \text{ in the } (p,q) \text{ block}

Algorithm Jacobi Method

Find largest off-diagonal element $|a_{pq}|$
Compute rotation angle $\theta$ to zero out $a_{pq}$
Apply rotation: $A \leftarrow J^T A J$
Repeat until off-diagonal elements are negligible

Final diagonal contains eigenvalues; product of rotations gives eigenvectors.

Theorem 8.3: Jacobi Convergence

For symmetric matrices, the Jacobi method converges. The sum of squares of off-diagonal elements decreases at each step. With proper ordering, convergence is quadratic.

Note:

The Jacobi method is simple and robust, but requires $O(n^2)$ operations per sweep and many sweeps. Modern software uses the more efficient QR algorithm.

5. Deflation and the QR Algorithm

Definition 8.4: Deflation

After finding eigenvalue $\lambda_1$ with eigenvector $v_1$ , modify $A$ to remove this eigenvalue:

A' = A - \lambda_1 v_1 v_1^T \quad (\text{for symmetric } A)

Then apply power method to $A'$ to find remaining eigenvalues.

Definition 8.5: QR Algorithm

The basic QR iteration:

Start with $A_0 = A$
For $k = 0, 1, 2, \ldots$ :
QR factorization: $A_k = Q_k R_k$
Reverse multiply: $A_{k+1} = R_k Q_k$

For real matrices, $A_k$ converges to upper quasi-triangular form (real Schur form).

Theorem 8.4: QR Convergence

If eigenvalues have distinct absolute values, QR iteration converges to upper triangular form, with eigenvalues on the diagonal.

Convergence rate for $a_{ij}^{(k)}$ (below diagonal): $O(|\lambda_j/\lambda_i|^k)$

Remark:

Practical QR: Uses shifts (Wilkinson shift), Hessenberg reduction, and implicit techniques for $O(n^3)$ complexity. This is the standard algorithm in LAPACK and similar libraries.

Practice Quiz

Eigenvalue Problems Quiz

Questions

Correct

Accuracy

The power method computes the eigenvalue that is:

Easy

Not attempted

The convergence rate of the power method depends on:

Easy

Not attempted

The inverse power method with shift

\mu

converges to the eigenvalue closest to:

Easy

Not attempted

Gershgorin's theorem states that all eigenvalues lie in:

Medium

Not attempted

The Jacobi method for eigenvalues uses rotations to:

Medium

Not attempted

For a symmetric matrix, the Jacobi method produces:

Medium

Not attempted

Rayleigh quotient for vector

x

and matrix

A

is:

Medium

Not attempted

\lambda_1 = -\lambda_2

are the two largest eigenvalues in absolute value, power method:

Hard

Not attempted

The QR algorithm is based on repeatedly:

Hard

Not attempted

Deflation in eigenvalue computation refers to:

Hard

Not attempted

Frequently Asked Questions

When should I use power method vs. QR algorithm?

Power method: When you only need the dominant eigenvalue (and eigenvector), especially for large sparse matrices where matrix-vector products are cheap.

QR algorithm: When you need all eigenvalues of a moderate-size dense matrix. It's the standard for complete eigendecomposition.

How do I find eigenvalues of a non-symmetric matrix?

Non-symmetric matrices may have complex eigenvalues. The QR algorithm (with Hessenberg reduction) handles this, producing a quasi-triangular (real Schur) form with 1×1 and 2×2 diagonal blocks corresponding to real and complex conjugate eigenvalue pairs.

What if the power method doesn't converge?

Check for these issues:

Equal magnitude eigenvalues: Use techniques for repeated or complex dominant eigenvalues
Poor initial guess: Try a random starting vector
Slow convergence: Use Rayleigh quotient iteration or shifted inverse power

How accurate are computed eigenvalues?

For well-conditioned problems, eigenvalues are computed to near machine precision. For ill-conditioned problems (nearly repeated eigenvalues, non-normal matrices), accuracy may be limited. Eigenvectors of close eigenvalues may be poorly determined.

What is the spectral decomposition?

For a symmetric matrix: $A = Q \Lambda Q^T$ where $Q$ is orthogonal (columns are eigenvectors) and $\Lambda$ is diagonal (eigenvalues).

This is useful for computing functions of matrices (e.g., $e^A, \sqrt{A}$ ) and understanding matrix behavior.