Algebraic Schwarz methods for the numerical solution of Markov chains

摘要

The convergence of additive and multiplicative Schwarz methods for computing certain characteristics of Markov chains such as stationary probability vectors and mean first passage matrices is studied. The main result is a convergence theorem for multiplicative Schwarz iterations when applied to singular systems. As a byproduct, a convergence result for alternating iterations is also obtained. It is also shown that, when the Markov chain is ergodic, additive and multiplicative Schwarz methods can be applied to the nonsingular systems that result from reducing the equations. The so-called coarse grid corrections are also studied. (C) 2004 Elsevier Inc. All rights reserved.