Linear Algebra › Section E · Eigenvalues and eigenvectors › Topic E.8

Iterative and numerical eigenvalue methods

Real applications need eigenvalues of large matrices with decimal entries, where factoring a characteristic polynomial is hopeless. Iterative methods instead multiply, scale and repeat, closing in on eigenvalues to any accuracy the computer allows.

Why not use the polynomial?

For a 2 × 2 or 3 × 3 matrix, the characteristic equation is a fine tool. For a 1,000 × 1,000 matrix it fails twice over. First, there is no formula for the roots of a general polynomial of degree 5 or more. Second, polynomial roots can be extremely sensitive to rounding: James Wilkinson showed that changing one coefficient of the degree-20 polynomial with roots 1, 2, ..., 20 by about \(2^{-23}\) turns several of those roots into complex pairs. Since computers round every coefficient, forming the polynomial throws accuracy away. Practical methods work on the matrix itself and improve an estimate step by step.

The idea behind the power method

Suppose \(A\) is diagonalisable with a strictly dominant eigenvalue \(\lambda_1\), so \(|\lambda_1| > |\lambda_j|\) for every other eigenvalue. As in "Discrete dynamical systems", write \(\mathbf{x} = c_1\mathbf{v}_1 + \dots + c_n\mathbf{v}_n\). Then

A^k\mathbf{x} = \lambda_1^k\Big(c_1\mathbf{v}_1 + c_2\big(\tfrac{\lambda_2}{\lambda_1}\big)^k\mathbf{v}_2 + \dots\Big)

Every ratio \(\lambda_j/\lambda_1\) has size below 1, so its powers die away, and if \(c_1 \ne 0\) the direction of \(A^k\mathbf{x}\) approaches that of \(\mathbf{v}_1\). Repeated multiplication alone uncovers the dominant eigenvector. The catch is that \(A^k\mathbf{x}\) itself grows or shrinks like \(\lambda_1^k\), soon overflowing or vanishing, so each step is rescaled.

The power method, step by step

1. Choose a starting vector \(\mathbf{x}_0\) whose largest entry is 1. 2. For \(k = 0, 1, 2, \dots\): compute \(A\mathbf{x}_k\); let \(\mu_k\) be an entry of \(A\mathbf{x}_k\) of largest absolute value; set \(\mathbf{x}_{k+1} = \frac{1}{\mu_k}A\mathbf{x}_k\). 3. For almost every starting vector, \(\mu_k\) approaches the dominant eigenvalue and \(\mathbf{x}_k\) approaches an eigenvector for it, scaled so its largest entry is 1. The reasoning: once \(\mathbf{x}_k\) is nearly an eigenvector, \(A\mathbf{x}_k \approx \lambda_1\mathbf{x}_k\), and since the largest entry of \(\mathbf{x}_k\) is 1, the largest entry of \(A\mathbf{x}_k\) is close to \(\lambda_1\). Only matrix-vector products are needed, which is why the method suits huge sparse matrices.

Worked example: the power method

Estimate the dominant eigenvalue of \(A\), starting from \(\mathbf{x}_0 = (1, 0)\).

A = \begin{bmatrix} 7 & 2 \\ 3 & 2 \end{bmatrix}

1. \(A\mathbf{x}_0 = (7, 3)\), so \(\mu_0 = 7\) and \(\mathbf{x}_1 = (1, 0.4286)\). 2. \(A\mathbf{x}_1 = (7.857, 3.857)\), so \(\mu_1 = 7.857\) and \(\mathbf{x}_2 = (1, 0.4909)\). 3. \(A\mathbf{x}_2 = (7.982, 3.982)\), so \(\mu_2 = 7.982\). 4. One more step gives \(\mu_3 = 7.998\) and \(\mathbf{x}_4 = (1, 0.4999)\). 5. The pattern suggests \(\lambda_1 = 8\) with eigenvector (1, 0.5). Check exactly: \(A(1, 0.5) = (8, 4) = 8(1, 0.5)\). The trace, 9, then gives the other eigenvalue as 1.

How fast, and when it fails

The error in step \(k\) is driven by the term \(c_2(\lambda_2/\lambda_1)^k\mathbf{v}_2\), so convergence depends on the ratio \(|\lambda_2/\lambda_1|\). In the example it is \(\frac{1}{8}\), and each step gains almost one decimal digit. With eigenvalues 10 and 9.5 the ratio is 0.95, and progress is painfully slow. The method breaks down without a strictly dominant eigenvalue: for eigenvalues 5 and -5, or for a complex pair of equal size, the vectors never settle. If the start happens to have \(c_1 = 0\), rounding errors usually introduce a small \(\mathbf{v}_1\) component, after which the method recovers, though more slowly.

A sharper estimate for symmetric matrices

For a symmetric matrix, the Rayleigh quotient

R(\mathbf{x}) = \frac{\mathbf{x} \cdot A\mathbf{x}}{\mathbf{x} \cdot \mathbf{x}}

gives a better estimate from the same vectors. Run the power method on the symmetric matrix with rows (2, 1) and (1, 2), whose eigenvalues are 3 and 1, from \(\mathbf{x}_0 = (1, 0)\). After two steps, \(\mathbf{x}_2 = (1, 0.8)\) and \(\mu_2 = 2.8\), but \(R(\mathbf{x}_2) = \frac{4.88}{1.64} \approx 2.976\), about eight times closer to 3. For symmetric matrices the error in \(R(\mathbf{x}_k)\) shrinks roughly like the square of the ratio \(|\lambda_2/\lambda_1|\) per step, rather than the ratio itself.

The inverse power method

To find an eigenvalue other than the dominant one, start from an estimate \(\alpha\) and use \(B = (A - \alpha I)^{-1}\). If \(A\mathbf{v} = \lambda\mathbf{v}\), then \(B\mathbf{v} = \frac{1}{\lambda - \alpha}\mathbf{v}\), so \(B\) has the same eigenvectors, and the eigenvalue of \(A\) closest to \(\alpha\) becomes the dominant eigenvalue of \(B\). The power method applied to \(B\) runs as follows. Solve \((A - \alpha I)\mathbf{y}_k = \mathbf{x}_k\); let \(\mu_k\) be an entry of \(\mathbf{y}_k\) of largest absolute value; set \(\nu_k = \alpha + \frac{1}{\mu_k}\) and \(\mathbf{x}_{k+1} = \frac{1}{\mu_k}\mathbf{y}_k\). The estimates \(\nu_k\) approach that eigenvalue. Solving a system is cheaper than inverting, and one LU factorisation of \(A - \alpha I\) serves every step.

Worked example: the inverse power method

Find the other eigenvalue of the matrix from the power-method example, using \(\alpha = 1.5\) and \(\mathbf{x}_0 = (1, 1)\). 1. \(A - 1.5I\) has rows (5.5, 2) and (3, 0.5). Solving \((A - 1.5I)\mathbf{y}_0 = (1, 1)\) gives \(\mathbf{y}_0 = (0.4615, -0.7692)\), so \(\mu_0 = -0.7692\) and \(\nu_0 = 1.5 - 1.3 = 0.2\). 2. Then \(\mathbf{x}_1 = (-0.6, 1)\), and the next steps give \(\nu_1 = 1.0548\), \(\nu_2 = 0.9957\) and \(\nu_3 = 1.0003\). 3. The estimates approach 1, and \(\mathbf{x}_k\) approaches \((-\tfrac{1}{3}, 1)\). 4. Check: \(A(-1, 3) = (-1, 3)\), so 1 is an eigenvalue. Convergence is fast because \(B\) has eigenvalues -2 and about 0.154, a ratio of about 0.08.

The QR algorithm and real software

Libraries compute all the eigenvalues at once with the QR algorithm, published independently by John Francis and Vera Kublanovskaya around 1961. Starting from \(A_0 = A\), factor \(A_k = Q_kR_k\), where \(Q_k\) has orthonormal columns and \(R_k\) is upper triangular (the factorisation of "The Gram-Schmidt process and QR"), then set \(A_{k+1} = R_kQ_k\). Since \(R_k = Q_k^{-1}A_k\), each \(A_{k+1} = Q_k^{-1}A_kQ_k\) is similar to \(A_k\), so the eigenvalues never change. Under suitable conditions the \(A_k\) approach upper triangular form, with the eigenvalues on the diagonal. With shifts and a preliminary reduction, it drives the general eigenvalue routines of LAPACK, the library that tools such as MATLAB and NumPy call.

Common mistakes to avoid

First, scaling by the largest entry's size but dropping its sign: \(\mu_k\) is the entry itself, so a negative dominant eigenvalue gives negative \(\mu_k\). Second, in the inverse power method, reporting \(\mu_k\) as the eigenvalue instead of \(\nu_k = \alpha + 1/\mu_k\). Third, expecting the inverse power method to find the smallest eigenvalue whatever \(\alpha\) is; it finds the one closest to \(\alpha\). Fourth, trusting the power method without a strictly dominant eigenvalue.

Key takeaways

Practical eigenvalue computation avoids the characteristic polynomial, whose roots are sensitive to rounding. The power method repeats \(\mathbf{x}_{k+1} = A\mathbf{x}_k/\mu_k\); \(\mu_k\) approaches a strictly dominant eigenvalue at a rate set by \(|\lambda_2/\lambda_1|\). For symmetric matrices the Rayleigh quotient sharpens the estimate. The inverse power method applies the same idea to \((A - \alpha I)^{-1}\), giving \(\nu_k = \alpha + 1/\mu_k\), which approaches the eigenvalue closest to \(\alpha\). The QR algorithm produces similar matrices that approach triangular form, and it is what software uses.

Flashcards

Flashcard

Why iterate

Polynomial roots are unstable, and degree 5 or more has no general formula

Work on the matrix itself.

Test your understanding

Question 1 of 5

Apply one step of the power method to the matrix with rows (4, 1) and (2, 3), starting from x₀ = (1, 0). What are μ₀ and x₁?

Question 2 of 5

The power method is run on four matrices with the eigenvalues listed. For which does it converge fastest?

Question 3 of 5

A has eigenvalues 1, 3.8 and 9. The inverse power method is run with α = 4. Which eigenvalue do the estimates νₖ approach?

Question 4 of 5

In the inverse power method with α = 2, one step gives μₖ = −4 as the largest-size entry of yₖ. What is the eigenvalue estimate νₖ?

Question 5 of 5

Why do the matrices Aₖ produced by the QR algorithm have the same eigenvalues as A?

← Previous topicNext topic →