Back to Search
Start Over
A family of fast fixed point iterations for M/G/1-type Markov chains
- Source :
- IMA Journal of Numerical Analysis. 42:1454-1477
- Publication Year :
- 2021
- Publisher :
- Oxford University Press (OUP), 2021.
-
Abstract
- We consider the problem of computing the minimal non-negative solution $G$ of the nonlinear matrix equation $X=\sum _{i=-1}^\infty A_iX^{i+1}$ where $A_i$, for $i\geqslant -1$, are non-negative square matrices such that $\sum _{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$, 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.
- Subjects :
- Discrete mathematics
Markov chain
Applied Mathematics
General Mathematics
Computation
Numerical Analysis (math.NA)
010103 numerical & computational mathematics
Extension (predicate logic)
Fixed point
Type (model theory)
01 natural sciences
Square matrix
010101 applied mathematics
Computational Mathematics
Matrix (mathematics)
Convergence (routing)
FOS: Mathematics
Mathematics - Numerical Analysis
0101 mathematics
Mathematics
Subjects
Details
- ISSN :
- 14643642 and 02724979
- Volume :
- 42
- Database :
- OpenAIRE
- Journal :
- IMA Journal of Numerical Analysis
- Accession number :
- edsair.doi.dedup.....ce1ff11d44c61ba92e36e455eef662fa