Numerical Methods for Ill-Posed Problems and Markov Chains

不适定问题和马尔可夫链的数值方法

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

This project concerns two topics in numerical linear algebra: the numerical treatment of Markov chains and regularization of ill-posed linear systems. The topics share common features: singular or nearly singular matrices; use of iterative methods for large-scale problems; problems in matrix perturbation; and connections with infinite dimensional problems. The computation of the steady-state vector of a Markov chain as well as other important quantities are being investigated. In particular, algorithms are being developed and analyzed for calculating mean first passage times and for computing the recurrence matrix of M/G/1 type queues. In addition aggregation methods with overlapping blocks and the behavior of chains with sluggish transients are being considered. When ill-posed problems are discretized they result in ill-conditioned linear systems which must be regularized to yield accurate solutions. There are three main goals in this work. The first is to prove the folk theorem that if the components of the data vector with respect to the singular vectors decay sufficiently fast then the conjugate gradient iteration will produce a regularizing set of solutions. The second is to treat problems with errors in the matrix by a regularized total-least-squares approach. The third is to further preconditioning strategies for iterative solution methods.

本课题涉及数值线性化中的两个课题 代数：马尔可夫链的数值处理和正则化 不适定线性系统 这些主题具有共同的特征： 或近似奇异矩阵;使用迭代方法解决大规模问题; 矩阵扰动问题;与 无穷维问题 一个稳定状态向量的计算 马尔可夫链以及其他重要的数量正在研究。 特别是，正在开发和分析用于计算的算法， 平均首次穿越时间和计算M/G/1型递推矩阵 排队。 此外，具有重叠块的聚合方法和 正在考虑具有迟滞瞬变的链的行为。 当 将不适定问题离散化，得到病态线性系统 其必须被正则化以产生精确的解。 有三 这项工作的主要目标。 第一个是证明民间定理，如果 数据向量相对于奇异向量的分量衰减 足够快，那么共轭梯度迭代将产生正则化 一套解决方案。 第二种是通过以下方式处理矩阵中存在错误的问题： 一种正则化的最小二乘方法三是进一步 迭代求解方法的预处理策略。