（运筹学与控制论专业论文）拟生灭过程平稳分布的计算试验.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 排队论是运筹学最蕈要的分支之一，在各个领域都有着广泛的应用。近些年 来，随着科学技术以及数学学科的不断发展与创新，涌现出大量的复杂系统的设 计与控制问题。这同时也使得排队论的解决方法获得了很大的发展。拟生灭过程 ( q b d ) 正是解决此类复杂排队模型的强有力的工具。2 0 世纪7 0 年代以来，? e u t s 等系统地发展了矩阵分析方法，为复杂随机模型的分析提供了强有力的_ 丁具。这 样也就为具有这种特殊的矩阵几何解形式的q b d 过程的研究以及计算提供了非 常有力的t 具，推动了拟生灭过程在随机模型分析中的广泛应用。 本文主要以有限位相拟生灭过程为基础，首先就位相型分布、拟生灭过程以 及矩阵分析方法的基本理论做了概括总结。然后介绍了两类针对拟生灭过程的主 要的算法：基于矩阵几何解的算法类( 包括经典迭代算法、对数简约算法和循环 简约算法) 币口谱展开方法。对各种算法的理论基础给予了详细的解释。 本文主要的工作，就是对每种算法，给出了具体的算法结构，进而使用m a t l a b 软件，编写出程序实现。然后应用一个实际算例，进行了详细的数值试验，对上 述几种算法的计算有效性进行了对比。发现了系统不同参数的改变对算法的小同 影响，以及系统吖i 同参数的改变对排队系统的影响。进而将有限位相的算例推广 到无限位相的情形，发现了无限位相拟生灭过程不再保留有限位相拟生灭过程的 某些性质。 关键词：位相型分布，拟生灭过程，矩阵几何解，谱展开，反馈串联排队 2 0 0 4 年e 海大学硕士学位论文 a b s t r a c t q u e u i n gt h e o r yi so n e o ft h em o s ti m p o r t a n tb r a n c h e so ft h eo p e r a t i o n sr e s e a r c h i ti sv e r yu s e f u li nl o t so ff i e l d s i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n ta n di n n o v a t i o n o ft h e t e c h n o l o g ya n ds c i e n c e ，t h e r e c o m es om a n yc o m p l e xs y s t e m sd e s i g na n d c o n t r o lp r o b l e m sa n dt h i sa l s os t i m u l a t e st h ed e v e l o p m e n to ft h eq u e u i n gt h e o r y q u a s i b i r t h a n d d e a t hp r o c e s si se x a c t l y t h ef i g h ti n s t r u m e n tt os o l v et h e 5 ep r o b l e m s i nt h es e v e n t i e so ft h et w e n t i e t hc e n t u r y , n e u t sd e v e l o p e dt h em a t r i xa n a l y s i sm e t h o d a n dt h i sm a d et h ea n a l y s i so fs t o c h a s t i cm o d e l st ot h en e w s t a g eo fu s i n gp h a s et y p e t h i so f f e r e dt h ea n a l y s i so ft h ec o m p l e xs t o c h a s t i cm o d e l sv e r yu s e f u li n s t r u m e n t a n dt h eq u a s i - b i r t h a n d d e a t hp r o c e s sc o m b i n e dc l o s e dw i t ht h em a t r i xa n a l y s i s m e t h o db e c a u s eo fi t s s p e c i a l m a t r i x g e o m e t r y s o l u t i o n t y p e s o t h i s s t r o n g l y i m p u l s e st h eu s eo ft h eq u a s i b i g h a n d - d e a t hp r o c e s si n t h ea n a l y s i so fs t o c h a s t i c m o d e l s m y w o r km a i n l yb a s eo nt h ef i n i t ep h a s et y p eq u a s i b i r t h a n d - d e a t hp r o c e s s f i r s t i g i v e a g e n e r a l i z a t i o n o fp h a s et y p e d i s t r i b u t i o n ，q u a s i b i n h a n d _ d e a t h p r o c e s sa n dt h em a t r i xa n a l y s i sm e t h o d a n dt h e n ，g i v eav e r yc l e a r l yi n t r o d u c eo n t w ok i n d so fi m p o r t a n ta l g o r i t h m ，t h a ti st h ea l g o r i t h mb a s e do nt h em a t r i xa n a l y s i s m e t h o d s ( i n c l u d i n gt h ec l a s s i c a li t e r a t i o nm e t h o d ，t h el o g a r i t h mr e d u c t i o na l g o r i t h m a n dt h ec y c l i cr e d u c t i o na l g o r i t h m ) a n dt h es p e c t r a le x p a n s i o nm e t h o d m y m a i nw o r ki st og i v et h ep r o g r a mo fe v e r ya l g o r i t h mu s i n gm a t l a bs o f t w a r e o nc o m p u t e r a n dt h e n ，u s i n ga n e x a m p l e ，ig i v ea n e x a c te x p e r i m e n ta n dc o m p a r eo f t h ea l g o r i t h mi n t r o d u c e da b o v e ，if i n dt h ee f f e c tt ot h ea l g o r i t h ma n dt h es y s t e mw h e n s o m eo ft h ep a r a m e t e rc h a n g e da f t e rt h a t ，ie x t e n dt h ee x a m p l et ot h ei n f i n i t ep h a s e t y p ea n di f i n ds o m ed i f f e r e n tc h a r a c t e rb e t w e e nt h ef i n i t eq u a s i - b i r t h a n d - d e a t h p r o c e s sa n d t h ei n f i n i t eq u a s i b i r t h a n d d e a t hp r o c e s s k e yw o r d s ：p h a s et y p ed i s t r i b u t i o n ，q u a s i - b i r t h - a n d - d e a t hp r o c e s s ，m a t r i x g e o m e 田s o l u t i o n ，s p e c t r a le x p a n s i o n ， i i 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究 工作。除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已发表或撰写过的研究成果。参与同一工作的其他同志对本 研究所作的任何贡献均已在论文中作了明确的说明并表示了谢 意。 签名： 盔珥日期：垃芏! 厶 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许被查阅和借阅：学校 可以公布论文的全部或部分内容。 ( 保密的论文在解密之后应遵守此规定) 签 名衄导师签名： 2 0 0 4 年上海大学硕士学位论文 第一章绪论 1 1 排队论的发展 运筹学是一门独立的新兴学科，这早己为国际社会所公认。它和自然科学、 技术科学、社会科学都有密切的联系，具有很强的应用性。它的理论和方法在科 学管理、t 程技术、社会经济、军事决策等方面，有着重要的应用，并且已产生 巨大的社会与经济效益。在运筹学发展的几十年间，它的学科分支也在不断的扩 大，从甲期的所谓的运筹学二大支柱：规划论、排队论和对策论开始，到目前己 发展成线性规划、整数规划、图论、随机规划、可靠性、库存沦等等一系列的分 支。 排队论是研究服务系统中排队现象随机规律的一门运筹学分支，是运筹学最 重要的分支之一，又称为随机服务系统理论。它起源于早期对电话系统的研究， 并逐渐应用于社会生活的各个领域。2 0 世纪初丹麦数学家、电器工程师a 尼 e r l a n g ，应用概率论的方法研究电话通话问题，从而开创了这门应用数学学科， 并为这门新学科建立了许多基本原则。在第二次世界大战以前，其研究多侧重于 电话以及远距离通信方面，当时发展较为缓慢；在二战之后，由于排队论渗透到 军事、经济生产与服务和管理等多方面，于是在理论利应用上得到了较大发展， 在运筹学这个新领域中成了一个重要的研究内容。特别是2 0 世纪7 0 年代以来， 由于电子训算机技术的不断更新与发展、因特网的建立与完善以及信息科学与生 命科学等学科的发展均涉及到最优设计和最佳服务问题，从而使排队论在理论和 应用上获得质和量的发展。 排队论研究的内容主要是排队系统的各种数量指标以及系统的最优化。其中 排队系统的数量指标是排队论研究的主要内容，而系统的最优化问题则是我们研 究的最终目的。 2 0 实际5 0 年代初，口k e n d a l l 对排队论做了系统的研究，他用嵌入马氏 链的方法研究排队论，使排队论得到了进一步的发展。并首先用三个字母组成的 符号来简单的表示排队系统，也即我们现在所广泛使用的表示方法x y n 来表 示一个排队系统。其中表示输入所服从的分布，y 表示服务所服从的分布，n 2 0 0 4 年卜海 学硕士擘位论文 表示服务台的个数。从而使一个抽象的排队系统具体化。比如g i m i l 排队就表 示输入为一般独立分布，服务时间服从指数分布，只有一个服务台的排队系统。 1 2 排队论的研究方法 排队论的研究的方法多种多样。在经典的排队模型中，马氏性，也即“己知 现在，将来与过去无关”的性质发挥着重要的作用。随着科学技术以及数学学科 的小断发展与创新，涌现出大量的复杂系统的设计与控制问题。这些问题都不具 有马氏性。这些问题的出现，不仅为排队论的发展提供了进一步发展的动力，更 为排队论提供了新的解决思路和解决方法。如f h a 馏的阶段化方法，马氏更新过 程方法，向量马氏过程方法，骨架马氏链( 过程) 方法，矩阵分析方法 1 6 等等。 马氏更新过程方法是通过在非马氏的随机模型中嵌入马氏链，然后利用马氏 链的数学性质来对原模型进行分析的一种方法。在使用更新过程方法时，面对非 马氏模型，最重要的就是构造过程的再生点。这种方法被广泛的应用到各种排队 模型中。 向量马氏过程方法是解决非马氏模型的另一种方法。实际问题中，无法构造 出再生点的模型，我们可以通过增加补充变量，把非马氏过程通过扩维后成为向 量马氏过程，将随机模型转化为确定的密度演化方程来进行研究。我们可以在史 定华教授的专著 1 中见到有关向量马氏过程方法的详细叙述，并称这种方法为 密度演化方法。 施f s 教授创建并发展的矩阵分析方法 1 6 ，把简单的指数分布扩展到p h 分布，形成了一套非常有效的解决复杂排队模型的方法。并且这种方法，易于在 计算机上实现，方便得到各种排队系统的数量指标。目前这种方法已得到充分的 发展与推广。 1 3 位相型分布 对各种随机模型进行解析处理的主要障碍，是条件概率引起的高度复杂性。 广泛使用的方法是约定所涉及的变量服从指数分布，通过无记忆性绕过这一困 难。但是，这样一来，不仅大大缩小了所研究模型的范围，也极大的降低了模型 的应用价值。一方面，离开指数分布，定量的和定性的分析都面临实质性的困难， 2 0 0 4 午上海大学硕士学位论文 另一方面，假定所研究的随机变量服从指数分布，在多数情况下将与客观事实大 相径庭。这一直是随机模型分析中的突出矛盾。 寻求保持指数分布易于进行解析处理的优点，又能包罗更广新分布类的努力 可以追溯到占h a 月幽早期工作。他从指数分布的独立和出发构造了毋+ a 馏分布。 在此后漫长的岁月里，许多学者尝试过各种混合型分布，如广义e r l a n g 分布，超 指数分布等等。这些分布都具有有理函数拉普拉斯变换，这就推动了白联于有 理变换分布类的研究。但是幻扮布类又过于宽泛，失去了解析处理的优点。位 相型分布( 朋) 正是有理变换分布类中能较好保持指数分布方便性的一个子类。 p 分布是一个有限状态腑m o 废 程吸收时间分布。使p h 分布成为有力工 具的关键性工作是n e u t s 4 故出的。他系统的发展了j d _ 分布的矩阵表示和解析处 理技巧。册分布函数被表示成矩阵指数形式，相当于把指数分布从数值参数到 矩阵参数的一种推广。最后，p 仃分布的算法意义也是不容忽视得。它具有优良 的封闭性和稠密性，p 日分布甚至使得随机模型分析中的一些数值积分转化为简 单的矩阵计算。涉及p h 分布模型的指标，通常都容易编制有效的计算机处理程 序。 1 3 1j p _ 日分布的定义： 定义1 ( 连续硝分布) ：考虑有限状态空间e = 1 , 2 ，m ，m + 1 ) 上以m + 1 为 吸收态的马尔可夫过程 x ( t ) ：t 0 ) 。过程的无穷小生成元矩阵可以表示成如下 分块形式： q = k ：l ( 1 。1 ) 其中m 阶非奇异方阵t = ( 0 ) 满足瓦 0 ，瓦0 ，i _ ，ls f ，m t 。= ( 1 。，2 0 ，l o ) 是非负列向量，满足n + t 。= 0 。p 为适当维数的全l 列向量。 给定马氏过程的初始分布为( 口，口。) ，其中a = ( 口l ，口：，口。) ，满足 o e + a 。= l 。那么，马氏过程 x ( f ) ：t o 由初始状态出发，最终进入吸收状态 所需时间的概率分布为： f ( x ) = 1 一口e x p ( t x ) e ，x 0( 1 3 2 ) 由上式所定义的概率分布称为p h 分布，( 口，t ) 称为f ( x ) 的一个表示。 可以证明t 4 = t + ( 1 一口。) t o 口是m 阶生成元。若t + 是不可约的，称 2 0 0 4 年匕海大学硕士学位论文 ( 。，t ) 是不可约j p | 【，表示。我们用到p h 分布时，均假设幢，t ) 为不可约的。 定义2 ( 离散| p 分布) ：有限状态空间e = 1 , 2 ，m ，, 9 1 + l 上以m + 1 为吸 收态的马氏f f i x 。：月0 ) ，其转移概率矩阵为 p ： 目0 矿1l ( 1 s 3 ) il + 其中日为m 阶子随机矩阵，满足h i o ，h e e ，一h 非奇异，且胁+ h o = p 。 给定马氏链 x 。：n o ) 的初始概率向量为 ，a 。) ，o 留+ a 。= l ，则马氏 链 x 。：月o ) 由初始状态出发第k 步进入吸收状态的概率p 。，k 0 为： p o2 口m + 1 p j = a h h 0 ，女2 1 由上式定义的概率分布 p 。：k o t 斛b 离散p h 分布 1 3 2 p h 分布的基本性质： ( 1 3 4 ) m ，h ) 称为它的表示。 p h 分布除了保持了指数( 几何) 分布易于进行解析处理的优点，还有许多其 之良好的性质。 性质1 ( 运算封闭性) 1 】：若干个户h 分布的运算结果如卷积运算，有限混 和运算等，通常是一个新的p h 分布：含有p h 分布的随机模型，其指标通常也 服从p h 分布。封闭性在模型的理论分析和实际应用中都带来极大的方便。 性质2 ( 稠密性) 2 ：可以证明，p h 分布类在 0 ，。) 上一切概率分布的类中稠 密。这意味着，无论我们研究什么样的随机分布，总可以选择一个适、上的p h 分 布来代替它，并且使误差达到我们所要求的精度。 性质3 ( 补分布的渐进指数性) 1 】：对有表示( 口，t ) 的连续p h 分布f 倒，若r 不 可约，则有： f ( j ) 寸k e 一，x _ o o( 1 3 5 ) 其中，k = 鲫，v 是r 的具有最大实部特征值一7 1 所对应的右特征向量，它可以唯 一的由“v = u e = 1 确定，“是r 的具有最大实部特征值一玎所对应的左特征向量。 1 4 拟生灭过程 n e t t t s 教授在他的两本专著( 1 9 8 1 ，1 9 8 9 ) 1 6 2 0 ，详细的研究了两类重要的 4 2 0 0 4 年上海大学硕士学位论文 排队模型，即m g 1 型排队和g ，m 1 型排队，而可以用拟生灭过程描述的排 队模型正是这两类排队模型的特例。拟生灭过程( q u a s i b i r t ha n d d e a t hp r o c e s s ， 简记为d ) 首先由w a l l a c e 和e v a n s 教授提出的。q b d 过程实际上就是一个二 维马氏链，其状态的转移只可以发生在相邻的两个水平之间。q s d 过程在解决 诸如肘p 日门，p h m l m a p p h 1 等类型的排队模型时，是一个非常重要的 t 具。而且n e u t s ( 1 9 8 1 ) 1 6 等系统的发展了处理q b d 的矩阵分析方法，目前已 得到广泛的发展与应用。 1 4 1 拟生灭过程的基本概念 考虑二维马氏链x = ( ，。，j 。) ；n 0 t 状态空间e = ( 女，j ) ：= 0 , 1 2 ； j = 0 , 1 2 ，m ，其中前一个变量k 称为水平，后一个变量，称为位相。若链的转 移概率矩阵p 有如下分块三对角形式： p = 战a o c lb l c ， cb 。a 。 ( 1 4 1 ) 一般情况下， a 。，吼和c 。均为非负m 十1 阶方阵， 且 ( 玩+ 心) b = ( c + b + a 。) p = e ，k ! l ，则称 ，。 为一个拟生灭过程。其中： a 。中的元素表示从状态( 女，j ) 到状态( 女+ 1 ，f ) 的水y d nl 的一步向上转移概 率。 吼中的元素表示水平4 i 变，状态从( i ，) 到( t ，) 的转移概率。 c 。中的元素表示从状态( 女) 到状态( k l ，d 的水平减1 的一步向下转移概 率。( 0 j ，s m ，k = 0 , 1 ，2 ，) 。 若状态空间中m 为有限的，即其中的矩阵块a 。、b 。和c 。均为有限维矩阵块， 则称之为有限位相拟生灭过程；若m 为无限的，则称之为无限位相拟生灭过程。 日前在处理无限位相拟生灭过程的问题上，还存在着很大的困难，很多问题有待 解决。本文主要讨论有限位相的拟生灭过程的性质及其算法。 形如( 1 4 1 ) 的转移概率矩阵p 的一般有限位相q n d 过程，若转移概率矩阵p 2 0 0 4 年h 海大学顺十学位论文 中的子块从某一个水平j c 时开始不再发生变化。过程的转移概率矩阵如下 b oa o c b 爿 c lb 。一l c 4 占爿 cba ( l 4 。2 、 巳 爿，2 一，j c l b i2 b ，j cc j = c ，j c ( 1 4 3 ) 此时，称之为水平独立的q s z ) 过程，独立水平为c 。对于此类的q s d 过程，已 经建立起了相对比较完善的解决方法即由n e u t s 教授发展的矩阵分析方法 1 6 】。 否则，称之为水平相依的。水平相依的q b d 过程，存在许多复杂问题有待解决。 迄今为止，广泛使用的为上述的水平独立q b d 过程。 上述的水平独立的q b d 过程，如果从水平i 开始，各水平就独立，即c = l ， 就称过程具有简单边界。否则，称过程具有复杂边界。下面以复杂边界水平独立 的有限位相d 过程为基础，来讨论q b d 过程的性质及其平稳分布z 的算法。 记 z # 2 熙j d ( ，。= t ，j 。= n k = 0 , 1 2 一；= 0 , 1 2 ，m ( 1 4 4 ) 口i = ( f ，石，z 女。) ，k = o ，l 2 ( 1 4 - 5 ) e = ( 庀o ，z l ，z ，)( 1 4 6 ) 假定q s z ) 过程正常返，且由水平c 开始各水平独立。由平衡方程1 r p = 口， 以及过程的转移概率矩阵的特殊结构，7 r k 满足如下矩阵方程组： 当k = 0 ，i ，2 ，c 一1 时，有： ，r 女一【a 女一l + 万 b + 开 + j c k + i = 开女 ( 1 4 7 ) 当k c 时，有： 石 一l a + 石b + 丌“l c = 刀女 ( 1 4 8 ) 进一步，平稳分布7 的所有分量的概率之和应该为1 ，也即： 7 ( k e = 1 ( 1 4 9 ) 6 2 0 0 4 年上海人学硕士学位论文 1 4 。2 矩阵几何解 在n e u t s 引进j d _ h 分布以后，使得原来在指数分布假定下才能分析的很多随 机模型推广到j d h 分布的情形。从而使得他所发展的矩阵分析方法得到了广泛的 应用。他的两本专著( 1 9 8 1 ，1 9 8 9 ) 1 6 】 2 0 】是关于这一方法的理论基础和应用的代 表作。而拟生灭过程具有的特殊的矩阵几何解形式有力的推动了拟生灭过程在 随机模型分析中的广泛应用。 定理1 ( 矩阵几何解) ：转移概率矩阵p 形如( 1 4 2 ) 的复杂边界妒d 过程 ，。，j 。) ，若过程正常返则过程的平稳分布具有矩阵几何解形式，也即平稳分 布向量以可以表示为如下形式： 致= f 。r “，k c( 1 4 1 0 ) 其中矩阵r 为矩阵方程 r = 尺2 c + r 占+ a f 1 4 1 1 ) 的最小非负解。 z 0 - 丌 唯一确定。 ，z 。由方程组 i ( ，r o ，万”，厅。) b 月 = ( 石o ，石 ，_ 7 r 。) 1 c - 1 凡叶硝，_ r ) ：l o 4 1 2 ) lk = o b r 】 吼a o c lb l a c 。一ib 。一【a 。一1 c r c + b ( 1 4 1 3 ) ( 1 ，4 】0 ) 是初等几何分布从数值参数到矩阵参数的推广，因此称这类分布为矩阵 几何解 1 6 】。帝 旦能解得率矩阵r ，由( 14 1 0 ) 式，那么平稳分布各分量月。就可以由口，表 示出来。再由方程组( 1 41 2 ) i k 算出唯一解，以，就可得到平稳分布。 矩阵方程( 1 4i l ) 的最小非负解r 称为率矩阵。并且，n e u t s 对率矩阵r 给出 了其概率解释。即r 中的元素r ( k ，j ) 表示从状态( f ，女) 出发，到再次访问水平状 态i 之前，访问：状态( f + 1 ) 的平均次数，其间决不访问i 以下的水平状态，并且 2 0 0 4 年上海大学硕士学位论文 数值不依赖于i 。在之后的研究中，率矩阵r 是一个非常重要的数量指标。 以上的讨论，均是在q b d 过程正常返的条件下进行的。如何来判定过程是 否正常返呢? 这是人们需要解决的一个首要问题。n e u t s 给出了一个判定有限位 相q b d 过程正常返的充要条件，也称为稳定性条件 1 6 。 定理2 ( 稳定性条件) ：有限位相q b d 过程正常返，当且仅当过程的率矩阵 r 的谱半径s p ( r ) l 。 证明：由率阵r 的概率意义，我们知道，若过程从水平0 开始，则过程在返 回水平0 时，访问水平1 的平均次数为r e ，访问水平2 的平均次数为r 2 e ， 访问水平n 的平均次数为：r 1 e 。则在返回水平0 时，访问所有状态的平均次数 为：yr 1 e 。链是正常返的当且仅当返回平均次数有限。因为由r 矩阵的概率 意义，r 为非负阵。r “p 有限当且仅当印( r ) x a e 。 反之，亦成立。 # 另外，人们还发现：一个正常返有限位相q b d 过程的平稳分布，是随着水 平的增加而几何衰减的，其衰减率就是n e u t s 教授所提出的率矩阵r 的谱半径 s p ( r ) 。过程的衰减率也是一个非常重要的数量指标，有助于我们了解过程平稳 分布的渐进性质。 1 5 本文所作工作简述 q b d 过程是解决复杂排队问题的强有力的工具，日前已得到广泛的应用与 发展。许多学者己对q b d 过程进行了多方面的探索与研究。我们知道，q b d 过 程的平稳分布具有矩阵几何解的形式，n e u t s 教授引进p h 分布，并深刻的发展 了矩阵分析方法，这样就为具有这种特殊结构的q 日d 过程的研究以及汁算提供 了非常强有力的工具。许多学者就已经提出了很多q b d 过程的计算方法。 本文第二章，对q b d 过程的广泛使用的几种算法做一简介与综述，给出它 们的理论基础以及算法结构，并使用m a t l a b 软件编程实现。第三章，通过一个 实际的算例，进行详细的计算试验，对第二章中所介绍的几种主要算法的计算复 杂性、稳定性和有效性做一比较。并且研究了系统各参数的变化对平稳分布与衰 减率的影响。第四章，则将有限位相拟生灭过程推广到无限位相的情况，通过一 个实际算例，研究了无限位相拟生灭过程平稳分布的计算以及衰减率的性质与有 限位相时的不同。并且发现截尾计算会产生很多的奇异现象。 2 0 0 4 年上海大学硕士学位论文 第二章计算方法 帚一早 丌畀力泫 近些年来，随着科学技术以及数学学科的不断发展与创新，涌现出大量的复 杂系统的设计与控制问题。这就使得模型的描述变得非常的复杂，系统的数量指 标的计算，必须借助计算机才可能完成。因此各种汁算方法的研究，成为了一个 非常重要的研究方向。 目前，最常用到的计算方法主要有两类；一是基于矩阵分析方法的算法：二 是谱展开方法的算法。本章就对这两类主要的算法的理论基础做一简介，并给出 算法结构。 2 1 基于矩阵分析方法的算法 通过上面的分析我们可以看出，率阵r 在矩阵几何解方法中，占有非常重 要的地位。求解出了率阵r ，很多数量指标就可以得到解决，如过程的平稳分布， 过程的衰减率等。本节，我们就将对目前部分文献中介绍的矩阵几何解方法中率 矩阵r 的常用计算方法，做一简要的介绍。 2 1 。l 经典迭代方法 n e u t s 教授在他的著作 1 6 1 已提出了一种非常直接而简单的迭代方法计算 率阵月，即： r ：r z c + r 。b + a r o = 0 ，n = o ，l 一2 ( 2 1 1 ) 我们称之为简单迭代算法，简记为s 1 ( s i m p l ei t e r a t i o n ) 算法。 这种算法计算耗时大，稳定性较差。于是如何提高算法的有效性，就成了一 个重要的研究课题。许多学者在n e u t s 教授的算法基础上，提出了很多经过改良 的算法。如 7 ： ( 1 )r 。= ( 爿+ r n2 c ) ( 卜- 占) “( 2 1 2 ) ( 2 )r 。a ( tb 最。c ) 。( 2 一3 ) 等等。 根据上述迭代方法，求得率阵尺后，由方程组( 1 4 1 2 ) 以及 巩= 口。r “。，k c ，即可求得平稳分布。 2 0 0 4 年卜海人学硕士学位论文 这些算法都没有引入任何的辅助矩阵，而是简单的直接迭代汁算率阵r ，收 敛性质与稳定性质较差。之后发展的算法，大多都是引进了各种辅助矩阵，经过 某些变换而构造的算法。如下面的这种利用定义出的g ，尺，u 矩阵的关系所 构造的算法。 三个矩阵分别为下述三个矩阵方程的最小非负解： g = c + b g + a g 2 月= a + r b + r2 c ( 2 1 4 ) u = b + a ( i u 1 1 c 且g ，r ，u 矩阵有如下的关系 1 4 ，2 4 】： g = ( ，一u ) 一1 c r = a f t u ) 。 ( 2 1 5 ) u = b + a g = b + r c 并且三个矩阵有具体的概率解释 1 4 ： g ( i ) 表示链从状态( 1 ，i ) 出发，以访问状态( o ) 返回水平0 的概率。 r ( i ) 表示链从状态( o ，f ) 开始，首次返回水平0 之前访问状态( 1 ，j ) 的平均 次数。 u ( i ) 表示从状态( 1 ，i ) 出发，以访问状态( 1 ，j ) 返回到水平1 但决不访问水 、p0 的概率。因此，这是一个禁忌概率( t a b o op r o b a b i l i 朔。 所以基于。【二述三矩阵的相互关系，可以构造如下计算尺矩阵的算法，算法的 大致结构如下。 步骤1 令u o = b ，r o = a ( i u 。) ； 步骤2 利用u = b + a ( i u 。) c ，r 女= a ( i u 。) “构造一个循环迭代，直至 两次迭代得到的r 值的差的范数满足l i r 。一r 。i l ，而求得率阵r 。 步骤3 由方程组( 1 4 1 2 ) 以及巩= 丌。rk - c ，k c ，即可求得平稳分布。 上述算法以u 矩阵做为辅助矩阵，构造迭代求解尺，所以我们称上述算法为 u 矩阵迭代算法，简记为u i ( ui t e r a t i o n ) 算法。 2 1 2 对数简约算法( l o g a r i t h m r e d u c t i o n a l g o r i t h m ) 上面所给出的算法，每次迭代过程所允许访问的水平只能增加l ，而且过程 所访问的水平内的所有的状态均要计算，是线性收敛的。l a t o u c h e 和r a m a s w a m i 2 0 0 4 年卜海大学硕士学位论文 在上述算法的基础上，进一步做了深入的研究，允许在每次选代时，过程所访问 的水平可以成倍增加，因此可以有效减少迭代次数，提出了一种收敛速度和性质 更好的算法 9 ，1 4 ，1 7 】。 如果我们假设u 矩阵迭代算法的总迭代次数为，那么由l a t o u c h e 和 r a m a s w a m i 构造的新的算法的总迭代次数则为l o g ：，。次，也即相对于u 矩阵迭 代算法，迭代的次数成对数级减少，因此称这种算法为对数简约算法，简记为 l 尺算法。而且，作者在文献 t 4 1 中严格证明了他们的算法为二次收敛的。 以肖表示以p 为转移概率矩阵的q b d 过程，记过程y 为观察x ，只有当水 平发生改变时，产生的新的过程。易知，产生的新的过程，。也是个q b d 过 程转移概率矩阵为： 只= 0 v o 胍0矿 其中， l = ( ，一旦) a ： v ”= f ，一b 1 1 4 且两个过程的6 矩阵是相同的， 对新产生的过程r ，有 k 一， 0 矿( 。1 ( o 0旷。 彬= ( ，一鳓“c ，0 i c w ( o = f ，一日1 1 c ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) g = ( 0 j + 矿( o ) g 2 f 2 1 9 ) 显然，如果可以求解出g 2 ，就可以求解出矩阵g 。 这里，( g 2 ) 。表示链从状态( 2 ，i ) 出发，以访问状态( o ，j ) 返回水平0 的概率。 根据矩阵g 的此概率意义，考虑一个新的过程y “，为观察过程y 只在访问偶数 水平即访问水平0 ，水平2 ，水平4 时产生的过程。易知，此过程y ”也是一 个q b d 过程，转移概率矩阵为： ! ! 坚王! 塑叁兰坚主兰堕堕兰一 b d c 、 a o 0 b 、ma l c 一1 ”b 一i a ” c b “a ” c “b ”a ( 2 1 1 0 ) 其中c ( = ( wc 。) 2 ，b ( ”= 矿【。+ y 叭，a 1 = ( 矿) 2 。 设这个新的过程y ( t 的g 矩阵记为g ”。则g 0 ) 为下述矩阵方程的最小非负 解： g 0 ) = c ( 1 + b i g 1 + 爿“( g 1 ) 2 ( 2 1 1 1 ) 令：( i - 占- 1 ) 一- c n ，v ( - ) ：( ，一b ) 4 “。按着( 2 1 9 ) 的格式，可以将上式化 为： g o ) ：w o ) + 矿( 1 1 ( g 1 1 2 ( 2 1 - 1 2 ) 囡为g ”：g ：，所以结合( 21 9 ) ( 2 1 1 2 ) 两式，得： g ( n = 0 1 + 矿( 0 1 十v ( m v ( g ”) 2 ( 2 ，1 t 3 ) 因为( g ) ：g 。同理，再次运用矩阵g 得概率意义，构造一个新的过程 y n ，为观察过程只访问水平0 ，水平4 ，水平8 一时产生的新过程。重复上 述步骤。最后可得g 矩阵的一个精确表达。： g = 三( 囊缈 ( 2 1 1 1 4 ) 其中， 矿( o ) = ( ，一占) 一1 a o = ( ，一b ) q c 矿。+ 1 ) = f ，一矿( w 一。v ) i ( 矿) 2 “1 ) = ( ，一矿( 矿忡一w 2 v ) 一1 ( 社) 2 由上述迭代关系式，可构造算法如下 步骤1 令 ( 2 1 1 5 ) ( 2 1 。1 6 ) ( 2 1 1 7 ) 2 0 0 4 年上海大学硕士学位论文 v o = ( 一占) 爿 2 ( 7 一c f 2 1 1 8 ) g o = w 0 、 r o = g o 步骤2 构造循环迭代： h t = 吸+ 吼吒 圪+ ，= ( ，一h ) 。以2 + i = ( ，一h 。) 。畎2( 2 1 1 9 ) g = g k + 瓦“ 疋+ ，= 五圪+ 直至两次迭代得到的g 矩阵的差的范数满足| | g 。一g 。 s 。 步骤3 利用u = b + a g ，r = 爿( ，一1 求得率阵r 。 步骤4 由方程组( 1 4 1 2 ) 以及以= z 。rk - c ，k c ，即可求得平稳分布。 2 1 3 循环简约算法( c y c l i c r e d u c t i o na l g o r i t h m ) 由b i n i 和m e i n i 共同发展了一种新的算法，称为循环简约算法 7 】 1 1 】，简记 为c r 算法。我们的目的是要求解矩阵方程 r = rz c + r 日十a ( 2 1 2 0 ) 的最小非负解。上述方程可以转化为如下矩阵方程形式： i b i b i b i b ，t o = = ( a 0 0 )( 2 1 2 1 ) i b l b i b ( 2 。1 2 2 ) i 一8 z篇。 譬 r凸= 陋 p啦pp 4 = 吣 矿疋 吣 吣 正z ，j飞 只r 得 r ： 序 | _ 阵 排 驴 矩 删 删 重 曩 中 偶 其 奇 出 按 导 式 推 上 易 对 容 ! ! 竺兰圭堡叁兰竺主兰堡堡墨 w o 一爿 一c一爿 一c 一4 一c 一爿 z o ) = c一爿 一c一爿 一c一爿 一c 展升( 2 1 2 2 ) ， f ( r ，r 3 , r5 r ) 正o + ( r2 ，r 4 ，尺。r ) z o = ( 彳，0 0 ) 【( r ，r 3 , r 5 ，一) 弦7 。+ ( r 2 ，r 4 , r6 ) 疋叭= ( o ，0 0 一) 对f 21 2 3 ) 运用一次高斯消去，消去( 尺2 ，r4 ，r 6 ，) 得： ( j r ，r 3 ，r 5 ) ( 正”一w ( 疋) 一1 z t o ) ) = ( 爿，0 ，0 ) 令 ( ”= 五”一w o ( 疋) + 1 z o 则 h m = ( ，一b ) 一( )一a ( z 一尽) 1 爿 一c ( 1 一口) 。c( ，一b ) 一( 4 ) 一a ( i 一占) “爿 一c ( 一b ) 。c ( 一b ) 一( + ) 一a ( i 一_ b ) 1 a c ( i 一占) “c ( ，一b ) 一( + ) f 2 1 2 3 ) ( 2 1 2 4 ) r 2 1 2 5 ) f 2 1 2 6 ) 其中( + ) 表示：c ( 1 一b ) “a + a ( i 一占) “c 。 - 将( 2 12 6 ) 代入( 2 1 2 4 ) 所得的矩阵方程，并令 a = a ( t 一日) 一1 a b ”= b + ( + )c = c u 一占) 一1 c( 2 1 2 7 ) 得： = ( a ，0 0 ) ( 2 1 2 8 ) ( 2 1 2 8 ) - 与( 2 1 2 1 ) 结构完全相同。所以重复上述步骤，最后可得 f 兄r2 协r 2 廿 一爿f ，1 i b ( ，)一a j 一c i b l i = ( a 0 0 ) 4 f“一 篇 钿 一卜 一 出 n ii110 v rr “ 门 雪 卜 一 ，u? 2 0 0 4 年上海大学砸十学盥论文 f 2 1 2 9 ) 在蕈复上述步骤过程中，我们可以发现，其中的爿，c ，”，分，有明显的迭代 结构： 展开( 21 2 9 ) ，其中第一个方程为： r ( 1 一台j ) 一r 1 4 ，+ 1 c = a ( 2 1 3 1 ) 冈为s p ( r ) 1 ，当迭代次数足够大时，r 2 。“jo ，_ m 。所以 r ( ，一b ) 一a _ o ，_ 。o 故当迭代次数足够大时，只需求得雪c ”，就可以以a ( i 一言) 。1 作为率矩阵r 的 近似值： r r 爿( ，一分，) ，_ o 。 ( 2 1 3 2 ) 算法结构如下： 步骤1 令一( =