Cyclic convergence of iterative methods in Markov modelling

Abstract

The stationary distribution of a continuous-time Markov chain satisfies a singular system of linear algebraic equations with the intensity matrix Aas coefficients. For solving such systems, iterative methods are considered, mainly the Jacob and the Gauss-Seidel methods. In order to enforce the convergence of these methods in every case, the notion of convergence is slightly generalized by averaging over a cycle of fixed length. Handy methods of finding a cycle of convergence are derived in which the directed graph of the Intensity matrix Ais considered. For the convergence of the Gauss-Seidel method the condition a_ij · a_ij≠0 for some i<jIs sufficient. Finally more general systems are treated with singular M-matrices as coefficients.

AMS 1980 Subject Classifications:

• Primary: 65 F 10
• Secondary: 60 J 27

Keywords:

• semi-iterative methods
• intensity matrices
• singular M-matrices
• Jacob method
• Gauss-Seidel method
• circuits in graphs