Solving nonlinear matrix equations arising in tree-like stochastic processes. (Q1874657)

The authors consider the problem of computing a nonsingular matrix \(X\) which solves the nonlinear matrix equation \[ X+ \sum_{1\leq i\leq d} A_i X^{-1} D_i= C,\tag{1} \] where \(C\), \(A_i\), \(D_i\in \mathbb{R}^{m\times m}\), \(i= 1,\dots, d\), are given matrices. It is assumed that 1) \(C= B-I\), and \(B\) is sub-stochastic; 2) \(A\) and \(D\) have nonnegative entries; 3) the matrices \(I+ C+ D+ A_1+\cdots + A_d\), \(I= 1,\dots,d\) are stochastic. This problem arises in the analyses of certain discrete-time bivariate Markov processes called tree-like processes. The computation of the stationary distribution of the Markov process can be reduced to solving (1). In this paper efficient algorithms for solving (1) are derived. First the rapidity of the natural fixed point iteration is anlyzed using the Perron-Frobenius theory of nonnegative matrices. Then two new improved methods are introduced. The first one consists in generating a sequence of approximations obtained by solving at each step quadratic matrix equations. The second method is based on Newton's scheme and is quadratically convergent. To compare the three methods under consideration these methods are tested on a service problem.