lizfcm/notes/Oct-30.org

35 lines
1.3 KiB
Org Mode
Raw Permalink Normal View History

2023-10-30 21:07:43 -04:00
* Power Method for computing the largest eigenvalue of a square matrix
An eigenvector, v \in R^n is a nonzero vector such that for some number, \lambda \in C, Av = \lambda v
\Rightarrow || v || = 1
Suppose we start with some vector v and assume, v = \alpha_0 v_0 + \alpha_1 v_1 + \cdots + \alpha_n v_n, where {v_1, \cdots, v_n}
are the eigenvectors of A. Assume {v_1, \cdots, v_n} is a basis for R^n
We can order the eigenvalues such that \lambda_1 \ge \lambda_2 \ge \lambda_3 \ge \cdots \ge \lambda_n
Compute u = Av
= A(\alpha_1 v_1 + \cdots + \alpha_n v_n)
= \alpha_1 Av_1 + A(\cdots) + \alpha_n A v_n
= \alpha_1 \lambda_1 v_1 + \alpha_2 \lambda_2 v_2 + \cdots + \alpha_n \lambda_n v_n
w = A (Av)
= \alpha_1 \lambda_1^2 v_1 + \alpha_2 \lambda_2^2 v_2 + \cdots + \alpha_n \lambda_n^2 v_n
Thus,
A^k v = \alpha_1 \lambda_1^k v_1 + \alpha_2 \lambda_2^k v_2 + \cdots + \alpha_n \lambda_n^k v_n
= \lambda_1^k ( \alpha_1 v_1 + \alpha_2 \frac{\lambda_2^k}{\lambda_1^k} v_2 + \cdots + \alpha_n \frac{\lambda_3^k}{\lambda_1^k} v_n)
As k \rightarrow \infty
A^k v = \lambda_1^k (\alpha_1 v_1) + \text{negligble terms}
Algorithm:
v \ne 0 with v \in R^n
y = Av = \alpha_1 v_1 + \cdots + \alpha_n v_n
w = \frac{1}{||y||} \cdot y
Rayleigh Quotient:
If $v$ is an eigenvector of A with eigenvalue \lambda then \frac{v^T A v}{v^T v} = \lambda