主题
Search

拟极小残差法


双共轭梯度法通常表现出相当不规则的收敛行为。此外,约化三对角系统的隐式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 已经获得了 x^^ 的大致相同的近似值。另一方面,当 BCG 根本没有进展时,QMR 可能仍然表现出缓慢的收敛速度。

此版本 QMR 方法中的前瞻步骤可以防止所有情况下的崩溃,除了所谓的“不可治愈的崩溃”,即任何实际数量的前瞻步骤都无法产生下一个迭代。

上面给出了使用预处理器 M=M_1M_2 的预处理拟极小残差方法的伪代码。该算法遵循不带前瞻的两项递归版本(Freund 和 Nachtigal 1994,算法 7.1)。此版本的 QMR 比带有前瞻的完整 QMR 方法更易于实现,但它容易受到底层 Lanczos 过程崩溃的影响。(其他实现变体包括是否缩放 Lanczos 向量,或者是否使用三项递归而不是耦合的两项递归。这些决策通常对算法的稳定性和效率有影响。)

残差的计算是为了收敛性测试。如果使用右(或后)预处理,即 M_1=I,那么在每次迭代中都可以计算出 |r^((i))| 的廉价上限,从而避免了 r^((i)) 的递归(Freund 和 Nachtigal 1991,命题 4.1)。这个上限可能过于悲观,最多相差 sqrt(i+1) 倍。

QMR 在向量和并行实现方面与双共轭梯度法大致存在相同的问题。每次迭代的标量开销略高于 BCG。在所有稍便宜的 BCG 方法收敛不规则(但足够快)的情况下,出于稳定性原因,QMR 可能是首选。


另请参阅

双共轭梯度法, 双共轭梯度稳定方法, 切比雪夫迭代, 共轭梯度法, 正规方程上的共轭梯度法, 共轭梯度平方方法, 灵活的广义极小残差法, 广义极小残差法, 线性方程组, 极小残差法, 非平稳迭代法, 预处理器, 平稳迭代法, 对称 LQ 方法, 无转置拟极小残差法

此条目由 Noel Black 和 Shirley Moore 贡献,改编自 Barrett et al. (1994) (作者链接)

使用 Wolfram|Alpha 探索

参考文献

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; 和 van der Vorst, H. 线性系统求解模板:迭代方法的构建块,第 2 版。 Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.htmlFreund, R. 和 Nachtigal, N. "QMR: 非 Hermitian 线性系统的拟极小残差法。" Numer. Math. 60, 315-339, 1991.Freund, R. 和 Nachtigal, N. "基于耦合两项递归的 QMR 方法的实现。" SIAM J. Sci. Statist. Comput. 15, 313-337, 1994.

在 Wolfram|Alpha 上被引用

拟极小残差法

请引用为

Black, NoelMoore, Shirley. "拟极小残差法。" 来自 MathWorld——Wolfram Web 资源,由 Eric W. Weisstein 创建。 https://mathworld.net.cn/Quasi-MinimalResidualMethod.html

学科分类