Abstract. The problem of the computation of the minimal nonnegative solution $G$ of the nonlinear matrix equation $X=\sum_{i=0}^{+\infty}X^iA_i$ is considered. This problem arises in the numerical solution of M/G/1 type Markov chains, where $A_i$, $i\ge0$, are nonnegative $k\times k$ matrices such that $\sum_{i=0}^{+\infty}A_i$ is column stochastic. We analyze classical functional iteration methods, by estimating the rate of convergence, in relation with spectral properties of the starting approximation matrix $X_0$. Based on these new convergence results, we propose an effective method to choose a matrix $X_0$, which drastically reduces the number of iterations; the additional cost needed to compute $X_0$ is much less than the overall savings achieved by reducing the number of iterations.

  <dvi>  <postscript>  files of the paper