06 幂法、反迭代与 Rayleigh 商迭代

1. 幂法提取主导方向

设 $A$ 可对角化，且

$$|{\lambda }_1|>|{\lambda }_2|\ge \cdots .$$

若初始向量在 $x_1$ 方向分量非零，则

$$A^k{v}_0={\lambda }_1^k(c_1{x}_1+\sum _{j>1}{c}_j({\lambda }_j/{\lambda }_1{)}^k{x}_j).$$

归一化迭代

$$v_{k+1}=\frac{A{v}_k}{\parallel A{v}_k{\parallel }_2}$$

以约 $|{\lambda }_2/{\lambda }_1|$ 的线性速率趋向主特征向量。特征值可用 Rayleigh 商

$$\rho (v)=\frac{v^{\ast }Av}{v^{\ast }v}$$

估计。

2. 反迭代与位移

对 $(A-\mu I{)}^{-1}$ 使用幂法，就会突出距离 $\mu$ 最近的特征值：

$$(A-\mu I)y_k=v_k,v_{k+1}=y_k/\parallel y_k{\parallel }_2.$$

实现时只分解一次 $A-\mu I$，每步做三角求解；不要显式求逆。

位移越靠近目标特征值，谱间隔越有利，但线性系统越病态。这里“病态”并不必然破坏方向收敛，因为求解误差常沿目标特征向量被放大。

3. Rayleigh 商迭代

令位移随当前向量更新：

$${\mu }_k=\rho (v_k),(A-{\mu }_{k}I)y_k=v_k,v_{k+1}=y_k/\parallel y_k\parallel .$$

对 Hermite 矩阵，在简单特征值附近通常具有三次局部收敛。代价是每一步位移变化，不能直接复用同一个分解。

4. 残差与停止准则

近似特征对 $(\hat{\lambda },\hat{x})$ 的残差为

$$r=A\hat{x}-\hat{\lambda }\hat{x}.$$

若 $\parallel \hat{x}\parallel =1$，则存在扰动 $E$ 满足

$$(A+E)\hat{x}=\hat{\lambda }\hat{x},\parallel E{\parallel }_2\le \parallel r{\parallel }_2.$$

Hermite 情形还可保证某个真实特征值 $\lambda$ 满足

$$|\lambda -\hat{\lambda }|\le \parallel r{\parallel }_2.$$

因此残差是自然的后向误差指标。

5. 子空间迭代

若需要一组主导特征向量，把向量推广为块矩阵：

$$Y_k=A{Q}_k,Y_k=Q_{k+1}{R}_{k+1}.$$

$Q_k$ 逐步逼近主导不变子空间，再在小矩阵

$$Q_k^{\ast }A{Q}_k$$

上求特征对。这是 Rayleigh-Ritz 思想的早期形式，也是 QR 算法和现代块迭代的桥梁。

6. 幂法的失效情形与改进

幂法并非总能给出一个固定方向：

• 若 $|{\lambda }_1|=|{\lambda }_2|$，主导分量之间不会相对衰减；
• 若初始向量恰好与主左特征向量正交，则主分量为零；
• 非正规矩阵的特征向量基可能病态，短期行为不一定由特征值模简单解释；
• 主导特征值是一对共轭复数时，实向量常在二维不变子空间内旋转。

可通过块幂法同时跟踪一个子空间，或用位移和多项式滤波放大目标谱区间。若已知一个右、左特征对，还可做 Hotelling 型亏损，但非正交亏损容易累积误差；正交 Schur 向量通常更稳。

7. 子空间迭代的收敛率

设目标是前 $p$ 个模最大的特征值，且

$$|{\lambda }_p|>|{\lambda }_{p+1}|.$$

理想情况下，子空间夹角按 $|{\lambda }_{p+1}/{\lambda }_p{|}^k$ 衰减。这里决定速度的是目标子空间与外部谱之间的 gap，而不是目标内部特征值彼此是否靠近。因而成簇特征值常适合用块方法整体求取。

每轮 QR 不是为了改变子空间，而是为了防止所有列都塌缩到最强的单一方向。随后对 $Q_k^{\ast }A{Q}_k$ 做 Rayleigh-Ritz，可在相同子空间中选出更好的向量组合。

8. Rayleigh-Ritz 与残差公式

若

$$Q^{\ast }AQy=\theta y,u=Qy,$$

则 Ritz 残差满足

$$Q^{\ast }(Au-\theta u)=0.$$

即残差正交于试探空间。对 Hermite $A$，Rayleigh 商具有驻点性质：若 $u=x+e$ 且 $e\perp x$，则特征向量误差为一阶时，特征值误差通常为二阶。这解释了为什么特征值常比特征向量更早达到高精度。

9. 广义特征值与位移反迭代

对

$$Ax=\lambda Bx,$$

位移反迭代求解

$$(A-\mu B)y_k=B{x}_k,x_{k+1}=y_k/\parallel y_k\parallel .$$

若 $A=A^{\ast }$ 且 $B=B^{\ast }\succ 0$，应使用 $B$-内积 $⟨x,y{⟩}_B=y^{\ast }Bx$ 做归一化和正交化。也可先 Cholesky 分解 $B=L{L}^{\ast }$，把问题化为标准 Hermite 特征值问题

$$L^{-1}A{L}^{-\ast }z=\lambda z,x=L^{-\ast }z.$$

10. 实现与停止准则

只看 Rayleigh 商变化可能过早停止。更稳健的相对残差是

$$\eta =\frac{\parallel Ax-\theta x{\parallel }_2}{(\parallel A{\parallel }_2+|\theta |)\parallel x{\parallel }_2}.$$

块方法还应监控 $\parallel Q^{\ast }Q-I\parallel$。若某些 Ritz 对已收敛，可锁定并从活动子空间移除；软锁定保留它们参与投影，硬锁定则不再更新，后者更省成本但要维护正交性。

11. 自检

• [ ] 能由谱展开推导幂法收敛因子。
• [ ] 知道反迭代为何只需一次分解、多次求解。
• [ ] 能写出 Rayleigh 商迭代并说明适用矩阵。
• [ ] 会用特征残差设计停止准则。
• [ ] 能解释块方法为何不受目标簇内部小间隔的同样限制。
• [ ] 会把 Hermite 正定广义特征值问题化为标准问题。

下一章：Hessenberg 化与 QR 算法。