隐式重启Arnoldi方法
  R. Lehoucq 和 D. Sorensen

或许是计算一般方阵A完整特征系统的最成功的数值算法是隐式移位QR算法。该方法成功的关键之一在于其与Schur分解的关系

A = U T U^{\ast}. \tag{7.11}

这一广为人知的分解断言，每个方阵A都与一个上三角矩阵T是酉相似的。

QR算法产生一系列酉相似变换，迭代地将A化为上三角形式（见第7.3节）。换句话说，它计算了一个Schur分解。QR算法的实际实现首先通过一个初始的酉相似变换将A化为紧凑形式V^{\ast} AV = H，其中H是上Hessenberg矩阵（“几乎上三角”），而V是酉矩阵。然后执行以下迭代。

SHIFTED QR METHOD
分解V^{\ast} AV = H
对j=1,2,3\ldots，直至收敛
选择一个移位\mu
QR分解QR = H - \mu I
H := Q^{\ast} H Q
V := VQ
结束循环

在此方案中，Q是酉矩阵，R是上三角矩阵（即H-\mu I的QR分解）。显然，H在整个迭代过程中与A是酉相似的。迭代继续进行，直到H的次对角元素收敛到零，即直到获得了一个（近似的）Schur分解。

如果U_k表示U的前k列，T_k表示公式(7.11)中T的前k \times k主子矩阵，那么

A U_k = U_k T_k,

我们称其为A的部分Schur分解。 由于存在一个Schur分解，使得A的特征值按任意给定顺序出现在对角线上，因此总是存在一个A的部分Schur分解，使得T_k的对角元素由A的任意指定子集的k个特征值组成。此外，\mathrm{span}(U_k)是这些特征值对应的A的不变子空间。

我们将利用Schur分解的这一特性。我们还将利用QR迭代的一个变体，该变体能够在迭代过程中迫使感兴趣的特征值出现在T的前k \times k块中。我们的目标是开发一种QR方法的截断形式，适合于计算大型矩阵A的选定k个特征值。我们称隐式重启Arnoldi方法为IRAM。