双共轭梯度法通常表现出相当不规则的收敛行为。此外,约化三对角系统的隐式LU分解可能不存在,导致算法崩溃。拟极小残差法(Freund 和 Nachtigal 1991)是一种相关的算法,旨在克服这些问题。
拟极小残差 (QMR) 方法算法背后的主要思想是以最小二乘意义求解约化的三对角系统,类似于广义极小残差法 (GMRES) 中采用的方法。由于为 Krylov 子空间构建的基是双正交的,而不是像 GMRES 中那样是正交的,因此获得的解被视为拟极小残差解,这解释了名称的由来。此外,QMR 使用前瞻技术来避免底层 Lanczos 过程中的崩溃,这使其比双共轭梯度法更稳健。
QMR 的收敛行为通常比双共轭梯度法 (BCG) 更平滑。 Freund 和 Nachtigal (1991) 提出了相当一般的误差界限,表明 QMR 的预期收敛速度可能与广义极小残差法大致相同。从 BCG 和 QMR 中残差之间的关系(Freund 和 Nachtigal 1991,关系式 5.10)可以推断出,在迭代过程中 BCG 取得重大进展的阶段,QMR 已经获得了 的大致相同的近似值。另一方面,当 BCG 根本没有进展时,QMR 可能仍然表现出缓慢的收敛速度。
此版本 QMR 方法中的前瞻步骤可以防止所有情况下的崩溃,除了所谓的“不可治愈的崩溃”,即任何实际数量的前瞻步骤都无法产生下一个迭代。
上面给出了使用预处理器 的预处理拟极小残差方法的伪代码。该算法遵循不带前瞻的两项递归版本(Freund 和 Nachtigal 1994,算法 7.1)。此版本的 QMR 比带有前瞻的完整 QMR 方法更易于实现,但它容易受到底层 Lanczos 过程崩溃的影响。(其他实现变体包括是否缩放 Lanczos 向量,或者是否使用三项递归而不是耦合的两项递归。这些决策通常对算法的稳定性和效率有影响。)
残差的计算是为了收敛性测试。如果使用右(或后)预处理,即 ,那么在每次迭代中都可以计算出 的廉价上限,从而避免了 的递归(Freund 和 Nachtigal 1991,命题 4.1)。这个上限可能过于悲观,最多相差 倍。
QMR 在向量和并行实现方面与双共轭梯度法大致存在相同的问题。每次迭代的标量开销略高于 BCG。在所有稍便宜的 BCG 方法收敛不规则(但足够快)的情况下,出于稳定性原因,QMR 可能是首选。