选择重新正交化

读者可参考Simon[402]的详细讨论。证明指出，如果通过具有半正交基 $V_j$ 的Lanczos算法计算三对角矩阵 $T$，那么 $T$ 是 $A$ 在计算基 $V_j$ 所张成子空间上的完全精确投影。

确保计算基半正交的一种方法是使用Paige推导的递归关系，监测早期步骤中正交性的损失如何传播到后续步骤，并在递归关系指示超过 $\sqrt{\epsilon_M}$ 阈值时进行再正交化。该递归关系涉及乘积矩阵 $W_{j}$ 的连续元素 $\omega_{j,k}$，并从基本递归关系推导得出。

首先注意到计算向量 $v_{j+1}$ 满足基本递归关系：

我们使用此递归关系逐行填充对称矩阵 $W$ 的下半三角部分。对角元素 $\omega_{k,k}=1$ 和紧邻对角线上下的元素 $\omega_{k-1,k}=\omega_{k,k-1}=O(\epsilon_M)$ 在舍入误差水平上，由于对称性和显式正交化。这为递归关系提供了初始值。我们估计最后两项的绝对值之和为 $2\epsilon_M\Vert A\Vert$，并将其输入递归关系，选择符号以最大化新的 $\vert\omega_{j+1,k}\vert$。

一旦某个元素 $\omega_{j+1,k}$ 超过 $\sqrt{\epsilon_M}$ 阈值，我们就将当前向量 $v_{j}$ 和 $v_{j+1}$ 对所有先前的向量 $v_k\,,\, k=1,\dots,j$ 进行正交化，并将相应的 $\omega_{j,k}$ 和 $\omega_{j+1,k}$ 降至舍入误差水平。由于Lanczos方法中的三项递归关系，我们需要正交化两个向量。存储矩阵 $W$ 的 $\omega$ 估计值时，仅需存储最新的两行 $j-1$ 和 $j$。

上述技术之一在[402]中描述。另一种方法仅对那些 $\omega_{j+1,k}$ 超过阈值的向量 $v_k$ 进行显式正交化。Simon[402]称之为部分再正交化，而这里描述的周期性再正交化，由Grcar[204]首次描述，实现更简单，并能使用Level 2 BLAS操作。