收缩与停止规则

收缩是QR迭代实际应用中的一个重要概念，因此对IRAM（隐式重启Arnoldi方法）同样至关重要。在QR迭代的背景下，收缩意味着将海森堡矩阵H的一个小次对角元素置零。之所以称为收缩，是因为这会将海森堡矩阵分割成两个更小的子问题，这两个子问题可以独立地进一步细化。

然而，在IRAM的背景下，传统的QR收缩技术并不总是适用。需要针对隐式重启的额外收缩功能。通常希望在精度水平\epsilon_D处进行收缩，其中1 > \epsilon_D > \epsilon_M，\epsilon_M是机器精度。理论上（即在精确算术中），当A具有对应于不同特征向量的多重特征值时，IRAM不可能计算出该多重性的多个实例，因为它是一种“单向量”方法，而非块方法。然而，在实践中，通常在收敛过程中方法会自行收缩，且舍入误差通常会在后续起始向量中引入新特征向量方向的分量，因此计算多重特征值通常没有太大困难。尽管如此，这种方法可能不可靠，可能会遗漏多重特征值。无论如何，这种方法通常需要严格的收敛容差才能成功找到多重特征值的所有实例。更有效的方法是，一旦近似特征值收敛到一定精度水平，就进行收缩（即锁定），然后强制后续的Arnoldi向量与收敛的子空间正交。通过这一功能，可以以相同的指定精度计算多重特征值的额外实例，而无需将它们收敛到不必要的过高精度。

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

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

锁定：

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

清除：

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

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