On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes

Abstract

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.