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

We consider the problem of computing the minimal non-negative solution G of the nonlinear matrix equation X=∑∞i=−1AiXi+1 where Ai⁠, for i⩾−1⁠, are non-negative square matrices such that ∑∞i=−1Ai 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⁠, which 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.