算法

我们得到以下算法。

算法 4.6 HEP的Lanczos方法
(1)  取初始猜测向量 r = v
(2)  \beta_0 = \Vert r \Vert_2
(3)  for j = 1,2,..., until convergence
(4)    v_j = r/\beta_{j-1}
(5)    r = A v_j
(6)    r = r - v_{j-1}\beta_{j-1}
(7)    \alpha_j = v_j^\ast r
(8)    r = r - v_j \alpha_j
(9)    如果需要，进行正交化
(10)   \beta_j = \Vert r \Vert_2
(11)   计算近似特征值 T_j = S \Theta^{(j)}S^\ast
(12)   测试是否收敛
(13) end for
(14) 计算近似特征向量 X = V_j S

让我们对算法4.6的一些步骤进行评论：

(1)

如果对所需的特征向量有一个好的猜测，可以用它作为初始值。例如，对于离散化的偏微分方程，如果已知所需的特征向量在网格上是平滑的，可以从全为1的向量开始。在其他情况下，选择一个随机值，例如由正态分布的随机数组成的向量。

(5)

这种矩阵-向量运算通常是CPU占主导的工作。任何执行矩阵-向量乘法的例程都可以使用。在位移-逆情况下，用分解矩阵求解系统。目前，在位移-逆情况下使用迭代方程求解器的经验还不多。

(9)

在有限精度计算中，一旦一个特征值收敛，正交性就会丧失。 重新正交化的选择有：

1. 完全正交化： 实现简单；参见下文第4.4.4节。随着j的增加，迭代所需的计算量会逐渐增加。在位移-逆情况下，当多个特征值在少数步骤j内收敛时，这是首选选择。

2. 选择性正交化： 最复杂的方案，适用于收敛缓慢且寻求多个特征值的情况。此选项也将在下文第4.4.4节中讨论。

3. 局部正交化： 用于巨大的矩阵，当难以存储整个基V_j时。我们确保v_{j+1}与v_{j-1}和v_j正交，通过对此两个向量进行额外的正交化，减去r=r-v_{j-1}(v_{j-1}^{\ast} r)和r=r-v_j(v_j^{\ast} r)一次。我们仍需使用Cullum装置检测并丢弃虚假的特征值近似；参见第4.4.4节。

(11)

对于每个步骤j，或在适当的间隔，计算三对角矩阵T_{j}的特征值\theta_i^{(j)}和特征向量s_i^{(j)}（参见第4.9节）。

如果期望快速收敛，如位移-逆问题，j将远小于n；那么这种计算非常快，推荐使用LAPACK等标准软件[12]。

如果直接对A应用Lanczos算法并计算大型三对角矩阵，有基于二分法和Givens递归的特殊三对角特征值算法；参见[356,358,128]和第4.2节。

(12)

当找到足够大的基V_j时，算法停止，使得三对角矩阵T_{j}的特征值\theta_i^{(j)}（参见第4.9节）对所寻求的A的特征值给出良好近似。

如果基V_j不完全正交，残差的估计\beta_{j,i}（参见第4.13节）可能过于乐观。那么Ritz向量x_i^{(j)}（参见第4.12节）的范数可能小于1，我们必须用以下估计替换（参见）：

\Vert r_i^{(j)}\Vert=\vert\beta_js_{i,j}^{(j)}\vert/\Vert V_js_i^{(j)}\Vert\;.

(14)

仅当步骤(12)中的测试表明特征向量已收敛时，才计算原始矩阵A的特征向量。然后使用基V_j进行矩阵-向量乘法以获得特征向量（参见第4.12节），

x_i^{(j)}=V_js_i^{(j)}\;,

对于每个标记为已收敛的i。

这类算法的一大优点是，矩阵A仅在算法4.6的步骤(5)中通过矩阵-向量运算被访问。任何类型的稀疏性和任何存储方案都可以利用。

只需保留三个向量r、v_j和v_{j-1}，随时可用；较早的向量可以留在后备存储中。甚至有一种变体只需要两个向量（参见[353, 第13.1章]），但编码它需要一些技巧。除了矩阵-向量乘法外，只需要内积和向量的倍数相加。我们推荐使用Level 1 BLAS例程；参见第10.2节。