A family of fast fixed point iterations for M/G/1-type Markov chains
share
We consider the problem of computing the minimal nonnegative solution G of the nonlinear matrix equation X=∑_i=-1^∞ A_iX^i+1 where A_i, for i≥ -1, are nonnegative square matrices such that ∑_i=-1^∞ 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. We introduce here a new family of fixed point iterations that include the classical iterations for the numerical computation of G. We perform a detailed convergence analysis and prove that the iterations in the new class converge faster than the classical iterations. Numerical experiments show that the acceleration in terms of CPU time is substantial with a speed-up which is generally greater than 2 and, in several cases, reaches much larger values.
READ FULL TEXT