Premium
On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes
Author(s) -
Bini D. A.,
Massei S.,
Meini B.,
Robol L.
Publication year - 2018
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2128
Subject(s) - mathematics , toeplitz matrix , quadratic equation , matrix (chemical analysis) , pure mathematics , geometry , composite material , materials science
Summary Matrix equations of the kind A 1 X 2 + A 0 X + A −1 = X , where both the matrix coefficients and the unknown are semi‐infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi‐Toeplitz matrices, are encountered in certain quasi‐birth–death processes as the tandem Jackson queue or in any other processes that can be modeled as a reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations that relies on semi‐infinite quasi‐Toeplitz matrix arithmetic. In particular, we show that the algorithm of cyclic reduction can be effectively applied and can approximate the infinite‐dimensional solutions with quadratic convergence at a cost that is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution and of the invariant probability measure of the associated quasi‐birth–death process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.