例11.2.2.

考虑单位正方形上泊松方程的有限差分离散化模型问题。主对角线是常数（均为4），因此对角预处理无效。它仅改变特征值的相对间隔，而不改变其分布。然而，不完全分解技术[326]已被证明对预处理相应线性方程有效，并有一些理论结果支持。无预处理时，共轭梯度法需O(n^{1/2})次迭代收敛。采用不完全分解IC(0)预处理，收敛速度加快，但仍约为O(n^{1/2})。而使用改进不完全分解MIC(0)[212]，收敛速度达到O(n^{1/4})。文献[330]表明，计算最小特征值时情况相同。改进不完全分解针对的是矩阵A，而非A-\theta I。理论结果可通过计算验证。 表11.1列出了随着问题规模增大，不同预处理方法下的迭代次数。使用了Lanczos算法（对应无预处理和仅对角预处理）、IC(0)和MIC(0)预处理。初始向量在区间(-1,1)内随机取值，收敛标准为残差范数小于10^{-8}。未采用重启策略。对于大规模问题，MIC(0)预处理效果显著更优。在双对数图中，Lanczos和IC(0)的斜率分别约为0.56和0.43，均接近预期的0.5，IC(0)略优。MIC(0)预处理的斜率约0.23，接近O(n^{1/4})预测的0.25。

计算多个特征值时，MIC效果不佳。以计算n=1600时的最小五个特征值为例，预处理基于A的不完全分解，未针对特定特征值调整。此次重启Davidson方法，最大子空间维度为20，但不重启Lanczos（若需特征向量，Lanczos也可能需重启）。相对而言，Lanczos在计算多个特征值时表现更好，因Davidson方法每次仅针对一个特征值。IC(0)需159次迭代，MIC(0)需158次，Lanczos需172次。但需注意，Lanczos未识别出其中一个小的特征值为双重的，而Davidson方法则正确计算出两个特征值。

表11.1： 模型问题的预处理

n	Lanczos	IC(0)	MIC(0)
25	13	11	12
49	25	14	15
100	36	17	17
196	51	24	20
400	69	27	22
784	99	40	26
1600	137	49	30
3136	182	64	34
6400	287	101	40

对于例11.2.2中的稀疏矩阵，除了迭代次数外，还需考虑每步迭代成本。Lanczos算法每步可能远比Davidson方法经济。这促使发展了利用预处理的Lanczos方法，既利用预处理优势，又保持Lanczos的高效性。此内容将在§11.2.6讨论。效率问题也与Jacobi-Davidson方法有关。减少Davidson方法迭代次数、降低Rayleigh-Ritz过程开销的一种方法是开发极佳的预处理。可在算法11.2的第(3)步，用迭代法近似求解(A-\theta B)w_j = r得到新向量w_j，并可精确至所需程度。对称情况下，可使用预处理的共轭梯度法。与预处理Lanczos类似，这形成了一个计算高效的内部循环，且存储需求也高效。但过度精确的预处理有风险，精确解(A-\theta B)w_j = r会得到已在子空间中的近似特征向量w_j=y。可通过求解(A-\mu B)w = r（\mu \ne \theta）处理，如同不完全Cayley变换。但在Jacobi-Davidson方法中，采用从(A-\theta B)w_j = r解中降维近似特征向量的方法。Jacobi-Davidson方法的联系将在下一小节继续讨论。

Davidson方法在初始向量或子空间不准确时可能遇到困难。文献[335]和[172]建议初始时设M为P - \mu I，其中P是A的近似，\mu接近目标特征值。如§11.1所述，另一种可能是先用Krylov子空间方法生成初始向量供Davidson方法使用。