Markov链的迭代解法

摘要

迭代法求解线性方程组起源于十九世纪上半叶，首先由Gauss、Jacobi和Seidel等人对其进行研究。-个多世纪以来，迭代法一直是求解线性方程组的主要方法之一。近些年来，求解奇异线性方程组的迭代法越来越受到人们的重视，并为许多计算数学工作者研究，尤其是针对Markov链的平稳概率向量的计算问题【5，9，14，17,20，21，22】然而，由于矩阵的奇异性所带来的复杂性，迭代法的许多问题都未能得到很好解决.例如，如何通过矩阵分裂构造新的迭代法、已有的矩阵分裂和迭代法的半收敛条件和收敛速度、一些经典迭代法和外推迭代法的最佳参数问题、在实际使用迭代法时如何建立可行的停机准则并估计近似解的误差界等。 　因为易于并行计算等原因，Schwarz方法在科学计算和工程的很多领域得到了广泛应用【4，11，13，16】。但是，Schwarz方法仅局限于求解非奇异线性方程组。近来，I Marek等【9】第一次将Schwarz方法引入了奇异线性方程组的求解问题.然而，由于没有引入其它参数和定义等原因，他们提出的方法对于分裂阵和迭代阵的要求过于严格。 　本文一方面在文献【9】的基础上，利用Drazin逆给出了拟非负分裂的定义，对分裂阵的要求由非负型分裂推广到拟非负型分裂。研究了Markov链的加性Schwarz迭代的收敛性及其它性质，使这种方法更具实用性.另一方面，对一种实用的加速迭代方法-Chebyshev加速方法做了系统研究，讨论影响该加速方法加速效果的几种因素。 　本文共分四章。第一章，给出了Markov链的有关概念和所需计算统计量-Markov链的平稳概率向量。第二章，我们给出了求Markov链平稳概率向量常用的迭代法，其中包括幂法、Jacobi迭代和Gauss-Seidel迭代、块Jacobi方法和块Gauss-Seidel方法以及Schwarz迭代。并给出了加性Schwarz迭代算法。第三章，研究了Markov链加性Schwarz迭代的半收敛陛，主要结果是：若A=I-B，B∈Rn×n是不可约列随机阵，令p>1为正整数，A=Mi-Ni为拟非负型分裂且pΣi=1EiTi≥pΣf=1(E)iTi(或EiTi≥(E)iTi),i=1，2…,p当θ<1/q时，则加性Schwarz迭代阵Tθ半收敛.本章还证明了全解迭代阵的收敛定理.第四章，对于Chebyshev加速方法做进一步的研究，在迭代矩阵是亏损阵的情况，讨论影响Chebyshev加速方法的加速效果的几大因素，结论表明，如果迭代矩阵的特征值分布不理想，或迭代矩阵的特征值的指标大，或迭代矩阵的Jordan基矩阵病态时，都会对Chebyshev加速方法的加速效果产生较大的影响。

目录

文摘

英文文摘

声明

第一章理论基础及需要解决的问题

§1.1 Markov链

§1.2离散和连续时间Markov链

§1.3所需计算统计量-Markov链的平稳概率向量

第二章基本迭代方法

§2.1幂方法

§2.2 Jacobi方法和Gauss-Seidel方法

§2.3块Jacobi方法和块Gauss-Seidel方法

§2.4 Schwarz方法

第三章 Markov链加性迭代解法的半收敛性

§3.1引言

§3.2预备知识

§3.3Markov链的加性Schwarz锄的半收敛

§3.4粗网格校正

第四章Chebyshev加速方法的收敛速度

§4.1引言

§4.2若干记号和引理

§4.3Chebyshev 加速方法

§4.4Chebyshev加速方法的收敛性

参考文献

致谢