A family of fast fixed point iterations for M/G/1-type Markov chains

Abstract

We consider the problem of computing the minimal nonnegative solution $G$ of the nonlinear matrix equation $X={\sum }_{i=-1}^{\infty }{A}_i{X}^{i+1}$ where $A_i$, for $i\ge -1$, are nonnegative square matrices such that ${\sum }_{i=-1}^{\infty }{A}_i$ is stochastic. This equation is fundamental in the analysis of M/G/1-type Markov chains, since the matrix $G$ provides probabilistic measures of interest. A new family of fixed point iterations for the numerical computation of $G$, that includes the classical iterations, is introduced. A detailed convergence analysis proves that the iterations in the new class converge faster than the classical iterations. Numerical experiments confirm the effectiveness of our extension.