04.1.Power-Method.md

The Power Method (幂法)

[toc]

数学原理

设 n 阶实矩阵 $B\in R^{n\times n}$, n 个特征值: $|\lambda_1|>|\lambda_2|\ge|\lambda_3|\ge\cdots\ge|\lambda_n|\ge0$, 其对应特征向量为 $X_i=(X_1^{(i)}, \cdots, X_n^{(i)})$ 线性无关

$\forall v_0\not=0, v_0\in R^n$, 令 $v_k=Bv_{k-1}$, 则 $v_k$ 逼近 $B$ 的优特征值对应的特征向量, 且 $\lambda_1\approx\frac{(v_{k+1})_i}{(v_k)_i}$

若存在不全为零的 $\alpha_i(i=1,\cdots n), \alpha_1\not=0$, 则有 $v_0=\sum\limits_{i=1}^n\alpha_ix_i$, $v_k=B^kv_0=\sum\limits_{i=1}^nB^k(\alpha_i x_i)=\sum\limits_{i=1}^n\alpha_i\lambda^kx_i=\lambda_1^k\left[\alpha_1x_1+\sum\limits_{i=2}^n\left(\frac{\lambda_i}{\lambda_1}\right)^k\alpha_ix_i\right]$

• $\left|frac{\lambda_k}{\lambda_1}\right|$ 越小, 收敛越快
• $v_0$ 取值恰使 $\alpha_1=0$ 时, 幂法依然可进行, 因为会有舍入误差导致 $x_1$ 系数又变成非零, 从而使得条件成立.
• $v_k\approx\lambda_1^k\alpha_1x_1$, 这里面要考虑 $|\lambda_1|&gt;1$和$<1$, 迭代过程需要规范化

算法

$\left{\begin{array}{l}u_k=Bv_{k-1} \ m_k=\max(u_k) \ v_k=\frac{u_k}{m_k}\end{array}\right.$

e.g. $u_k=(2,3,1,-5)\Rightarrow v_k=\left(\frac{2}{5}, \frac{3}{5}, \frac{1}{5}, -1\right)$

• $m_k=\lambda_1+O(\left(\left|\frac{\lambda_2}{\lambda1}\right|^k\right))$. 说明: $u_k=Bv_{k-1}\approx Bx_1=\lambda_1x_1$, $\max(v_{k-1})\approx 1$, $m_k=\max(\lambda_1x_1)$, $u_k\approx\lambda_1x_1$, $\max(u_k)\approx\lambda_1\cdot 1=\lambda_1$

特殊情况

• $\lambda_1$ 是 $m$ 重根, 即 $|lambda_1|=\cdots=|lambda_m|&gt;|\lambda_{m+1}|\ge\cdots\ge|\lambda_n|\ge0$, $B$ 有 $n$ 个线性无关的特征向量, 则 $$v_k=\lambda_1^k\left[\alpha_1x_1+\cdots+\alpha_mx_m+\sum\limits_{i=m+1}^n\left(\frac{\lambda_i}{\lambda_1}\right)^k\alpha_ix_i\right]$$
• $\lambda_1=-\lambda_2$, 且 $|\lambda_1|&gt;|\lambda_3|$, 则 $$v_k=\lambda_1^k\left[\alpha_1x_1+(-1)^k\alpha_2x_1+\sum\limits_{i=3}^n\left(\frac{\lambda_i}{\lambda_1}\right)^k\alpha_ix_i\right]$$ 因此 $v_k$ 是摆动的, 当 $k$ 足够大的时候, 有 $\left{\begin{array}{l}v_{2k+1}\approx\lambda_1^{2k+1}(\alpha_1x_1-\alpha_2x_2) \ v_{2k}\approx\lambda_1^{2k}(\alpha_1x_1+\alpha_2x_2)\end{array}\right.$, 因此 $\lambda_{1,2}\approx\sqrt{\frac{(v_{k+2})i}{(v_k)i}}$, 进而$\left{\begin{array}{l}v{k+1}+\lambda_1v_k=2\lambda_1^{k+1}\alpha_1x_1 \ v{k+1}-\lambda_1v_k=2\lambda^{k+1}(-1)^{k+1}\alpha_2x_2\end{array}\right.$
• 求最小特征值和特征向量: 反幂法, 用 $B^{-1}$
• 求第 k 个, 求出第 $k-1$ 个后减去之类的方法.