4.1 幂迭代法

幂迭代法是计算特征值和特征向量的一种简单易用的算法。幂迭代法虽然简单，但它却建立了计算特征值和特征向量的算法的一个基本框架。

4.1.1 算法介绍

任意给定一个非零向量 $x^{(0)}$ ，不断用 $A$ 左乘该向量，得到向量序列：

在一定条件下, 可以证明该向量序列收敛到模最大特征值 $\lambda_{1}$ 所对应的特征向量, 然后通过计算 Rayleigh 商 (Rayleigh 商的定义见 (5.10)) 就可以得到 $\lambda_{1}$ . 这就是幂迭代法, 算法描述如下, 为了防止溢出, 每次计算后对向量进行单位化处理.

算法4.1.幂迭代法 (PowerIteration)

1: Choose an initial guess $x^{(0)}$ with $\| x^{(0)}\|_2 = 1$
2: set $k = 0$
3: while not convergence do
4: $y^{(k + 1)} = Ax^{(k)}$

5: $x^{(k + 1)} = y^{(k + 1)} / \| y^{(k + 1)}\| _2$ $\%$ 单位化, 防止溢出
6: $\mu_{k+1} = (Ax^{(k+1)}, x^{(k+1)})$ $\%$ 计算 Rayleigh 商
7: $k = k + 1$
8: end while

4.1.2 收敛性分析

下面讨论幂迭代法的收敛性. 我们假定

(1) $A \in \mathbb{R}^{n \times n}$ 是可对角化的, 即 $A = V\Lambda V^{-1}$ , 其中 $\Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n) \in \mathbb{C}^{n \times n}, V = [v_1, v_2, \ldots, v_n] \in \mathbb{C}^{n \times n}$ , 且 $\|v_i\|_2 = 1, i = 1, 2, \ldots, n$ .
(2) $|\lambda_1| > |\lambda_2| \geq |\lambda_3| \geq \dots \geq |\lambda_n|$ .

由于 $V \in \mathbb{C}^{n \times n}$ 非奇异, 所以它的列向量组构成 $\mathbb{C}^n$ 的一组基. 因此迭代初始向量 $x^{(0)}$ 可表示为

我们假定 $\alpha_{1} \neq 0$ ，即 $x^{(0)}$ 不属于 $\operatorname{span}\{v_{2}, v_{3}, \ldots, v_{n}\}$ （由于 $x^{(0)}$ 是随机选取的，从概率意义上讲，这个假设通常是成立的）。于是我们可得

又 $|\lambda_i / \lambda_1| < 1, i = 2,3,\ldots ,n,$ 所以

故当 $k$ 趋向于无穷大时，向量

收敛到 $e_1 = [1,0,\dots ,0]^{\mathsf{T}}$ .所以向量 $x^{(k)} = A^k x^{(0)} / \| A^k x^{(0)}\| _2$ 收敛到 $\pm v_{1}$ ，即 $A$ 的对应于(模)最大的特征值 $\lambda_{1}$ 的特征向量.而 $\mu_k = \left(Ax^{(k)},x^{(k)}\right)$ 则收敛到 $v_{1}^{*}Av_{1} = \lambda_{1}$

显然，幂迭代的收敛快慢取决于 $|\lambda_2 / \lambda_1|$ 的大小， $|\lambda_2 / \lambda_1|$ 越小，收敛越快

结论

(1) $x^{(k)}$ 收敛到 $\pm v_{1}$ ; (2) $\mu_{k}$ 收敛到 $\lambda_{1}$ ; (3) $|\lambda_2 / \lambda_1|$ 越小, 收敛越快.

通过上面的分析可知, 幂迭代只能用于计算矩阵的模最大的特征值和其相应的特征向量. 如果 $A$ 的模最大的特征值是唯一的, 则称其为主特征值. 当 $\left|\lambda_{2} / \lambda_{1}\right|$ 接近于 1 时, 收敛速度会非常慢. 同时, 如果 $A$ 的模最大特征值不唯一, 比如一对共轭复特征值, 则幂迭代就可能就会失效.

思考：如果 $A$ 不可以对角化，则能否得到类似的结论？

如果需要计算其他特征值, 比如模第二大特征值 $\lambda_{2}$ , 则可以在模最大特征值 $\lambda_{1}$ 计算出来后, 采用收缩 (Deflation) 技术: 构造酉矩阵 $U$ , 使得

然后将幂迭代作用到 $A_{22}$ 上, 就可以求出 $\lambda_{2}$ . 以此类推, 可以依次求出所有特征值 (这里假定特征值互不相同).

思考：上面的收缩技术中的 $U$ 怎么选取？

4.1.3 位移策略

前面已经提到, 幂迭代法的收敛速度取决于 $|\lambda_2 / \lambda_1|$ 的大小. 当它的值接近于 1 时, 收敛速度会非常缓慢. 因此, 为了加快幂迭代法的收敛速度, 我们希望 $|\lambda_2 / \lambda_1|$ 的值越小越好.

一个简单易用的方法就是使用位移策略，即将计算 $A$ 的特征值转化为计算 $A - \sigma I$ 的特征值，即对 $A$ 做一个移位.这里 $\sigma$ 是一个给定的数,称 $\sigma$ 为位移 (shift).为了使得幂迭代作用到 $A - \sigma I$ 时具有更快的收敛速度,我们要求 $\sigma$ 满足下面的两个条件：

(1) $\lambda_{1} - \sigma$ 是 $A - \sigma I$ 的模最大的特征值;
(2) $\max_{2 \leq i \leq n} \left| \frac{\lambda_i - \sigma}{\lambda_1 - \sigma} \right|$ 尽可能地小.

其中第一个条件保证最后所求得的特征值是我们所要的，第二个条件用于加快幂迭代的收敛速度.

显然, 在实际应用中, $\sigma$ 的取值并不是一件容易的事.

例4.1 设 $A = X\Lambda X^{-1}$ , 其中 $\Lambda$ 为对角矩阵, 分别用幂迭代法和带位移的幂迭代法计算 $A$ 的主特征值. (见Eig_Power_shift.m)

位移策略在特征值计算中非常重要, 特别是在反迭代法和 QR 迭代法中.