NECESSARY AND SUFFICIENT CONDITIONS FOR GLOBAL GEOMETRIC CONVERGENCE OF BLOCK GAUSS-SEIDEL ITERATION ALGORITHM APPLIED TO MARKOV CHAINS

スポンサーリンク

概要

• 論文の詳細を見る

• Convergence properties of the block Gauss-Seidel algorithm applied to ergodic Markov chains are discussed in this paper. This algorithm is one of the most prevalent methods for computing ergodic probability vectors of large-scale Markov chains. We will provide necessary and sufficient conditions for global geometric convergence of this algorithm. To apply this algorithm, the state space of a Markov process is decomposed into mutually exclusive and exhaustive lumps. The convergence properties depend on this lumping. It is also shown that, there exists at least one set of lumps, for any ergodic stochastic matrix, which assures geometric convergence of the algorithm.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Igaki Nobuko

  Department Of Management Information Systems And Decision Sciences Tezukayama University

• Sumita Ushio

  Graduate School Of International Management International University Of Japan

関連論文

• SOCIAL BENEFIT ANALYSIS OF CONGESTION SYSTEMS WITH HETEROGENEOUS USERS
• NECESSARY AND SUFFICIENT CONDITIONS FOR GLOBAL GEOMETRIC CONVERGENCE OF BLOCK GAUSS-SEIDEL ITERATION ALGORITHM APPLIED TO MARKOV CHAINS
• A PARALLEL QUEUEING SYSTEM GI/M/2 WITH PROBABILISTIC BRANCHING

スポンサーリンク