算法

厄米矩阵 A 的带状 Lanczos 算法的完整陈述如下。

接下来，我们将更详细地讨论算法4.12的一些步骤。

(4)

通常，是否需要对 \hat{v}_j 进行收缩的决策应基于检查是否

\Vert\hat{v}_j\Vert_2 \leq {\tt dtol}, \tag{4.42}

其中 {\tt dtol} 是一个适当选择的收缩容差。如果满足(4.42)，则对向量 \hat{v}_j 进行收缩。在这种情况下，如果 j-p_c 为正，则将其添加到包含 T_j^{\rm {(d)}} 中非零行索引的集合 {\mathcal I} 中，并将当前块大小更新为 p_c=p_c-1。如果 p_c=0，则块 Krylov 序列(4.27)耗尽，算法自然终止。如果 p_c>0，则删除向量 \hat{v_j}，将其余候选向量 \hat{v}_{k+1} 的索引 k+1 重置为 k，最后，算法返回到步骤(3)。如果不满足(4.42)，则不需要收缩，算法继续进行步骤(5)。

通常，在(4.42)中，会选择一个小的容差 {\tt dtol}，例如机器精度的平方根。然而，{\tt dtol} 不一定很小；算法4.12及其性质对于任何 {\tt dtol} 的选择仍然正确。请注意，如果在(4.42)中设置 {\tt dtol}=0，则算法仅进行精确收缩。

(5)

向量 \hat{v}_j 已通过收缩检查，现在被归一化为下一个 Lanczos 向量 v_j。归一化使得

\left\Vert v_j \right\Vert _2 = 1\quad \text{for all}\quad j.

(6)

其余的候选向量， \hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+p_c-1}，与最新的 Lanczos 向量 v_j 进行显式正交化。请注意，在前 p 步中，某些 t_{j,k-p_c} 将具有非正列索引。它们用于使起始基正交，但不需要存储在 T_j 矩阵中。

(7)

通过计算一个新的候选向量 \hat{v}_{j+p_c}，作为最新 Lanczos 向量 v_j 的 A 倍数，推进块 Krylov 序列。

(8)

向量 \hat{v}_{j+p_c} 与先前的 Lanczos 向量 v_{k_0}, v_{k_0+1}, \ldots, v_{j-1} 进行正交化，其中 k_0=\max\{1,j-p_c\}。这里，我们利用了矩阵 T_j^{(\rm pr)} 是厄米的特性，因此我们不显式计算 t_{kj}，而是设置 t_{kj} = \overline{t_{jk}}。请注意，t_{jk} 在步骤(6)中已显式计算。

(9)

向量 \hat{v}_{j+p_c} 与 Lanczos 向量 v_k，k\in {\mathcal I}，以及 v_j 进行显式正交化。请注意，使用改进的 Gram-Schmidt 方法进行此正交化。

(11)

现在已计算出第 j 行和第 j 列中的所有非零元素，并将它们添加到前一次迭代 j-1 的矩阵 T_{j-1}^{(\rm pr)} 中，以产生当前矩阵 T_{j}^{(\rm pr)}。这里，我们约定在算法4.12中未显式定义的条目 t_{ik} 和 s_{ik} 设置为零。

(12)

为了测试收敛性，计算厄米矩阵 T_j^{\rm {(pr)}} 的特征值 \theta_i^{(j)}，i=1,2,\ldots,j，如果某些 \theta_i^{(j)} 是 A 的期望特征值的良好近似，则停止算法。