（计算数学专业论文）两类sylvester矩阵方程数值求解算法的研究.pdf

摘要 l i i i i i11111i 1 1i l i i l l i i il u lli l u l y 17 4 6 3 7 5 摘要 在控制论、信号处理、神经网络、模型降阶、图像恢复等领域经常会涉及到 s y l v e s t e r 矩阵方程的数值求解问题，本文主要研究了两类s y l v e s t e r 矩阵方程 彳x + x b = c 和x + a x b = c 的数值求解问题首先，在梯度型迭代算法的基 础上，给出了一个改进型梯度迭代算法，并证明了算法在一定条件下收敛；其 次，研究并解决了一个公开问题，即梯度型迭代算法的最优收敛因子的确定问 题；最后，利用预条件思想给出了求解矩阵方程x 4 - , 4 x b = c 的一个预条件迭代 算法本文共分5 章，组织如下： 第一章介绍了s y l v e s t e r 矩阵方程的研究背景和研究现状及相关预备知 识，同时介绍了本文的主要研究内容 第二章在梯度迭代算法的基础上，研究给出了一个改进型梯度迭代算法， 新算法有效地利用了算法前半步迭代的信息理论分析表明，新方法在适当的条 件下对任意初始值是收敛的同时，数值实验显示，新算法比梯度迭代算法收敛 速度要更快 第三章研究解决了基于梯度型迭代算法的作者在其论文中所给出的一个 公开问题，即最优收敛因子的确定问题，数值实验也证实了理论结果 第四章针对s y l v e s t e r 矩阵方程x + , 4 x b = c ，结合预条件技术，给出了 一个预条件的梯度型迭代算法，数值实验证实了算法的有效性 第五章对全文的工作进行了总结，并对今后的研究方向作了一些展望 关键词：s y l v e s t e r 矩阵方程；梯度迭代算法；松驰梯度迭代算法；最优松驰因 子；预条件 a b s t r a c t a b s t r a c t n u m e r i c a lm e t h o d sf o rs o l v i n gm a t r i xe q u a t i o n sb e c o m ei n t e r e s t i n ga ss o o na s t h e y p l a ya ni m p o r t a n tr o l ei nv a r i o u sf i e l d s ，s u c ha sc o n t r o l ，s i g n a lp r o c e s s i n g ，n e u r a l n e t w o r k , m o d e lr e d u c t i o na n di m a g er e s t o r a t i o ne t c i nt h i sd i s s e r t a t i o n ，w es t u d i e d t h en u m e r i c a lm e t h o d sf o r s o l v i n gt w ok i n d so fs y l v e s t e rm a t r i xe q u a t i o n s a x + x b = ca n d x + a x b = c f i r s t l y ，w ep r e s e n t e d am o d i f i e d g r a d i e n tb a s e d i t e r a t i v e a l g o r i t h m f o rs y l v e s t e rm a t r i xe q u a t i o n s ，b a s e do nt h eg r a d i e n tb a s e d i t e r a t i v ea l g o r i t h ma n dp r o v e dt h en e wa l g o r i t h mw i l lc o n v e r g ef o ra n yi n i t i a lv a l u e u n d e rc e r t a i n c o n d i t i o n s e c o n d l y , w ep r o v e d t h ee x i s t e n c eo ft h e o p t i m a l c o n v e r g e n c e f a c t o ra n dp r e s e n t e daf o r m u l af o r g r a d i e n t - t y p e b a s e di t e r a t i v e a l g o r i t h mb yd e t a i l e dt h e o r e t i c a la n a l y s i s ，w h i c hi sa l lo p e np r o b l e m f i n a l l y ，an e w a l g o r i t h mw a sp r e s e n t e db yc o m b i n i n gt h ep r e c o n d i t i o n e dt e c h n i q u ew i t hg r a d i e n t b a s e d a l g o r i t h m f o r s y l v e s t e rm a t r i xe q u a t i o n sx - i - a x b = c t h i sd i s s e r t a t i o n i n c l u d e sf i v ec h a p t e r s ，w h i c hi so r g a n i z e da sf o l l o w s ： f i r s t l y , t h er e s e a r c hb a c k g r o u n da n dr e s e a r c hs t a t u sa r eg i v e n ，a sw e l la st h e p r e l i m i n a r yk n o w l e d g e f u r t h e r m o r e ，t h em a i nc o n t e n t so ft h i sp a p e ra r eb r i e f e d i nt h es e c o n dc h a p t e r ，am o d i f i e dg r a d i e n tb a s e di t e r a t i v ea l g o r i t h mi sp r e s e n t e d ， b a s e do nt h eg r a d i e n tb a s e di t e r a t i v ea l g o r i t h m a st h ei n f o r m a t i o no ft h ef i r s th a l f i t e r a t i v es t e pi sr e q u i r e dt ou p d a t et h es o l u t i o nb yt h em o d i f i e dm e t h o d ，t h en e w a l g o r i t h ms h o w sb e t t e rc o n v e r g e n c eb e h a v i o r m o r e o v e r , t h en e wa l g o r i t h mh a sb e e n p r o v e dt ob ec o n v e r g e n tu n d e rc e r t a i nc o n d i t i o n n u m e r i c a lr e s u l t ss h o wt h a tt h e p r o p o s e da l g o r i t h mi se f f i c i e n tt h a nt h ee x i s t i n gn u m e r i c a lo n e s a no p e n - p r o b l e m ，t h a ti s ，h o wt oc h o o s et h eo p t i m a lc o n v e r g e n c ef a c t o rf o r f a d i e n tb a s e di t e r a t i v ea l g o r i t h m ；h a sb e e nd i s c u s s e da n ds o l v e di nt h et h i r dc h a p t e r a b s t r a c t t h en u m e r i c a le x p e r i m e n t sv e r i f yt h et h e o r e t i c a lf i n d i n g s i nc h a p t e r4 ，an e w a l g o r i t h mb yc o m b i n i n gt h ep r e c o n d i t i o n e dt e c h n i q u ew i t h t h eg r a d i e n t - t y p ea l g o r i t h mh a sb e e np r o p o s e df o rs o l v i n gs y l v e s t e rm a t r i xe q u a t i o n s x + a x b = ca n dt h e a l g o r i t h m i st e s t e do nc o m p u t e r t h ep e r f o r m a n c eo ft h e p r e c o n d i t i o n e dg r a d i e n tb a s e di t e r a t i v em e t h o di sc o m p a r e dw i t ht h ee x i s t i n go n e s o ns e v e r a ln u m e r i c a le x a m p l e s t h ef a s t e rc o n v e r g e n c eb e h a v i o ri si l l u s t r a t e d f i n a l l y , t h er e s e a r c hw o r ko ft h i sd i s s e r t a t i o ni ss u m m a r i z e da n dt h ep o s s i b l e d i r e c t i o ni sf u r t h e rp r o p o s e d k e y w o r d s ：s y l v e s t e rm a t r i xe q u a t i o n s ；g r a d i e n tb a s e di t e r a t i v ea l g o r i t h m ；r e l a x e d g r a d i e n t b a s e di t e r a t i v e a l g o r i t h m ；o p t i m a lc o n v e r g e n c ef a c t o r ； 一“f 。 p r e c o n d i t i o n ：j ：。，j ：i ： ： 0 1 1 i 目录 目录 摘要i a b s t r a c t ：i i 第l 章绪论1 1 1 引言1 1 2 预备知识2 1 3 本文研究的主要内容4 第2 章第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法5 2 1 基于梯度迭代算法和基于梯度的松弛迭代算法5 2 2 改进型梯度迭代算法6 2 3 数值实验9 2 4 小结1 3 第3 章梯度迭代算法的最优收敛因子1 4 3 1 最优收敛因子1 4 3 2 数值实验1 8 第4 章第二类s y l v e s t e r 矩阵方程的预条件迭代算法2 5 4 1 预条件加速迭代方法简介2 5 4 2a x b + x = c 的梯度迭代算法及预条件梯度迭代算法2 5 4 3 数值实验2 7 4 4 总结2 8 第5 章结束语2 9 致谢3 0 参考文献3 l 附录：m a t l a b 源程序3 4 攻读学位期间的己发或已接受的文章4 5 i v 第1 章绪论 1 1 引言 第1 章绪论 众所周知，在控制论、信号处理、神经网络2 1 、模型降阶f 3 1 、图像恢复川等 领域经常会涉及至l j s y l v e s t e r 矩阵方程的求解，例如矩形域上的椭圆边值问题离散 后会得到一个s y l v e s t e r 形式的矩阵方程；在常微分方程定性理论研究及数值求解 常微分方程的隐式r u n g e k w u t t a 方法与块方法中也常会碰到这类方程；在线性统 计领域中也会遇至u j s y l v e s t e r 矩阵方程的求解问题另外在控制理论及应用中，比如 在极点配置、观测器没计及构造s y l v e s t e r g _ l 数中都涉及对上述方程的求解此外， 当b = 时，s y l v e s t e r 方程即为l y a p u n o v 方程，这类方程在实际应用中同样具有 重要意义，特别在连续时和离散时稳定性分析中 s y l v e s t e r 矩阵方程的求解问题包括精确解的研究和数值解( 即近似解) 的研究 尽管精确解在系统稳定性分析等众多应用当中非常重要，但是当系统的参数未 知时，不可能得到其精确解，此时其数值解的研究就非常必要，而且在许多实 际应用当中，若能求得其数值解就足够了f 5 - 7 1 正因为s y l v e s t e r 矩阵方程数值解在 众多应用领域的重要性，近几年国内外众多学者对各种类型的s y l v e s t e r 矩阵方程 的数值求解进行了研究，得到了一些有效的数值求解算法陋1 本论文主要研究了如下两类s y l v e s t e r 矩阵方程的数值求解问题 彳x + = c 和削圆+ x = c ( 1 ) 其中彳j r ，b 尺胁，c 尺为已知常系数矩阵，尺为未知的 矩阵本文中分别记上述两类s y l v e s t e r 矩阵方程为第一类s y l v e s t e r 矩阵方程和第 二类s y l v e s t e r 矩阵方程 传统的求解方法是利用矩阵方程的拉直及k r o n n e c k e r 积将上述方程转为化一 个等价的m n x m n 阶线性方程组14 1 ，再利用线性方程组的求解算法计算其数值解 然而，通常情况下m 和n 都非常大，从而导致计算线性方程组的常用算法由于存 储空间太大和计算量太大而失去效用为克服这一缺陷，文l 纠7 1 利用矩阵初等变 换将上述矩阵方程转化为三种不同形式的更容易求解的等价线性方程组，然而 这些方法均要求计算相应的矩阵变换2 0 0 1 年，s t a r k e 和n i e t h a - m m e r 研究给出 第1 章绪论 了求解a x 一肋= c 的一个块逐次超松驰迭代算法l 1 9 1 2 0 0 2 年，j o n s s o n 和 k a g s t r o m 在文19 1 和文2 0 1 中给出了计算广义s y l v e s t e r 矩阵方程和l y a p u n o v 矩阵 方程的块递归算法文2 1 1 给出了广义l y a p u n o v 矩阵方程的一个数值求解算法然 而，上述这些算法有一个共同的缺陷，即在每一步迭代时都需要计算矩阵的 逆2 0 0 5 年，d i n gf e n g 等学者利用分级确定原则2 2 。2 3 1 给出了计算s y l v e s t e r 矩阵方 程的一个非常有效的算法，即基于梯度的迭代算法f 2 4 1 ，并且证明了在适当选取 收敛因子的前提下算法是收敛的，但是数值实验显示在一些情况下算法收敛速 度偏慢最近，牛强等在文1 2 4 l 的基础上给出了一个带松驰因子的基于梯度迭代算 法1 2 5 1 ，数值实验显示算法的收敛速度较文1 2 4 1 中的算法要快，但是正如作者所指 出的，最优的松驰因子的选取非常困难 1 2 预备知识 定义1 2 1 惭1 设彳= ( ) c ”期，矩阵的2 一范数和f 一范数分别定义为： ial l ：全( 丸戡( 彳h 彳) ) j ，i iai i f 全( t r ( a 日彳) ) j ， 其中缸( 彳) ，t r ( a ) 分别表示矩阵彳的最大特征值和矩阵的迹 定义1 2 2 m 1 设彳= ( ) c 脓”， a j = ( a i ，a 2 i , - - , a m ，) r ( f = 1 ，2 ，2 ) 令 vpcc彳，=r量 则称v e c ( a ) 为矩阵彳的列拉直 定义1 2 3 f 2 6 1 设彳c 肘砌，8 c 脚，a 与b 的k r o n n e c k e r 积为m r m p 砌口 则 记为m = ao 曰 2 - a 1 b 1 ；i l j 8 b q l = m 第1 章绪论 弓i 理1 2 3 1 2 6 1 设彳c 脚，b c 舣p ，c c 脚，则 v e c ( a b c ) = ( c roa ) v e c ( b ) 引理1 2 4 1 设4 c ，e c 蜘( f = l ，2 ，p ) ，c c 脚是己知矩 阵，则矩阵x c 是如下矩阵方程 的解的充分必要条件是x = v e c ( x ) 是如下线性方程组的解 g x = = v e c ( c ) p 其o pg = 彰o4 ，= l 引理1 2 5 1 2 6 1 设厂( x ，y ) = c o x 7 y ，是变量x , y 的复系数三元多项式，对 。 ，j = o k 彳c “x i ，l ，b c ，定义聊胛阶矩阵厂( 彳，b ) = 勺彳7ob ，j 其中a 。= l ， b o = l 如果a 和b 的特征值分别为五，五，以和从，段，觞，贝j j f ( a ，b ) r _ j 一 的特征值为厂( 乃，从f = l ，2 ，m ，j = 1 ，2 ，甩) 、 引理l - 2 6 1 2 6 i 设彳c 肌撕，口c 删，a 和b 的特征值分别为a ，如，以 和鲳，鲍，以，则s y l v e s t e r 矩阵方程彳x + x b = c 有惟一解的充分必要条 件是 丑+ ，0 ，江1 ，2 ，m ，j = 1 ，2 ，刀 即a 和一b 没有共同的特征值 引理1 2 7 1 2 6 1 设a c 朋黼，b c 脚，a 和b 的特征值分别为 a ，五，a m 和“，段，以，则s y l v e s t e r 矩阵方程x a x b = c 有惟一 解的充分必要条件是 五，1 ，江1 ，2 ，m ，j = 1 ，2 ，刀 c = 碜4 兰矧 第1 章绪论 1 3 本文研究的主要内容 本文主要研究两类s y l v e s t e r 矩阵方程的数值求解问题首先，在d i n gf e n g 等学 者给出的基于梯度迭代算法的基础上给出了一个改进型求解算法；同时，研究 解决t d i n gf e n g 等学者在文f 2 4 1 中所提出的一个公开问题，即基于松驰迭代算法 中最优收敛因子的选择问题，并且利用类似的思想解决了牛强等人在文1 2 4 1 中所 给出的松驰梯度迭代算法中最优收敛因子和最优松驰因子的确定问题；最后， 研究t s y l v e s t e r 矩阵方程预条件求解 具体的结构安排如下： 第一章介绍了两类s y l v e s t e r 矩阵方程的研究背景及现状，同时给出了相 关预备知识 第二章研究第一类s y l v e s t e r 矩阵方程的数值求解问题，给出了一个改进 型基于梯度的迭代求解算法，同时给出了算法收敛的一个充分条件数值实验结 果验证了算法的有效性 第三章研究松驰型梯度迭代算法最优松驰因了的选取问题，并推广到梯 度型迭代算法的最优收敛因子的确定问题 第四章研究第二类s y l v e s t e r 矩阵方程预条件求解方法，并进行了数值实 验以验证方法的有效性 第五章对全文的工作进行了总结，并对今后的研究方向作了一些展望 4 第2 章第一类s y l v c s t c r 矩阵方程的改进型梯度迭代算法 第2 章第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法 2 0 0 5 年，d i n gf e n g 等在文2 4 i 中得用分级确定原则给出了求解s y l v e s t e r 矩 阵方程的一个基于梯度的迭代算法( 简记为g l 算法) ，并证明了在适当条件下 算法对任意初值均收敛g i 算法较之于原有的数值求解算法具有运算量少、存储 空间少的特点同时，数值实验证实了算法的有效性( 特别是当方程组是良态的 时候) 2 0 0 9 年，牛强等人利用相似的思想，给出了带松驰因子的梯度型迭代算 法( 简记r g i 算法) 数值实验显示，在适当选取松驰因子的前提下，r g i 算法 比g i 算法收敛速度要更快然而，正如作者在文中所提出的，r g i 算法最优松 驰因子的选取是非常困难的通过研究g i 算法和r g i 算法，我们发现无论是g i 算法还是r g i 算法，其前半步所求出的解没有有效利用因此，本章我们研究给 出了一个改进型的梯度型迭代算法( 简记为m g i 算法) ，有效地利用了算法前 半步迭代的信息用来更新解理论分析表明，新方法在适当的条件下对任意初始 值是收敛的同时，数值实验显示，m g i 算法比g i 算法收敛速度要快，而与r g i 算法相比，收敛速度差不多但不含松驰因子 2 1 基于梯度迭代算法和基于梯度的松弛迭代算法 考虑如下s y l v e s t e r 矩阵方程 彳x + 胎= c ( 2 ) 其中a 尺，b r 胁，c 尺为已知常系数矩阵，尺一为未知的矩阵 可以把它改写成如下两个等价的形式 a x = c x b 。 和 x b = c a x 丁峰等利用上述分级确定原则给出了如下求解算法忙4 l ： 算法l 基于梯度迭代算法( g i ) 1 任给两个初龇( o ) ，五( o ) ，x ( o ) = 【置( o ) + 五( o ) 】2 ； 2 ( 尼) = x ( k - 1 ) + g a7 【c a x ( k 一1 ) 一x ( 尼- 1 ) b 1 ； 孤二，啥- 第2 章 第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法 3 x 2 ( k ) = x ( k 1 ) + 【c a x ( k 一1 ) 一x ( k 一1 ) b i b 。； 4 x ( 尼) = 【墨( 后) + 置( 尼) 】2 ； 5 若满足精度则结束，否则转2 同时，d i n 吕f e n g 等心4 1 证明了当收敛因子o 瓦j 酉矛盂痂时， g i 算法对任意初值x ( 0 均收敛 基于相似的思想，牛强等给出了基于梯度的松弛迭代算法2 5 1 ： 算法2 基于梯度的松弛迭代算法( r g i ) 1 给定两个初始矩嘲( o ) 和鼍( o ) ，令x ( o ) = 毗( o ) + ( 1 一c o ) x 2 ( o ) ； 2 x ( 后) = x ( k - 1 ) + ( 1 一妫彳7 c a x ( k 一1 ) 一x ( 后一1 ) 日】； 3 置( 后) = x ( k 一1 ) + c o 4 c - a x ( k - 1 ) 一x ( k 一1 ) b b 。； 4 x ( 尼) = c o x l ( 尼) + ( 1 一c o ) j ，2 ( 尼) ； 5 若x ( 尼) 满足精度要求，则结束，否则转2 ， 其中松驰因子0 g o 1 牛强脚1 证明了当收敛因子满足如下关系式时 对任意初值算法均收敛 0 2 烈1 一叫( 五十如+ 以) 卅 矗= 丸双 a a7 】，五= 丸戤 b7 b 】，五= 戤 b a r 】 其中( 4 ) 表示矩阵彳的最大奇异值 根据大量数值试验表明，g i 算法和r g i 算法都能有效地计算，并且当松弛 因子适当地选取后，r g i 算法比g i 算法拥有更快的收敛行为然而，我们发现 g i 算法和r g i 算法都有缺点对于g i 算法，收敛速度慢且对病态问题有可能停 滞至于r g i 算法，最佳松弛因子的选取是一个相当困难的事情，而这正是我们 在第三章中讨论的问题 2 2 改进型梯度迭代算法 通过研究g i 算法和r g i 算法，我们发现无论是g i 算法还是r g i 算法，其 前半步所求出的解没有有效利用事实上，当我们在计算x ：( 露) 时，。( 足) 已经 计算出了因此，我们可以利用，( 足) 的信息去更新x ( | j 2 - 1 ) ，于是可得如下算 6 第2 章第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法 法： 算法3 改进型梯度迭代算法( m g i ) 1 任给两个初馘( o ) ，x 2 ( o ) ，x ( o ) = 【五( o ) + x ：( o ) 1 2 ； 2 x i ( k ) = x ( k 一1 ) + 彳7 【c a x ( k - 1 ) - x ( 尼一1 ) b 】； 一3 x ( k 一1 ) = 【墨( 尼) + x 2 ( 七一1 ) 】2 ； 4 五( 后) = x ( k 一1 ) + f l c 一彳x ( 尼- 1 ) 一x ( 尼一1 ) b b7 ； 5 x ( 尼) = 【x ，( 尼) + x ：( 忌) 】2 ； 6 若满足精度则结束，否则转2 下面讨论这个算法3 的收敛性 定理1 若s y l v e s t e r 矩阵方程彳x + x b = c 有唯一解，且 0 a m i n 1 九a x ( 彳彳7 ) ，1 九。( b7 b ) ) ， 则由算法3 产生的迭代序列x ( k ) 收敛于，即la m x ( k ) = x ；等价于对任何初 始值x ( o ) ，误差x ( k ) = x ( k ) 一x 收敛于零 证明：为了证明的清晰性，在迭代的第四步我们引入一个新变量x ( k 一1 ) 代 替x ( k 一1 ) 定义误差矩阵： x ( k ) = x ( k ) 一x ，x - ( 后) = x l ( 后) 一x ， 二 ( 3 ) x 2 ( k ) = x 2 ( 尼) 一x ，x ( k ) = x ( k ) - x 并定义如下矩阵： 孝( 尼) = ax ( k - 1 ) ，7 7 ( 尼) = x ( k 一1 ) b ， a ( 4 ) 以庀) = a x ( 尼- 1 ) ，f ( 尼) = x ( k ) b 由式( 2 ) ( 4 ) 可以推出如下等式 x l ( 七) = x ( k ) + j u a 7 一孝( 尼) 一刀( 后) 】 ( 5 ) j l 。：”：，x 2 ( k ) = x 、( k ) + f l a r 万( 七) 一f ( 七) 】! 一i ：，7 ：_ ：? ：i 6 ) 7 第2 章 第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法 在( 5 ) 式两边i 司时取f - 范数司得 7 l | x - ( 后) l2 爿lx ( k - 1 ) 1 1 2 + 2 f l t r x ( k - d a7 卜万( 后) 一f ( 忌) 】) + 2j ia r - 4 ( k ) - q ( 1 c ) 】1 1 2 | ix ( k - 1 ) 1 1 2 + 2 肛 善7 ( 尼) 【一孝( 尼) 一7 7 ( 七) 】) + 2 2 丸戤( a a7 1 ) l l 孝( 尼) + 7 7 ( 尼) 1 1 2 同理，在( 6 ) 式两边同时取f 范数可得 i ix z ( k ) i2 - 1 ix ( k 一1 ) 1 1 2 + 2 a t r 一文七) 一f ( 后) 】f 7 ( 尼) + 2 t 2 丑m x ( b 丁b ) | | 万( 尼) + f ( 死) 1 1 2 由x ( 尼) = 【x i ( k ) + x ：( 尼) 】2 ，则我们有 j lx ( k ) l2 = 【l | x 一( 忌) i 2 + | ix 2 ( 尼) 忉2 - i ix ( 尼) 1 1 2 2 - z 1 一儿( a a7 ) 】l | 孝( 尼) + 7 7 ( 尼) 1 1 2 + i ix ( 后一1 ) 1 1 2 2 - 1 一风( b b7 ) 】i i 万( 尼) + f ( 后) 1 1 2 - 1 1x ( o ) 1 1 2 2 七一从1 _ 凤( 4 彳r ) 】顺f ) + 7 7 ( f ) l | 2 一 加一凡( 咖封酮蜘旷+ 善k 学 ( 7 ) ( 8 ) 显然，喜掣 o o 实际上，由算法3 皇成的迭代序列 宕( 后) ，尼= 2 ， 也可被看作是算法1 生成的序列，i 玫。l i m 。x ( k ) = 0 易知，若 0 m i n 1 丸觚( a a r ) ，1 丸缸( b r b ) ) ， 则有 第2 章第一类s y l v e s t e r 矩阵方程的改进型梯度迭代算法 愤f ) + 7 7 ( 珊 0 ，则 1 ) 若6 口 o ，则：艘。 m a x l1 一们儿i1 一b w i ) ) = 等焉 0 a ，则r a i n m a x i1 一删l ，l1 - b w1 ) ) 1 ，此时对任意的w o 有： m a x i1 一a wi ，i1 6 wi 1 ； 3 ) 若口 o 有： m a x i1 一a w i , i1 - b w i 1 证明：若b a 0 ，则 m a x l1 l ，ll 勘甜吲w ， 以亭 ib w - 1 ，w ia + b 从而卜们孙南ab 口= 暑a ，址南ab = 象a + 6+ 6 a 而m 删i n ， m a x i1 一a w l ，il 一6 ，1 ) ) = b - 万a a - i - ，且最小值在三a 处取到 w ” d + d 若a 1 ； w 若b 0 a ，因为l1 一删i 与i1 - b w l 中至少有个大于1 ，从而对任意的w 0 有： m a x i1 一a wi , il - b wi 1 简单计算可将算法1 等价表示成如下形式： z ( 尼) = x ( k 一1 ) + 删7i v a x ( k 一1 ) 一x ( 肛1 ) b 2 f 9 、 + t c a x ( k 一1 ) 一x ( k - 1 ) b i b 7 1 2 、。 从而， ( 尼) = ( 尼) 一 = x ( k 一1 ) 一+ 彳7 【c 一彳( 后- 1 ) 一x ( k d b 】2 + 【c a x ( k - 1 ) 一x ( k - 1 ) b i b 7 2 = x ( k 一1 ) + t d7 【a x a x ( k 一1 ) + x b x ( k 一1 ) b 2 ( 1 0 ) + 【彳x a x ( k 1 ) + x b x ( k - 1 ) b b 7 2 = x ( k 一1 ) 一彳7 ax ( k 一1 ) + x ( k 一1 ) b 】2 一 彳x ( k 一1 ) + x ( k 一1 ) b i b r 2 上面第二个等式用到了( 2 ) 式 对( 1 0 ) 式拉直可得相应的误差方程 v e c ( ( k ) ) = 【，。一中】v e c ( x ( k 一1 ) ) ( 1 1 ) 其中，中= 去 lo ( 彳7 彳) + b 7 oa 7 + b pa + ( b b r ) l 】 由( 1 1 ) 式可得如下命题 命题2 梯度迭代算法( 即算法1 ) 收敛的充要条件是p ( l 。一触) 0 ，的谱半径 都会大于l ，从而算法l 发散若k 。( 中) 大于0 ，而九；。( m ) 小于0 ，即矩阵西为 不定阵，则由引理l 的2 ) 知，对任何的2 0 ，m 的谱半径都会大于l ，算法l 此时也将发散故若g i 算法收敛，则矩阵m 必定是正定阵 类似地，可得到算法2 的误差方程 x ( k ) = x ( k - 1 ) - ( 缈- 矿) 【彳2n x ( k 一1 ) + a 2x ( k 1 ) 曰 + 似( 后- 1 ) b 1 - 4 - x ( k 一1 ) b b 。】， 即 v e c ( x ( k ) ) = 【k 一( c o - ) 神 v e c ( x ( k 一1 ) ) ， 其中中= 去 lo ( 彳7 彳) + 矿圆a r + b oa + ( b b r ) p l ) 由此可知，算法2 与 算法l 数学上是等价的故易得算法2 的最优松驰因子和最优收敛因子应满足 1 6 第3 章梯度迭代算法的最优收敛因子 ( c o - - 0 ) 2 ) 2 瓦丽f 2 瓦面 一 下面考虑求解线性矩阵方程圭4 皿+ 圭g x r 口= f 的g i 算法中最优收敛 i = li = i 因子的选取问题m 1 类似地，可求出其误差矩阵方程为 其中 v p c ( 宝( 尼) ) = 【k 一譬西】v p c ( 量( 尼一1 ) ) ， p 十g 匕= 岛。霹，e o - - e ，p 歹 i = l1 = 1 = r r 色髟p 4 a , + q t c fo 口谚 j = li = 1 1 = 1i = 1 + ( 易硝0 4 g ) 厶+ ( 口4o q 彰) 一j j = li = 1 1 = 1i = 1 引理5 1 2 1 设彳r ”煳，b r m 煳，则有 ： 乞疗( 彳ob ) 巴疗= b pa 岭，- 由引理5 易知，矩阵中为对称阵，从而由定理3 可得 dd l 推论6 若矩阵中为正定阵，则求解线性矩阵方程4 皿+ g x r 口= f 的梯度型迭代算法的最优收敛因子为 p + q k ( m ) + 丸；n ( 中) 1 7 第3 章梯度迭代算法的最优收敛因子 3 2 数值实验 例4 考虑s y l v e s t e r 矩阵方程a x + x b = c ，其中 彳= 三二 ，b = 二，： ，c = 二2 兰 利用m a t l a b 可求得：k 。 ) = 7 1 2 1 3 ，丸i 。( m ) _ 2 8 7 8 7 ，故最优松弛因 子为2 0 2 此外可求得瓦j 瓦万2 。9 现在我们分别取值为： 0 0 5 ，0 1 0 ，o 1 5 ，0 2 0 ，0 2 5 ，0 3 ，由算法1 编程计算可得如下收敛曲线( 图 6 ) 由图6 可知，当= o 2 时，g i 算法的收敛速度达到最快，从而也证实了上 述理论结果 为进一步证实定理3 的结论，给定算法终止的条件为：当解的相对误差小 于10 “时，让算法终止令横坐标表示，纵坐标表示迭代步数，z 同样考虑例4 中 第3 章梯度迭代算法的最优收敛因子 的方程，由算法l 编程计算可得( 图7 ) 燕 懿 芒 剃 从图7 可以看出，当= o 2 时的算法的迭代次数最小 例5 考虑s y l v e s t e r 矩阵方程膨+ = c ，其中a ，b 和c 是1o x lo 矩阵( 即 m = n = 1 0 ) 且由下面程序随机产生( 本例中的实验矩阵取自文1 2 4 1 ) m = 1 o ：刀= 1o ：己= 3 0 ；x = o n e s ( m ，门) 水1e 一6 ： r a n d ( s t a t e ，o ) ；a = t r i u ( r a n d ( m ，脚) ，1 ) + d i a g ( c z + d i a g ( r a n d ( m ) ) ) ； b = t r i u ( r a n d ( n ，刀) ，1 ) + d i a g ( a + d i a g ( r a n d ( n ) ) ) ；c = r a n d ( m ，力) ； 其中参数历分别取0 1 ，o 5 ，1 o ，收敛因子取由定理3 给出的最优值，在 m a t l a b 上编程计算可得g i 算法、m g i 算法、r g i 算法和带最优收敛因子的 g i 算法( 简记为b g i 算法) 的收敛曲线比较图( 图8 ，图9 ，图1 0 ) ? t 锻0 ：j 一 7 一 - 7 。；。 - j _ ，；+ j 一 1 9 第3 章梯度迭代算法的最优收敛因子 的 c 图8 且a = o 1 图9 且a = o 5 2 0 第3 章梯度迭代算法的最优收敛因子 例6 考虑s y l v e s t e r 矩阵方程a x + x b = c ，其中a ，b 和c 是6 0 x 6 0 矩阵( 即 ! 聊= i = 6 0 ) 且由下面程序随机产生( 本例中的实验矩阵取自文m 1 ，是非常病 态的) r a n d ( s t a t e ，o ) ； a = t r i u ( r a n d ( m ，聊) ，1 ) + d i a g ( 10 0 + d i a g ( r a n d ( m ) ) ) ； b = a ；c = r a n d ( m ，朋) + e y e ( m ) 木2 ；c = c + c ； 编程计算可得g i 、b g i 、r g i 和m g i 算法的收敛曲线图( 图1 1 ) 注2 ：具有最佳松弛因子的g i 算法( 即b g i 算法) 比g i 算法和r g i 算法 收敛速度更快，但在一些情况下，b g i 可能比m g i 更快，也可能更慢，这取决 于的条件数 2 1 第3 章梯度迭代算法的最优收敛因子 例7 考虑线性矩阵方程a x + x r b = f ，其中 么= 三二。 ，曰= ：_ 二1 ，f = 萎萎， 其精确解为x = 三三 ，矩阵：和中分别为 2 = 100o 0 010l 。 l ， = 010 0l 0 0 01 一 6 o o3 o 2 由推论7 可求得其最优收敛因子为0 3 9 6 1 ，算法的收敛区间为( 0 ，0 4 1 4 ) 编 程计算可得算法的收敛速度与收敛因子的关系图( f i g 1 2 和f i g 1 3 ) 第3 章梯度迭代算法的最优收敛因子 f i g 1 2 2 3 第3 章梯度迭代算法的最优收敛因子 f i g 1 3 第4 章 第二类s y l v e s t e r 矩阵方程的预条件迭代算法 第4 章第二类s y l v e s t e r 矩阵方程的预条件迭代算法 由前两章可知，梯度型迭代算法的收敛速度由其误差矩阵方程的系数矩阵 中的条件数决定，西的条件数越小，算法的收敛速度越快因此本章我们讨论用 预条件梯度迭代算法求解第二类s y l v e s t e r 矩阵方程削圆+ x = c 4 1 预条件加速迭代方法简介 1 8 4 5 年，j a c o b i 在研究利用平面旋转变换将正规方程变换为对角占优阵2 9 1 时首次引入了预条件的思想1 9 6 8 年，e v a n s 在其论文f 3 0 1 中第一次使用了预条件 迭代法这一术语随后，众多学者对预条件迭代法进行了深入的研究”卜3 4 i 然而， 预条件迭代方法一个主要的突破发生于2 0 世纪七十年代中期，m e i j e r i n k 和 v a nd e rv o r s t 给出了不完全c h o l e s k y 分解共轭梯度算法f 3 5 1 ，而真正使这一