求解标准形式的大规模离散不适定问题的Krylov迭代法正则化理论和算法

Numerical solutions of large discrete ill-posed problems are an extremely important and difficult research field. This kind of problem arises from numerous disciplines and has very extensive applications, such as mage deblurring, signal processing, geophysics, computerized tomography, heat propagation, biomedical and optical imaging, groundwater modeling, and many others. Typically, they come from discretization of the first kind Fredholm integral equation. The resulting discrete ill-posed problem is highly ill-conditioned and the right-hand side b is noisy, caused by measurement, modeling or discretization errors, and is typically contaminated by a white noise, and the singular values of the coefficient matrix A decay to zero without a noticeable gap. Under the continuous and discrete Picard conditions, the underlying continuous ill-posed problem and the discrete ill-posed problem have bounded true solutions, respectively. Because of the presence of noise and the extreme ill-conditioning of A, the naive solution of the discrete ill-posed problem is unbounded, and has bear no relation to the true solution. Therefore, one has to use regularization to extract a best possible approximation to the true solution. In principle, regularizing an ill-posed problem is to replace it by a well-posed one, such that the error is compensated by the gain in stability. For small and/or moderate sized problems, the truncated singular value decomposition (TSVD) method and standard-form Tikhonov regularization are most commonly used regularization methods, and they have been proved to be reliable and effective for computing best possible approximations to the true solution under certain assumptions on the true solution. The critical point on them is the determination of an optimal regularizartion parameter. For large problems, only iterative solvers are computationally viable, due to the computational complexity of both space and time. One major class of iterative solvers is Krylov iterative solvers that project the large problem onto a sequence of low dimensional Krylov subspaces and compute iterates to approximate the true solution. Of Krylov iterative solvers, the LSQR method and its mathematically equivalent CGLS method, which implicitly applies the Conjugate Gradient (CG) method to the normal equations, have been most commonly used. The Krylov solvers CGME and LSMR are also choices. These solvers have been known to have general regularizing effects and exhibit semi-convergence: The iterates converge to the true solution and the residual norms decrease in an initial stage; then afterwards the noise starts to deteriorate the iterates so that they start to diverge from the true solution and instead converge to the naïve solution. Since 1979, a fundamental and paramount long-standing concern is: Is the regularized solution by each of these methods at semi-convergence a best possible one? That is, is it at least as accurate as the best TSVD or Tikhonov solution? It has turned out that the behavior of an ill-posed problem critically depends on the decay rates of the singular values and the Picard condition. Depending on such decay rates, the problems are classified as three kinds: severely ill-posed, moderately and mildly ill-posed. The main goal of this project is to establish a rigorous regularization theory of CGLS, LSQR, CGME and LSMR for the three kinds of problems and for the first time give definitive conclusions on the above open question. The theory will play the central role in guiding correct use of the methods and identifying if a best possible solution has been found, and it will also derive effective developments of Krylov iterative solvers.

大规模离散不适定问题的数值求解是一个非常重要和困难的研究领域，其中的系数矩阵A的奇异值衰减到零，且随着奇异值的变小，相邻之间没有明显的隔离，右端项b是不精确的，带有（白）噪声。当准确的右端项满足Picard条件时，不适定问题的真解存在。然而，用标准方式得到的解是无界的，和真解没有任何关系。因此，必须对问题使用正则化方法，在稳定性和精度之间达到最佳的平衡，以得到最优可能的近似解。半个世纪以来，求解标准形式的大规模离散不适定问题的主要方法是以共轭梯度方法为代表的Krylov子空间迭代法，最著名和常用的是LSQR, CGLS, CGME和LSMR。但这些方法能否得到最优可能的近似解一直没有确定性的结论。本项目将建立这几个方法对严重、中度和温和不适定问题的严格正则化理论，解决1979年提出的关于方法对这三类问题能否得到最优的近似解这一公开问题，对方法的正确与合理使用提供理论指导，并用之开发新算法。

大规模离散不适定问题的数值求解是一个非常重要和困难的研究领域，在信号处理、图像去噪、地球物理等中有广泛的应用。问题中的系数矩阵A的奇异值衰减到零，且相邻的之间没有明显的隔离，右端项b是不精确的，带有高斯噪声。当准确的右端项满足Picard条件时，不适定问题的解存在。然而，用标准方式得到的解是无界的，和真解没有任何关系。因此，必须使用正则化方法，在稳定性和精度之间达到最佳的平衡，以得到最优可能的近似解。求解标准形式正则化的大规模离散不适定问题的主要方法是以共轭梯度方法为代表的Krylov子空间迭代法，最著名和常用的是LSQR, CGME和LSMR。但这些方法能否得到最优可能的近似解一直没有确定性的结论。本项目建立了这几个方法对严重、中度和温和不适定问题的严格正则化理论，揭示了这几个方法正则化方法相互之间的密切关系，证明了对严重不适定问题和中度不适定问题，LSQR和LSMR能得到最优可能的近似解，但CGME无论对哪类问题，得到的解一般都不是最优的。提出了求解一般形式正则化的大规模离散不适定问题的随机化算法和联合双对角化方法，分别建立了方法的正则化理论，开发了数值算法，给出了可靠的停机准则和最优正则化参数的选取方法。标准形式和一般形式正则化的大规模不适定问题的正则化分析的基本手段分别是奇异值分解(SVD)和广义奇异值分解(GSVD)，本项目提出了计算部分SVD的Jacobi-Davidson型方法，找到了内部校正方程组最低求解精度要求，最大限度地提高了方法的计算效率；研究了文献中已有的将GSVD转化为两种广义特征值问题格式，证明了选取哪种格式能得到更高精度的计算解，对于计算部分GSVD的联合双对角化方法，揭示了联合双对角化方法有限精度运算下的形态。标准形式和一般形式的Tikhonov正则化问题和信頼域子问题的Lagrange乘子型形式问题密切相关。求解后者的最著名方法是广义Lanczos方法，该方法四个核心的收敛性问题中的两个一直没有结果。我们彻底解决了收敛性问题，并建立了结果相互之间的关系，为设计灵活实用的停机准则提供了可靠的理论指导。