1.3 KiB
Power Method for computing the largest eigenvalue of a square matrix
An eigenvector, v ∈ R^n is a nonzero vector such that for some number, λ ∈ C, Av = λ v ⇒ || v || = 1
Suppose we start with some vector v and assume, v = α_0 v_0 + α_1 v_1 + ⋯ + α_n v_n, where {v_1, ⋯, v_n} are the eigenvectors of A. Assume {v_1, ⋯, v_n} is a basis for R^n
We can order the eigenvalues such that λ_1 ≥ λ_2 ≥ λ_3 ≥ ⋯ ≥ λ_n
Compute u = Av = A(α_1 v_1 + ⋯ + α_n v_n) = α_1 Av_1 + A(⋯) + α_n A v_n = α_1 λ_1 v_1 + α_2 λ_2 v_2 + ⋯ + α_n λ_n v_n
w = A (Av) = α_1 λ_1^2 v_1 + α_2 λ_2^2 v_2 + ⋯ + α_n λ_n^2 v_n
Thus, A^k v = α_1 λ_1^k v_1 + α_2 λ_2^k v_2 + ⋯ + α_n λ_n^k v_n = λ_1^k ( α_1 v_1 + α_2 \frac{λ_2^k}{λ_1^k} v_2 + ⋯ + α_n \frac{λ_3^k}{λ_1^k} v_n)
As k → ∞ A^k v = λ_1^k (α_1 v_1) + \text{negligble terms}
Algorithm: v ≠ 0 with v ∈ R^n y = Av = α_1 v_1 + ⋯ + α_n v_n
w = \frac{1}{||y||} ⋅ y
Rayleigh Quotient: If $v$ is an eigenvector of A with eigenvalue λ then \frac{v^T A v}{v^T v} = λ