Semistability of switched linear systems with application to PageRank algorithms

Abstract

This paper investigates semistability and its computation for discrete-time, switched linear systems under both deterministic and random switching policies. The notion of semistability pertains to a continuum of initial state dependent equilibria, and finds wide applications in multi-agent and distributed network systems. It is shown in this paper that exponential semistability on a common equilibrium space is equivalent to output exponential stability of a reduced switched linear system with a suitably defined output, under arbitrary and random switchings. Besides, their convergence rates are shown to be identical. A generating function based approach is proposed to compute convergence rates of the reduced switched systems under these switching rules. The obtained semistability results are applied to performance analysis of PageRank algorithms for distributed web-page systems subject to topology switching. The iteration processes of these algorithms are formulated as switched linear systems. Their equilibrium properties are studied, and convergence rates are characterized via the semistability techniques and the generating function approach.