马尔可夫链平均首达时间的计算

发布时间：2021-01-31 01:12

　　众所周知,平均首达时间是有限马尔可夫链的要素之一,被广泛应用于宏观和微观网络的动态性能研究.因此,其理论表达式和数值计算一直是国内外学者的研究方向之一.对于有限不可约马尔可夫链,设计有效的方法来计算平均首达时间显得尤为重要.这类计算问题已有秩一更新、有限计算、解析表达式和多项式迭代等计算方法.除了迭代法,其他方法都与转移矩阵的广义逆-群逆有关.本论文对有限不可约马尔可夫链的平均首达时间计算问题,给出了新的有限算法和迭代算法.首先,构造有限算法.通过降维,将马尔可夫链转移矩阵群逆的计算转为若干方程组求解问题,然后直接构造平均首达时间矩阵.其次,构造迭代算法.主要想法是依据平均首达时间的定义方程,将平均首达时间的计算问题归结为一系列收敛或半收敛的线性方程组的求解问题.主要构造了两类迭代算法.第一,基于这类线性方程组,构造了一类无参数迭代法,然后证明了其半收敛性,并给出了解的显式表示.第二,基于这类线性方程组,构造了Krylov子空间类迭代算法,并证明了这类算法的收敛性,也给出了解的显式表示.最后,若干个数值例子对经典算法和我们构造的迭代格式作了比较分析,同时也验证了这些迭代法的有效性和稳定... 

【文章来源】：南京师范大学江苏省 211工程院校

【文章页数】：55 页

【学位级别】：硕士

【部分图文】：

图５－１时间??－－??

１２３４５６７８９??图５－２误差??由图５－１和图５－２所呈现出的结果，我们发现两种方法在误差方面相差不大，??属于同一误差级．在时间方面，测试矩阵的阶数越大，含参迭代法所花的时间??快速增加，而且比无参数迭代法所花的时间多得多．也就是说在同等条件下，??无参数迭代法不仅能够快速达到收敛效果，并且能够保证算法的高精度．??注我们对算法ＡＬ１－ＡＬ６也作了数值试验，结果表明，当ｎ?＞?４００后，这类算??法收敛非常慢，且误差也比较大．因此，下面我们不再将这类算法用来比较．??５．２预处理Ｋｒｙｌｏｖ子空间类迭代法??由上一小节可知，尽管无参数迭代格式收敛，但往往巧的（特征值）谱半径??接近于１或等于１．当Ｐ（只）＜?１时其收敛往往比较慢，再加上可能有的坏条件??数

图５－３时间??


本文编号：3009934