（概率论与数理统计专业论文）markov链的迭代解法.pdf

m a r k o v 链的迭代解法 摘要 迭代法求解线性方程组起源于十九世纪上半叶，首先由g a u s s 、 j a c o b i 和s e i d e l 等人对其进行研究个多世纪以来，迭代法一 直是求解线性方程组的主要方法之一近些年来，求解奇异线 性方程组的迭代法越来越受到人们的重视，并为许多计算数学 工作者研究，尤其是针对m a r k o v 链的平稳概率向量的计算问 题【5 ，9 ，1 4 ，1 7 ，2 0 ，2 1 ，2 2 然而，由于矩阵的奇异性所带来的复杂性， 迭代法的许多问题都未能得到很好解决例如，如何通过矩阵 分裂构造新的迭代法、已有的矩阵分裂和迭代法的半收敛条件 和收敛速度、一些经典迭代法和外推迭代法的最佳参数问题、 在实际使用迭代法时如何建立可行的停机准则并估计近似解的 误差界等 因为易于并行计算等原因，s c h w a r z 方法在科学计算和工程 的很多领域得到了广泛应用【4 ，1 1 ，1 3 ，1 6 】但是，s c h w a r z 方法仅 局限于求解非奇异线性方程组近来，i m a r e k 等【9 】第一次将 s c h w a r z 方法引入了奇异线性方程组的求解问题然而，由于没 有引入其它参数和定义等原因，他们提出的方法对于分裂阵和 迭代阵的要求过于严格 本文方面在文献【9 】的基础上，利用d r a z i n 逆给出了拟非 负分裂的定义，对分裂阵的要求由非负型分裂推广到拟非负型 分裂研究了m a r k o v 链的加性s c h w a r z 迭代的收敛| 生及其它l 生 质，使这种方法更具实用性另一方面，对一种实用的加速迭 代方法一c h e b y s h e v 加速方法做了系统研究，讨论影响该加速 方法加速效果的几种因素 m a r k o v 链的迭代解法 i i 本文共分四章第一章，给出了m a r k o v 链的有关概念和所需 计算统计量一m a r k o v 链的平稳概率向量第二章，我们给出了 求m a r k o v 链平稳概率向量常用的迭代法，其中包括幂法、j a c o b i 迭代和g a u s s - s e i d e l 迭代、块j a c o b i 方法和块g a u s s - s e i d e l 方法以 及s c h w a r z 迭代并给出了加性s c h w a r z 迭代算法第三章，研究 了m a r k o v 链加性s c h w a r z 迭代的半收敛陛，主要结果是：若a = i - b ，b 舻n 是不可约列随机阵，令p 1 为正整数，a = 舰一m 为拟非负型分裂且妻最噩妻最正( 或最互k i t , ) ，i = 1 ，2 ，p 当p 1b eap o s i t i v en u m b e r ，a = 尬一mi sq u a s i - n o n n e g a t i v es p l i t t i n g sa n d 圭e 互壹e i t i ( o r 晟正或互) ，i ：1 ，2 ，p 、v h e np ；1 ，t h ee 互 晟正邑互) ，= ，2 ， 、v h e np i ， l = 11 2 i t e r a t i v em a t r i xo ft h ea d d i t i v es c h w a x zi t e r a t i v et oi ss e m i c o n v e r g e n c e a n d w ea l s op r o v et h a tt h et h e o r yo fi t e r a t i v em a t r i x e x a c ts o l v e s i nc h a p t e r4 ， t h i sc h a p t e rd i s c u s s e st h ec o n v e r g e n c eo ft h ec h e b y s h e va c c e l e r a t i n gm e t h o d s i nc a s et h ei t e r a t i v em a t r i x sa x ed e f e c t i v e t h er e s u l t ss h o wt h ec h e b y s h e v a c c e l e r a t i n gm e t h o d sa x el i k e l yt oc o n v e r g es l o w l yw h e n e v e ro n e o ft h r e ec a s e s o c c u r s ：t h ei t e a t i v em a t r i x si sd e f e c t i v e ，t h ed i s t r i b u t i o no fi t ss p e c t r u mi sn o t f a v o r a b l e ，o rt h ej o r d a nb a s i so ft h ei t e r a t i v em a t r i xi si l l - c o n d i t i o n e d k e yw o r d ：s c h w a x zm e t h o d ；m a x k o vc h a i n s ；q u a s i - n o n n e g a t i v es p l i t t i n g s ； c h e b y s h e va c c e l e r a t i n gm e t h o d s ；c h e b y s h e vp o l y n o m i a l s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果本人在论文写作中参考的其它个人或集体的研究 成果，均在文中以明确方式标明本人依法享有和承担由 此论文而产生的权利和责任 声明人( 签名) ：驴广振 稠年朝? 泊 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论 文的纸质版和电子版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆被查阅，有权将学位 论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版。保密的学位论文在解密后适用本规 定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) 。 ( 请在以上相应括号内打“ 力) 作者签名。即j 广掘 新獬。一 日期硼年明纠日 嗍3 歹瓣 m a x k o v 链的迭代解法 第一章理论基础及需要解决的问题 1 1m a r k o v 链 m a r k o v 链是m a r k o v 过程的个具体情况，而m a r k o v 过程则是满足 某种需要的随机过程随机过程是指在指示参数t 指示的给出概率空间 上的随机变量族 x ( t ) ，t t ) ，这里t 属于某个指示集( 参数空间t ) 般来说，指示t 的取值范围为( 一，+ o 。) 在应用中，指示集t 作 为系统观察到的时间点集，即随机变量的指示t 定义为x ( t ) 所取观察 值的时间点在这种情况下，指示t 的取值范围为 0 ，+ o o ) 令 x ( t ) ，t t 】为定义在时间指示参数t 指示的给定概率空间的随 机过程如果系统所取为时间点t o ，t - ，t n 上的观察值z n 且 t o t l t n 随机过程 x ( 亡) ，t t ) 具有m a r k o v 性的充要条件为 p x ( t ) z l x ( t o ) = x o ，x ( t 1 ) = t , 1 ，x ( t 竹) = x n ，) = p x ( t ) x l x ( t n ) = z n m a r k o v 链是状态空间离散的m a r k o v 过程，在m a r k o v 链的术语中， 个链的状态空间一般与自然数集联系在一起换句话说，这个状态指 状态0 ，状态1 等等 当随机过程加上基于随机变量和指示参数( 即m r a k o v 性) 的某个 条件时，这个过程被称为m a r k o v 过程类似地，根据m a r k o v 链的时 间指示集和状态空间特性可以将m a r k o v 链分为同质m a r k o v 链和异质 m a r k o v 两种 在同质m a r k o v 链中，系统的转移概率与时间参数t 独立m a r k o v 性 要求步转移概率与这个过程以前的历史状态独立然而，在异质m a r k o v 链中，这个过程就是使转移概率依赖于与时间参数t 相关的系统的现在 状态和状态的取值 第一章理论基础及需要解决的问题 与这个过程的状态空间相类似，指示集( 时间参数) 有连续和离散之 分如果m a r k o v 链的时间参数t 从离散集中取值，则称为离散m a r k o v 链如果m a r k o v 链的时间参数t 从连续集中取值，则称为连续m a r k o v 链 1 2 离散和连续时间m a r k o v 链 如果m a r k o v 链的指示集是计数的，这个m a r k o v 链称为离散时间 m a r k o v 链在这种情况下，指示集般表示为，墨，k 这个过程从现在的状态i 转移到新状态j 的条件概率为 砌( 佗) = p 1 k + 1 = 歹i k = i ) ， 而当m a r k o v 链的步转移与指示参数n 无关时，步转移概率记为 p q = p k + 1 = j f l = 讲 当m a r k o v 链的时间指示集是连续的，这个m a r k o v 链称为连续时间 m a r k o v 链( d t m c ) 而在d t m c 的情况下，状态空间仍然为离散的换 句话说，用来描述这个过程的随机变量可能取离散值 异质连续时间m a r k o v 链的m a r k o v 性表示为 p x ( t n + 1 ) + , i x ( t o ) = x 0 ，x ( h ) = x l ，x ( t n ) = z n ) = p x ( t ) x l x ( t n ) = x n ， 且有t o t l s ) 在同质情况下，因为在时间点s 和t 的实际值与转移概率独立，所 第一章理论基础及需要解决的问题 以转移概率根据丁= t s 的不同表示为 肼( s ，t ) = p x ( 8 + 7 - ) = i l x ( s ) = 1 ) 1 3 所需计算统计量：m a r k o v 链的平稳概率向量 建立m a r k o v 链模型的目的是获得这个模型的某些定量性质获得与 模型最相关的信息，模型最可能出现的状态，从长远说模型在某个状态 有多长等等 现在介绍两个重要的定义，这些定义在它们回答或提供必要信息的 同时，也从m a r k o v 链模型找到了一些问题的答案 离散时间m a r k o v 链的极限分布：假如初值概率分布为丌( o ) ，如果极 限 l i m 7 r ( 佗) 存在，则这个极限称为极限分布，这里我们记作 7 r = l i m7 r ( 亿) 记礼= t ，上式即为连续时间m a r k o v 链的极限分布 m a r k o v 链的平稳概率分布为：令p 为m a r k o v 链的转移概率矩阵， 且向量z 的元素句表示状态歹的概率分布即 乃r ，0 乃1 ，口f 玢乃= 1 则z 称为平稳概率分布的充要条件是 设 k ，礼0 ) 为m a r k o v 链，若p = ) 是转移概率矩阵，行随机 矩阵( 即元素非负且行和为1 ) ，令e = ( 1 ，1 ) r 舻，则p e = e 第一章理论基础及需要解决的问题 记q = ( ) 为 矗，n o ) 的转移率阵对于连续时间m a r k o v 链， q = p ( o ) = ( 钧) ， 其中妁= l i m t _ + o 华，i 歹，= 一t 搿的，i ，j = 1 ，2 ，佗，黝是经过时 间t 从状态i 到状态歹的概率，且p = j + a q ，0 q 佗约 束算子尼= 吲o 】几，其中五是础t 的恒等阵，死是置换阵，拓展算子砰， 对角阵最= r t 尼，i = 1 ，p 记最= i 1 ，1 2 ，i n ) ( i 1 i 2 l n ) 为 尼非零元素所在列的指示集，q 为交叉测度，故最q i 子空间k 对于a 的约束是a = 兄a 砰，a 是a 的n i 啦主子阵的对称置换阵 ( n i 佗 加性s c h w a x z 迭代算法为： 1 f o rk = 0 ，1 ，u n t i lc o n v e r g e n c ed o ： 2 f o ri = l ，2 ，pd o ： 3 s o l v ey i = a f l 昆a z ( 舢，i = l ，p 4 e n d d o 5 s e t + 1 ) ：) 一壹r t 玑 j = i 6 e n d d o 相应的同一水平乘性s c h w a x z 法的迭代阵为 t = 1 只= ( j 一昂) ( j 一弓一1 ) ( i p d 8 ( 8 ) 在文献【9 】中，i m a r k 等在非负性分裂阵的情况下，对上述方法进行了 研究 最后，我们给出阻尼加 p p z ( m ) - z ( 砷一p r t a 一1 r a z 的= ( z - 0 霹a 一1 r a ) 以 i = 1 i = 1 0 0 1 j 0 ， 0 厂一、 ig g = = 互 尸 一 互 ， 一 口 j 0 g 一； g 、liiij， 1 ， 阮 町 0 一、， ， o j ， 0 0 0 ， i 1 g g = = 0 0 ， o 砬 第三章m a r k o v 链加性迭代解法的半收敛性一 一 1 2 先给出如下引理： 引理1 【17 】若分裂a = m n 满足i n d e x ( i t ) 1 ，则 ( a ) ( ，一t e ) 一1 存在且( ，一t e ) 一1 = ( j t ) d + j e ( b ) 对于i ，j 0 ，e ( t e ) e j = t e 引理2 【2 】对于阵t ，若p ( t ) = 1 ，t 收敛的充要条件： ( a ) a 仃( t ) ，l 入i = l ，贝0 入= 1 ，担口毋( t ) 兰 。q p i = 1 p 0f z ， i - - - - 1 p pp 砰a 一1 死a = i - 0 e t m ( - 1 a i = li - - - - 1 p 晟- 0 鼠蚜1 a i = l 最( ，一何1 a ) p p oz 最正口息正oe 正扇0 i = 1i = li = l 最后，取0 1 是正整 数，a = 尬一m 是拟非负型分裂，i = 1 ，2 ，p ，0 o ，磊= ，( b ) 0 o ，( c ) d i a g ( 磊) 0 则啊果0 一 正的-，l 第三章m a r k o y 链加性迭代解法的半收敛性 1 4 - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ - _ _ _ - _ _ _ - _ 一一 一 首先，b 舻n 是不可约列随机阵，则有一正的p e r r o n 根即 沪e ：1 ，得b ：，加：0 ，所以磊：一p p 砑a 一1 尼肋= i = o 其次， p 磊= j p r t a 。1 忍a i - - - - o p 最后，取9 口f 一 i - - - - - - o p p e , m ；- 1 a p 最一p 岛岈1 a i - - - - o i - - o 最( ，一蟑1 a ) pp p 晟正p 豆正p 正直0 i = oi = 0 i - - - - - 0 l 口+ l ，有d i a g ( i ) 出叼( 口p 易) ，因而 i = 0 d i a g ( t o ) = d i a g ( i 一口 p d i a g ( d i a g ( = 0 p e , w 1 m ) 定理4 【比较定理】如果有u 0 ，使a w = e 0 ，则磊u t o w 证因为 p 田1 = p r t a 。兄 o r t a 0 1 r o + 蚜1 晦1 0 o诗 第三章m a r k o v 链加性迭代解法的半收敛性 故 霭u = 田1 厩u u 一砑1 a u = u 一 虿1 e u 一蚜1 a u 1 5 第四章c h e b y s h e v 加速方法的收敛速度 一一 1 6 第四章c h e b y s h e v 加速方法的收敛速度 4 1 引言 迭代方法的收敛陛、收敛速度以及方法的健壮性等是制约迭代方法 有效使用的三大要素为了使迭代方法更加实用有效，对迭代法加速是 十分必要的在众多的加速方法中，1 9 6 2 年提出的c h e b y s h e v 加速方 法是加速迭代的一种非常有效的方式【1 5 】，在实际使用中效果非常理想 【3 ，2 a 如果迭代矩阵可对角化，只要迭代矩阵的特征值分布密集，则c h e b y - s h e v 加速方法效果非常理想而如果迭代矩阵的最大特征值接近1 时， 直接采用c h e b y s h e v 加速方法效果不会太理想本章借助文献【1 5 1 9 】研 究的c h e b y s h e v 多项式的一些性质，讨论在迭代矩阵是亏损矩阵的情况 下，研究了c h e b y s h e v 加速方法的收敛陛，提出影响c h e b y s h e v 加速方 法迭代效果的的几大因素，结论表明，如果迭代矩阵是亏损的，迭代矩 阵的特征值分布不好，或迭代矩阵的指标较大时，或迭代矩阵的j o r d a n 基矩阵病态时，c h e b y s h e v 加速方法效果不会太理想 4 2 若干记号和引理 设矩阵g 有m 个相异实特征值，按模排列为 0 i 入1 i l a 2 l 1 是某个固定的值，并且 0 歹m ，则碟( z ) 随着歹的增加而增加 文中使用的范数均为2 范数，矩阵的条件数为c o n d ( s ) = s s 一1 引理8 i i a i i n 3 m 。j a s x n i 1 4 3c h e b y s h e v 加速方法 设 圣( 七+ 1 ) = g 童( 舢，k = 0 ，1 为求解问题( 1 ) 的加性s c h w a r z 迭代方法令z ( 0 ) = 牙( 们，在迭代格式 计算出迭代值岔( m ，叠( n ，岔( m ) 后，选择满足篷。口础= 1 的组常数 a m o ，a m l ，m ，令 z ) - 孟佧， k - - o 用新的近似z ( o ) ，z ( ，z ( m ) 作为新的解的近似值为研究它们的作为 近似的准确程度，引入 ( m ) = ( m ) 一z ，r ( m ) = z 西) 一z ， 其中矿为方程组的准确解，即满足 z + = g x 。 由于孟( 0 ) = z ( o ) ，故p ( o ) = i ( o ) ，而 m mm ，7 ) - 七牙砷一七矿= a m k # ( 舢 k = ok = ok = - o 第四章c h e b y s h e v 加速方法的收敛速度 但 故 则 p ( m ) = g p 帧一1 ) = = 6 即p ( o ) ， 仇 ，7 ( m ) _ a m k g 七p o ) _ p m ( g ) ，7 4 4c h e b y s h e v 加速方法的收敛性 关于c h e b y s h e v 加速方法计算的近似解的相对误差有 定理5 设 。嘲2 p 勰) - 1m a xp ( j i ) i i m ， p q t n ，p ( 1 ) = l 一一 1 9 ( 1 2 ) c o n d ( s ) e ( m ) 伽( 1 3 ) 利用关系式( 1 0 ) 、( 1 1 ) 和( 1 2 ) 有 定理得证 定理5 表明 p e q m m , p i n ( 1 ) = lp ( g ) 伽 、， = m i n sp(j)speqm,p(1)=l 一1 伽。 c o n d ( s ) p e q m m , p i n ( 1 ) = lp ( t ，) 珈 ， = c o n d ( 刚p 勰) _ lm a x p(ji)伽lim p q m ，p ( 1 ) = l 如果反= 1 ，i = 1 ，2 ，m ，即矩阵a 可对角化，关系式( 1 3 ) 为 c o 们( 们p 勰) = 11 m 她a x 肘p ( ) h ) r o ， 这与文献【2 3 】中的结论类似 第四章c h e b y s h e v 加速方法的收敛速度 2 0 如果矩阵s 不太病态，只要e ( m ) 能比较小，则相对误差必非常 小，此时c h e b y s h e v 加速方法近似解z ( m ) 具有较多的有效数位 如果矩阵s 太病态，即使e ( 仇) 非常小，则相对误差也可能非常 大，此时c h e b y s h e v 加速方法近似解收敛将会是非常慢的 4 4 1 矩阵g 特征值均为正实数 定理6 假设矩阵a 的特征值均为正实数，并且按( 9 ) 排序， d = 谢m 盔a x ，m 舻普肛上a m - - a 1 ， 则 抄) 甜似4 ) 剐们i 邛 1 ， 其中( z ) 为m 次第类c h e b y s h e v 多项式 令a = 【入1 ，入m 】， 五( z ) = ，i = 1 ，2 ，m 因此 e 忡k p 勰) - 1 矾m ，1 a x 酬p ( 五( z ) ) ( 1 4 )一p q m ，p ( 1 ) = l 霉j ，l t f 由逼近论的理论知满足关系式( 1 4 ) 的最优多项式p o ( x ) 是存在的进一 步由c h e b y s h e v 多项式的性质，最小最大问题 m i n mzaxp(peqm,p(1)=l i a z ) z 第四章c h e b y s h e v 加速方法的收敛速度 2 1 的最优多项式为 p 0 ( z ) 5 等2 x - a m - - a l 甲 因此满足关系式( 1 4 ) 的最优多项式为m ( z ) = 舶( z ) 利用引理8 有 e m z “一m a x i = 12 ，m 阢( 五( z ) ) z j ， m盔ax烈m胚a烈x$-1a - 1 i 学i 。朋霉t ，u 气j d 4 一工71 剑z 纛d - 1 i 学i 根据引理7 第部分有 e m hd omax一责胪m巧c(mojd1j ，j ) ( ，y ) 一 一! “”7 其中c ( m ，j ) 随歹增加而减少，c ( m ，0 ) = 1 ，因此 e ( m ) ! 脯似_ ) 剐们， 邶 l ， 【d 卢2 ( d - 1 ) m 2 ( d - 1 ( ，y ) ，i f 胗1 定理6 表明 如果d = 1 ，i = 1 ，2 ，m ，即矩阵a 可对角化，关系式( 1 3 ) 为 e ( 帕赤， 此结论与文献【2 3 】结论同 由入m 1 ，根据c h e b y s h e v 多项式性质，随m 的增加， 1 ( 7 ) 必收敛到零进一步地，如果矩阵g 的最大和最小特征值 距离越近近，则，y 越大，此时1 ( ，y ) 收敛到零的速度也越快， c h e b y s h e v 加速方法加速效果也就越好而对矩阵g 的最大和最小 特征值距离较大的情况，此时，y 接近1 ，因此l ( ，y ) 收敛到零的 速度非常慢，c h e b y s h e v 加速方法加速效果不理想 第四章c h e b y s h e v 加速方法的收敛速度 2 2 对亏损矩阵，如果特征值的指标d 越大，e ( 仇) 收敛速度越慢，因此 用c h e b y s h e v 加速方法加速的效果越不理想 4 4 2 矩阵g 特征值均为实数 定理9 假设矩阵a 的特征值均在实轴上，并且按( 9 ) 排序， 7 = 专警肛瓣2 则 ， ( m ) d 【警】2 “_ 1 ) 噩罟“，y ) ， i fp 1 i 州铲扣i t l - 引( y ) ，i f 胁1 ， 其中【筹】为警的整数部分，研号】( z ) 是次数为吲的第一类c h e b y s h e v 多项式 五( z ) 定义如上，假设d a = 阳，嘞】，故 e 州 m i n mmaxsmp(j；f(z)(15peq,n,p(1)=li a l i _ = _ - i - x ) 一 f i ，1 s m 、”“ 7 由逼近论的理论知满足关系式( 1 5 ) 的最优多项式p o ( x ) 是存在的 进一步因为 舶( z ) = q o ( x 2 ) ，q o q 【罟】， 故( 1 5 ) 化为 e k 口r a i 口n ( 1 ) ：m a xq ( j j ( 1x e d a z ) ) ( 1 6 ) 口q 【蛩1 口( 1 ) = 。 由c h e b y s h e v 多项式的性质，最小最大问题 m 1 1 2i l l a xq i zj q e q 【哿l ，口( 1 ) = 1x e d a “7 的最优多项式为 ，：萼 第四章c h e b y s h e v 加速方法的收敛速度 因此满足关系式( 1 6 ) 的最优多项式为啦( z ) = q b ( z ) 利用引理8 有 e 嘲 i = i 州2 ，m ( 五( z ) ) 一 ， 、， m 坫a ，x 蚺眦m a x - 1 | 学 d z i a 墨o g a x d - 1i 学i z ， j ! 。 根据引理7 第部分有 e ( m ) d 。蚓m a x 一。嘉胪【c ( 2 1 ，州嘲( ，y ) 其中c ( m ，j ) 随j 增加而减少，c ( m ，0 ) = 1 ，因此 p ( m ) d 【罟】2 似一t i 罟l ( y ) ， 讧p l i 叩2 ( 扣1 畔扣1 佃詈】( ，y ) ，i f 胗1 定理7 表明对亏损阵g ，如果特征值的指标d 越大，e ( m ) 收敛速度 会越慢，此时用c h e b y s h e v 加速方法加速的效果越不理想，且矩阵g 的 特征值的分布对c h e b y s h e v 加速方法加速效果起到非常关键的作用，如 果零在最大和最小特征值决定的区间内的话，c h e b y s h e v 加速方法算法 的加速效果会十分不理想的 l 鲨耋丛 2 4 参考 文献 f l 】a b e r m a na n dr j p l e m m o n s ：n o n n e g a t i v em a t r i c e s 饥t h em a t h e m a t i c a ls c i e 竹。甑 c l a s s i c sa p p l m a t h 9 ，s i a m ，p h i l a d e l p h i s ，( 1 9 9 4 ) 【2 】a b e r m a n ，r j p l e m m o n s ：n o n n e 暂a t i v em a t r i c e si nt h e 肘a t 7 l e 仇a 纸斌匏n 鲫a c 和 d e m i c ，n e w y o r k ，( 1 9 7 9 ) 【3 】a b j r c k ：n u m e r u 碰m e t h o d s o rl e a s ts q u a r e sp r o b l e m s ，s i a m ，( 1 9 9 9 ) 4 1 a f r o m m e ra n dd b s z y l d ：w e i g h t e d 仇凹伽l 仃瑚，s p l i t t 9 = g s ，a n dd t ，e 咖l n 9 口d d i t 而e 8 c h w a r zi t e r a t i o n s , n u m e r i s c h em a t h e m a t i k ，8 3 ：2 5 9 - 2 7 8 ，( 1 9 9 9 ) 【5 】b p h i l i p p e ，y s a a da n dw j s t e w a r t ：n u m e r i c a lm e t h o d s 讯m a r k o vc h a i n ，l o d e l l i n g ，o p e r a t r e s e a r c h ，4 0 ：1 1 5 6 - 1 1 7 9 ( 1 9 9 2 ) f 6 】b a r k e r ，g p ，p l e m m o n s ，r j ：c o n v e r g e n ti t e r a t i o n s o rc o m t n t g = g 咖哪蝴 b u t i o n so fm a r k o vc h a i n s , s i a mj a l g d i s c m e t h 7 ，3 9 0 - 3 9 8 ( 1 9 8 6 ) f 7 】d b s z y l d ：e q u i v a l e n c eo ，c o n v e r g e n c ec o n d i t i o n sf o ri t e r a t i v em e t h o d sf o rs 酬a r e q u a t i o n s , n u m e r l i n e a ra l g e b r aa p p l ，1p p 1 5 1 1 5 4 ，( 1 9 9 4 ) i s g a l e f e l da n dn s c h n e i d e r ：o ns q u a r er o o t so fm - m a t r i c e s , l i n e a ra l g e b r aa p p l ，4 2 ， 1 1 9 - 1 3 2 ( 1 9 8 2 ) 【9 】1 m a r e ka n dd b s z y l d ：a l g e b r a i cs c h w a r zm e t h o d sf o rt h e 讹仇e r i c a l3 d l u t i d n 吖m o 他伽 c h a i n s , l i n e a ra l g e b r aa p p l ，3 8 6 ，6 7 - 8 1 ( 2 0 0 4 ) 1 0 l j m o r t e g aa n dw r h e i n b o l d t ：i t e r a t i v es o l u t i o no ! n o n 如，l 鲫勖n t i d 船h 抛埘 v a r i a b l e s ，c a d e m i cp r e s s ，n e wy o r k ，s a ne r a n c i s c o ，l o n d o n ，( 1 9 7 0 ) f 1 1 】m b e n z i ，a p r o m m e r ，r n a b b e n ，a n dd b s z y l d ：a l g e b r a i c 纨阿o ，仇础劾矗如e 8 c h w a r zm e t h o d s ，n u m e r i s c h em a t h e m a t i k ，8 9 ：6 0 5 - 6 3 9 ，( 2 0 0 1 ) 【1 2 】m e y e r ，j r c d ，p l e m m o n s ，r j ：c o n v e r g e n tp o w e r so yam 耐r 谊诚执口p p 玩坑d t o 妃e 他t 姚m e t h o d s 细s i n g u l a rl i n e a rs y s t e m s , s i a mj n u m e r a n a l 1 4 6 9 9 - 7 0 5 ( 1 9 7 7 ) 【1 3 】r n a b b e n ：c o m p a r i s o n sb e t w e e na d d i t i v ea n dm u l t i p l i c a t i t ，e 鼢叫毗i t e m “伽讥 d o m a i nd e e x n n p o s i t i o nm e t h o d s ，n u m e r m a t h 9 51 4 5 - 1 6 2 ( 2 0 0 3 ) 参考文献 【1 4 】r b r u ，f p e d r o c h ea n dd bs z y l d ：i t e r a t i o n s o rm a r k o vc h a i n s ，s o c i e t y o ri n d u s t r i a l a n da p p l i e dm a t h e m a t i c s , s o c i e t yf o ri n d u s t r i a la n da p p l i e dm a t h e m a t i c s v 0 1 2 7 ，n o 2 ， 4 4 5 - 4 5 8 ，( 2 0 0 5 ) 【1 5 r s v a r g a ：ac o m p a r i s o no f s u c c e s s i v eo v e r r e l a x a t i o nm e t h o da n ds e m i - i n e r a t i v em e t h - o t t su s i n g ec h e b y s h e vp o l y n o m i a l s ，j s o c i n d u s t a p p l m a t h ，5 ，3 9 - 4 6 ( 1 9 5 7 ) f 1 6 】t f c h a n ，t p m a t h e w ：d o m a i nd e c o m p o s i t i o nm e t h o d s ，a c t an u m e r 6 1 - 1 4 3 ( 1 9 9 4 ) 【1 7 y o n g z h o n gs o n g ：s e m i c o n v e r g e n e ed ，n o n n e g a t i v es p l i t t i n g sf o rs i n g u l a rm a t r i c e s , n u m