We consider the problem of computing the minimal nonnegative solution G of the nonlinear matrix equation X=i=-1^\infty A_iX^{i+1} where A_i, for i\ge -1, are nonnegative square matrices such that 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. 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 .
We consider the problem of computing the minimal nonnegative solution G of the nonlinear matrix equation X=i=-1^\infty A_iX^{i+1} where A_i, for i\ge -1, are nonnegative square matrices such that 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 , that 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 .
R
We introduce here a
A
D
that include the classical iterations
R
. We perform a
, that includes the classical iterations, is introduced. A
R
and prove
proves
R
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
confirm the effectiveness of our extension