Numerical Methods for III-Posed Problems and Large Scale Eigenvalue Programs

本文的工作涉及数值线性代数中的两个主题：1）不适定线性系统的正则化; 2）大型稀疏特征值问题的求解。 这些主题具有共同的特点：广泛的应用问题;使用迭代方法解决大规模问题;以及矩阵摄动理论中的有趣问题。 当连续不适定问题离散化时，它们导致病态线性系统，必须正则化以产生精确解。 这部分工作有几个目标。 首先是证明民间定理，如果数据向量的分量相对于矩阵的奇异向量衰减足够快，那么共轭梯度迭代将产生一组正则化的解向量。 第二个是比较离散不适定问题的众多公式，看看哪些是最有效的。 第三是进一步发展预条件子以加速求解算法的收敛。 第四是改进数据收集技术，使成像的准确度更高，从而揭示更小的肿瘤或有关遥远恒星的更多信息。 在过去的十年中，已经提出了许多新的算法，寻找集群的大型矩阵的特征值。 虽然这些算法的有效性已被证明经验，分析结果稀疏。 幸运的是，大量的这些方法共享一个共同的框架，因此有可能开发出广泛适用的分析工具。 作为实现这一目标的一个开始，注意力集中在一个新的，有前途的方法--奇异向量增强-适合的框架。 对一种特殊情况的初步分析，已经在特征值与奇异值的关系上得出了有价值的结果。 该项目的结果将影响不适定问题的解决方案，如医学图像增强，天文数据处理，无损检测和光谱学，以及系统建模（马尔可夫链），计算化学和结构分析中出现的特征值问题。

This work concerns two topics in numerical linear algebra: 1) Regularization of ill-posed linear systems; 2) Solution of large, sparse eigenvalue problems. These topics share common features: a wide range of application problems; the use of iterative methods for large-scale problems; and interesting problems in matrix perturbation theory. When continuous ill-posed problems are discretized they result in ill-conditioned linear systems which must be regularized to yield accurate solutions. This part of the work has several goals. The first is to prove the folk theorem that if the components of the data vector with respect to the singular vectors of the matrix decay sufficiently fast then the conjugate gradient iteration will produce a regularizing set of solution vectors. The second is to compare the numerous formulations of discrete ill-posed problems to see which are most effective. The third is to further develop preconditioners to speed convergence of solution algorithms. The fourth is to improve data-gathering techniques so that the attainable accuracy from imaging is better, thus, for example, revealing smaller tumors or more information about distant stars. Over the past decade many new algorithms for finding clusters of eigenvalues of large matrices have been proposed. Although the effectiveness of some of these algorithms has been demonstrated empirically, analytic results are sparse. Fortunately, a large number of these methods share a common framework, so that it is possible to develop analytic tools that are widely applicable. As a start toward this goal, attention is focused on a new, promising method---singular vector enhancement---that fits in the framework. A preliminary analysis of a special case has already yielded valuable results on the relation of eigenvalues and singular values. The results of this project will impact the solution of ill-posed problems such as medical image enhancement, astronomical data processing, nondestructive testing, and spectroscopy, as well as eigenvalue problems arising in systems modeling (Markov chains), computational chemistry, and structural analysis.