隐式重启

Lanczos或Arnoldi过程的一个不幸方面是，无法提前确定需要多少步才能在指定精度内确定感兴趣的特征值。通过这一过程获得的特征信息完全取决于初始向量v_1的选择。除非v_1的选择非常幸运，否则感兴趣的特征信息可能要等到k变得非常大时才会出现。显然，保持V_k的数值正交性变得难以处理。需要大量的存储空间，并且反复求解H_k的特征系统也会变得昂贵，成本为O(k^3)次浮点运算。

控制这一成本的明显需求促使了重启方案的发展。重启意味着用一个“改进的”初始向量v_1^+替换初始向量v_1，然后使用新向量计算一个新的Arnoldi分解。f_k的结构起到了指导作用：我们的目标是通过迭代迫使v_1成为感兴趣的特征向量的线性组合。理论上，如果v_1是A的k个特征向量的非平凡线性组合，f_k将消失。然而，一个更普遍且实际上更好的数值策略是迫使初始向量成为跨越所需不变子空间的Schur向量的线性组合。

重启的需求在Karush[258]早期就已被认识到，不久之后Lanczos[285]的原始算法出现。随后，Paige[347]、Cullum和Donath[89]以及Golub和Underwood[197]等人的发展。最近，基于Manteuffel[316]最初为线性系统迭代求解引入的多项式加速方案，Saad提出了一种用于特征值计算的重启方案。所有这些方案都是显式的，即通过某种过程产生一个新的初始向量，然后构建一个全新的Arnoldi分解。

还有一种重启方法提供了更高效且数值稳定的公式。这种方法称为隐式重启，是一种将隐式移位的QR方案与k步Arnoldi或Lanczos分解相结合的技术，以获得隐式移位QR迭代的截断形式。避免了通常与Arnoldi和Lanczos过程相关的数值困难和存储问题。该算法能够计算具有用户指定特征（如最大实部或最大幅值）的少数(k)个特征值，使用2nk + O(k^2)存储。计算出的所需k维特征空间的Schur基向量在数值上是正交的，达到工作精度。

隐式重启提供了一种从大型Krylov子空间中提取有趣信息的方法，同时避免了与标准方法相关的存储和数值困难。它通过不断将有趣信息压缩到固定大小的k维子空间中来实现这一点。这是通过隐式移位的QR机制完成的。一个长度为m = k+p的Arnoldi分解， A V_m = V_m H_m + f_m e_m^T， 被压缩为一个保留感兴趣特征信息的k长度的分解。这是通过使用QR步骤隐式应用p个移位来完成的。移位过程的第一阶段结果为 A V_m^+ = V_m^+ H_m^+ + f_m e_m^T Q， 其中V_m^+ = V_m Q，H_m^+ = Q^* H_m Q，且 Q = Q_1Q_2 \cdots Q_p。每个Q_j是移位\mu_j在移位QR算法中使用的正交矩阵。由于矩阵Q_j的海森堡结构，向量e_m^* Q的前k-1个条目为零。这意味着方程(7.13)中的前k列保持在Arnoldi关系中。将(7.13)两边的第一个k列等式化，提供了一个更新的k步Arnoldi分解 A V_k^+ = V_k^+ H_k^+ + f_k^+ e_k^T， 其更新后的残差形式为 f_k^+ = V_m^+ e_{k+1} \beta_k + f_m \sigma。 以此为起点，可以应用p个额外的Arnoldi步骤返回到原始的m步形式。

隐式重启的k步Arnoldi分解计算模板在算法7.7中给出。

算法 7.7：用于NHEP的IRAM
(1)  从 v_1 = \frac{v}{\|v\|} 开始
(2)  计算 m 步Arnoldi分解  A V_m = V_m H_m + f_m e_m^* 
(3)  重复直至收敛
(4)      计算 \sigma(H_m) 并选择 p 个移位 \mu_1, \mu_2, \ldots, \mu_p
(5)      Q = I_m
(6)      对于 j = 1, 2, \ldots, p
(7)          QR分解 Q_j R_j = H_m - \mu_j I
(8)          H_m := Q_j^* H_m Q_j
(9)          Q := Q Q_j
(10)     结束循环
(11)     \beta_k = H_m(k+1, k); \sigma_k = Q(m, k)
(12)     f_k := v_{k+1} \beta_k + f_m \sigma_k
(13)     V_k := V_m Q(:, 1: k); H_k := H_m(1: k, 1: k)
(14)     从 k 步Arnoldi分解开始
              AV_k = V_k H_k + f_k e_k^* 
             应用 p 个额外的Arnoldi步骤
             以获得新的 m 步Arnoldi分解
              A V_m = V_m H_m + f_m e_m^* 
(15) 结束重复

现在我们将描述一些实现细节，参考算法7.7中的相应阶段。

(1)

选择初始起始向量v，归一化并计算初始(m = k+p)步Arnoldi分解。理想情况下，对于特征值计算，应尝试构建一个在感兴趣的特征向量方向上占主导地位的v。如果有一系列密切相关的特征值问题，此向量应取自前一个问题的感兴趣的特征向量（或Schur向量）的线性组合。在没有其他考虑的情况下，随机向量是一个合理的选择。

(3)

Ritz对(x, \theta)被认为是“收敛的”，如果 \Vert f_k\Vert\vert e_k^*y\vert < \Vert H_k\Vert\epsilon_D 其中x = V_k y且\theta是“想要的”。收敛后，这一对应进行收缩。参见关于收缩的讨论，见第7.6.6节。

(4)

移位选择：移位\mu_j根据用户的“想要集”规范以及当前和可能过去的H_m的谱信息进行选择。一个成功的策略是将H_m的特征值排序为一个“想要集” \theta_1, \theta_2, \ldots, \theta_k和一个“不想要集” \mu_1, \mu_2, \ldots, \mu_p，并将后者作为选定的移位集。这被称为精确移位策略。其他策略将在下面讨论。

“想要集”规范的例子包括

具有最大实部的k个特征值，

具有最大幅值的k个特征值，

具有最小实部的k个特征值，

具有最小幅值的k个特征值。

(6)-(10)

使用移位\mu_1, \mu_2, \ldots, \mu_p对H_m应用p步移位QR迭代。这应使用隐式移位QR变体完成。如果使用精确移位， 那么\beta_k = H_m(k+1,k)应在p步QR完成后为零，且领先子矩阵H_m(1:k,1:k)应具有 \theta_1, \theta_2, \ldots, \theta_k作为其特征值。

(12)

当使用精确移位时，通常在有限精度下这些性质是近似正确的。然而，由于舍入误差，它们可能无法实现。因此，在更新残差向量时， f_k \leftarrow v_{k+1}\beta_k + f_m \sigma_k， 即使项 v_{k+1}\beta_k在精确算术中应为零，也包括两项是很重要的。请注意，使用精确移位，更新后的V_k和H_k将提供一个新的k步Arnoldi分解，其Ritz值和向量是迄今为止产生的最佳近似，符合用户规范。

(14)

这一步骤需要对先前讨论的Arnoldi分解进行轻微修改。它简单地从通常方案的第k步开始。

有许多方法可以选择QR步骤应用的移位\{\mu_j\}。几乎任何显式多项式重启方案都可以通过这种隐式机制应用。已经取得了相当成功的选择是精确移位。这种选择是通过将H_m的特征值排序为k个“想要”和p个“不想要”的特征值，并使用后者作为移位集。通过这种选择，p次移位应用结果是H_k^+具有k个想要的特征值作为其谱。

其他有趣的策略包括Chebyshev多项式的根[383]、调和Ritz值[331,337,349,411]、Leja多项式的根[23]、最小二乘多项式的根[384]和精细移位[244]。特别是，Leja和调和Ritz值已被用于估计 A 的内部特征值。