主题
Search

最小残差法

共轭梯度法可以被看作是兰索斯方法对于正定对称系统的特殊变体。最小残差法 (MINRES) 和 对称 LQ 方法 (SYMMLQ) 是可以应用于对称不定系统的变体。

共轭梯度法中的向量序列对应于类似于系数矩阵的三对角矩阵的分解。因此，如果矩阵是不定的，则可能发生算法崩溃，对应于零主元。此外，对于不定矩阵，共轭梯度法的最小化性质不再明确定义。MINRES 方法是共轭梯度法的一种变体，它避免了 LU 分解，并且不会发生崩溃。MINRES 最小化 2-范数中的残差。Paige 等人 (1995) 分析了共轭梯度法和 MINRES 方法对于不定系统的收敛行为。

当 A 不是正定的，而是对称的时，我们仍然可以通过三项递推关系为克雷洛夫子空间构造一个正交基。消除共轭梯度法方程中的搜索方向得到一个递推式

Ar^((i))=r^((i+1))t_(i+1,i)+r^((i))t_(i,i)+r^((i-1))t_(i-1,i),
(1)

它可以写成矩阵形式为

AR_i=R_(i+1)T^__i,
(2)

其中 T^__i 是一个 (i+1)×i 三对角矩阵。

在这种情况下，我们遇到 (·,·)_(A) 不再定义内积的问题。然而，我们仍然可以尝试通过获得以下内容来最小化 2-范数中的残差

x^((i)) in {r^((0)),Ar^((0)),...,A^(i-1)r^((0))}, x^((i))=R_iy^_
(3)

从而最小化

||Ax^((i))-b||_2=||AR_iy^_-b||_2
(4)
=||R_(i+1)T^__iy-b||_2.
(5)

现在我们利用以下事实，如果

D_(i+1)=diag(||r^((0))||_2,||r^((1))||_2,...,||r^((i))||_2),
(6)

那么 R_(i+1)D_(i+1)^(-1) 是相对于当前克雷洛夫子空间的正交变换

||Ax^((i))-b||_2=||D_(i+1)T^__iy-||r^((0))||_2e^((1))||_2,
(7)

并且这个最终表达式可以简单地看作是一个最小范数最小二乘问题。

T^__i 的 (i+1,i) 位置的元素可以通过简单的吉文斯旋转来消去，并且得到的上双对角系统（其他次对角元素已在之前的迭代步骤中移除）可以简单地求解，这导致了 MINRES 方法 (Paige and Saunders 1975)。

另请参阅

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

此条目由 Noel Black 和 Shirley Moore 贡献，改编自 Barrett 等人 (1994) (作者链接)

使用 Wolfram|Alpha 探索

参考文献

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. 线性系统求解模板：迭代方法构建块，第二版 Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.html.Paige, C.; Parlett, B.; and van der Vorst, H. "来自克雷洛夫子空间的近似解和特征值界限。" Numer. Lin. Alg. Appl. 29, 115-134, 1995.Paige, C. and Saunders, M. "稀疏不定线性方程组的解。" SIAM J. Numer. Anal. 12, 617-629, 1975.

在 Wolfram|Alpha 中引用

最小残差法

以此引用

Black, Noel 和 Moore, Shirley. "最小残差法。" 来自 MathWorld——Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/MinimalResidualMethod.html

主题分类