（计算数学专业论文）ali算法求解非对称代数riccati方程的最小非负解（奇异状态下）.pdf

摘要 非对称代数r i c c a t i 方程出现在许多科学计算和工程应用问题中，该方程的数值求解 问题也就成为了科学研究的热点之一。而该方程的众多解中只有最小非负解具有物理意 义，所以人们主要研究该方程何时存在最小非负解以及求解这类解的数值方法。对一般 形式的非对称代数r i c c a t i 方程，当方程的四个常数矩阵组成的矩阵k 为非奇异m 一矩阵 或不可约奇异m 一矩阵时，巴经被证实其最小非负解存在。k 为非奇异m 一矩阵时，已 经有许多数值算法来求解最小非负解，其中a l i 算法已经被证实是一种可行的算法。然 而该算法在为不可约奇异m 一矩阵时的可行性还没被考虑。 本文说明了当k 为不可约奇异m 一矩阵时，a l l 算法也是可行的，但数值实验显示 此时算法不是很稳定。但对一类特殊的非对称代数r i c c a t i 方程，我们运用位移变换可 将其转换成一个新的r i c c a t i 方程，使得新方程的四个常数矩阵组成的矩阵k 为非奇异矩 阵。并说明了a l l 算法对新的方程也是可行的，而且所得的解为原方程的最小非负解。 数值实验显示此时算法比直接运用于原方程的算法效率有明显提高而且优于牛顿法。 关键词：非对称代数f l i c c a t i 方程，最小非负解，a l l 算法，位移变换 a b s t r a c t 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 na p p e a r si nm a n y a r e a so fs c i e n t i f i cc o r n - p u t i n ga n de n g i n e e r i n ga p p l i c a t i o n s ，t h en u m e r i c a lm e t h o d sf o rs o l v i n gt h ee q u a t i o n b e c o m et h ef o c u so fs c i e n t i f i cr e s e a r c h t h ee q u a t i o nh a sm a n ys o l u t i o n s ，b u to n l yt h e m i n i m a ln o r m e g a t i v eh a s p h y s i c a lm e a n i n g , s op e o p l e m a i n l yt os t u d yw h e ne x i s t st h e m i n i m a l n o n n e g a t i v e s o l u t i o na n dt h en u m e r i c a lm e t h o d st of i n dt h em i n i m a l n o n n e g - a t i v es o l u t i o n l e tkb ea nm m a t r i xw h i c hi sc o m p o s e do ff o u rc o e f f i c i e n tm a t r i c e s o fn 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 s v 兀n e t iki san o n s i n g u l a rm m a t r i xo r i r r e d u c i b l es i n g u l a rm m a t r i x ，i th a sb e e nc o n f i r m e dt h a tt h eg e n e r a lf o r mo fn 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 nh a st h em i n i m a ln o n n e g a t i v es o l u t i o n 仇h e nki sa n o n s i n g u l a rm 。m a t r i x ，t h e r ea r ea l r e a d ym a n yn u m e r i c a la l g o r i t h m st od e t e r m i n et h e m i n i m a ln o n n e g a t i v es o l u t i o n a l la l g o r i t h mh a s b e e np r o v e nt ob ef e a s i b l e h o w - e v e r ，t h ea u a l g o r i t h mi sn o tb e i n gc o n s i d e r e df e a s i b l eo rn o tw h e nk i sa ni r r e d u c i b l e s i n g u l a rm - m a t r i x t h i sa r t i d es h o w st h a tw h e nki sa ni r r e d u c i b l es i n g u l a rm m a t r i x , a l ia l g o r i t h m i sf e a s i b l e ，b u tt h en u m e r i c a le x p e r i m e n t ss h o wt h a tt h i sm e t h o di sn o tv e r ys t a b l e f o ras p e c i a lc l a s so fn o n s y r n 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 ，w eu s es h i f tt e c h n i q u e t ot r a n s f o r mt h eo r i g i n a lr i c c a t ie q u a t i o ni n t oan e wr i c c a t ie q u a t i o n ，m a k i n gkan o n s i n g u l a rm a t r i x w es h o wa l ia l g o r i t h mi sa l s of e a s i b l ef o rt h en e wr i c c a t ie q u a t i o n , a n dt h es o l u t i o ni st h eo r i g i n a le q u a t i o n 7 sm i n i m a ln o n n e g a t i v es o l u t i o n n u m e r i c a l e x p e r i m e n t ss h o wt h a ta l ia l g o r i t h mi se x c e l l e n t l ye f f e c t i v ew h e n i ti sa p p u e dt ot h e n e we q u a t i o na n db e t t e rt h a nn e w t o n a l g o r i t h m k e yw 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 ，m i n i m a ln o n n e g a f i v es o - l u t i o n , a l la l g o r i t h m ，s h i f tt e c h n i q u e 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得滥鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝江盘堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘鲎 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期： 年月日签字日期：年月日 第1 章引言 随着科学技术的迅速发展，计算领域的具有广泛应用背景的非对称代数r i c c a t i 方程 的数值求解问题也成为科学研究的热点之一。 非对称代数r i c c a t i 方程出现在许多问题的应用中，比如马尔可夫链的维纳一霍普夫 因子分解【1 ，2 】，迁移理论【3 ，4 】，对称约束或无对称约束全最小二乘问题【5 】，有理矩阵 函数的谱分解【6 ，7 1 ，线性和非线性优化控制【8 ，9 】，矩阵符号函数计算1 1 0 ，1 1 1 等等。 在迁移理论中，由散度方程，x ( p ，l ，) 满足以下积分微分方程： ( 赤+ 熹) m 垆c ( 1 + 丢裂幽) ( 1 + 丢z 1 裂幽) ， ( 1 1 ) 其中口，c 【0 ，1 】，x ( p ，) 为定义在如下定义域的实值函数( 详见【1 2 】) ： q = ( p ，) l ( p ，王，) 【a ，1 】【q ，1 1 ， q 【0 ，1 】) 。 对( 1 1 ) 用高斯一勒让德积分法进行数值积分，得到如下形式的非对称代数r i c c a t i 方 程( 详见 1 3 ，1 4 】) ： 留( x ) = x c x x d a x + b = 0 ， 其c a ，b ，e d 有如下结构： a = 一e q r ，b = e e t ，c = q q t ，d = f q e t ， 这里 = 旋8 9 ( 蠡，如，厶) ，文= 瓦及丽i ， r = 出口9 ( ，y - ，7 2 ，) ，m ；五；刁f 1 面 都为对角元为正数的对角矩阵； 三三：，：l ：t ，吼：鑫，i ：1 ，2 ，n ( 1 2 ) ( 1 3 ) 浙江大学硕士学位论文 第1 章引言 为正向量， q ) 饕1 和【咄) 鍪1 分别为高斯一勒让德积分的系数和节点的集合，并且 q ) 坠l 和 咄) 冬1 满足： 一0 。0 3 2 ) 对所有的 1 ，2 ，m ) ，j 1 ，2 ，n ) 均成立，那么 我们记a b ( a b ) 。如果矩阵a 驴肌它的所有元素满足 0 ( o ) ，其 中t 1 ，2 ，m ) ，j 1 ，2 ，n ) ，那么我们称a 为正矩阵( 非负矩阵) 。 一个实的方阵a ，它的所有非对角元都是非正的，那么我们称a 为z 一矩阵我 们可以很容易地把任何一个z 一矩阵a 写成s ，一b 的形式，其中ser ，b 0 。如 果s p ( b ) ，这里p ( b ) 表示矩阵b 的谱半径，则称z 一矩阵a 为m 一矩阵。迸一步， 当s = p ( b ) 时，我们称a 为奇异m 一矩阵；当s p ( b ) 时，我们称a 为非奇异m 一矩 阵。 我们用盯( a ) 来表示方阵a 的特征值集。c 和c 分别表示复平面上开的 左半平面，闭的左半平面，开的右半平面和闭的右半平面。 下面的引理将描述m 一矩阵的一些相关性质。 引理2 1 【3 0 ，3 1 】 对于z 一矩阵a 破期，下列叙述是等价的： ( 1 ) a 是非奇异m 一矩阵。 ( 2 ) a - 1 0 。 ( 3 ) 存在正向量u 瞅，使得a v 0 。 ( 4 ) o ( a ) cc 。 孑l 理2 2f 3 0 ，3 1 l 设a = ( a i j ) r n x n 是m 一矩阵。如果矩阵b = ( ) p 加满足 鼬s 玩 且a q 幻0 ， l j ，1 i ，j 船， 那么b 也是m 一矩阵。特别地，对于任意的正实数毋，b = 0 i + a 是非奇异m 一矩阵。 引理2 3 【2 8 】 假设m 是非奇异m 一矩阵或是不可约奇异m 一矩阵，若m 被划分为 m = 池， 其中舰1 和是方阵，那么尬1 和2 是非奇异m 矩阵。 浙江大学硕士学位论文第2 章基本概念与引理 以下倚述( 1 1 5 ) 的一些性质，详见【3 ，2 3 ，2 4 , 2 5 ，2 8 ，3 2 1 ，其中k 为( 1 1 6 ) 所定义。 引理2 4 【3 ，2 3 ，2 4 , 2 5 , 2 8 ，3 2 1 假设k 是非奇异m 一矩阵或不可约奇异m 一矩阵，那么( 1 1 5 ) 有最小非负解s 。 当k 是不可约m 一矩阵时，a s c 和d c s 也是不可约m 一矩阵。如果k 是非奇 异m 一矩阵，那4 a s c 和d c s 也是非奇异m 一矩阵。 p e r r o n f r o b e n i u s 定理可知，当m 是不可约奇异m 一矩阵时，存在正的向量t 和 满足 u t m = 0 ，m v = 0 。( 2 1 ) 类似于【2 8 ，3 2 1 ，我们把1 l 和 分别记为u t = ( 也 “；) ，矿= ( 谭谚) ，并定义 巾个 p = t ；v l t ；啦， ( 2 2 ) 其中“l ， 0 1 r n ，u 2 ，v 2 r ”。 引理2 5 【2 3 ，2 4 ，2 5 ，2 8 ，3 2 1 假设k 是不可约奇异m 一矩阵，s 是( 1 1 5 ) 的最小非负解，p 为上面所定义，那么下 列性质成立： ( 1 ) 如果p 0 ，那么s 口l = v 2 。 ( 2 ) 如果p = 0 ，那1 , s v l = v 2 。 ( 3 ) 如果p 0 ，那么s v l v 2 。 引理2 6 【2 3 ，2 4 ，2 5 ，2 8 ，3 2 】 假设k 是不可约m 一矩阵，s 是( 1 1 5 ) 的最小非负解，a 1 ，k + n 是h = d i a a ( 1 一 k ) k 的特征值，且a 1 ，k + 按实部非增排列。那么我们有如下结果： ( 1 ) k 和k + l 均为实数并且满足 r e a n + 竹i r e a n + 2 k + 1 0 入t l 0 ，那么k = 0 ，入n + 1 0 ，口