GEMV形式的Lanczos方法

在算法4.7每次重启时，我们拥有一个 k步的Lanczos分解

AV_k = V_k T_k + r_k e_k^{\ast}

或者，对于k=0，有一个初始向量r_0。 算法4.8提供了一个模板，用于应用p个额外的 Lanczos步骤将其扩展为一个m步的Lanczos分解

AV_m = V_m T_m + r_m e_m^{\ast}.

算法 4.8：m 步Lanczos分解
(1)  开始于 r = r_k （之前的剩余向量或初始向量），令 \beta_k = \Vert r_k \Vert
(2)  for j = k+1,...,m
(3)      v_j = r/\beta_{j-1}
(4)      r = Av_j - v_{j-1}\beta_{j-1}
(5)      \alpha_j = v^\ast_j r
(6)      r = r - v_j\alpha_j
(7)      if \Vert r \Vert_2 \lt \rho \sqrt{\alpha_j^2 + \beta^2_{j-1}}
(8)          s = V_j^\ast r
(9)          r = r - V_j s
(10)         \alpha_j = \alpha_j + s_j, \; \beta_j = \beta_j + s_{j-1}
(11)     end if
(12) end for

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

(2)

如果从头开始(k=0)，取r_0=v作为初始向量。 理想情况下，为了计算特征值，应尝试构建一个在感兴趣的特征向量方向上占优势的v。 在没有其他考虑的情况下，随机向量是一个合理的选择。

(3)

将r归一化以获得新的基向量v_{j}。 范数 \beta_{j-1} = \Vert r \Vert 已经在步骤(7)中为前一个j计算过了。

(5)

这是Lanczos三项递归步骤，用于使r相对于V_j的两个最新列正交化。 它以改进的格拉姆-施密特形式组织。

(7)

此if子句中的语句序列确保新的残差方向r在数值上与先前计算的方向正交，即与V_{j}的所有列正交。 参数\rho必须指定（ 0 \le \rho < \infty）。 此测试询问的问题是：“r = Av_{j}是否接近已经构建的空间？” 比率 \Vert r\Vert/ \sqrt{ \alpha_{j}^2 + \beta_{j-1}^2 } = \tan \theta， 其中\theta是向量r与V_{j}的值域空间之间的夹角。 \rho的值越大，正交性要求越严格。 当\rho = 0时，算法恢复为没有再正交化的标准Lanczos过程。 这种修正的一个步骤可能不够，应该作为一个迭代实现，后续修正的测试为 \Vert r\Vert < \rho \Vert s \Vert； 参见[96]中的讨论。 如果在固定次数的尝试后（例如五次）没有生成合适的r，则应将\beta_{j}设为零，并随机生成一个向量，该向量与基V_j正交，并替换r以继续分解。 我们建议设置\rho = 1。

众所周知，经典的Lanczos三项方案在 Ritz 值（近似特征值）收敛到 A 的特征值时，将无法精确生成正交向量。 为了解决这个问题，我们引入了一种迭代细化技术，该技术以非常合理的成本保持正交性至完全工作精度。 隐式重启的特殊情况使得这种修改对于获得准确的特征值和数值上正交的特征向量至关重要。 如果数值正交性没有保持，隐式重启机制的效果将降低，甚至可能失败。