Perturbation results for nearly uncoupled Markov chains with applications to iterative methods

The standard perturbation theory for linear equations states that nearly uncoupled Markov chains(NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that shows that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping criteria, iterative aggregation/disagregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to Grassman, Taksar, and Heyman was recently shown by O'Cinneide to achieve such bounds. Keywords Structured error bounds, aggregation/disaggregation, eigenvector, stopping criteria. AMS(MOS) Subject Classifications 65F05, 65F15,65F20,65G05. 1 Introduction We consider the problem of solving the homogeneous system of linear equations Ap = 0 (1) Department of Computer Science, The Pennsylvania State University, University Park, PA 1680..