幂法

最简单的特征值问题就是计算主要特征值及其对应的特征向量。 算法 4.1 中介绍的 幂法 是解决这一任务的最简单的迭代方法。在适度的假设下，它能够找到矩阵 A 的最大绝对值的特征值及其对应的特征向量。

算法 4.1: HEP的幂法
(1) 取初始猜测向量 y = z，
(2) for k = 1, 2, ...
(3)   v = y / \Vert y \Vert_2,
(4)   y = Av,
(5)   \theta = v^\ast y,
(6)   若 \Vert y-\theta v\Vert_2 \le \epsilon_M \vert\theta\vert, 结束
(7) end for
(8) 结果： \lambda = \theta, \; x = v

设 x_1 是与 \lambda_1=\lambda_{\max}(A) 对应的特征向量。x_1 和 z 之间的 夹角 \angle(z,x_1) 定义如下：

\cos \angle(z,x_1)= \frac{z^{\ast} \, x_1}{\left\Vert z\right\Vert _2 \, \Vert x_1\Vert _2} .

如果初始向量 z 和特征向量 x_1 相互垂直，那么 \cos\angle(z,x_1) = 0。在这种情况下，幂法在精确算术中不会收敛。 另一方面，如果 \cos \angle(z,x_1)\not=0，幂法会产生一系列向量，这些向量会越来越平行于 x_1。如果随机选择 z，两者不垂直的条件在极高概率下是成立的。

幂法的收敛速度取决于 \vert \lambda_2 / \lambda_1\vert，其中 \lambda_2 是 A 的绝对值第二大的特征值。 这个比值通常小于 1，从而实现适当的收敛。但也存在比值非常接近 1 的情况，导致非常缓慢的收敛。关于幂法的详细讨论，请参见 Demmel [114, Chap. 4]，Golub 和 Van Loan [198]，以及 Parlett [353]。