A family of fast fixed point iterations for M/G/1-type Markov chains

2020/08/25 by Bini, Dario Andrea, Latouche, Guy, Meini, Beatrice · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2008.11051

Abstract

We consider the problem of computing the minimal nonnegative solution G of the nonlinear matrix equation X=∑_i=-1^∞ A_iXⁱ⁺¹ where A_i, for i≥ -1, are nonnegative square matrices such that ∑_i=-1^∞ 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, that 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.

Cited by

• A Block-Shifted Cyclic Reduction Algorithm for Solving a Class of Quadratic Matrix Equations

Related

• Relaxed Fixed Point Iterations for Matrix Equations Arising in Markov Chains Modeling
• A fast Newton-Shamanskii iteration for M/G/1-type and GI/M/1-type Markov chains
• Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes
• Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems
• The Newton-Shamanskii method for solving a quadratic matrix equation arising in quasi-birth-death problems