子空间迭代法

子空间迭代法，又称同时迭代法，最初是为厄米特征值问题（HEP）设计的，同样可以推广到非厄米特征值问题（NHEP）。算法7.2是基于第4.3.4节中针对HEP的子空间迭代法的改进版本，它包含了用于计算n_{\mathrm{ev}}个主特征值的缩减（锁定）步骤。由于NHEP的特征值可能非常病态，因此我们采用了更为严格的收敛标准。

算法 7.2：用于NHEP的带投影和消去的子空间迭代
(1)  对起始向量 Z 进行QR分解，得到 VR := Z
(2)  当 j \leq nev 时执行循环
(3)      计算 \widehat{Y} := [v_1, v_2, \ldots, v_{j-1}, A^{iter} V]
(4)      将 Y 的列（从 j 开始）正交归一化到 V 中。
(5)      计算 \Theta := V^* A V 并得到 Schur 分解 \Theta = Q \Lambda Q^*，其中近乎等模的特征值被分组在 A 的对角块中。
(6)      对于 A 中的每个对角块 A_k，k = 1, 2, \ldots 执行循环
(7)          让 Q_k 是 Q 中对应的列
(8)          如果 \| A(V Q_k) - (V Q_k) A_k \| \leq \text{eth} 则
(9)              将 V Q_k 添加到 [v_1, v_2, \ldots, v_{j-1}]
(10)             设置 j = j + V Q_k 的列数
(11)         否则
(12)             跳出循环
(13)         结束如果
(14)     结束循环
(15)     选择一个新的迭代参数 iter
(16) 结束循环

下面我们将介绍一些具体的实现细节。

(1)

初始矩阵V的构建应使其在感兴趣的特征向量方向上占优，以加速收敛。若事先不了解相关信息，随机矩阵也是一个不错的选择。

(3)

迭代参数iter的引入旨在尽可能减少正交化计算的开销。然而，iter值不宜过大，以免在计算矩阵\widehat{Y}时损失数值精度，导致部分特征值计算不准确。通常iter的取值范围为3到5。

(6)-(13)

上述算法中的收敛标准仅针对具有相近模数的特征值组进行检查。步骤(6)中的对角块从上至下排序，其中第一个块位于\Lambda的顶部。在步骤(12)中，一旦\Lambda中的第一个特征值块未能收敛，则停止测试。

(16)

迭代参数iter的选择应在保持合理数值精度的同时，尽可能降低正交化成本。

若希望求解接近某个位移\sigma的特征值，并且A - \sigma \, I的分解易于获得，则可将上述算法应用于\left(A - \sigma \, I\right)^{-1}。接近\sigma的特征值将更快收敛。

此外，通过用多项式T_{iter} [ (A - \sigma I) / \rho ] 替换幂A^{iter}，可以利用多项式加速来加快计算速度，其中T_{iter}是第一类切比雪夫多项式，\rho是A的谱半径的估计值。

本节内容大量参考了Bai和Stewart[37]以及Saad[387]的研究。关于子空间迭代的进一步讨论，读者可参阅Wilkinson[457]和Stewart[422]的著作。