  We present some accelerated variants of fixed point iterations for computing
the minimal non-negative solution of the unilateral matrix equation associated
with an M/G/1-type Markov chain. These variants derive from certain staircase
regular splittings of the block Hessenberg M-matrix associated with the Markov
chain. By exploiting the staircase profile we introduce a two-step fixed point
iteration. The iteration can be further accelerated by computing a weighted
average between the approximations obtained at two consecutive steps. The
convergence of the basic two-step fixed point iteration and of its relaxed
modification is proved. Our theoretical analysis, along with several numerical
experiments show that the proposed variants generally outperform the classical
iterations.
