（计算数学专业论文）控制理论和计算中一些问题的投影方法.pdf

控制理论和计算中一些问题的投影方法 摘要 本文研究控制理论和计算中一些大规模问题的投影方法我们给出迭代求解广 义s y l v e s t e r 方程的g a l e r k i n 方法和极小残量方法，这两种方法都利用a r n o l d i 过程 构造某个k r y l o v 子空间的一组正交规范基并利用系数矩阵的结构减少了对存储量 的需求基于全局a r n o l d i 过程，我们又分别给出求解大规模s y l v e s t e r 方程和大规 模广义s y l v e s t e r 方程的新的投影方法为求解二次特征值问题，我们首先引入基于 方阵a 1 和a 2 以及具有正交规范列的矩阵q 1 的块二阶k r y l o v 子空间，然后再分 别给出生成该子空间一组正交规范基的块二阶a m o l d i 过程和生成双正交基的块二 阶双正交过程利用投影技巧给出两种块二阶k r y l o v 子空间方法，这两种方法都直 接应用于二次特征值问题，从而保留了问题的结构和性质然后我们给出保结构模 型降阶算法来求解大规模二阶多输入多输出动力系统的模型降阶问题这是基于块 二阶k r y l o v 子空间的投影方法，利用块二阶a m o l d i 过程来生成投影空间的一组正 交规范基计算所得的约化系统保留了原始系统的二阶结构最后，我们给出求解 传输理论中非对称代数r i c c a t i 方程的修改的简单迭代法和修改的牛顿法 关键词； 广义s y l v e s t e r 方程；g a l e r k i n 方法；极小残量法；s y l v e s t e r 方程； 全局a r n o l d i 过程；二次特征值问题；块二阶k r y l o v 子空间；块二阶a r n o l d i 过程； 块二阶双正交过程；二阶动力系统；模型降阶；非对称代数r i c c a t i 方程；简单迭代 法；牛顿法 p r o j e c t i o nm e t h o d sf o rp r o b l e m si nc o n t r o lt h e o r ya n dc o m p u t a t i o n a b s t r a c 。r t h ep r e s e n tp h d d i s s e r t a t i o ni sc o n c e r n e dw i t hp r o j e c t i o nm e t h o d sf o rl a r g e - s c a l e p r o b l e m si nc o n t r o lt h e o r ya n dc o m p u t a t i o n w ep r o p o s eg a l e r k i nm e t h o da n dm i n i m a l r e s i d u a lm e t h o df o ri t e r a t i v e l ys o l d n gg e n e r a l i z e ds y l v e e t e re q u a t i o n s 。t h ea l g o r i t h m su s e k r y l o vs u b s p a c ef o rw h i c ho r t h o g o n a lb a s i sa r eg e n e r a t e db yt h ea r n o l d p r o c e d u r ea n d r e d u c et h es t o r a g es p a c er e q u i r e db yu s i n gt h es t r u c t u r eo ft h em a t r i x w ep r o p o s ean e w p r o j e c t i o nm e t h o db a s e d o ng l o b a la r n o l d ip r o c e d u r ef o rs o l v i n gl a r g es y l v e e t e re q u a t i o n s a n dt h el a r g eg e n e r a l i z e ds y l v e s t e re q u a t i o n s f o rs o l v i n gl a r g e - s c a l eq u a d r a t i ce i g e n v a l u e p r o b l e m ( q e p ) ，w ef i r s ti n t r o d u c eab l o c ks e c o n d - o r d e rk r y l o vs u b s p a c eb a s e do nap a i r o fs q u a r em a t r i c e sa la n da 2a n da no r t h o n o r m a lm a t r i xq 1 ，t h e nw ep r e s e n ta b l o c k s e c o n d - o r d e ra r n o l d ip r o c e d u r ef o rg e n e r a t i n ga no r t h o n o r m a lb a s i so ft h es p a c ea n da b l o d cs e c o n d - o r d e rb i o r t h o g o n a l i z a t i o np r o c e d u r ef o rg e n e r a t i n gb i o r t h o n o r m a lb a s i s b y a p p l y i n gt h ep r o j e c t i o nt e c h n i q u e s ，w ed e r i v et w ob l o c ks e c o n d - o r d e rk r y l o vs u b s p a c e m e t h o d s t h e s em e t h o d sa r ea p p l i e dt ot h eq e pd i r e c t l y h e n c et h e yp r e s e r v ee s s e n t i a l s t r u c t u r e sa n dp r o p e r t i e so ft h eq e p w ep r e s e n t8s t r u c t u r e - p r e s e r v i n gm o d e l - o r d e rr d u c t i o nm e t h o df o rs o l v i n gl a r g e - s c a l es e c o n d - o r d e rm u l t i i n p u tm u l t i - o u t p u td y n a m i c a l s y s t e m s i ti sap r o j e c t i o nm e t h o db a s e do na b l o c ks e c o n d - o r d e rk r y l o vs u b s p a c e w e 啦et h eb l o c ks e c o n d - o r d e ra r n o l d ip r o c e d u r et og e n e r a t ea no r t h o n o r m a lb a s i so ft h ep r o - j e c t i o ns u b s p a c e t h er e d u c e ds y s t e mp r e s e r v e st h es e c o n d - o r d e rs t r u c t u r eo ft h e o r i g i n a l s y s t e m f i n a l l y , w ep r o p o s eam o d i f i e ds i m p l ei t e r a t i v em e t h o da n d am o d i f i e dn e w t o n m e t h o df o rn o n s y m m e t r i ca l g e b r a i cr i e c a t ie q u a t i o n sa r i s i n gi nt r a n s p o r tt h e o r y k e y w o r d s lg e n e r a l i z e ds y l v e s t e re q u a t i o n s ；g a l e r k i nm e t h o d ；m i n i m a lr e s i d u a l m e t h o d ；s y l v e s t e re q u a t i o n s ；g l o b a la r n o l d ip r o c e d u r e ；q u a d r a t i ce i g e n v a l u ep r o b l e m ； b l o c ks e c e n d - o r d e rk r y l o vs u b s p a c e ；b l o c ks e c o n d - o r d e ra r n o l d ip r o c e d u r e ；b l o c ks e c o n d - o r d e rb i o r t h o g o n a l i z a t i o np r o c e d u r e ；s e c o n d o r d e rd y n a m i c a ls y s t e m s ；m o d e l - o r d e rr e d u e - t i o n ；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 s ；s i m p l ei t e r a t i v em e t h o d ；n e w t o n m e t h o d l n 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均己在论文中作了明确的声明 并表示了谢意。 作者签名：鱼氐氲昌期：绁! z ：【 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：熊盎导师签名： 日期：垫丑： 第一章前言 大规模控制理论和计算具有广泛的实际背景和实际需求【6 2 1 ，2 9 ，3 0 ，7 6 1 ，如；超 大规模电子电路；大规模结构动力学和微电子系统等等在这些问题中，有矩阵方 程问题，包括r i c c a t i 方程以及s y l v e s t e r 方程等，也有二次特征值问题和模型降阶 问题由于实际问题规模的日益增大，往往需要利用投影技巧来得到一个小规模的 问题，从而易于计算和求解基于k r y l o v 子空间构造各种投影方法成为解决大规模 问题的重要手段 本文以基于k r y l o v 子空间的投影方法为主线，围绕控制理论和计算中的一些 问题逐一进行探讨 第二章讨论求解广义s y l v e s t e r 方程的两种k r y l o v 子空间方法【1 6 】，分别为g a l e r k i n 方法和极小残量方法，这两种方法都通过a m o l d i 过程【3 3 】构造某个k r y l o v 子空间 的一组正交规范基，再利用投影技巧得到一个低阶的广义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 的显解表达式来构造新的投影方 法【1 8 】，分别提出s y l v e s t e r 全局a r n o l d i 方法和广义s y l v e s t e r 全局a r n o l d i 方法 在第四章讨论求解二次特征值问题的块二阶k r y l o v 子空间方法【7 1 二次特征 值问题有很多重要的实际应用，比如在结构分析中的有限元离散 8 6 】以及各向异性 材料的弹性形变【8 5 】等对于求解二次特征值问题，【1 4 ，9 7 l 中提出了用投影技巧得 到二次特征值问题的一些特征值( 常常是那些模最大的特征值和相应的特征向量) 的方法这些方法直接应用于二次特征值问题，而不必将二次特征值问题扩展为一 个阶数更高的线性特征值问题，所以它们的一个典型特征是保留了矩阵的结构以及 谱的性质在这一章中将推广他们的思想，提出块二阶k r y l o v 子空间方法来求解二 次特征值问题 第五章讨论多输入多输出时不变二阶系统的模型降阶问题f 7 2 | 由于实际问题规 模的日益增大，处理大规模控制问题的常用方法是利用模型降阶技巧 9 ，1 1 1 3 ，3 6 - 3 8 来降低原问题的规模具体来说就是适当选取例如k r y l o v 子空间的一组基，将原问 1 题投影到低维子空间上，在低维子空间上求解小规模的控制计算问题近年来，【13 】 中提出了利用二阶a r n o l d i 过程对二阶线性系统进行模型降阶的方法，其最显著的 特点是不仅保持了系统的二阶结构而且和标准的k r y l o v 予空间方法进行线性化得 到的系统有同样的近似的阶数这种方法是为单输入、单输出系统设计的而本章 将针对时不变的多输入多输出二阶线性系统提出保结构的块二阶a m o l d i 算法 第六章考虑用迭代法求解传输理论中得到的非对称代数r i c c a t i 方程【1 7 ，7 3 1 ，出 于实际问题的需要，只有方程的极小正解才具有物理意义我们将根据传输问题中 r i c c a t i 方程的特性，改进简单迭代法( 7 卅和n e w t o n 迭代法( 7 5 j ，使之有更快的收敛 速度 现在我们给出本文常用的一些记号m 表示由所有n m 阶矩阵构成的空 间；”表示n 维向量空同0 1 和1 1 2 分别表示向量或矩阵的1 范数和2 范 数对两个矩阵x ，y r n x m ，定义内积僻，y ) f = t r a c e ( x t y ) ，其中t r a c e ( ) 表示 矩阵的迹，其相应的范数就是p t o b e n i u s 范数，用来表示厶表示n n 阶 的单位矩阵韶表示维向量空间中的第m 个坐标向量s p a n q t ，口2 ，) 和 s p a n q 1 ，q 2 ，锄) 分别表示由向量q l ，9 2 ，q n 和矩阵q 1 ，q 2 ，劬的列张成的 子空间上标t 表示向量或矩阵的转置 2 第二章求解广义s y l v e s t e r 方程的k r y l o v 子空间方法 考虑利用k r y l o v 子空间方法求解广义s y l v e s t e r 矩阵方程 a x b x = g( 2 0 1 ) 其中a r n x n ，b r m 。m 和c r 。m 是已知的系数矩阵，x r 。 f 是要找 的解 广义s y l v e s t e r 方程( 2 0 1 ) 在控制和通信理论中扮演着重要的角色【3 0 】已有很 多学者对广义s y l v e s t e r 方程( 2 0 1 ) 的数值解法进行了研究，提出了许多行之有效 的方法当各类矩阵方程阶数适中时，可以用直接法进行求解，参见【1 9 ，4 2 ，4 8 ，0 0 而当a 和b 是大规模稀疏矩阵时，迭代方法就更加适用【1 6 ，7 0 】 令x = k 1 ，z 2 ，z j i f l ，其中：r i 是矩阵x 的第i 列定义线性算子y e a ：r 。盯一 r m 3 3 1 ， v e c ( x ) 四，z ；，瑶1 t 于是广义s y l v e s t e r 方程( 2 0 1 ) 可以写成线性方程组 a v e c ( x ) = v e c ( c ) ， ( 2 0 2 ) 其中a = b t o a i m r m n 。m ，o 代表k r o n e c k e r 积，详见 3 3 】k r o n e c k e r 积 有下面的性质： v e c ( a b c ) = ( c toa ) v e c ( b ) ， v e c ( a ) t v e c ( b ) = t r a c e ( a r b ) ， ( a o b ) ( c o d ) = ( a c o b d ) ， ( a o b ) t = a t o b t 令a ( a ) 和一( 口) 分别表示矩阵a 和b 的谱，那么矩阵a 的谱可以表示为 口( 一4 ) = 九一1 ：丸口( a ) ，口) ，i = 1 ，2 ，- 一，y ；j = 1 ，2 ，一，m ) 3 这表明广义s y l v e s t e r 方程( 2 0 1 ) 有唯一解当且仅当沁1 对任意k a ( a ) 和 k 口( b ) 成立在本章中我们总是假设这个条件成立，即广义s y l v e s t e r 方程( 2 0 1 ) 有唯一解 本章将给出迭代求解广义s y l v e s t e r 方程( 2 0 1 ) 的g a l e r k i n 方法和极小残量方 法，这两种方法都基于a m o l d i 过程由a r n o l d i 过程可以构造某个k r y l o v 子空间 的一组正交规范基，再利用投影技巧，就可以得到一个低阶的广义s y l v e s t e r 方程 对这个小规模的广义s y l v e s t e r 方程就可以利用直接法或者迭代法进行求解在接下 来的表述和分析中，有时为方便起见，考虑方程( 2 0 2 ) 2 1 g a l e r k i n 方法和极小残量方法 完全正交化方法，作为一种g a l e r k i n 方法由s a a d 在【8 3 】中给出，而广义极小 残量( g e n e r a l i z e dm i n i m a lr e s i d u a l ，简称为g m r e s ) 方法，则由s a a d 和s c h u l t z 在 i s 4 中给出这两种方法都利用a r n o l d i 过程来构造某个k r y l o v 子空间 尼七( a ，口) 二= s p a u v ，a v ，一，a 知一1 口) 的一组正交规范基 2 1 1a r n o l d i 过程 在本小节中首先回顾一下a r n o l d i 过程【2 ，3 3 1 算法描述如下： 算法2 1 1 a r n o l d i 过程 j 选择 ，令砚= 川口1 1 2 2 循环：j = 1 ，2 ，知 t i = a 吩 帆，j = t 乒 ，t l ，= 一，j 仇，t = 1 ，2 ，一，j b + 1 ，j = i i 叫1 2 ，若嘞+ 1 ，j = 0 ，则算法中止 吩+ l = t t ，吻+ 1 ，j 算法2 1 1 利用修正的g r a m - s c h m i d t 过程计算k r y l o v 子空间( a ， ) 的一组 正交规范基 1 ，抛，地 引入矩阵 巧：= v l ，忱，吲，j 仕，+ 1 ， 4 并且令矾r k 。表示上h e s s e n b e r g 矩阵； 凰= h uh 1 2 h 2 1 惋2 h 3 2 h l k 7 b 七 蚝 ： h k k 其非零元，j 由算法2 1 1 得到另外定义上h e s s e n b e r g 型矩阵鼠豫( + 1 ) 。： 凰；k 赫t 那么根据算法2 1 1 ，有下面的关系式成立： h k = v t a v k ，a r k = k + l 凰 2 1 2 广义s y l v e s t e r 方程的g a l e r k i n 方法和极小残量方法 由于在实际应用中，( 2 0 2 ) 中矩阵的规模可能很大，所以当很大时，很难在内 存中存储k r y l o v 子空间g k ( b roa j ，r o ) 的一组基本节将给出求解广义s y l v e s t e r 方程( 2 0 2 ) 的g a l e r k i n 方法和极小残量方法，这两种方法都通过利用( 2 0 2 ) 中系数 矩阵a 的结构来减少对存储空间的需求在这两种方法中，用 ( b t ，g ) 西( a ，) 来替代k r y l o v 子空间 c k ( b t 固a 一，t o ) ，其中f r ，g r f 在【5 2 】中，h u 等 利用这种形式的子空间来求解s y l v e s t e r 方程 首先。由a m o l d i 过程可以分别生成k r y l o v 子空间k ( a ，f ) 和 c m ( b t , g ) 的两 组正交规范基锄) 譬1 和 q ) 銎1 至于向量f 和g 如何选取，我们将放在下一小节 中讨论 引入矩阵k ：= 扣l ，t ，2 ，仇】，i n ，n + 1 ) 和：= 呻1 ，耽，蚴1 ，j m ，m + 1 由a r n o l d i 过程得到的上h e s s e n b e r g 矩阵h ，日b 和上h e s s e n b e r g 型矩 阵吼，如满足 h a = 曙a k ，l i b = w 焉b r w k ， a v = + 1 j 玖，b r w = 职。+ 1 - i b ， a k ；v n h a + 撬。帅( ) 丁，b t = w m h b + 积1 ，。+ 1 ( 剞) t 因此，矩阵矸ok 的列张成子空间局。( b t ，9 ) o1 c 。( a ，) 的一组正交规范基 设z o 是方程( 2 0 2 ) 的一个初始近似解，相应的残向量为 r o = c 一( ( b r o a ) x o z o ) ， 其中c = w c ( e ) 我们希望从子空间k k ( b r ，9 ) o 咒。( a ，) 中找到一个向量z o ，使得x l = z o + z o 是方程( 2 0 2 ) 一个更好的近似解向量z o 可以写为 z 0 = ( o k ) 玑 其中y r m n 因此新的残向量为 r l = r o 一( ( b r o a ) ( w m o 碥一( 仰k 固k ) 暑，) = i 0 一( ( b t w k ) o ( ) ) y + ( w k o k ) v = r o 一( ( w + 1 f l b ) 固( 0 1 詹) ) y + ( 1 1 7 m b ( 2 1 1 ) 再根据g a l e r k i n 条件 r l 上s p a n w 1 0 k 就得到 ( 。v 。) t r o ( 。碥) r ( ( ( + - 凰) 。( k + - 宜 ) ) ”+ ( 。k ) ) 因此有 ( ，m o k ) t r o = ( t t s o h a ) y y ( 2 1 2 ) 即 h a y h t y = 昭岛w k ， ( 2 1 3 ) 其中矩阵r o r x m 满足r o = v e c ( 凰) 而矩阵y 舯。”满足= v e c ( y ) 这样，为得到向量f ，就只需求解一个小规模的线性系统( 2 1 2 ) 或者小规模的 广义s y l v e s t e r 方程( 2 1 3 ) 总结上述求解过程就得到求解广义s y l v e s t e r 方程( 2 0 2 ) 的g a l e r k i n 方法 接下来，我们导出求解广义s y l v e s t e r 方程( 2 0 2 ) 的极小残量方法 首先由( 2 1 1 ) 得 r o 一( ( - 。+ 1 ) ( 吼。吼) ( 。k ) ) ( 卜( 。+ 1 ) ( + ，固+ 1 ) r ) r o + ( 椰) ( ( 们) r r 0 一( 岛。凰+ ( k 1 ，。l + 1 。) 可1 ，( 2 1 4 ) 其中“l ，表示由0 + 1 ) g + 1 ) 的单位矩阵的前i 列构成的矩阵，i m ) 极小残量法要求 f f n | f 。= ，嗽一( 。1 ) ( + t 。) r ) + ( w r 卅，。k + 1 ) ( ( l 。“ 一( 岛。疗 ) | ，+ ( ，m “m 。“- ，) ) 此 = 一( 棚) ( + l 。) r ) r o i j 。 所以为了得到向量可，需求解最 b - - = - 乘问题 螂r a i n i i ( w m + 1 。+ 1 ) r r o 一( 如。凰+ ( 厶冲1 ，m 。厶+ 1 ，n ) 讹 这等价于要求矩阵y 满足下面的极小化条件； ，敬。1 l 嚼1 r o w 1 一以y 雄+ k 1 ，n y t “。惦 ( 2 为求解( 2 1 5 ) ，首先定义线性算子s ：r n x m r 加+ 1 ) ( 州。1 ) 为 s ( y ) ：= 吼y 詹舌- - i n + 1 ，。y 蠕+ 1 。 在内积( ，) f 意义下，s 的共轭算子舻：r ( n + 1 ) x ( 卅1 ) 一r n m 是 矿( 矿) = 詹j p 凰一焉1 。矿k + 1 。 7 其中矿r ( 什1 ) 。( m + ”因此得到( 2 1 5 ) 的法方程 i 尹( s ( y ) ) = s r ( 蠕1 r o l 4 7 ；件1 ) ， ( 2 1 6 ) 其中 矿( s ( y ) ) = 群s ( y ) 岛一毋1 。s ( y ) 厶件1 ，。 = 霹【矾y 郦一k 1 ，。y j ： = + 1 。】岛 一曩1 。阮y 霹一厶+ l 。y 磊l ，。】k + 1 。 = 豆j a a y 豆毛叠b h t y h a h a y h 否+ y 1 而 酽( 蠕1 r o w , 。+ i ) = 霹噍1 r o w , + i b 8 一昭r o w t 可以用下面的全局共轭梯度法【3 4 】来求解法方程( 2 1 6 ) 令c 表示线性算子c ：r n m 。舯x m ，在内积( ，) f 下它是对称正定的全局共 轭梯度法求解方程 c ( y ) = d ， 其中y d 渺m 算法描述如下； 算法2 1 2 全局共轭梯度法 j 选择初始矩阵娲，计算初始残量矩阵凰= d c ( r o ) ，令p o = r o 幺循环。j = 0 ，1 ，j m “ q = ( 弓，马) f ( c ( 弓) ，弓) f 巧+ 1 = 巧+ 弓 岛+ 1 = 而一a j c ( 弓) 岛= ( 毋+ 1 ，r j + d f i r ，r j ) f 马+ 1 = 吗+ 1 + 岛弓 下面详细给出求解广义s y l v e s t e r 方程( 2 0 1 ) 的重开始极小残量方法【1 6 】 算法2 1 3 求解广义s y l v e s t e r 方程的重开始极小残量方法 1 选择初始近似解，得到初始残量矩阵r 0 ：= c a x o b + x o 8 2 由算法2 4 得到向量，和9 3 应用a r n o l d i 过程分别得到k r y l o v 子空间k + 1 ，) 和k 。+ 1 ( b t ，g ) 的两组正 交规范基k + 1 ，+ 1 以及矩阵西 和亩百 4 形成近似解 x 1 = x o + k y w 主， 英中y 是法方程( 2 i 6 的解 置计算新的残量矩阵r 1 = p , o v n + l 豆- y 霹w ：+ 1 + v n y w 三若l i r x l i f 足够小则 停止；否则，令x o ：= x 1 ，r o ：= r 1 ，转到幺 注2 1 g a l e r k i n 算法和极小残量法唯一不同的地方在于算法的第4 步，矩阵y 是 方程偿1 剀的解 若c = v e c ( c ) = 9o ，且初始解取为x o = 0 ，下面的结果表明近似解噩= k y w 三是一个扰动后的广义s y l v e s t e r 方程的精确解 定理2 1 若c = v e c ( c ) = g o ，且初始解取为弱= 0 若a r n o l d i 过程对矩阵a 已 经进行了t l 步，对矩阵口已经进行了m 步，那么有 ( a f a ) x l ( b f b ) 一墨= g 其中矩阵霸= 7 l 昭。+ 1 碡以及f e = 黑l , m w m w t + 1 证明在方程( 2 1 3 ) 的左端乘上，右端乘上w 三，利用关系式a v = 碥置t + 鼢。+ l ( 毋) t 和b t w , 。= w m h b + 磁鲁1 ，。i + l ( e 船) t 得 ( a v 一锹。坼t ( e 妒) t ) y ( b t 一嘿，m + ( 留) r ) 1 一y 瞩= a 既然和都具有正交规范列，从而有 a j 岛b 一，h v n b + ) l 。a x l w k 韶) t ，。t + 1 一牟1 。 。十1 ( e 磬) t v t x t b + 端，。嘏1 ，。+ 1 ( 毋) r 曙五留t + l 一班= d 定义矩阵f l a = h 一( a ) 。v t 。和如= h ( s ) 1 ，。o 。 三+ l 即得 一乃) 墨一殆) 一托= c n 注2 2 从上面的定理中即可看出，若 ，。= 罂1 。= 以蜀就是广义s y l v e s t e r 方程 ( e 0 1 ) 的精确解 9 2 1 3 子空闻的选择 下面考虑如何在算法2 1 3 中选择合适的向量，r n 和g r 吖理想情况下， 希望选择向量，和g 使得伽矗。( 口t ，g ) o h 似，) 然而这样的向量很难找到，所 以转而寻找使得0 砌一g p 川2 较小的向量，和g ，或者等价地说，使得i i 硒一，怙 较小，其中、，e c ( 岛) 一r o 令a l 是凰的最大奇异值，口l 和叮r 分别是相应的单位长度的左右奇异向量 那么有 m i n f l 劢一向t 怙= 0 岛一口1 m 一忙( 2 1 7 ) 要求解极小化问题( 2 1 7 ) 通常需要很多的运算量，我们转而用下面的办法来寻找近 似解向量，和g 假设，0 ，g 0 定义函数 t f f , g ) ：_ 疡一向t 惰 那么就有 嚣= 。坳营，= 篇，( z 1 s ) 以及 面o t = 。铮g = 器 ( 2 1 9 ) 因此，给定向量g ，从( 2 1 8 ) 就可以得到极小化t ( ，g ) 的向量，相应地，给定向 量，从( 2 1 9 ) 式可以得到极小化t ( f ，g ) 的向量g 下面给出近似求解( 2 1 7 ) 的算 法，由这个算法我们得到向量，和g 算法2 1 4 【5 2 】求得，和g 的方法 若f f 岛| f 1 0 凰。那么令，是矩阵扁中得到范数| f 凰i | 1 的那一列，然后再由 偿j 9 j 得到向量g 若0 凰0 1 n 一1 幺全局a r n o l d i 过程在第n 步停止当且仅当矩阵y 的级为n 只当n p 时， h ，) 是矩阵k r y a v 子空间l 品( a ，v ) 的一组f 正交基 类似于【5 7 】，我们定义一些记号：表示n n 8 矩阵= 陬，】凰 表示+ 1 ) n 的上h e s s e n b e r g 型矩阵，其元素k ，j 由算法3 1 1 得到，而矩阵风 则是从矩阵鼠中删去最后一行后得到的n n 的上h e s s e n b e r g 矩阵 令= 驯4 g 怙，阢= d u d i i f ，利用全局a r n o l d i 过程可以分别生成矩阵 k r y l o v 子空间( a ，) 和 = ，l ( b r ，啊) 的两组f 正交基k 与w 。 利用，月l 和w f 。，h b 以及k r o n e c k e r 积记号o ，得到下列关系式【5 7 】： b r 嚣二溢( h b 裂矗糍1 , r n w l m 箍， 叫， b r w m = w mo 厶) + 憾 十1 碍， 、 其中霹= i o ，0 一，l 】r “”，螺= 【o | ，0 ，纠r “” 3 1 2s y l v e s t e r 方程的精确解 【3 1 】中证明s y l v e s t e r 方程( 3 1 1 ) 的唯一解可以写为 x = m j a 一1 c d r b j 一1 ， ( 3 1 3 ) 仁l j = l 其中p 是矩阵a 相对于矩阵g 的极小多项式p 的阶数( p ( a ) c = 0 ) ，q 是矩阵 矿相对于矩阵d 的极小多项式q 的阶数( q ( b r ) d = 0 ) 而矩阵r = ( 竹，) ，i = 1 ，p ，j = 1 ，q 则是一个低维的s y l v e s t e r 方程的解 下面来看如何利用全局a r n o l d i 过程构造的基来得到矩阵r 的元素椎j 【5 8 】中 给出了下面的引理 引理3 1 令p 是矩阵c 的级，n p 令= 眦，】，其中矩阵，由 全局a r n o l d i 过程所构造那么对任意j = 1 ，n 一1 有 h = ( 职e l p 厶) ， 其中e 1 = ( 1 ，0 ，0 ) t 舯 2 】 下面来看具体的推导过程，首先( 3 , 1 3 ) 可以写为 x = 【ca c a p 1 c1 ( r o 厶) 舯 r x = f i i d i l f b ( e p x c r o 厶) 再利用k r o n e c k e r 积的性质有 ( ( e 铲) t ( e ) t 霹 ( e ) t ( 酲) a 一1 琊_ 1 e p 】。l ) 增 jj x = ”g “f u 。“f 嵋( e p 岛e p 丑；一l e 妒 r 定义矩阵 于= o c 归o d 忙 e p 缉e p 琊e p r 就得到( 3 , 1 3 ) 钓简化表达式 x = 嵋( 于o l ) 嵋 ( e p ) t ( e ) t 田 ( e p ) t ( 砑) a 一1 ( e p ) t ( e ，) r 瑶 ( e ( 口) r ( h t ) q 一1 又由c ：l l c l l f h ，d = i i d i i f 啊以及全局a m o l d i 过程可知 ( 3 ，1 4 ) a 睇= ( 耳。l ) ，b r m = m ( 风。l ) c 3 1 5 ) 盎；一 0如 最后再利用( 3 1 4 ) 和( 3 1 5 ) 得 o = a x + x b + c d r = 哆 ( 易于+ p 霹+ e 妒( e p ) rj j c i i 州i d o ，) p 厶 m 孕 而矩阵于是低维s y l v e s t e r 方程 日；亡+ f 爿孑+ i i c i f i i d i f e 2 p ( e ) 丁= 0 ( 3 1 6 ) 的解容易看出矩阵 e 2 p 日p e p j ；f ；一1 e p 和 e 岛e p ) 明e ，】 都是上三角矩阵且它们的对角元都不等于零 这样，s y l v e s t e r 方程( 3 1 1 ) 的精确解就由( 3 1 4 ) 和( 3 1 6 ) 给出 3 1 3s y l v e s t e r 全局a r n o l d ! 方法 本小节中，我们来讨论如何利用全局a r n o l d i 过程得到s y l v e s t e r 方程( 3 1 1 ) 的 低秩近似解 既然s y l v e s t e r 方程( 3 1 1 ) 精确解的表达式由( 3 1 4 ) 和( 3 1 6 ) 给出，那么这里 考虑的近似解矗。就定义为 。= ( yol ) 焉， ( 3 1 7 ) 其中 m 矩阵y 是低维s y l v e s t e r 方程 h a y + y 日否+ i i g | i f l l m l l f e p ( e p ) r = 0 ( 3 1 8 ) 的解从这里开始，总假定随着仉m 不断增大，( 丑- ) + a j ( h b ) 0 对所有的 i = 1 ，竹和j = 1 ，m 成立，这样就保证了( 3 1 8 ) 有唯一解y 低维s y l v e s t e r 方程( 3 1 8 ) 可以用直接法，比如h e s s e n b e r g - s c h u r 方法【4 2 来求 解 接下来，我们给出残量矩阵f 范数的个上界，这个上界可以用来判断迭代是 否应当中止，而且计算这个上界不涉及额外的矩阵向量积 定理3 1 令矗。是s y l v e s t e r 全局a r n o l d i 方法在第n ，m 步得到的近似解，r ( ，m ) = a ) 【。+ 五。b + c d t 是相应的残量那么有 。懿，。( ，。) 哆( m + 1 ) ( i 鼎。刚y ( n 胁i 罂1 ，。阳y ”哟， ( 3 1 9 ) 其中y ( 呐是矩阵y 的最后一列而y ( 呐是矩阵y 的最后一行 2 3 证明由( 3 1 7 ) 知残量矩阵可以写为 矗，。( j m ) = a z n ( yo 厶) _ n 焉+ 。( y 固厶) 1 壤b + c d 于 利用( 3 1 2 ) 以及e m = 衍固厶和晶= 毋圆l 可得 ，。( 矗。) = k + l ( go 厶) 兹+ 1 其协( 蹦+ y h 舌b + i i c ( 抑l i f i i o i i f 印k e p 广蛾，) 利用( 3 1 8 ) 并对残量取f 范数，有 叫驯憾w l 怙卜 ( 龆，赫y 婚葛垴) 。吼 既然 n ，w 2 ，件1 ) 是矩阵k r y l o v 子空间 + 1 ( b t ，d ) 的一组f 正交基并且 + 1 = 【m ，w j ，啊计1 】，从而有 0 焉+ 1 临刮n + 1 另一方面，不难证明 | l t ( 螂l ，。品垆y 鼎。苫y 删) 固厶m = l l ( 赫y 鼎一0 蛾 = i 托，。刚y ( “) 幅+ j 瓣1 。j 2 | j y ( ”幢 其中y ( m ) 是矩阵y 的最后列而y ( ”) 是矩阵y 的最后一行 口 ( 3 1 9 ) 给出的残量。( ，。) 范数的上界可以用来在s y l v e s t e r 全局a r n o l d i 算 法中停止迭代而且在算法中只有当残量范数收敛后才形成近似解仇，从而节约 了大量的运算量 下面我们给出s y l v e s t e r 全局a r n o l d i 算法【1 8 】 算法3 1 2 s y l v e s t e r 全局a r n o l d i 算法 j 设定参数k l ，z 1 并且设k = 0 ，z = 0 ，n = 1 ，m = z 1 ，令= 叫ij o i i f ，m = d i i d i f 2 对j = + 1 ，+ 2 ，k + 1 ，根据算法只j j 构造矩阵k r y l o v 子空问瓦( a ，) 的 一组f 正交基k + 1 ，k + 1 ，同时得到矩阵玩 只对j = z + 1 ，z + 2 ，z + z 1 ，根据算法3 1 j 构造矩阵k r y l o v 子空间( b r ，d ) 的 一组f 正交基w z + 1 ，m + j 1 ，同时得到矩阵l i b 4 求解低维问题。h a y + y i - 瑶b + 0 c 0 f o