On functional iteration methods for solving nonlinear matrix equations arising in queueing problems

The problem of the computation of the minimal nonnegative solution G of the nonlinear matrix equation X = Sigma(i=0)(+infinity) X(i) A(i) is considered. This problem arises in the numerical solution of M/G/1 type Markov chains, where A(i), i greater than or equal to 0), are nonnegative k x k matrices such that Sigma(i=0)(+infinity) Ai is column stochastic. We analyze classical functional iteration methods, by estimating the rate of convergence, in relation to the 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.