幂迭代

形式陈述 ​

给定矩阵或线性算子 $A$、非零初值 $x_0$、容差和最大迭代数，先令 $\Vert x_0{\Vert }_2=1$，再反复计算

$$y_{k+1}=A{x}_k,x_{k+1}=\frac{y_{k+1}}{\Vert y_{k+1}{\Vert }_2}.$$

若 $\Vert y_{k+1}{\Vert }_2=0$，当前轨道已进入 $A$ 的核，算法不能继续归一化。特征值用 Rayleigh 商估计：

$${\theta }_k=\frac{x_k^{\ast }A{x}_k}{x_k^{\ast }{x}_k};$$

当 $x_k$ 已归一化时，分母为 $1$。每步只需一次矩阵—向量乘法和向量归一化；稠密矩阵成本为 $\mathrm{\Theta }(n^2)$，稀疏矩阵为 $\mathrm{\Theta }(\mathrm{nnz}(A))$，额外存储为若干向量。算法不会也不应显式形成 $A^k$。

最清楚的收敛结论假设 $A$ 可对角化，特征值按模排序为

$$|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|,$$

且初值在主特征向量公理库特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。 $v_1$ 上的分量非零。写成 $x_0=\sum _i{c}_i{v}_i$ 后，

$$A^k{x}_0={\lambda }_1^k(c_1{v}_1+\sum _{i\ge 2}{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i),$$

所以归一化方向以渐近因子 $|{\lambda }_2/{\lambda }_1|$ 线性收敛。严格分离的是特征值的模，不是实部、实数大小或代数排序；若 $c_1=0$，主方向从轨道中永久缺席。

当 ${\lambda }_1<0$ 时，归一化向量会在 $v_1$ 与 $-v_1$ 之间交替；复数主特征值则每步累积相位 ${\lambda }_1/|{\lambda }_1|$。因此方向误差应在符号或相位对齐后比较，或直接考察投影与残差，而不能只用 $\Vert x_{k+1}-x_k\Vert$。常用完成准则为

$$r_k=A{x}_k-{\theta }_k{x}_k,\Vert r_k{\Vert }_2\le \mathrm{atol}+\mathrm{rtol}\Vert A{\Vert }_2,$$

并同时检查相位对齐后的方向变化、零向量、非有限值与迭代上限。小残差到特征向量误差的转换仍需要谱分离和特征向量条件性。

直觉 ​

幂迭代像反复拉伸一团由多个特征方向组成的材料。第 $i$ 个方向经过 $k$ 步后乘上 ${\lambda }_i^k$；只要某个模严格最大且初值确实含有该方向，其他分量相对于它就按比值的幂衰减。每步归一化只防止数值溢出或下溢，不改变方向竞争。

谱隙决定速度。$|{\lambda }_2/{\lambda }_1|$ 很小时，主方向很快显露；比值接近 $1$ 时，归一化后的向量看似稳定变化，却要很多步才能真正分离。算法便宜的每一步并不能弥补不存在的谱隙。

例子与边界 ​

取

$$A=\mathrm{diag}(5,2,1),x_0=\frac{1}{\sqrt{3}}(1,1,1{)}^{\mathsf{T}}.$$

令 ${\eta }_k=\sqrt{x_{k,2}^2+x_{k,3}^2}/|x_{k,1}|$ 衡量非主方向相对第一分量的大小。实际迭代历史为：

$k$	Rayleigh 商 ${\theta }_k$	${\eta }_k$	$|A{x}_k-{\theta }_k{x}_k{|}_2$
0	2.666666667	1.414213562	1.699673171
1	4.466666667	0.447213595	1.203698006
2	4.919003115	0.164924225	0.492606017
3	4.987507967	0.064498062	0.193842689
4	4.998024979	0.025649951	0.077015546
5	4.999685051	0.010244999	0.030743428
6	4.999949653	0.004096500	0.012290460

${\eta }_{k+1}/{\eta }_k$ 逐渐趋向 $2/5=0.4$，正好对应次大模与主模之比；这是一条可复算的收敛历史，而不是只更换数字的示意。

若 $A=\mathrm{diag}(1,-1)$ 且初值两个分量都非零，两项模相同，轨道会在不同方向间振荡，无法选出唯一主方向。即使 $A=\mathrm{diag}(5,2)$ 有严格谱隙，取 $x_0=e_2$ 也永远看不见特征值 $5$，因为缺少主分量。

非正规矩阵还可能先出现很大的瞬态增长，特征向量基的病态性会把渐近阶段推得很晚。唯一主模特征值保证的是受适当假设约束的尾部行为，不承诺每一步单调靠近，也不让 Rayleigh 商自动成为可靠前向误差界。

推论与应用 ​

幂迭代是逆迭代、Rayleigh 商迭代和子空间迭代的基线：后续方法不是放弃“放大目标方向”，而是通过 shift-and-invert 改写谱，使想要的特征值成为新的主模。

它适合只求一个外端特征方向、矩阵—向量乘法便宜且谱隙明显的问题。若需要整个谱或稳定处理聚集特征值，QR 特征值算法把同样的正交迭代思想组织到 Schur 分解中，而不是逐个显式计算 $A^k$。

参考资料

• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lectures 27 and 28.
• Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §7.3.
• Y. Saad, Numerical Methods for Large Eigenvalue Problems, 2nd ed., SIAM, 2011, Ch. 4.