On Functional Iteration Methods for Solving M/G/1 Type Markov Chains

We consider functional iteration methods, based on the recursion\break $X_{n+1}=F(X_n)$, $n\ge 0$, for solving the nonlinear matrix equation $X=\sum_{i=0}^{+\infty}X^i A_i$ which arises in the numerical solution of M/G/1 type Markov chains. We propose two strategies for improving the rate of convergence of such iterative methods, based on the spectral properties of the solution $G$. The first strategy consists in choosing an initial approximation $X_0$ which shares with $G$ some eigenvalues and the corresponding left eigenvectors; the second one relies on a relaxation technique which modifies the spectral properties of the Jacobian matrix associated with the iteration function $F$. Numerical results show the effectiveness of these strategies.