A NEW ANALYSIS OF ITERATIVE REFINEMENT AND ITS APPLICATION TO ACCURATE SOLUTION OF ILL-CONDITIONED SPARSE LINEAR SYSTEMS
A NEW ANALYSIS OF ITERATIVE REFINEMENT AND ITS APPLICATION TO ACCURATE SOLUTION OF ILL-CONDITIONED SPARSE LINEAR SYSTEMS
复制标题
DOI：
10.1137/17m1122918
复制
发表时间：
2017-01-01
影响因子：
3.1
通讯作者：
Higham, Nicholas J.
中科院分区：
文献类型：
--
作者：
Carson, Erin;Higham, Nicholas J.
迭代细化是一项长期存在的技术，用于提高通过 LU 分解获得的非奇异线性系统 Ax = b 的计算解的准确性。它利用以额外精度（通常是工作精度的两倍）计算的残差，并且如果矩阵 A 的条件数安全地小于单位舍入 u 的倒数，则现有结果可以保证收敛。我们确定了一种机制，允许迭代细化为具有 u(-1) 或更大条件数的系统产生 u 阶范数相对误差的解，前提是更新方程的求解相对误差充分小于 1。给出了新的舍入误差分析，并分析了其含义。在分析的基础上，我们开发了一种基于 GMRES（广义最小残差）的迭代细化方法 (GMRES-IR)，该方法利用计算的 LU 因子作为预处理器。 GMRES-IR 利用了这样一个事实：即使 A 条件极其恶劣，LU 因子也包含足够的信息，预处理可以大大减少 A 的条件数。我们的舍入误差分析和数值实验表明，GMRES-IR 可以在标准细化失败的情况下取得成功，并且可以为条件数为 u(-1) 及更大的系统提供准确的解决方案。事实上，在我们对此类随机矩阵和来自佛罗里达大学稀疏矩阵集合的实验中，GMRES-IR 在每种情况下最多在三个步骤中产生 u 阶的正态相对误差。
Iterative refinement is a long-standing technique for improving the accuracy of a computed solution to a nonsingular linear system Ax = b obtained via LU factorization. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix A has condition number safely less than the reciprocal of the unit roundoff, u. We identify a mechanism that allows iterative refinement to produce solutions with normwise relative error of order u to systems with condition numbers of order u(-1) or larger, provided that the update equation is solved with a relative error sufficiently less than 1. A new rounding error analysis is given, and its implications are analyzed. Building on the analysis, we develop a GMRES (generalized minimal residual)-based iterative refinement method (GMRES-IR) that makes use of the computed LU factors as preconditioners. GMRES-IR exploits the fact that even if A is extremely ill conditioned the LU factors contain enough information that preconditioning can greatly reduce the condition number of A. Our rounding error analysis and numerical experiments show that GMRES-IR can succeed where standard refinement fails, and that it can provide accurate solutions to systems with condition numbers of order u(-1) and greater. Indeed, in our experiments with such matrices both random and from the University of Florida Sparse Matrix Collection GMRES-IR yields a normwise relative error of order u in at most three steps in every case.