We consider the problem of computing the minimal non-negative solution G of the nonlinear matrix equation X=∑∞i=−1AiXi+1 where Ai⁠, for i⩾−1⁠, are non-negative square matrices such that ∑∞i=−1Ai 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.

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

Bini, Dario A;Latouche, Guy;Meini, Beatrice
2022-01-01

Abstract

We consider the problem of computing the minimal non-negative solution G of the nonlinear matrix equation X=∑∞i=−1AiXi+1 where Ai⁠, for i⩾−1⁠, are non-negative square matrices such that ∑∞i=−1Ai 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.
2022
Bini, Dario A; Latouche, Guy; Meini, Beatrice
File in questo prodotto:
File Dimensione Formato  
blm_fixed_point_finalpub.pdf

non disponibili

Descrizione: articolo rivista
Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - accesso privato/ristretto
Dimensione 703.3 kB
Formato Adobe PDF
703.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
funit_arxiv.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 682.55 kB
Formato Adobe PDF
682.55 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1119030
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact