MINRES-QLP: A KRYLOV SUBSPACE METHOD FOR INDEFINITE OR SINGULAR SYMMETRIC SYSTEMS
MINRES-QLP: A KRYLOV SUBSPACE METHOD FOR INDEFINITE OR SINGULAR SYMMETRIC SYSTEMS
复制标题
DOI：
10.1137/100787921
复制
发表时间：
2011-01-01
影响因子：
3.1
通讯作者：
Saunders, Michael A.
中科院分区：
文献类型：
--
作者：
Choi, Sou-Cheng T.;Paige, Christopher C.;Saunders, Michael A.
CG、SYMMLQ和MINRES是求解对称线性方程组的Krylov子空间方法。当这些方法应用于不相容系统（即奇异对称最小二乘问题）时，CG可能会崩溃，SYMMLQ的解可能会爆炸，而MINRES将给出最小二乘解，但不一定是最小长度（伪逆）解。这一认识促使我们设计一个类似MINRES的算法来计算奇异对称系统的最小长度解。MINRES使用来自Lanczos过程的三对角矩阵的QR因子（其中R是上三对角）。MINRES-QLP使用QLP分解（其中右侧的旋转将R减少到下三对角形式）。对于病态系统（奇异或非奇异），MINRES-QLP可以给出比MINRES更精确的解。我们导出了预条件MINRES-QLP，新的停止规则，以及解和剩余范数、矩阵范数和条件数的更好的估计。
CG, SYMMLQ, and MINRES are Krylov subspace methods for solving symmetric systems of linear equations. When these methods are applied to an incompatible system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ's solution could explode, while MINRES would give a least-squares solution but not necessarily the minimum-length (pseudoinverse) solution. This understanding motivates us to design a MINRES-like algorithm to compute minimum-length solutions to singular symmetric systems. MINRES uses QR factors of the tridiagonal matrix from the Lanczos process (where R is upper-tridiagonal). MINRES-QLP uses a QLP decomposition (where rotations on the right reduce R to lower-tridiagonal form). On ill-conditioned systems (singular or not), MINRES-QLP can give more accurate solutions than MINRES. We derive preconditioned MINRES-QLP, new stopping rules, and better estimates of the solution and residual norms, the matrix norm, and the condition number.