Quant Academy Math · Probability · Quant Finance
Phase 5 - Lesson 5.5

Eigenvalue & SVD Algorithms and Iterative Methods

Why we iterate instead of solving a characteristic polynomial, from power iteration to the QR algorithm and conjugate gradients.

⏱ 60 min● Advanced🔗 Prereqs: 5.3
↖ Phase 5 hub
Builds on: QR (5.3) reappears as the engine of the eigenvalue algorithm.
Leads to: PCA (Phase 11), spectral risk, and large sparse solves all rest on these methods.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Key Vocabulary

Power iteration
Repeatedly applying \(A\) and normalizing; converges to the dominant eigenvector.
Rayleigh quotient
\(\rho(v)=\dfrac{v^\top A v}{v^\top v}\); best scalar eigenvalue estimate for a given \(v\).
QR algorithm
Iterating \(A_k=Q_kR_k,\ A_{k+1}=R_kQ_k\); converges to (block) triangular Schur form revealing eigenvalues.
SVD
\(A=U\Sigma V^\top\) with orthogonal \(U,V\) and nonnegative singular values on \(\Sigma\).
Krylov subspace
\(\mathrm{span}\{b,Ab,\dots,A^{k-1}b\}\); the search space for CG and GMRES.
Conjugate gradients
An iterative solver for symmetric positive-definite systems converging in terms of \(\sqrt{\kappa}\).

Intuition & Motivation

Intuition
There is a hard theorem lurking here: for degree \(\ge5\) there is no formula for polynomial roots (Abel–Ruffini), and eigenvalues are roots of the characteristic polynomial. So any eigenvalue method must be iterative - we converge, we don’t solve. The simplest iteration just multiplies by \(A\) over and over: the dominant eigendirection wins because its factor \(|\lambda_1|\) dwarfs the rest. The famous QR algorithm is a beautifully disguised version of running that idea on all directions at once.

Why iterate?

Computing eigenvalues by forming and rooting the characteristic polynomial is both unstable and, by Abel–Ruffini, impossible in closed form beyond degree four. Every practical method converges through repeated orthogonalization instead.

Power iteration

Write \(v_0=\sum_i c_i x_i\) in an eigenbasis. Then \(A^k v_0=\sum_i c_i\lambda_i^k x_i\), and dividing by \(\lambda_1^k\):

\[\frac{A^k v_0}{\lambda_1^k}=c_1 x_1+\sum_{i\ge2}c_i\Big(\tfrac{\lambda_i}{\lambda_1}\Big)^k x_i \;\longrightarrow\; c_1 x_1,\] (5.6)

since every ratio \(|\lambda_i/\lambda_1|\lt 1\). Convergence is linear at rate \(|\lambda_2/\lambda_1|\) - the eigengap governs speed.

Theorem - QR algorithm converges to Schur form
For the unshifted QR iteration \(A_{k+1}=R_kQ_k\) (where \(A_k=Q_kR_k\)), the \(A_k\) converge to upper-triangular form whose diagonal holds the eigenvalues, ordered by magnitude. Shifts accelerate this to cubic convergence in practice.
Worked Example - Power iteration by hand
1
Take \(A=\begin{psmallmatrix}2&0\\0&1\end{psmallmatrix}\) with eigenvalues \(2,1\) and \(v_0=(1,1)^\top\).
2
\(Av_0=(2,1)^\top\), normalize; \(A^2v_0\propto(4,1)^\top\), \(A^k v_0\propto(2^k,1)^\top\).
3
The second component fades like \((1/2)^k\), so \(v_k\to(1,0)^\top\), the dominant eigenvector.
4
The Rayleigh quotient \(\rho(v_k)=v_k^\top A v_k/v_k^\top v_k\to2=\lambda_1\).

Interactive: power iteration & the Rayleigh quotient

Implement power iteration and read off the dominant eigenvalue via the Rayleigh quotient; watch convergence track the eigengap.

Direct vs. iterative for large systems

Dense factorizations (LU, QR, Cholesky) are \(O(n^3)\) and store the whole matrix - impossible for the huge sparse systems in PDE-based pricing. Krylov methods (CG for SPD, GMRES otherwise) only need matrix-vector products and converge in a number of steps governed by \(\sqrt{\kappa}\), making them the tool for large sparse problems.

Common Mistakes to Avoid
  • Trying to compute eigenvalues by rooting the characteristic polynomial - unstable and impossible in closed form past degree 4.
  • Running power iteration when \(|\lambda_1|=|\lambda_2|\) (e.g. complex-conjugate pair): it fails to converge to a single direction.
  • Forgetting to normalize each power-iteration step, causing overflow/underflow.
  • Using CG on a non-symmetric or indefinite matrix; it can break down - use GMRES/MINRES instead.
Quant Practitioner Tips
  • Use the Rayleigh quotient, not a single component, as the eigenvalue estimate - it converges twice as fast for symmetric \(A\).
  • For the smallest eigenvalue, run power iteration on \(A^{-1}\) (inverse iteration) with a shift.
  • Precondition CG to shrink the effective \(\kappa\) and cut iterations dramatically.
  • For PCA/risk, you usually need only the top few eigenvectors - a partial (Lanczos/randomized) SVD beats a full one.

Knowledge Check

Q1 Medium
Why must eigenvalue algorithms be iterative rather than closed-form?
Because matrices are too big
Because eigenvalues are roots of a polynomial, and there is no general formula past degree 4 (Abel–Ruffini)
Because of floating-point error only
Because eigenvalues are always complex
Q2 Medium
Power iteration converges to the dominant eigenvector at a linear rate equal to:
\(|\lambda_1|\)
\(|\lambda_2/\lambda_1|\)
\(|\lambda_1/\lambda_2|\)
\(\kappa(A)\)
Q3 Easy
For a very large sparse symmetric positive-definite system, the method of choice is:
Dense LU
Explicit matrix inverse
Conjugate gradients (a Krylov method)
Cramer’s rule

Practical Exercise

Starting from \(v_0=\sum_i c_i x_i\) (with \(c_1\ne0\) and \(|\lambda_1|\gt |\lambda_2|\ge\dots\)), show that normalized power iteration converges to \(\pm x_1\) and state the convergence rate.

▶ Show full solution

Apply \(A^k\): \(A^k v_0=\lambda_1^k\big(c_1 x_1+\sum_{i\ge2}c_i(\lambda_i/\lambda_1)^k x_i\big)\).

Each ratio \(|\lambda_i/\lambda_1|\lt 1\), so the sum tends to \(c_1 x_1\). After normalization the direction is \(\pm x_1\) (sign depends on \(\mathrm{sign}(\lambda_1^k)\)). The error shrinks like \(|\lambda_2/\lambda_1|^k\), so convergence is linear with rate \(|\lambda_2/\lambda_1|\).

After the reveal, answer for yourself: How would a spectral shift \(A-\sigma I\) change the ratio that controls convergence?

Lesson Summary

Eigenvalues are polynomial roots, so by Abel–Ruffini they must be found iteratively. Power iteration exposes the core idea - repeated multiplication amplifies the dominant eigendirection at rate \(|\lambda_2/\lambda_1|\) - and the QR algorithm generalizes it to the whole spectrum. For large sparse systems, Krylov methods (CG/GMRES) replace \(O(n^3)\) factorizations.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: What sets the convergence rate of power iteration?
A: The eigengap ratio \(|\lambda_2/\lambda_1|\); a bigger gap means faster linear convergence to the dominant eigenvector.
Q: Why can't we compute eigenvalues in closed form in general?
A: They are roots of the characteristic polynomial, and Abel–Ruffini forbids a radical formula for degree \(\ge5\); hence all methods iterate.

Completion Checklist

Confidence / mastery rating
Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

← 5.4Next: 6.1 →