预处理共轭梯度法

在这一小节中，我们将介绍我们最偏爱的方法，从实际效率的角度来看：即局部最优PCG方法 [266]。它结合了算法的鲁棒性和简洁性，如算法11.6所示，预处理Lanczos算法的三个项递归关系，如算法11.7所示，以及可能的预处理投影算法11.8和Davidson方法的快速收敛性。

一个简单的PCG方法变体，针对矩阵束B - \mu A，可以写成如下形式：

\begin{aligned} x^{(i+1)} &= w^{(i)} + \tau^{(i)} x^{(i)} + \gamma^{(i)}x^{(i-1)}, \\ w^{(i)} &= T(Bx^{(i)}-\mu^{(i)} A x^{(i)}), \\ \mu^{(i)} &= \mu (x^{(i)}), \end{aligned} \tag{11.17}

其中，适当选择的标量迭代参数\tau^{(i)}和\gamma^{(i)}。参数选择最简单且最有效的方式基于局部最优的思想[266]；即，选择\tau^{(i)}和\gamma^{(i)}，通过Rayleigh-Ritz方法最大化Rayleigh商\mu(x^{(i+1)})；参见算法11.10。

算法 11.10：用于广义特征值问题的PCG方法

(1) 选择一个初始向量 x^{(0)}。
(2) 对于 i=0,..., 直到收敛执行：
(3) \mu^{(i)}:=\left(x^{(i)}, B x^{(i)}\right)/\left(x^{(i)}, A x^{(i)}\right)
(4) r:=Bx^{(i)}-\mu^{(i)}Ax^{(i)}
(5) w:=Tr
(6) 在 \operatorname{span}\left\{w,x^{(i)},x^{(i-1)}\right\} 上对 B-\mu A 应用Rayleigh-Ritz方法
(7) x^{(i+1)}:= 对应最大Ritz值的Ritz向量

对于局部最优版本的PCG方法，我们可以直接应用收敛速率估计（11.13），因为该方法在最大化Rayleigh商方面不慢于预处理的陡峭上升法。

我们已经收集了算法11.10每次迭代的主要成本，包括存储和浮点运算，分别列于以下表格中。

项目	存储
残差	1 n-向量
近似特征向量	2 n-向量
临时向量	3-5 n-向量

操作	主要成本
Rayleigh-Ritz方法	9点积和 2矩阵-向量乘积,
残差 r	2矩阵-向量乘积, 1更新
预处理残差 w	取决于预处理矩阵 T
近似特征向量	1更新

特征值问题的共轭梯度方法由布拉德伯里和弗莱彻[61]提出，并最近引起了关注；不同的版本已被提出，例如[433,394,429,186,464,185,167,48]。它们通常构建为一般的共轭梯度方法，应用于Rayleigh商的最小化，并且不利用Rayleigh商的具体特性，即局部最小化问题可以通过Rayleigh-Ritz方法轻松解决。它们通常基于（现在线性系统的标准）两个链接的双项递归，其中一个标量参数的选择是为了在某种意义上使方向共轭。算法11.10的特点是它使用了一个三项递归，这使我们既可以通过解决局部最小化问题来选择标量参数，又不必担心找到共轭方向。

我们最后注意到，算法11.10在某种程度上是不稳定的，因为试验子空间的基几乎是线性相关的。这可以通过在应用Rayleigh-Ritz方法之前进行正交化来解决。

我们在下一小节中介绍了算法11.10的块版本。