A FAST NEWTON%26apos;S ITERATION FOR M/G/1-TYPE AND GI/M/1-TYPE MARKOV CHAINS

作者：Perez Juan F; Telek Miklos; Van Houdt Benny^*

来源：Stochastic Models, 2012, 28(4): 557-583.

DOI：10.1080/15326349.2012.726038

• Markov chains
• Matrix-anaytic methods
• Newton iteration
• Numerical methods for Markov chains

In this article we revisit Newton%26apos;s iteration as a method to find the G or R matrix in M/G/1-type and GI/M/1-type Markov chains. We start by reconsidering the method proposed in Ref.([15]), which required O(m(6) + Nm(4)) time per iteration, and show that it can be reduced to O(Nm(4)), where m is the block size and N the number of blocks. Moreover, we show how this method is able to further reduce this time complexity to O(Nr(3) + Nm(2)r(2) + m(3)r) when A(0) has rank r %26lt; m. In addition, we consider the case where [A(1)A(2) ... A(N)] is of rank r %26lt; m and propose a new Newton%26apos;s iteration method which is proven to converge quadratically and that has a time complexity of O(Nm(3) + Nm(2)r(2) + mr(3)) per iteration. The computational gains in all the cases are illustrated through numerical examples.

• 出版日期2012