NR-SSOR right preconditioned RRGMRES for arbitrary singular systems and least squares problems

技术摘要：针对非值域对称系统及秩亏矩形最小二乘问题的 NR-SSOR 右预处理 RRGMRES 方法

问题陈述
广义最小残差法 (GMRES) 是求解线性方程组 $Ax = b$ 的标准 Krylov 子空间迭代求解器。然而，当 $A$ 是奇异的且系统是不一致的（即 $b \notin R(A)$）时，已知 GMRES 在无法提供最小二乘 (LS) 解的情况下会发生崩溃，除非 $A$ 是值域对称 (EP) 的，即满足 $R(A) = R(A^T)$。具体而言，如果 $R(A^T) \neq R(A)$——这种情况包括 $A$ 的指数大于或等于 1 的情形——则存在初始向量 $x_0$ 和右端项 $b$，使得 GMRES 失效。此外，即使 $A$ 是值域对称的，在处理不一致系统时，GMRES 内部求解的最小二乘子问题也可能变得极度病态。

现有方法（如无崩溃 GMRES）缺乏始终有效的理论保证。同样，虽然 AB-GMRES 方法（对 $ABz=b$ 应用 GMRES）可以处理奇异系统，但标准的预处理器 $B$ 选择（例如使用平稳内迭代的 $B=A^TC$）并不能保证对于不一致系统，$AB$ 仍是值域对称的，这可能导致无法找到最小二乘解。

方法论
作者提出了一种结合三个关键组件的鲁棒迭代方法：

1. 使用 $B = CA^T$ 的右预处理： 该方法不是直接求解 $Ax=b$，而是求解变换后的最小二乘问题$\min_z |b - ABz|_2$，其中$B = CA^T$且$C \in \mathbb{R}^{n \times n}$ 是一个对称正定 (SPD) 矩阵。这种变换确保了乘积 $AB = ACA^T$ 是对称且值域对称的，无论 $A$ 本身是否为值域对称。因此，该方法可以针对任意奇异的 $A$ 和 $b$ 确定最小二乘解 $x = CA^Tz$ 而不会发生崩溃。
2. RRGMRES（值域限制 GMRES）： 为了解决不一致系统中 GMRES 固有的病态问题，作者采用了 RRGMRES 而非标准 GMRES。RRGMRES 将搜索空间限制在 $A$ 的值域内，从而为不一致的值域对称系统提供了更高的稳定性。理论分析表明，RRGMRES 中 Hessenberg 矩阵的最小奇异值存在下界，而这一性质在标准 GMRES 中是无法保证的。
3. NR-SSOR 预处理器： 本文引入了非对称 SSOR (NR-SSOR) 方法作为内迭代右预处理器来构建矩阵 $C$。作者证明，如果 $A$ 没有零列且松弛参数 $\omega$ 满足 $0 < \omega < 2$，则由此产生的矩阵 $C$（源自 NR-SSOR 迭代）是对称正定的。这一理论保证验证了在所提框架内使用 NR-SSOR 处理平方奇异系统和矩形秩亏最小二乘问题 ($A \in \mathbb{R}^{m \times n}$) 的有效性。

核心贡献

• 理论依据： 本文证明了对于 NR-SSOR 右预处理器 $B = CA^T$，在标准条件下（$A$ 无零列，$0 < \omega < 2$），矩阵 $C$ 是对称正定的。这确保了 $AB$ 是值域对称的，从而使该方法能够稳健地求解非值域对称系统的最小二乘解。
• 针对不一致系统的鲁棒性： 证明了所提 NR-SSOR 右预处理 RRGMRES 对于任意 $b \in \mathbb{R}^m$ 和奇异 $A$（包括指数 $\ge 1$ 且 $R(A) \neq R(A^T)$ 的情况）均能确定最小二乘解。
• 向矩形问题的扩展： 该方法成功扩展到了欠定及超定矩形最小二乘问题，其中 $A$ 可能存在秩亏。
• 与 MINRES-QLP 的比较： 本文建立了一个与 MINRES-QLP（一种以处理奇异对称系统著称的方法）的比较框架，指出虽然 MINRES-QLP 在一致系统下寻找最小范数解，但本文方法在处理不一致系统时表现出更优越的性能。

数值实验结果
针对以下场景进行了广泛的数值实验：

1. GP 不一致系统： 指数为 1 的矩阵，满足 $R(A) \cap N(A) = \{0\}$ 但 $R(A) \neq R(A^T)$。
2. 指数为 2 的不一致系统： 指数为 2 的矩阵。
3. 欠定最小二乘问题： 大规模矩形矩阵（如 Maragal, landmarkT, lp dfl001）。

结果表明：

• 收敛性： 直接应用于 $Ax=b$ 的标准 GMRES 和 RRGMRES 在处理这些不一致、非值域对称系统时往往无法收敛到最小二乘解。
• NR-SSOR 的优越性： 与其他预处理器（如 $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ 或 $B = A^T$）相比，所提 NR-SSOR 预处理的 RRGMRES 始终能获得显著更小的残差（通常为 $10^{-10}$ 至 $10^{-15}$）。
• 效率： 与未预处理或采用不同预处理的变体相比，所提方法所需的迭代次数更少，计算时间显著缩短（在特定欠定情况下快达 87.9 倍）。
• 与 MINRES-QLP 的比较： 在不一致场景下，所提方法的残差比 MINRES-QLP 低几个数量级，并且能以更少的迭代次数达到该极小值。

意义
本文声称，所提 NR-SSOR 右预处理 RRGMRES 为一类困难的线性代数问题提供了具有理论依据且数值鲁棒的解决方案：即奇异、非值域对称系统以及秩亏矩形最小二乘问题。通过证明由 NR-SSOR 导出的预处理器矩阵 $C$ 的对称正定性，作者确保了该方法避免了标准 GMRES 在不一致设定下的崩溃问题。数值实验验证了该方法不仅在理论上是完备的，而且在实践中也是高效的，在处理不一致系统时，其残差降低能力和计算速度均优于 AB-GMRES 及其他预处理方案和 MINRES-QLP。