选择重新正交化

随着基的大小 j 增长，完全再正交化将需要大量的算术工作，我们寻求一种更经济的方案。可以证明，只要基是近正交（semiorthogonal）的，即正交到机器精度的二分之一，Lanczos算法的大多数期望性质都能保持。

W_{j}=V^{\ast}_jV_j=I_{j}+E\,, \quad \Vert E\Vert < \sqrt{\epsilon_M}\,.

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

T_{j}=N_j^{\ast} AN_j+G\,, \quad \Vert G\Vert = O(\epsilon_M\Vert A\Vert)\,.

这里 N_j 是 V_j 所张成子空间的一个正交基。即使 N_j 不显式已知，我们也知道 T_j 的特征值是 A 特征值的精确近似。

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

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

\beta_jv_{j+1}=Av_j-\alpha_j v_j - \beta_{j-1}v_{j-1}+f_j,

其中 f_j 是舍入误差向量。为得到乘积矩阵 W_{j} 的元素 \omega_{j,k}，我们用 v_k^{\ast} 预乘以上式：

\beta_j\omega_{j+1,k}=v_k^{\ast}Av_j-\alpha_j \omega_{j,k} - \beta_{j-1}\omega_{j-1,k}+v_k^{\ast}f_j\,.

交换 j 和 k 的乘积关系得到：

\beta_k\omega_{j,k+1}=v_j^{\ast}Av_k-\alpha_k \omega_{j,k} - \beta_{k-1}\omega_{j,k-1}+v_j^{\ast}f_k\,,

两式相减得到：

\beta_j\omega_{j+1,k}=\beta_k\omega_{j,k+1}+(\alpha_k-\alpha_j)\omega_{j,k} + \beta_{k-1}\omega_{j,k-1} - \beta_{j-1}\omega_{j-1,k}-v_j^{\ast}f_k+v_k^{\ast}f_j.

注意到由于 A 是厄米矩阵，涉及 A 的项抵消了。

我们使用此递归关系逐行填充对称矩阵 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。

\tilde{\omega}=\beta_k\omega_{j,k+1}+(\alpha_k-\alpha_j)\omega_{j,k}+\beta_{k-1}\omega_{j,k-1}-\beta_{j-1}\omega_{j-1,k},

\omega_{j+1,k}=(\tilde{\omega}+\mathrm{sign}(\tilde{\omega})2\epsilon_M\Vert A\Vert)/\beta_j.

一旦某个元素 \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操作。