Triangular and skew-symmetric splitting method for numerical solutions of Markov chains

In this paper, a theorem is presented to indicate that there exists a nonnegative constant ϵ≥0ϵ≥0 such that the matrix A=QT+ϵI is a positive-definite matrix, where I∈Rn×nI∈Rn×n is an identity matrix and QT∈Rn×n is a matrix with positive diagonal and nonpositive off-diagonal elements. Then a class of triangular and skew-symmetric splitting (TSS) iteration method is applied to solve the positive-definite linear system Ax=bAx=b for obtaining the stationary probability vector of an irreducible Markov chain. Theoretical analyses show that the TSS iteration method converges unconditionally to the unique solution of the linear system, with the upper bound of its contraction factor dependent only on the spectrum of the triangular part and independent of the eigenvectors of the matrices involved. Moreover, the inexact triangular and skew-symmetric splitting (ITSS) iteration method, which employs certain Krylov subspace methods as the inner iteration processes at each step of the outer TSS iteration method, is proposed to accelerate the convergence of the TSS iteration method. Numerical experiments are used to illustrate the effectiveness of the TSS and ITSS iteration methods.