A fast Newton-Shamanskii iteration for M/G/1-type and GI/M/1-type Markov chains

2015/08/26 by Pei-Chang Guo, Guo, Pei-Chang
Business, Management and Accounting · Computer Science · Mathematics · #65F30 #65H10 #Advanced Queuing Theory Analysis #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Matrix Theory and Algorithms #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1508.06341

openalex publication_date 2015/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

For the nonlinear matrix equations arising in the analysis of M/G/1-type and GI/M/1-type Markov chains, the minimal nonnegative solution G or R can be found by Newton-like methods. Recently a fast Newton's iteration is proposed in \citeHoudt2. We apply the Newton-Shamanskii iteration to the equations. Starting with zero initial guess or some other suitable initial guess, the Newton-Shamanskii iteration provides a monotonically increasing sequence of nonnegative matrices converging to the minimal nonnegative solution. We use the technique in \citehoudt2 to accelerate the Newton-Shamanskii iteration. Numerical examples illustrate the effectiveness of the Newton-Shamanskii iteration.

Citations

• Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems

Related

• A family of fast fixed point iterations for M/G/1-type Markov chains
• The Newton-Shamanskii method for solving a quadratic matrix equation arising in quasi-birth-death problems
• Relaxed Fixed Point Iterations for Matrix Equations Arising in Markov Chains Modeling
• How to get high order without loosing efficiency for the resolution of systems of nonlinear equations: A short review of Shamanskii's m method
• Nonlinear Matrix Equations in Applied Probability—Solution Techniques and Open Problems