预处理Lanczos方法

预处理Lanczos方法由Scott[397]提出，当时T=I，并由Knyazev[264,265]进行了分析。该方法基于内外迭代的基本思想，我们在此针对矩阵束B - \mu A进行描述。

设定参数\mu为固定值。我们考虑以下辅助特征值问题：

T (B- \mu A)v= \nu v. \tag{11.14}

若\mu = \mu_1，则存在零特征值\nu，且对应的特征向量在式(11.14)中也是原矩阵束B - \mu A对应于\mu_1的特征向量。该零特征值是矩阵T (B- \mu A)的最大特征值，并与其他负特征值分离开来。因此，可采用标准的多项式方法（特别是Lanczos方法）计算该值。我们注意到，决定收敛速度的分离程度依赖于预处理矩阵T的质量；详见[264,265]。

在方法中，我们选择参数\mu= \mu^{(0)}的初始值，然后利用若干Lanczos内迭代求解式(11.14)的最大特征值。假设预处理矩阵T为对称正定，则矩阵T (B- \mu A)相对于T^{-1}基的标量积是对称的，因此可采用经典的Lanczos方法结合此标量积进行计算；参见§4.4。随后，新的\mu = \mu^{(1)}值通过原矩阵束对最近内迭代向量迭代的Rayleigh商计算得出。此向量亦作为下一轮内迭代的初始猜测。这种内外迭代方法显然符合我们定义的预处理特征求解器。

我们在算法11.7中展示了针对矩阵束B - \mu A的单向量版本方法。

算法 11.7：预处理Lanczos方法用于广义特征值问题

(1) 选择一个初始向量 x^{(0)}。
(2) 对于 i=0,..., 直到收敛执行：
(3) \mu^{(i)}:=\left(x^{(i)}, B x^{(i)}\right)/\left(x^{(i)}, A x^{(i)}\right)
(4) 应用 l_{i} 步经典Lanczos方法，使用内积 (x,T^{-1}y)，以找到 T(B-\mu^{(i)}A) 的最大特征值和对应的特征向量，使用向量 x^{(i)} 作为初始猜测。
(5) x^{(i+1)}:= Lanczos方法的最新向量迭代

Scott[397]证明了对于完全收敛的内迭代过程，外迭代具有渐近二次收敛性。当然，这并不保证在有限内迭代次数下方法的收敛性。任意内迭代次数的显式收敛率估计已由[264,265]建立。结果显示，首先，对于任意固定内迭代次数，例如仅一次，方法至少线性收敛；其次，内迭代次数的缓慢但无限增长可改善平均内迭代次数的收敛率估计。

预处理Lanczos方法可能比预处理最速下降/上升法收敛更快。此外，若在内迭代中采用无重正交化的标准三项递归，则每次迭代的计算成本与预处理最速下降/上升法相近。

主要缺点在于Lanczos过程中需要基于T^{-1}的标量积，因此应易于计算向量T^{-1}x。对于某些预处理矩阵，如基于域分解的预处理矩阵，可能仅能高效计算Tx（这也是必需的），而无法计算T^{-1}x。

在这种情况下，我们仍可为算子T(B - \mu^{(i)}A)构造Krylov子空间，并利用Rayleigh-Ritz方法将算子B - \mu A投影到该子空间。示意如下：

\begin{aligned} \mu (x^{(i+1)}) &= {\rm max}_{ x \in {\mathcal{K}} \mu(x)}, \\ \mathcal{K} &= \mathrm{span}\{x^{(i)}, T(B-\mu^{(i)}A)x^{(i)}, \ldots, [T(B- \mu^{(i)} A)]^{l_i}x^{(i)} \} \end{aligned}\tag{11.15}

其中l_i为第i次外迭代步骤的内迭代步数。

这引出了算法11.8，可通过修改算法11.7的第(4)和(5)行得到：

算法 11.8：预处理投影方法用于广义特征值问题

(1) 选择一个初始向量 x^{(0)}。
(2) 对于 i=0,..., 直到收敛执行：
(3)     \mu^{(i)}:=\left(x^{(i)}, B\, x^{(i)}\right)/\left(x^{(i)}, A\, x^{(i)}\right)
(4)     使用矩阵 T(B-\mu^{(i)}A) 和向量 x^{(i)} 作为初始猜测，构建 (l1+1) 维Krylov子空间
(4a)    对 B-\mu^{(i)}A 应用Rayleigh-Ritz方法
(5)     x^{(i+1)}:= 对应最小Ritz值的Ritz向量

该方法由[264,265]提出，后在[336]中重新发现。若仅使用一次内迭代，该方法等同于预处理最速下降/上升算法11.6。

由于与预处理Lanczos过程的相似性，大部分收敛理论及主要结论同样适用于此过程；详细内容参见[264,265]。预处理投影算法11.8在相同内迭代次数下比预处理Lanczos算法11.7收敛稍快。然而，现在只能使用标准三项递归计算Krylov子空间的基。为实现Rayleigh-Ritz方法，我们需要存储基中的所有向量并显式计算所有标量积，这增加了计算投影矩阵的成本并显著提高了存储需求，除非采用重启机制。