Relaxed functional iteration techniques for the numerical solution of \(M/G/1\) type Markov chains
type: Item
instance of: scholarly article
title: Relaxed functional iteration techniques for the numerical solution of \(M/G/1\) type Markov chains
zbMATH Open document ID: 0914.65145
DOI: 10.1007/BF02510257
author: B. Meini
author: Paola Favati
published in: BIT
publication date: 1999-03-07T00:00:00Z
review text: 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.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60K25
Mathematics Subject Classification ID: 15A24
Mathematics Subject Classification ID: 65F10
zbMATH DE Number: 1228552
zbMATH Keywords: convergence
zbMATH Keywords: minimal nonnegative solution
zbMATH Keywords: matrix equation
zbMATH Keywords: \(M/G/1\) type Markov chains
zbMATH Keywords: functional iteration method
zbMATH Keywords: numerical experiments
zbMATH Keywords: algorithm
describes a project that uses: na12
MaRDI profile type: Publication
cites work: Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
cites work: An invariant subspace approach in m/g/l and g/m/l type markov chains
cites work: Q3943082
cites work: On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
cites work: Improved cyclic reduction for solving queueing problems
cites work: Solving certain queueing problems modelled by Toeplitz matrices
cites work: Q4109064
cites work: Q3976668
cites work: On functional iteration methods for solving nonlinear matrix equations arising in queueing problems
cites work: Solutions of the basic matrix equation for M/G/l AND G/M/1 type markov chains
cites work: Q3961697
cites work: Newton's iteration for non-linear equations in Markov chains
cites work: A logarithmic reduction algorithm for quasi-birth-death processes
cites work: Q5687232
cites work: New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains
cites work: Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems
cites work: A stable recursion for the steady state vector in markov chains of m/g/1 type
cites work: Q5342712
description: scientific article; zbMATH DE number 1228552