A family of fast fixed point iterations for M/G/1-type Markov chains
| Autor: | Guy Latouche, Dario Andrea Bini, Beatrice Meini |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
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 |
| Zdroj: | IMA Journal of Numerical Analysis. 42:1454-1477 |
| ISSN: | 1464-3642 0272-4979 |
| DOI: | 10.1093/imanum/drab009 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|