（计算数学专业论文）非对称代数riccati方程的数值解法.pdf

愀删 非对称代数r i c c a t i 方程的数值解法 学位论文完成日期：二垒生生砷a 一 指导教师签字：豆堕霞 答辩委员会成员签字：i 争立塑址 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：习矗呐签字日期：加扣年r 月旷日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，并同意以 下事项： 1 、学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。 2 、学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权清华大 学”中国学术期刊( 光盘版) 电子杂志社”用于出版和编入c n k i 中国知识资源 总库，授权中国科学技术信息研究所将本学位论文收录到中国学位论文全 文数据库。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：j 舡娟 导师签字： 爵疃麦 签字日期：_ p 年孓月i 日 签字日期：7 y l o 年岁月f 7 日 非对称代数r i c c a t i 方程的数值解法 摘要 非对称代数r i c c a t i 方程的数值求解是数值代数中的一个重要课题，而人 们普遍关心的是求解非对称代数r i c c a t i 方程的最小非负解对于这一课题，已 有大量论文讨论了该方程的性质，并结合数值代数中常用的数值方法给出了相 应的迭代算法，形成了一定的理论体系对于这些算法，仍然可以通过某些思想 和技巧，使其改进和完善，或者结合其他数值方法构造创新算法，因此有丰富 的内容可以研究，这便是本文研究的初衷 本文主要内容如下： 第一部分提出了非对称代数r i c c a t i 方程的数值求解问题，并简要概述了 该问题的研究进展 第二部分给出了基本概念和引理，对影响a l i 算法收敛速率的参数进行讨 论，并找到使收敛达到最快的参数值 第三部分结合矩阵分裂和两步迭代法的思想，a l i 算法将原方程拆分所得 两个线性方程，构成两个交错的迭代方程，以此作为外迭代，然后对每个方程 的系数矩阵进行分裂，分别得到新的迭代序列，此为内迭代，将两个分离的迭 代过程结合起来，构造出完整统一的两步迭代算法，并讨论其单调收敛性 第四部分验证了在方程的四个系数矩阵组成的矩阵k 为不可约奇异m 矩 阵时，引入位移变换得到的新方程应用a l i 算法仍可得到最小非负解，并结合 数值实验说明了算法的有效性 关键词：非对称代数r i c c a t i 方程，a l i 算法，两步迭代法，位移变换 。n u m e r i c a lm e t h o d sf o rs o l v i n g n o n s y m m e t r i ca l g e b r a i cr i c c a t ie q u a t i o n a b s t r a c t n u m e r i c a lm e t h o df o rs o l v i n gn o n s y m m e t r i ca l g e b r a i cr i c c a t ie q u a t i o n ( n a r e ) i sa ni m p o r t a n ts u b j e c ti nt h ea r e ao fn u m e r i c a la l g e b r a r e s e a r c h e r sp a ym u c h a t t e n t i o nt ot h ec o m p u t a t i o no ft h em i n i m a ln o n n e g a t i v es o l u t i o no fn a r e t h e r eh a v eb e e nal o to fp a p e r sd i s c u s s e dt h ep r o p e r t i e so fn a r ea n dp r e s e n t e d i t e r a t i v em e t h o d s ，f o r m i n gat h e o r e t i c a ls y s t e m t h e s em e t h o d sc a nb ei m p r o v e d ， a n df u r t h e r m o r e ，n e wm e t h o d sw i l lb ec o n s t r u c t e db ys o m ei d e a sa n dt e c h n i q u e s a l lt h ea b o v ei st h eo r i g i n a li n t e n t i o no ft h i sp a p e r t h ep a p e ri so r g a n i z e da sf o l l o w s ： s e c t i o n1 t h ep r o b l e mo fn a r ea n dt h er e s e n tw o r ka r ep r e s e n t e d s e c t i o n2 ，f i r s t l yw ei n t r o d u c es o m eu s e f u ld e f i n i t i o n sa n dl e m m a s ，a n d t h e nd i s c u s sh o wt h ec h o i c eo ft h ep a r a m e t e ri na l ia l g o r i t h mi n f l u e n c e s t h ec o n v e r g e n c er a t ea n df i n di t so p t i m a lv a l u ei nt h es e n s eo fm o n o t o n e c o n v e r g e n c e s e c t i o n3 ，t h ea l ia l g o r i t h md i v i d e st h eo r i g i n a le q u a t i o ni n t ot w ol i n e a r e q u a t i o n s ，c o n s t i t u t i n ga l t e r n a t ei t e r a t i o n s t h i si t e r a t i o ni sc o n s i d e r e da s t h eo u t e ri t e r a t i o n b a s e do nt h es p l i t t i n go ft h ec o e f f i c i e n tm a t r i c e so f b o t he q u a t i o n s ，w eg a i nt h ei n n e ri t e r a t i o n b yc o m b i n gt h et w os e p a r a t e i t e r a t i o n s ，t h ei n t e g r a t e dt w o - s t a g ei t e r a t i o nm e t h o di se s t a b l i s h e d s e c t i o n4 ，w h e nt h em a t r i xk c o m p o s e do ft h ef o u rc o c f f i c i c n tm a t r i c e so f n a r ei si r r e d u c i b l es i n g u l a rm m a t r i x ，i ti sp r o v e dt h a tt h ea l ia l g o r i t h m b a s e do ns h i f tt e c h n i q u ei ss t i l la ne f f e c t i v es o l v e r ，a n dt h ee f f e c t i v e n e s si s t e s t i f i e db yt h en u m e r i c a le x p e r i m e n t k e y w o r d s ：n o n s y m m e t r i ca l g e b r a i cr i c c a t ie q u a t i o n ，a l ia l g o - r i t h m ，t w o - s t a g ei t e r a t i o nm e t h o d ，s h i f tt e c h n i q u e 3 1 多重分裂法 3 2 两步迭代法 3 3 数值实验 第4 t 奇异情形下的非对称代数r i c c a t i 方程解法 4 1 位移变换 4 2 基于位移变换的a l i 算法 4 3 数值实验 致谢 攻读硕士学位期间完成的文章 简历 2 7 2 9 1 2 5 7 7 9 1 5 n 挖玷 均殂 弱 第1 章综述 1 1非对称代数r i c c a t i 方程数值方法的研究进展 非对称代数r i c c a t i 方程的数值求解是计算数学领域有广泛应用背景的 一类热点问题它出现在许多科学工程计算的应用研究中，如马尔可夫链的 w i e n e r h o p f 因子分解【1 6 】，有理矩阵函数的谱分解【1 9 】，输运理论【1 2 ，1 5 , 1 7 】等等 人们普遍关心的是该类方程的最小非负解的数值求法 考虑如下的非对称代数r i c c a t i 方程( a r e ) ： n ( x ) = x c x x d a x + b = 0 ， ( 1 1 ) 其中a r m m ，b p n ，c r n m ，d r ，n a r e ( 1 1 ) 的最小非负解s 指的是对于该方程的任意正解，都有s ， 也就是说s ，s 7 的所有元素满足s , j ，对于所有的1 i m ，1 j 礼成 立 令 = jo 以+ d t 圆， g u o 和l a u b x l 证明当矩阵a ，b ，c ，d 满足b 0 ，c 0 ，w 是非奇异的m 一矩阵 时，a r e ( 1 1 ) 存在正解，并由此构造出不动点迭代法和牛顿法 m e t h o d1 1 ( 不动点迭代法) 给定初始值x 0 r m 煳，对k = 0 ，1 ，2 ，计算矩阵序列 托) 直到该序 列收敛，其中溉+ l 由下面包含托的s y l v e s t e r 方程解得： m a x k + l + x k + 1 m d = a + 虬d + x k c x k + b( 1 2 ) 其中，a = m a 一帆，d = m d n o 。 m e t h o d1 2 ( 牛顿法) 给定初始值x 0 r m x n ，对k = 0 ，1 ，2 ，计算矩阵序列 托) 直到该序 列收敛，其中托+ 1 由下面包含溉的s y l v e s t e r 方程解得： ( a 一虬c ) x k + 1 + x k + i ( d c x 知) = b x k c x k( 1 3 ) 但不论是不动点迭代法还是牛顿法，每一步迭代都需要求解一个形为a x + x b = c 的s y l v e s t e r 方程，计算量很大且算法复杂g u o 2 】证明当矩阵 k ；id 旬i 【一b aj 非对称代数r i c c a t i 方程的数值解法 为非奇异m 一矩阵或不可约奇异m 一矩阵，且b 0 ，c 0 时，a r e ( 1 1 ) 有 最小非负解在此基础上，为避免不动点迭代法和牛顿法的缺点，g u o l i n 和x u 3 提出了保结构加倍算法( s d a ) ，b a i ，g u o 和x u 4 提出交替线性 化隐式迭代算法( a l i ) m e t h o d1 3 ( s d a ) 其中， e o = b ，f o = 日，g o = g 1 ，h o = 日， e k + 1 = 邑( 厶一g 七h k ) e k ， 最+ 1 = 最( k h 七g k ) 一1 兄， g k + 1 = g k + e k ( 厶一g k h k ) g k f k ， 凰+ 1 = 风+ 最( 厶一风g 知) - 1 风鼠， 马= 厶一2 7 y 7 - - 1 日= k 一2 7 町1 ，q = 2 7 町1 c w 丁1 , 日= 2 7 町1 b 珥1 ， 明= 厶一b 巧1 c ，k = 巩一c 笃1 b ，厶= a + ，y ，m ，d r = d + v i n g u o 、l i n 和x u 3 i l t了当k 为非奇异m 一矩阵时，h k 将收敛于a r e ( 1 1 ) 的 最小非负解，g 七收敛- ：a r e ( 1 1 ) 的共轭方程的最小非负解 1 2a l i 算法 先考虑b a i 5 1 提出的求解线性方程组的一种算法考虑线性方程组 a x = b ， ( 1 4 ) a c 似n ，把a 作如下分解： a = h + s 、 其中h = ( a + a 日) ，s = ( a a 日) ，日和s 分别是h e r m i t e 和反h e r m i t e 矩 阵，假定日是正定矩阵，即它的特征值都是正数，取一个正参数o ，研究方程 组 ( a i + h ) x = ( a i s ) x + b ， ( q ，+ s ) x = ( a i h ) x + b ， 它们的解就是方程组( 1 4 ) 的解由此我们得到h e r m i t i e 和反h e r m i t e 分裂 法( h s s ) 2 1 ： ， ( q ，+ h ) x k + l 2 = ( a l s ) x k + b ， ( 1 5 a ) 2 非对称代数r i c c a t i 方程的数值解法 ( q ，+ s ) z 知+ l = ( a i h ) x k + l 2 + b ( 1 5 b ) 在此算法的基础上，通过将矩阵分裂和逐次逼近结合，并选取一个正参数0 f 。 b a i ，g u o 和x u 4 1 提出了交替线性化隐式迭代算法( a l i ) m e t h o d1 4 ( a l i ) 取x 0 = 0 r 煳，对k = 0 ，1 ，2 ，计算 x k ) 直到该序列收敛，由虬得 到拖+ 1 是由解下面的线性矩阵方程来实现的： x k + l 2 ( a i + ( d c x k ) ) = ( a i a ) 虬+ b ， ( 1 6 a ) ( q j + ( a x k + v 2 c ) ) x k + 1 = 虬+ 1 2 ( o d d ) + b ( 1 6 b ) 算法每一步迭代只需求解两个线性矩阵方程，从而避免了求较为复杂 的s y l v e s t e r 方程，因此，要比牛顿法和不动点迭代法都更为行之有效，且易 于在并行计算中执行文献【4 1 中证明，当k 为非奇异m 一矩阵时，方程 ( 1 6 a ) ，( 1 6 b ) 产生的迭代序列收敛到a r e ( 1 1 ) 的最小非负解，算法是可行的 以上我们简单介绍了几种非对称代数r i c c a t i 方程的数值解法，本文从 a l i 算法出发，对算法作进一步分析，并在此基础上构造一种解决a r e ( 1 1 ) 的新算法另外，对于一类特殊的k 为不可约奇异m 一矩阵的情况，应用位移 变换【6 】后得到新方程仍可使用已知算法进行求解 本文第二部分将介绍一些基本概念和引理，并讨论参数对算法收敛速率的 影响 ? 4 第三部分给出解非对称代数r i c c a t i 方程的两步迭代算法 第四部分把位移变换应用于a l i 算法解k 为不可约奇异m 一矩阵的情况， 并结合数值实验说明算法的有效性 3 第2 章a l i 算法收敛速率的讨论 首先，我们将a l i 算法( 1 6 ) 改写如下： m e t h o d2 1 取x o c l j = 0 r m 煳，对k = 0 ，1 ，2 计算 碡叫) 直到该序列收敛，由砖得 到x 龆是由解下面的线性矩阵方程来实现的： x 器2 ( q ，+ ( d c x f ) ) = ( a i a ) x + b ，( 2 1 ) ( a l + ( a 一叉龆2 c ) ) x 器= 砖翁2 ( a ，一d ) + b ， ( 2 2 ) 其中口 0 是给定的迭代参数 在【4 】中，作者证明了由m e t h o d2 1 产生的迭代序列 蹬) 单调收敛 到a r e ( 1 1 ) 的最小非负解，并且估计出渐进收敛因子【4 】中的数值实验进一步 证实，a l i 迭代法能够有效的求解非对称代数r i c c a t i 方程 从迭代过程可以看出，收敛速度取决于参数q 的选取据此，分析口如何影 响算法将是本部分讨论的重点 2 1基本引理 一个实方阵a ，若它的所有非对角线元素都是非正的，那么称a 为二矩 阵显然任意z 矩阵都可以表示为a = s i b ，其中8 0 ，b 0 一个z 矩 阵被称为m - 矩阵，如果s p ( b ) ，其中p ( b ) 为j e 7 的谱半径下面给出关于 m 一矩阵的几个引理： 引理2 1 【l ，2 ，1 2 ，1 8 】 对于z 矩阵a ，下面的命题是等价的： ( 1 ) a 是m 一矩眸； 俐a _ 1 0 j ( 3 ) a v 0 ，央寺 q ； “，盯( a ) cc 引理2 2 【1 ，2 ，4 ，1 8 】 设a r n 竹是m 矩阵，若b r n n 的元素满足 饥t a i i ， a i j b i j 0 ， z j ，1 z ，j n ， 则b 也是m 一矩阵特别地，对于实数口 0 ，b = o i + a 是m 一矩阵 引理2 3 【1 】1 设ab 瞅x n 都是m 矩阵，如果a b ，则a 一1 b 引理2 4 【4 ，1 2 ，1 3 矩阵k 定义为： k ：d 彤1 i bal l j 如果k 为m 一矩阵，且b 0 ，c 0 ，j 目, a r e ( 1 1 ) 存在最小非负解s ，并使 得d c s 和a s c 都是m 矩阵 引理2 4 揭示出，当m e t h o d2 1 产生的序列 砖口) 趋近于s 时，( d c x ) 和( a x 龆2 c ) 将成为m 一矩阵很显然，当k 为m _ 矩阵时，a 和d 都是从矩阵 引理2 5 【4 】 设 x p ) 是由m e t h o d2 1 产生的序列，则以下的等式成立： ( 1 )( x 龆2 一叉紫) ( a ，+ ( d c 义p ) ) = 冗( 叉? ) ( 2 ) ( 口，+ ( a 一义龆2 c ) ) ( 砖冀一叉嚣2 ) = 冗( x 龆2 ) 由文献【4 】中的定理4 1 可知，对于满足冗( 砖口) o 的砖q = 0 ，如果参数 q 满足： 口撇z m a x 。矗磷 勤) ) ， ( 2 3 ) 其中啦；，也；分别是矩阵a 和d 的第i 个对角线元素，那么序列 砖) 单调递 增且收敛至, j a r e ( 1 1 ) 的最小非负解s 2 2参数对收敛速率的影响 定理2 6 ，、 设卢，7 o 且满足卢，y 仇n z l m 冗( 砖2 ) ( 卢，+ ( d c x 船) ) 一1 + 堪一冗( 磷) ( 7 ，+ ( d c 堪) ) 一堪 隧2 g x 龆一x 龆c x 龆一( 砖2 一砖乌) d a ( 砖2 一叉龆) 】( 7 ，+ ( d c 叉龆) ) 一1 + 砖翁一砖臻 = 【( 砖2 c a ) ( 砖2 一x 龆) + ( 砖2 一一x 磨( - + r ) 。) ( c x 2 。一d ) 】 x ( 7 + ( d c 叉龆) ) 一1 + 砖翁一x 器 = ( 7 1 一a + x 器c ) ( x 龆一义龆) ( ，y j + ( d c 义龆) ) 由t - y 1 m i a x m 【a i t ) ，7 i a + 义龆c 0 ，( 7 ，+ ( d 一嘣) ) 一1 0 因而， 堪2 飞a r k ( + 3 ) 2 参照证明x i 芦x 的过程，可以得到 粥一堪( p ，+ ( a 一堪。c ) ) 一1 ( 墨笔2 一堪。) ( 卢，+ c 堪2 - o ) 0 说明了结论对于k + 1 同样成立 综上所述，我们递推证得( 2 4 ) 对于所有整数k 0 都成立 口 定理2 6 表明，当迭代参数q 满足( 2 3 ) 时，q 越大，收敛越慢特别地，当 ( 2 3 ) 中等号成立时a u 迭代法收敛达到最快 其中 2 3数值实验 考虑【4 】中算例5 2 ，矩阵表示为： t , = m 2 ，并且 a = d = t r i d i a g ( - i ，t ，- i ) r 似n ， t - t r i d i 醒( - 1 , 4 + 南，_ 1 ) r m ， b = 击t r i d i a g ( 1 ，2 1 ) r 似n ，c = 1 5 b 8 非对称代数r i c c a f i 方程的数值解法 图2 1 参数不同取值下的收敛速度 令卢21 m s 。a s x m a i i ) = 4 + 郦2 0 0 因此m e t h 。d1 1 中的参数满足q 卢 取m = 8 ，) c o = 0 ， r 陆丽雨烈甏丽 通过选取不同的q ，我们得到表格中的不同数值结果并且绘制出收敛曲线，其 中i t 和c p u 分别代表迭代步数以及计算时间 p a r a m e t e r a = 口 口= 1 5 8口= 2 0 8口= 2 5 8 i t1 6 2 53 34 2 c p u0 2 6 5 00 2 3 4 0 0 3 4 4 00 4 0 6 0 r e s2 8 8 5 4 e - 0 1 3 2 5 6 1 5 e ，0 1 34 7 8 8 3 e - 0 1 33 3 5 1 9 e - 0 1 3 表2 1 给以不同的q 得到的迭代结果 上图中，纵坐标为l o g ( e r r ) = 1 0 9 ( 燃) 。显然，随着参数值增加，收 敛变慢另外，当口= 卢= m a x 麟 口曲，l m j a x n _ 【吗j ) ) 时达到最优情况数 值实验很好的验证了定理2 6 的准确性 综上，理论分析和数值实验两方面都证实了迭代参数对收敛速度的极大影 响，且找到了使收敛达到最快的参数值 9 第3 章两步迭代法 3 1 多重分裂法 矩阵的多重分裂法( m u l t i s p l i t t i n go fm a t r i c e s ) 最初是o l e a r y f g j w h i t e 7 在 研究线性方程组a x = b 时提出的概念，这类方法将线性问题里的系数矩阵进 行不同分裂，在并行计算中每个处理器对相应的某种分裂所得到的子问题进行 计算，再将结果按适当方式组合构成整个问题的迭代解，充分发挥了多重分裂 的组合性和并行计算的高效性，将大规模问题简化为几个规模比较小的问题 定义3 1 【7 】7 令a ，风，q ，d k r 似n ，若满足 ( 1 ) a = b k c k ，七= 1 ，2 ，k ，并且每个玩都是非奇异的 ( 2 ) 怎1 d k = i ，其中d 知是对角矩阵r d k 0 则称( 风，g ，d k ) 是a 的一个多重分裂 利用( 1 ) ，a x = b 可写为 风z = 仇z + b ，k = 1 ，2 ，k 或 z = 巧1 仉z + 巧1 b ， k = 1 ，2 ，k 上式两端乘d 七并求和得 篷1 d 七z = 怎1 d 七巧1 仉z + 怎1 d k 巧1 b ， 记日= 冬l d k 耳1 瓯，g = 怎1 d k 巧1 ，则迭代式即为 t , i + 1 = h x i + g b ( 3 1 ) 定义3 2f 7 1 7 设a ，b ，c 是实矩阵，若a = b c ，b _ 1 0 ，且b - 1 c 0 ，则称( b ，c ) 是a 的 弱正则分裂；若b _ 1 0 ，c 0 ，则称( b ，c ) 是a 的正则分裂 下述结果是多重分裂迭代法( 3 1 ) 收敛性的一个结论 定理3 3 【7 】 若对于k = 1 ，2 ，k ，( b k ，c k ) 是a 的弱正则分裂且a 是m 一矩阵，则迭代式 ( 3 1 ) 是收敛的 定理( 3 3 ) 是后文两步迭代法收敛性分析的基础 非对称代数r i c c a t i 方程的数值解法 3 2 两步迭代法 多重分裂法在大规模并行计算中有重要应用，本文中我们只考虑k = 1 即 单分裂的情形对于线性方程组( 1 4 ) ，令a = m n ，m = f g 分别是矩阵 a ，m 的分裂形式，其中a ，m 都是非奇异矩阵，f r o m m e r 和s z y l d l 9 1 建立了求 解( 1 4 ) 的两步迭代法( t w o - s t a g ei t e r a t i o nm e t h o d ) m e t h o d3 1 ( 两步迭代法) 给定初始向量x 0 r n ，执行以下过程： f o rp = 0 , 1 ，2 u n t i l 矿) c o n v e r g e n c ed o 护，o ：护： f o rk = 0t os 0 ) 一1d o 矿，七+ 1 = f 一1 ( g 矿，七+ 矿+ 6 ) ； e n d x p + 1 = 矿，。( p ) ：， r n 丁) 算法中的8 ( p ) 是内循环的迭代步数， s ( p ) ) 品。是一个正整数序列，当然，内 循环步数也可取固定值s 下述结果是算法3 1 的单调收敛性结论： 定理3 4 【9 - 1 1 】 令a 为非奇异矩阵且a 一1 0 ，若a = m n 是正则分裂，m = f g 是弱正则 分裂，s ( p ) 1 ) 0 内循环迭代序列，给定初始向量z o 满足a 知b ，则算法3 _ f 产 生的序列 矿) 单调递增收敛到原方程的解 我们在算法( 1 4 ) 的基础上，对每一方程系数矩阵再进行一次分裂构造两 步迭代过程，形成新的算法格式 定义3 5 【9 】 ， 对于矩阵a 的一种分裂形式a = b c ，若b 是m 矩阵且c 0 ，则它是 m 一分裂 引理3 6 【9 】9 对于肛分裂a = b c ，p ( b 一1 c ) l 当且仅当a 是胁矩阵 记 w k = a l + ( d c 托) ，r k = ( q ，一a ) 凰+ b ， t k = o h + ( a x k + m c ) ，鼠= x k + l 2 ( a l d ) + b ， y k = x k + l 2 ， 1 2 非对称代数r l c c a t i 方程的数值解法 则( 1 6 ) 式转化为 对肌，孔作分裂， 其中， 容易得到以下结论： k 帆= 冗知， 死托+ 1 = 鼠， 眠= m 一眠，死= f g 知， m = q j r4 - d f = a i + a ， n k = c x k ， g k = x k + i 2 c 定理3 7 按上述方式所做的矩阵分裂眠= m n k ，死= f g 七都是规范分裂，也 是m 一分裂 推论3 8 p ( m 一1 眠) 1 ，p ( v g 七) 0 即 x o ，) 单调递增有上界为x 1 ，又知p ( f 一1 g o ) 1 ，所以有x o ，单调收敛 到x l ，也即是说，x 1 近似于x 1 k = 1 时， x 1 ，o = x 1 , y 1 ，o = y o = x l 2 x 3 2 假设x 1 2 y 1 ，x 3 2 ， 。 y 1 ，+ 1 一x 3 2 = y i , i n l m 一14 - r ( x 1 ) f 一1 一x 3 2 = ( y 1 - 一x 3 2 ) n l m - 1 0 y 1 ，+ 1 一x 1 2 = y 1 ，l m 一14 - r ( x 1 ) m 一b m 一1 = y 1 , 1 n 1 m 一14 - ( r ( x 1 ) 一b ) m - 1 0 1 4 非对称代数r i c c a t i 方程的数值解法 所以，x 1 2 y l t 。+ 1 x 3 1 2 y 1 ，f + 1 一y 1 ，。= y 1 ，。1 m 一1 + r ( x 1 ) m 一y 1 , - 1 n 1 m 一一r ( x 1 ) m 一1 = ( y 1 ，一y 1 , t - 1 ) n 1 m 一 = ( y 1 ，1 一y i , o ) ( n i m _ 1 ) 0 即 y 1 ，1 ) 单调递增有上界为x 3 2 ，又知p ( n 1 m 一1 ) 1 ，所以有y 1 。单调收敛 到x 3 2 此过程进行下去，我们可以得到每步内循环y 奄，单调递增收敛到托+ 1 2 ， x 奄，单调递增收敛到扎+ 1 在前述分析的基础上，容易得到下面结论 口 定理3 1 0 4 - 弓i 理2 彳中定义的矩阵k 为m 一矩阵，s 为a r e ( 1 j ) 的最小非负解，矩阵分 裂w k = m n k ，t k = f g 南都为m 一分裂，取x o = 0 为初始矩阵，则由 算法3 孵到的序列 x 知) ， y 七) 单调递增，即 x o y o x 1 x 知y 知x 知+ 1 s 并且【x 知) 收敛到s 3 3数值实验 同样应用【4 】中的算例5 2 ，内循环迭代步数7 - 此处我们选择固定正整数值 初始x o = 0 ，残差定义为： 麟= 丽丽剞警丽 两步迭代法求解a r e ( 1 1 ) 有如下表所示数值结果 由实验数据可看出，内循环迭代步数的选择对收敛性并无太大影响，仅对 花费时间有显著影响 1 5 非对称代数r i c c a t i 方程的数值解法 m = 4m = 8m = 1 6m = 3 2 i t e r81 64 41 2 4 t = 2c p u0 0 1 6 00 2 5 0 04 2 0 6 2 02 0 4 5 9 9 5 0 r e s7 8 9 7 3 e - 0 1 42 8 8 7 7 e - 0 1 32 5 2 0 6 争0 1 34 3 9 5 6 e 0 1 1 i t e r81 64 41 2 4 t = 5c p u0 0 1 6 00 5 9 3 08 3 4 8 4 04 9 0 3 5 3 7 0 r e s7 8 9 7 3 e 0 1 42 8 8 7 7 争0 1 32 5 2 0 6 e - 0 1 34 3 9 5 6 e 0 1 1 i t e r81 64 41 2 4 r = 1 0 c p u0 0 3 2 01 0 7 8 01 5 4 6 8 7 0 9 4 1 1 7 3 4 0 r e s7 8 9 7 3 e - 0 1 42 8 8 7 7 争0 1 32 5 2 0 6 e - 0 1 34 3 9 5 6 e - 0 1 1 表3 1 不同7 - 下数值实验结果 1 6 假设 k ：d l b l 为不可约奇异m 一矩阵，由p e r r o n - f r o b e n i u s 定理知0 是单特征值，存在向量 让，秽使得 记 定义 让t k = 0 k v = 0 ，= ( 砰，钍 ) ，= ( ，谚) ， p = u 钉1 一缸弛， 引理4 1 【6 】6 假设k 为不可约奇异m 一矩阵，x 是a r e ( 1 1 ) 的最小非负解，则成立： 口夕如果肛0 ，x v l = v 2 ； 例如果p 0 ，x v l o ，矿= ，硝) o ，使得h v = o ，p t v = 1 所以有， 肚瞄二讣如匕j i 一l l b i 其中， d 7 = d + r l v l 刃，= c 一? 7 1 西，b 7 = b + r l v 2 p ，a 7 = a y v 2 西，( 4 2 ) 于是，可以定义一个新的非对称代数r i c c a t i 方程： x c 7 x x d 7 一a 7 x + b 7 = 0 ( 4 3 ) 引理4 2 【6 ，1 4 】 令t 是奇异矩阵，弛= 0 ，存在向量7 使得7 t u = 1 ，刀 0 ，于是矩阵 r = t + y w r t 的特征值是t 的特征值，只是t 的一个零特征值被7 7 代替 引理4 3 【6 】 令k 为不可约奇异矩阵，入l ，入m + n 是h = j k 按实部非增排列的全部特征 值，那么入n 和a n + 1 是实的，且 r e 入n + m r e x + 2 0 ，a n + l = 0 由引理4 2 可知，日7 的特征值是日的特征值，只是日的一个零特征值被 卵代替 整理可知， x c x x d 7 一a 7 x + b 7 = x c x x d a x + b n ( x v l v 2 ) 0 ；x + 刃) 所以当p 0 时，方程( 4 3 ) 与( 1 1 ) 有相同的最小非负解 当肛= 0 时，日有两个零特征值，此时可以采用双位移变换将两个零特征 值都替代掉，构造出新的r i c c a t i 方程仍与原方程有相同的最小非负解存在 ，= ( ，谚) ，w t = ( 钆 ，一让；) 使得h v = 0 ，w t h = 0 ，因此可以构造 - i = h + 叼 ，+ f 口叫t 其中7 1 0 ， 0 的情形 4 2 基于位移变换舯a l i 算法 假设k 为不可约奇异m 一矩阵，在研究马尔可夫模型中我们得到k e = 0 ， 其中e 为各元素都是1 的向量( 见【1 7 】) 我们可以通过选取适当的叩和p ，在进行 位移变换后将a l i 算法用于求解k 为不可约奇异m 一矩阵情形下的a r e ( 1 1 ) 对于日= j k = d - 一c a 构造日的秩l 修正： h 7 = h + 7 7 e ， 非对称代数r i c c a t i 方程的数值解法 其中，7 7 o ，矿= 研，硼0 ， 重新定义： 使得h e = 0 ，p t e = 1 1 一u i 一i j k ，：f l b l = d + v i e l 矸，= c y e l 西， b 7 = b + r l e 2 p t ，a 7 = a 一叩e 2 西( 4 5 ) 我们选取7 7 o ，p t = 研，西】0 满足 ( 卯1 ) j l 型m 蛳i n 向i d , j l ，歹= l ，2 ，。，扎 ( 靴) j 恕，j = 1 ，2 ， m 由此可得，为m 一矩阵，b 7 0 ，c 7 0 ，由引理2 2 知d 7 也为m 一矩阵 于是，可以定义一个新的非对称代数r i c c a t i 方程： x c 7 x x d 一a 7 x + b 7 = 0 ( 4 6 ) 我们仍然只讨论肛 0 的情形从前述讨论可知，新方程( 4 6 ) 与( 1 1 ) 有相同 的最小非负解s 引理4 4 臀一sc l 和d i c i s 都是m 一矩阵 证明： a 7 一s c 7 = a v i e 2 西一s c s 叩e 1 z 当p 0 时，s e l = e 2 ，故一s c = a s c ，因此一s c 是m 一矩阵 d 7 一c s = d + t i e l 矗一c s + 叼e l 西s = d c s + y e l ( 开- i - 班t s ) 因为研+ 刃s ) e l = p r e l + p t e 2 = p t e = 1 ，由引理4 3 ， 莎( 一c s ) = 入1 ，入n l ， 7 ) 所以由引理2 1 ( 4 ) 可得，d ，一c s 是m 一矩阵 口 最后，关于a l i 算法用于位移变换后方程的单调收敛性，有如下结论，证 明过程类似文献【4 】中定理4 1 ，本文不再给出 2 n 。l = 日 中其 非对称代数r i c c a t i 方程的数值解法 定理4 5 初始矩阵x o = 0 ，运用a l i 算法解由似f 圳构造出的系数矩阵组成 的位移变换后的非对称代数r i c c a t i 方程，产生的迭代序列 咒) 单调递增有上 界，收敛到a r e ( 1 1 ) 的最小非负解s 4 3数值实验 本部分中，我们分别对k 为不可约奇异矩阵时的a r e ( 1 1 ) 应用a l l 算法 和基于位移变换的a l i 算法进行求解，对数值结果进行比较 t e s t4 1 生成mxm 阶随机矩阵t ，令k = d i a g ( t e ) 一t ，则有k e = 0 且 k 为不可约奇异m 一矩阵d ，一c ，b ，一a 分别是k 的四个罟署阶子阵，选 取向量叼 0 ，p 0 满足： ( 卯1 ) j = 幽r a 缉i n ；向i d , jl 庐1 2 ，筹 ( 彻) j = 1 垡m i n 导，歹- 1 2 ，筹 a l i 算法中的参数取 口= m a x 。m s ；a x s 蚩 口“) ，。m a x d j j ) ， 残差定义为 麟= 丽吁秽器酊砜 m e t h o dm = 1 0m = 2 0m = 5 0m = 1 0 0 i t e r1 0 56 6 08 3 51 2 8 4 a l i c p u 0 0 1 6 0 0 2 9 7 01 2 3 4 0 9 3 9 0 0 r e s3 0 0 4 7 e - 0 1 32 9 9 5 5 e 0 1 32 7 2 8 6 e - 0 1 32 6 3 9 9 e 0 1 3 i t e r4 81 2 61 6 33 8 5 s h i f ta l ic p u0 0 6 3 00 0 4 7 00 2 3 5 02 6 8 7 0 r e s2 4 7 2 0 e - 0 1 32 8 2 7 4 e - 0 1 32 7 2 0 2 e - 0 1 32 7 4 0 2 争0 1 3 表4 1 t e s t4 1 数值实验结果 从表4 1 可以看出，求解奇异情形的非对称代数r i c c a t i 方程时，用带有位 移变换的a l i 算法在迭代步数和花费时间上都优于直接使用a l l 算法，凶此 2 1 非对称代数r i c c a t i 方程的数值解法 可以说位移变换是求解奇异情形的十分有效的技巧 t e s t4 2 6 】 令 k = 0 0 0 3 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 3 则k 是奇异m 一矩阵，且其对应的非对称代数r i c c a t i 方程的最小非负解 为s = j 易，2 ，其中e 2 ，2 为元素都为1 的2 2 阶矩阵定义解的误差范数 e r r = i i x s i i m e t h o di t e rc p ue r r a l i2 4 5 62 8 5 3 2 6 02 7 6 1 2 争0 1 2 s h i f ta l i1 805 5 5 1 1 争0 1 6 表4 2 t e s t4 2 数值实验结果 从表4 2 可以看出，直接使用a l i 算法和使用位移技巧后的a l i 算法都可以 收敛到方程的最小非负解，且使用位移技巧的算法显著优于原