×

A family of fast fixed point iterations for M/G/1-type Markov chains. (English) Zbl 1498.65056

Summary: We consider the problem of computing the minimal non-negative solution \(G\) of the nonlinear matrix equation \(X=\sum_{i=-1}^\infty A_iX^{i+1}\) where \(A_i\), for \(i\geqslant -1\), are non-negative 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\), 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.

MSC:

65F45 Numerical methods for matrix equations
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI arXiv