Relaxed functional iteration techniques for the numerical solution of \(M/G/1\) type Markov chains (Q1272877)

The paper investigates a new iterative method for the computation of the minimal nonnegative solution \(G\) of the matrix equation \(X=\sum^\infty_{i=0} X^iA_i\), arising in the numerical solution of \(M/G/1\) type Markov chains. The classical methods to obtain \(G\) are based on the recursive functional iterations: \[ X_{i+1}= F(X_i),\quad n\geq 0,\tag{1} \] where \(X_0\) is a nonnegative matrix and \(F\) belongs to a matrix function class. In order to improve the performance for the computation of the sequence \((X_n)_{n \in N}\) in (1), the authors propose a functional iteration method based on the recursion: \[ X_{n+1}= (1-\omega_n)X_n+ \omega_nF(X_n),\quad n\geq 0,\tag{2} \] where the relaxation parameter \(\omega_n\) is dynamically computed at each step, and relates the approximation errors between \(X_n\) and \(X_{n+1}\). The proposed algorithm is implemented in Fortran 77 and the numerical experiments show that the number of iterations required by the relaxed functional iteration formulas is about half of the number of iterations required by the standard algorithm, while the amount of computations needed to estimate the relaxation parameter does not significantly increase the ratio between the execution times. Thus the proposed method for the computation of the matrix \(G\) is easy to implement and converges faster, even if still linearly, than the standard one.