Lanczos 算法

Lanczos 方法是一种迭代算法，它把尺寸为 $N \times N$ 的对称矩阵 $A$ 约化为尺寸为 $m \times m$ 的三对角矩阵 $T$，其中 $m \ll N$。$T$ 的本征值近似于 $A$ 的极端本征值，并且可以重构出相应的本征矢。

Lanczos 方法的关键步骤

1. 初始化：

   • 选取一个单位模长的随机初始矢量 $v_1$。
   • 令 $\beta_0 = 0$，$v_0 = 0$。

2. 迭代： 对于 $j = 1, 2, \dots, m$：

   • 计算 $w = A v_j - \beta_{j-1} v_{j-1}$。
   • 计算 $\alpha_j = v_j^\top w$。
   • 计算 $w = w - \alpha_j v_j$。
   • 计算 $\beta_j = \|w\|$。
   • 若 $\beta_j = 0$，则停止；否则令 $v_{j+1} = w / \beta_j$。

3. 三对角矩阵： 经过 $m$ 次迭代后，构造矩阵 $T$ 如下：

   $$T = \begin{pmatrix} \alpha_1 & \beta_1 & 0 & \dots & 0 \\\ \beta_1 & \alpha_2 & \beta_2 & \dots & 0 \\\ 0 & \beta_2 & \alpha_3 & \dots & 0 \\\ \vdots & \vdots & \vdots & \ddots & \beta_{m-1} \\\ 0 & 0 & 0 & \beta_{m-1} & \alpha_m \end{pmatrix}$$

4. 对角化 $T$：

   • 用标准的稠密矩阵技术（例如 QR 算法）对角化 $T$。
   • $T$ 的本征值近似于 $A$ 的极端本征值。
   • $A$ 的相应本征矢可以由 Lanczos 矢量 $v_j$ 重构得到。

Lanczos 方法的优点

1. 高效：

   • 只需要矩阵与矢量的乘积，因此适用于稀疏矩阵。
   • 内存占用为 $O(N \cdot m)$，而不是 $O(N^2)$。

2. 可扩展性：

   • 对于稠密方法无法处理的超大矩阵也能很好地工作。

3. 专注于极端本征值：

   • Lanczos 方法在求最大或最小的本征值及其本征矢时尤其有效。

挑战与注意事项

1. 正交性丢失：

   • 在有限精度运算中，Lanczos 矢量 $v_j$ 可能失去正交性，从而导致伪本征值。
   • 补救方法包括重新正交化，或使用更高级的变体，如隐式重启 Lanczos 方法。

2. $m$ 的选取：

   • 迭代次数 $m$ 必须谨慎选取，以平衡精度与计算代价。

3. 收敛性：

   • 收敛到极端本征值通常很快，但内部本征值可能需要很多次迭代。