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

III 提出问题和大规模特征值规划的数值方法

• 批准号: 9732022
• 负责人: Dianne O'Leary
• 金额: $ 29.62万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-15 至 2001-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9732022&HistoricalAwards=false
• 关键词: Numerical; Methods; III; Posed; Problems

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.

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