Lecture 12: Computing Eigenvalues and Singular Values

What this lecture covers

This lecture answers a practical question the course has avoided until now: when you call an eigenvalue or SVD routine, what algorithm actually runs? Gilbert Strang shows that the QR factorization from the previous lecture is the hidden engine behind both. Repeatedly factoring a matrix into Q and R and multiplying them back in reverse order produces a sequence of similar matrices whose off-diagonal entries shrink toward zero, leaving the eigenvalues on the diagonal.

The lecture builds up the method in stages: the basic QR iteration, a shift trick that speeds up convergence, and a preprocessing step (reducing to Hessenberg or tridiagonal form) that makes each iteration cheap. It then turns to singular values, asking what operations preserve them the way similarity transformations preserve eigenvalues, and sketches how large sparse problems are instead handled by Krylov subspace methods. After this lecture you can explain why eig and svd calls converge quickly and what structure in a matrix makes them faster.

Key ideas

• QR method: factor a matrix as A = QR, then form the next matrix as RQ; the new matrix is similar to the old one, so eigenvalues are preserved, and the lower-triangular part shrinks toward zero as this repeats.
• Similarity transformation: two matrices A1 = Q^-1 A0 Q have the same eigenvalues; this is the property the QR method must preserve at every step.
• Shifts: subtracting a multiple of the identity before factoring (and adding it back after) leaves the similarity relation intact but converges faster, especially when the shift approximates an eigenvalue.
• Cubic convergence: in a worked small example, the off-diagonal entry shrinks by being cubed at each step, showing why the method converges so quickly.
• Hessenberg form: a matrix that is triangular except for one extra diagonal; reducing a general matrix to this form first (by a similarity transformation) keeps those zeros through QR steps and cuts the work per iteration substantially.
• Symmetric case: if the starting matrix is symmetric, it stays symmetric through the QR method, and a symmetric Hessenberg matrix is tridiagonal, which reduces the work to about 2n numbers per step instead of order n^2.
• Abel's impossibility result: for degree five and higher, there is no finite formula solving the eigenvalue equation exactly, which is why these are iterative methods that converge within a tolerance rather than exact algorithms.
• Invariance for singular values: multiplying a matrix by orthogonal matrices on the left and right (Q1 A Q2^T) leaves its singular values unchanged, the analog of similarity transformations for eigenvalues.

Walkthrough

The QR method for eigenvalues (1:01)

Strang introduces the central idea: starting from a matrix A0, factor it as Q0 R0, then multiply the factors back in reverse order to get A1 = R0 Q0. He shows algebraically that A1 is similar to A0 (since A1 = Q0^-1 A0 Q0), so the eigenvalues never change. Repeating this process, most matrices lose entries below the diagonal, and after enough steps the eigenvalues appear (approximately) on the diagonal. A small worked example illustrates cubic convergence: an off-diagonal entry gets cubed, then raised to the ninth power, then the 27th, vanishing very fast.

Shifts speed up convergence (10:14)

To accelerate the method, each step works with A0 - sI instead of A0, where s is a scalar shift. Shifting by a multiple of the identity leaves eigenvectors unchanged and shifts every eigenvalue by s, so choosing s close to an eigenvalue drives that eigenvalue toward zero and speeds convergence. Strang verifies algebraically that after factoring the shifted matrix and adding the shift back, the result is still similar to the original, so shifting is "free" in terms of correctness while improving speed.

Hessenberg form cuts the cost (18:33)

The real cost of the QR method is the repeated QR factorization at each step, so the lecture asks how to make that factorization cheaper. If the starting matrix already has many zeros, those zeros can be preserved through the process, cutting work. You cannot triangularize a matrix completely by simple similarity steps (that would already give you the eigenvalues, which Abel proved impossible to find exactly by finite algebraic steps for n of 5 or more). The best you can do is reduce to upper Hessenberg form: triangular plus one extra diagonal. This is done once as a preprocessing step, and Hessenberg structure survives subsequent QR steps, making each iteration cheap. When the original matrix is symmetric, this same process produces a tridiagonal matrix, and symmetry is preserved throughout, cutting the work per step from order n^2 to roughly 2n.

Singular values and orthogonal invariance (27:42)

Strang turns to singular values, noting that although SVD(A) relates to the eigenvalues of A^T A, you would never actually form A^T A (it's slow and numerically unstable) or solve the characteristic determinant equation directly (extremely slow and ill-conditioned). Instead, the question becomes: what operations leave singular values unchanged, the way similarity transformations leave eigenvalues unchanged? The answer is multiplying by different orthogonal matrices on the left and right: Q1 A Q2^T has the same singular values as A, because a product of orthogonal matrices is itself orthogonal (checked using the test that a matrix's inverse equals its transpose). This extra freedom, compared to eigenvalues, allows reduction past tridiagonal form all the way to bidiagonal form, from which a QR-type method extracts the singular values efficiently.

Krylov methods for very large matrices (42:13)

For matrices too large for the full QR method (order up to roughly a thousand, by Strang's estimate), the lecture briefly revisits the Krylov subspace idea from an earlier class: build a subspace by repeatedly multiplying a starting vector b by A, orthogonalize that basis with Gram-Schmidt, and restrict the matrix to this much smaller subspace (say, size 100 instead of a million). Solving the smaller eigenvalue problem gives good approximations to some of the original matrix's eigenvalues, without ever forming or factoring the full matrix.

Before you watch

• Review the QR factorization (Gram-Schmidt producing orthogonal Q and upper-triangular R) from the previous lecture in this course, since it is the building block for everything here.
• Be comfortable with similarity transformations and why they preserve eigenvalues.
• Recall the SVD (A = U Sigma V^T) and the idea of orthogonal matrices, since the lecture builds directly on both.

Check your understanding

1. Why does forming A1 = RQ from A0 = QR guarantee that A0 and A1 have the same eigenvalues?
2. How does introducing a shift A0 - sI before factoring change the eigenvalues, and why does undoing the shift afterward still preserve similarity to the original matrix?
3. What is a Hessenberg matrix, and why does reducing a matrix to this form first make the QR method faster?
4. Why does a symmetric matrix reduce to tridiagonal form under this process, and how much work per step does that save compared to a general matrix?
5. What operation preserves singular values in the way similarity transformations preserve eigenvalues, and why does a product of two orthogonal matrices remain orthogonal?