Entrywise perturbation theory and error analysis for Markov chains |
| |
Authors: | Colm Art O'Cinneide |
| |
Institution: | (1) School of Industrial Engineering, Purdue University, Grissom Hall, 47907-1287 West Lafayette, IN, USA |
| |
Abstract: | Summary Grassmann, Taksar, and Heyman introduced a variant of Gaussian climination for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem itself is well-conditioned, in the sense of entrywise relative error. Thus the algorithm computes each entry of the steady-state vector with low relative error. Even the small steady-state probabilities are computed accurately. The key to our analysis is to focus on entrywise relative error in both the data and the computed solution, rather than making the standard assessments of error based on norms. Our conclusions do not depend on any Condition numbers for the problem.This work was supported by NSF under grants DMS-9106207 and DDM-9203134 |
| |
Keywords: | 65F05 65G05 15A51 60J10 60J27 |
本文献已被 SpringerLink 等数据库收录! |
|