Numerical Methods for Ill-Posed Problems and Markov Chains

本项目涉及数值线性代数中的两个主题：马尔可夫链的数值处理和不适定线性系统的正则化。这些主题有共同的特点：奇异或接近奇异的矩阵；大规模问题的迭代方法的使用；矩阵摄动问题；以及与无限维问题的联系。马尔可夫链的稳态向量的计算以及其他重要的量正在被研究。特别是，正在开发和分析用于计算M/G/1型排队的平均首次通过时间和计算递归矩阵的算法。此外，正在考虑具有重叠块的聚集方法和具有迟缓瞬变的链的行为。当不适定问题被离散化时，它们导致病态线性系统，必须正则化才能产生准确的解。这项工作有三个主要目标。第一个是证明Follow定理，即如果数据向量相对于奇异向量的分量衰减得足够快，则共轭梯度迭代将产生正则化的解集合。第二种是用正则化的总体最小二乘法处理矩阵中有误差的问题。三是进一步提出了迭代求解方法的预处理策略。

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.