Iterative Methods For Solving Markov Chains

Iterative methods for solving linear systems are almost 180 years old.Atfirst, Iterative methods were studied by Gauss,Jacobi and Seidel,and so on.After more than 100 years,iterative method is one of main methods to solvegeneral linear equations. Currently,the research on the iterative methods forsolving singular linear systems has got more attention because of the manypractical applications,especially solving the stationary probability distributionof the Markov chain[5,9,14,17,20,21,22]. But there are many work to do be-cause of the complexity of solving singular matrixs.Schwarz methods are being applied in many areas of science and engineer-ing[4,11,13,16],for it is very convinient to vectorize and to parallelize;but thesemethods were only used in the numerical solution of nonsingular linear sys-tems. Up to now,it is the first time that singular systems are analyzed usingan algebraic approach to Schwarz methods (with overlap) by I. Marek[9], andthat Markov chains problems are studied in that context.But because thereare no new defintion and parameter used , it is strict to splitting matrix anditerative matrix.In this paper,on the one hand,we give the definition of quasi-nonnegativesplittings using Drazin inverse,and let splitting matrix vary from nonnegativesplittings to quasi-nonnegative splittings.it is shown that the semiconvergenceof the additive schwarz iterative method and others.On the other hand,westudy generally the Chebyshev accelerating methods-the common usedaccelerating iterative methods,and discusses the convergence of the methodsin case the iterative matrixs are defective.The paper is made up of four chapters.In chapter 1, to begin with,we give some defines about Markov chains,the sovled statistic-the stationary prob-ability distribution of Markov chains. In chapter 2, we intrdiuce some iterativemethods about the stationary probability distribution of Markov chains: thepower method,the method of Jacobi and Gauss-Seidel, the method of BlockJacobi and Block Gauss-Seidel,and the Schwarz Methods. In chapter 3, Westudy the convergence of addtive iterative methods for solving Markov chains,the main result is:if A=I-B,B∈R^n×n is irreducible,column stochasticmatrix,let p>1 be a positive number,A=M_i-N_i is quasi-nonnegative split-tings and sum from i=1 to p E_iT_i≥sum from i=1 to p(?)_iT_i(or E_iT_i≥(?)_iT_i),i=1,2,...,p．Whenθ<1/q,theiterative matrix of the additive schwarz iterative T_θis semiconvergence．Andwe also prove that the theory of iterative matrix' exact solves. In chapter 4,this chapter discusses the convergence of the Chebyshev accelerating methodsin case the iterative matrixs are defective. The results show the Chebyshevaccelerating methods are likely to converge slowly whenever one of three casesoccurs: the iteative matrixs is defective, the distribution of its spectrum is notfavorable, or the Jordan basis of the iterative matrix is ill-conditioned.