收缩与停止规则

收缩是QR迭代实际应用中的一个重要概念，因此对IRLM同样至关重要。在QR迭代的背景下，收缩意味着将三对角矩阵T的一个小次对角元素（及其相应的超对角元素）置零。之所以称为收缩，是因为它将三对角矩阵分割成两个更小的子问题，这两个子问题可以独立地进一步细化。

然而，在IRLM的背景下，常规的QR收缩技术并不总是适用。需要针对隐式重启的特定收缩能力。通常希望在较粗略的精度水平\epsilon_D上进行收缩，其中1 > \epsilon_D > \epsilon_M，\epsilon_M是机器精度。理论上（即在精确算术中），当A具有多个特征值时，IRLM不可能计算出多个特征向量。这是因为IRLM是一种“单向量”方法，而不是块方法。但在实践中，计算多个特征值通常没有困难，因为随着收敛的进行，方法会自我收缩，并且舍入误差通常会在后续的初始向量中引入新的特征向量方向的成分。尽管如此，这种方法可能不可靠，并且可能遗漏多个特征值。无论如何，这种方法通常需要严格的收敛容差，以便找到所有多个特征值的实例。

更有效的方法是在近似特征值收敛到一定精度水平后进行收缩（即锁定），并强制后续的Lanczos向量与已收敛的子空间正交。通过这种能力，可以以相同的指定精度计算多个特征值的附加实例，而无需强制它们收敛到不必要的精度。

在Lanczos过程中，与QR迭代一样，隐式重启过程中可能会使前k个次对角元素变小。然而，通常情况下，在次对角元素变小之前，T的谱中会出现已经收敛的Ritz值。这种收敛通常通过观察T的特征向量y的最后一个小分量来检测。当这种情况发生时，我们能够构造T的正交相似变换，这将给出具有轻微扰动的T的等效Lanczos分解，确实具有零次对角元素，这是我们收缩方案的基础。

在IRLM的背景下，需要两种类型的收缩：

锁定：

如果一个Ritz值\theta已经收敛（意味着\Vert Ax - x\theta\Vert < \epsilon_D）并且被认为是所需特征值集合的成员，我们希望宣布它收敛，解耦特征对(x, \theta)，并继续计算剩余的特征值，不再对x或\theta进行任何更改。这个过程称为锁定。

清除：

如果一个Ritz值\theta已经收敛但不是所需集合的成员，我们希望解耦并从由Lanczos向量张成的当前Krylov子空间中移除特征对(x, \theta)。这个过程称为清除。

这种收缩技术最初在[289,294]中开发。我们在这里介绍的方案基于[420]中开发的改进。该方案允许稳定且高效地收缩（或锁定）已经以指定相对精度\epsilon_D收敛的Ritz值，该精度可能远大于机器精度\epsilon_M。在没有SI加速收敛的情况下，这一点尤为重要。在这种设置中，矩阵-向量乘积的数量通常会很大，因此以低容差锁定收敛的Ritz值将非常可取。这将避免为了达到允许正常QR类型收缩的精度而需要进行的矩阵-向量乘积的开销。此外，能够清除已收敛但不想要的Ritz值也很重要。正如[289]中所指出的，Parlett和Le在[359]中发现的QR波峰追逐过程的前向不稳定性将阻止隐式重启用于清除已收敛的不想要Ritz值。