Lanczos方法
  A. Ruhe

Lanczos算法与前一节讨论的迭代算法密切相关，因为它只需要通过矩阵-向量操作来访问矩阵。不同的是，Lanczos算法在利用信息方面更为高效。它通过记忆所有计算方向，并始终让矩阵作用于一个与之前所有尝试方向正交的向量，从而更好地利用了这些信息。

本节我们将介绍适用于特征值问题的厄米Lanczos算法，

Ax=\lambda x\;,

其中A是一个厄米矩阵，或在实数情况下是对称矩阵。

算法从一个适当选择的初始向量v开始，构建Krylov子空间的正交基V_j，

{\mathcal K}^j(A,v)=\mathrm{span}\{v,Av,A^2v,\dots,A^{j-1}v\}\;,

一次构建一列。每一步只需进行一次矩阵-向量乘法

y=Ax

在新正交基V_j下，算子A表示为一个实对称三对角矩阵，

T_{j}=\begin{bmatrix} \alpha_1 & \beta_1 & & \\ \beta_1 & \alpha_2 & \ddots & \\ & \ddots & \ddots & \beta_{j-1} \\ & & \beta_{j-1} & \alpha_j \end{bmatrix},

该矩阵也是一次构建一行和一列，通过如下递归关系

AV_j=V_{j}T_{j}+re_j^{\ast} \quad \mathrm{with} \quad V^{\ast}_j r = 0.

在任何步骤 j，我们可以计算T_{j}的特征解，

T_{j}s_i^{(j)}=s_i^{(j)}\theta_i^{(j)}\;,

其中上标(j)用于表示这些量在每次迭代j中变化。如果残差的范数很小，Ritz值\theta_i^{(j)}及其Ritz向量，

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

将是A的一个特征对的良好近似；参见第4.8节。

让我们计算这个Ritz对的残差，

r_i^{(j)}=Ax_i^{(j)}-x_i^{(j)}\theta_i^{(j)}=AV_js_i^{(j)}-V_js_i^{(j)}\theta_i^{(j)}=(AV_j-V_jT_{j})s_i^{(j)}=v_{j+1}\beta_js_{j,i}^{(j)}\;.

我们看到其范数满足

\Vert r_i^{(j)}\Vert _2=\vert\beta_js_{i,j}^{(j)}\vert=\beta_{j,i}\;,

因此我们只需要监测T的次对角元素\beta_j及其特征向量的最后一个元素s_{i,j}^{(j)}，就可以估计残差的范数。一旦这个估计值变小，我们就可以将Ritz值\theta_i^{(j)}标记为收敛到特征值\lambda_i。注意，计算Ritz值不需要矩阵-向量乘法。我们可以节省这个耗时的操作，直到步骤j，当估计值指示收敛时再进行。