We consider the problem of computing the minimal non-negative solution G of the nonlinear matrix equation X=∑∞i=−1AiXi+1 where Ai, for i⩾−1, are non-negative square matrices such that ∑∞i=−1Ai 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.
A family of fast fixed point iterations for M/G/1-type Markov chains
Bini, Dario A;Latouche, Guy;Meini, Beatrice
2021-01-01
Abstract
We consider the problem of computing the minimal non-negative solution G of the nonlinear matrix equation X=∑∞i=−1AiXi+1 where Ai, for i⩾−1, are non-negative square matrices such that ∑∞i=−1Ai 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.