（计算数学专业论文）线性约束矩阵最小二乘问题：理论与算法.pdf

摘要 近年来，随着社会的发展和科学的进步，并受其他学科与工程技术领域应用中产生的 迫切需求所驱动，带各种约束的线性方程及其对应的最小二乘问题越来越引起人们的关 注如在众多领域中拥有广泛应用的s y l v e s t e r 方程，l y a p t m o v 方程和带各种约束的”逆 特征值问题”及其最小二乘问题等 理论上，利用k r o n e c k e r 积，可以等价地将矩阵形式的约束最小二乘问题写成向量形 式，因此，通解能够用高维空间的向量表示由于约束方程可以视为对应的最小二乘问题 残量为零时的特殊情形，所以这种表示也同样适合约束方程但是，这种从矩阵到向量的 等价变换方式引起系数阵的不必要增大，将直接导致计算量和存储量的成倍增3 j n ；同时， 系数矩阵的一些特殊结构在解的表示中可能会丢失为了克服在结构分析和通解表示中 引入k r o n e c k e r 积产生的各种困难，许多研究者更为感兴趣地是从矩阵层面上寻求无约 束或者线性约束最小二乘问题的通解表示常用的方法是借助于一些矩阵分解，如广义奇 异值分解( g s v d ) ，典型相关分解( c c d i 和商奇异值分解( q s v d ) 等一般而言，矩阵方 程可以通过特殊分解简化为”对角”形式，由此产生的新系统是容易求解的：我们只需将 新变量阵合理的进行分块即可，其中的子块一部分可以直接求解，另一部分则通过求解一 个小规模的线性系统实现此外，有些研究者也通过迭代数值求解一些特殊的约束最小二 乘问题 一般地，矩阵分解是对特殊问题采取的特定解法，需要很强的技巧性；并且它也依赖 于方程本身和约束条件因此，很难将一个特定的分解直接应用于一系列相关的却又不同 的问题可”移植”性较差此外，这些方法通常是不”鲁棒”的，微小的改交约束条件可能 会引起求解的巨大变化一个自然的问题是：对于一般的线性约束最小二乘问题，是否在 通解和迭代上存在着统一的求解模式在本文中，我们试图在理论和算法上给出框架式的 研究方法，通过对老问题从新的切入点和视角入手进行研究我们相信文中提出的方法对 约束最小二乘问题的求解能够提供启发和帮助 本文的主要贡献如下： 1 利用约束空问的基矩阵( 约束矩阵) ，我们用一个低维的列向量空间( 坐标空间) 刻 划该线性约束空间，并且给出一般矩阵到这个约束空间上正交投影的矩阵表示 2 我们揭示了强约束最小二乘问题和弱约束最小二乘问题解空间之间的内在联系 强约束解集是否包含于弱约束解集，取决于方程的右端矩阵l 对于一般情形，我们证明 了：存在一个t 的等价映射c 趵，使得关于右端为妒( r ) 的强约束最小二乘闯题与原强约 i 浙江大学博士学位论文 束问题同解更为重要的是：以妒( 为右端的弱约束问题的解集中，包含了原强约束问题 的所有解因此，对给定的右端庐( ，如果相应的弱约束问题的通解已知或者容易得到，那 么，原强约束问题也就容易求解我们用定理3 5 揭露上述潜在的性质，同时，该定理也表 明：强约束解集实际上就是强约束空间与以毋( t ) 为右端的弱约束解集的交集因此，等价 映射的获锝就成为了求解约束最小二乘问题的关键。t 的等价映射多( 即是不唯一的，它 可以取成是在强约束变换值域( 约束问题本身的线性变换关于强约束空间的值域) 上的正 交投影在文中，我们提出了刻划等价映射的几个定理，并且给出了等价映射可验证的一 些构造途径然后，将这些理论应用于一些特殊的约束最小二乘问题，得到了通解的简单 表示形式从弱约束解集中寻找强约束通解为一般的带约束最小二乘问题提供了一种统 一的求解模式，特别适合逐步施加更多约束条件的矩阵最小二乘问题的求解 3 对于特殊约束的两类特定方程，通过约束条件中矩阵的特征值分解，我们实现约束 方程的无约束化；同时将原约束方程等价于一个通解已知的无约束方程；然后重构出原约 束方程的解在通解的表示中不涉及具体的特征值分解 4 我们提出了求解线性约束最小二乘问题的几种矩阵形式k r y l o v 子空间方法本 质上，这些算法是向量形式的c g l s , g m r e s 和i s q r 对应的矩阵迭代，但不仅仅是它 们简单的重写理论上，借助于基矩阵和k r o n e c k e r 积，我们得到约束最j 、- - 乘问题的无 约束向量形式，并对其应用向量形式的k r y l o v 子空间方法，由此可以推导出矩阵形式的 k r y l o v 方法但是在具体的矩阵迭代中，我们要求是不涉及k r o n e c k e r 积和基矩阵的因 此，这种向量到矩阵的对应是不平凡的在文中，我们利用定理5 2 刻划了给定向量到约束 空间上特定矩阵的1 - 1 对应，从而实现了k r y l o v 予空间方法从向量到矩阵形式地等价转 换，并给出了特殊约束方程的具体算法此外，我们也用几个例子说明这些算法的数值效 果我们相信所提出的想法将适合于寻找剔的矩阵形式的迭代法 关键词；基矩阵，正交投影，特征值分解，矩阵形式迭代，k r y l o v 子空间方法 a b s t r a c t i nt h er e c e n td e c a d e s , w i t ht h ed e v e l o p m e n to fs o c i e t ya n dt h ep r o g r e s so f s c i e n c e , m o r ea n dm o r en e wp r o b l e m sw h i c ha r eu r g e n tt ob es o l v e da r i s ef r o mt h ee n s i n e e r t e c h n o l o g ya n dm a n yo t h e rd o m a 妇m a n y o ft h e s ep r o b l e m sc a nb er e d u c e dt ol i n e a r s y s t e m so fm a t r i xe q u a t i o n sa n d o rl e a s ts q u a r e sp r o b l e m sw i t hl i n e a rc o n s t r a i n t so n s o l u t i o n s , t h o s es y s t e m si n c l u d es y l v e s t e re q u a t i o n , l y a p u n o ve q u a t i o n , i n v e r s ee i g e n - v a l u ep r o b l e ma n dt h e c o r r e s p o n d i n gl e a s ts q u a r e sp r o b l e m sw h i c h h a v eb e e nw i d e l y c o n s i d e r e di nm a n y a p p f i e dd o m a i n m o r ea n d m o r e p e o p l eh a v e b e e na t t r a c t e di nm i s r e s e a r c h 矗e l d t h e o r e t i c a l l y , al e a s ts q u a r e sp r o b l e mi nm a t r i x f o r mc a l lb er e w r i t t e ni nv e c t o r f o r m b y k r o n e c k e rp r o d u c t s os o l u t i o n so ft h em a t r i xl e a s ts q u a r e sp r o b l e ma r ek n o w n i nt e r m so fh i g h e rd i m e n s i o n a lc o l u m n - v e c t o r s s od o e si tf o rm a t r i xe q u a t i o n ss i n c ea l i n e a rs y s t e mo fm a t r i xe q u a t i o n sc mb el o o k e da sal e a s ts q u a r e sp r o b l e mw i t hz f f f o r e s i d u a l h o w e v e r , t h i se q u i v a l e n tt r a n s f o r m a t i o nf r o mm a t r i xl st ov e c t o rl sm a y 朗? l a r g e t h e c o e f f i c i e n t m a t r i c e s o f t h e l i i l e a r s y s t e m s u n n e c e s s a r i l y , w h i c h r e s u l t s i n a g r e a t c o m p u t a t i o nc o s ta n ds t o r a g er e q u i r e m e n t m o r e o v e r , p o s s i b l es p e c i a ls t r u c t u r eo ft h e c o e f f i c i e n tm a t r i c e si nt h em a t r i xs y s t e mw i nb el o s ti nt h ev e c t o r - e x p r e s s i o n so fg e n e r a l s o l u t i o n s , e v e ni fm a t r i xs o l u t i o n sa r er e c o n s t r u c t e df r o mt h ev e c t o r - e x p r e s s i o n s t o a v o i dt h e s ed i f f i c u l t i e s ，b a s i c a l l yt oa v o i di n t r o d u c i n gk r o n e c k e r p r o d u c t si nt h e s t r u c - t u r ea n a l y s i so fs o l u t i o n so rf o r m u l a t i n gs o l u t i o n s , m a t r i x - l e v e ld i s c u s s i o no ra n a l y s i s f o rs o l u t i o n so fm a t r i xl s p r o b l e m si sm u c hi n t e r e s t i n ga n dt h e r eh a v e b e e ns o m ev a l u - a b l ee f f o r t so nt h i si s s u e t h et e c h n i q u e s c o m m o n l y u s e da r es o m em a t r i x - f a c t o r i z a t i o n s s u c ha st h eg e n e r a 嘲曲s u i a rv a l u ed e c o m p o s i t i o n ( g s v d ) ，t h ec a n o n i c a lc o r r e l a t i o n d e c o m p o s i t i o n ( c c d ) ，a n dt h eq u o t i e n ts i n g u i a rv a l u ed e c o m p o s i t i o n ( q s v d ) i ng e n - e r a l , t h e s ef a c t o r i z a t i o n sa 舱u s e dt or e d u c em a t r i xe q u a t i o n st ob es i m p l ed i a g o n a l - l i k e f o r ms ot h a tt h en e ws y s t e m sc a nb ee a s i l ys o l v e db ys u i t a b l yp a r t i t i o n i n gt h en e w i r m a t r i x - v a r i a b l e s s o m es u b - m a t r i c e sa 舱d e t e r m i n e di m m e d i a t e l ya n do t h e r sa r eo b - r a i n e db ys o l v i n gas m a l ll i n e a rs y a e m i nt h em e a n t i m e , i t e r a t i v em e t h o d sf o rn u - m e r i c a l l y s o l v i n gt h el e a s ts q u a r e sp r o b l e m sa i e a l s oc o n s i d e r e d s o m e p r o b l e m sw i t h s p e c i a lc o n s t r a i n t sh a v eb e e ns o l v e d 浙江大学博士学位论文 i ng e n e r a l , t h ep r o d u c ef a c t o r z a t i o na p p l i e do nm a t r i xl sp r o b l e m sr e q u i r e sp r o - f i c i e n ts k i l l , d e p e n d i n go nt h es y s t e mo fm a t r i xe q u a t i o n sa n dt h ec o n s t r a i n t so ns o l u - t i o n s i ti sd i f f i c u l tt od i r e c t l ya p p l yac o n s i s t e n tf a c t o r i z a t i o np r o d u c eo nt h o s e 曲t e d b u td i f f e r e n tp r o b l e m s f u r t h 衄o r e , t h o s ea p p r o a c h e sa r eg e n e r a l l yn o tr o b u s t i v l i n o r m o d i f i c a t i o n so nt h ec o n s t r a i n tm a yg i v ef i 8 et og r e a tc h a n g eo ns o l u t i o n s an a t u r a l q u e s t i o nk e p ti n0 1 1 1 m i n d i st h a tw h e t h e rw ec a nf i n dau n i f o r n ta p p r o a c hf o ra n a l y s i s o ri t e r a t i v e l ys o l v i n gt h el i n e a rs y s t e mo fm a t r i xe q u a t i o n sw i t hl i n e a rc o n s t r a i n so ns 伊 l u t i o n s t h i st h e s i sw i l lc o n c e n t r a t eo nt h i sq u e s t i o na n d t r yt og i v ea n s w e l 8 , b a s e do n an e w v i e w p o i n ta n dj u m p i n g - o f fp o i n to ft h e s e w e l l - k n o w np r o b l e m s w ew i l lp r e s e n t af x a l n ew o r ki f lb o t ht h e o r ya n d a l g o r i t h m s w eb e l i e v et h a tt h e m e t h o d sp r o p o s e di n t h i st h e s i si se n l i g h t e n i n ga n dh e l p h t lf o ro t h e rc o n s t r a i n e dm a t r i xl sp r o b l e m s 办ec o n t r i b u t i o n so ft h i st h e s i sa 弛o u t l i n e da sf o l l o w s ： 1 w ec h a r a c t e rt h el i n e a rc o n s t r a i n tm a t r i x - s p a c e sb yt h e i rl o w e r - d i m e n s i o np a - r a m e t e rv e c t o rs p a c e s , u s i n gm a t r i x - f o r m b a s i s t h o s ep r o p e r t i e sw i l lb eu s e dt oa n a l y z e a n ds o l v et h el e a s ts q u a r e sp r o b l e m sw i t hl i n e a rc o n s t r a i n t s , a n df o ra r b i t r a r ym a t r i x , w ea l s op r e s e n ti t so r t h o g o n a lp l = 0 j e c t i o ni nt h ec o n s t r a i n e ds p a c e 2 w eu n c o v e rt h ei n h e r e n tr e l a t i o n sb e t w e e l lt h es o l u t i o n - s p a c eo ft h em a t r i xl s w i t h ( r e l a t i v e l y s t r o n g e r ) c o n s t r a i n t s a n d t h e s o l u t i o n - s p a c e t o t h e m a t r i x l s w i t h w e a k e r c o n s t r a i n t s w h e t h e rt h ef o r m e rs o l u t i o ns p a c ei sc o n t a i n e db yt h el a t t e ru n i q u e l yd e - p 朗d so nt h er i g h t - h a n ds i d em a t r i xt o ft h ee q u a t i o n w ep r o v et h a tt h e r ee x i s t s a ne q u i v a l e n tt r a n s f o r m a t i o n ( 即o nt h er i g h t - h a n ds i d em a t r i xts u c ht h a tt h es o - l u t i o ns p a c eo ft h ec o n s t r a i n e dp r o b l e mi sn o tc h a n g e dw h e nt h el h s m a t r i xti s r e p l a c e db y ( m o r ei m p o r t a n t l y , t h es o l u t i o ns p a c eo ft h ew e a k e r - c o n s t r a i n e dn q h a - t r i x 玛w i t ht h et r a n s f o r m e dr h s ( 刃c o n t a i n sa l lt h es o l u t i o n so ft h e 嘶g i r l a lp r o b - l e mw i t ht h e ( s t r o n g e r ) c o n s t r a i n t s 。t h e r e f o r e , i ft h es o l u t i o ns p a c ea s s o c i a t et ot h e w e a k - c o n s t r a i n t sa n dr s a h 毋仃) i sk n o w no r 锄b e e a s i l yo b t a i n e d , t h es o l u t i o ns e to f t h es t r o n g - c o n s t r a i n e dp r o b l e mc a nb ee a s i l yc o n s t r u c t e d i ti st h ei n t e r s e c t i o no ft h e s t r o n g - c o n s t r a i n ts p a c ea n dt h es o l u t i o ns e to ft h ew e a k - c o n s t r a i n tp r o b l e m w ed i s - c o v e rt h i sl a t e n tp r o p e r t i e sb yt h e o r e m3 5 t h i st r a n s f o r m a t i o nc a nb e ( n o tl l n i q u e ) 吐圯o r t h o g o n a lp r o j e c t i o no ft h e r h sm a t r i xo nt ot h er a n g es p a c eo ft h el i n e a rs y s t e m o fm a t r i xe q u a t i o n sc o r r e s p o n d i n gt ot h es t r o n g - c o n s t r a i n t s w ep r e s e n tt h ed e t a i l so f c o n s t r u c t i n gt h ee q u i v a l e n tm a p t h i sd e v e l o p m e n ti si m p o r t a n t f o rs o l v i n gl i n e a r l y 英文摘要 c o n s t r a i n e dm a t r i xl sp r o b l e m ss i n c et h em a t r i xl sw i t hw e a k e rc o n s t r a i n t s ( o rw i t h - o u tc o n s t r a i n t s ) m a yh a v e b e e ns o l v e d w ea p p l yt h i st e c h n i q u eo ns o m ec o n s t r a i n e d m a t r i xl sp r o b l e m sa n do b t a i ns i m p l em a t r i x - r e p r e s e n t a t i o n so fs o l u t i o n s i n d e e d ，t h i s t e c h n i q u ec a nb e u s e dt oh a n d l et h em a t r i xl sp r o b l e m sw h e n m o r el i n e a rc o n s t r a i n t s a r ea d d e d 3 w ed i s c u s st w ok i n d so fs t r u c t u r e - m a t r i xe q u a t i o n sw i t hs p e c i f i cc o n s t r a i n t s t h e o r e t i c a l l y , am a t r i xe i g e n v a l u ed e c o m p o s i t i o na r eu s e dt or e n l o v et h e c o n s t r a i n t s i no u r d i s c u s s i o n h o w e v e r , t h ee i g e n v a l u ed e c o m p o s i t i o n i sa l s og o t t e no f fl a t e r g e n - e r a ls o l u t i o n so f 廿伦c o n s t r a i n e de q u a t i o n sa r er e c o n s t r u c t e d n o t et h a tt h ef o r m u l ao f t h eg e n e r a ls o l u t i o n si ss i m p l ea n de i g e n v e c t o r - f r e e 4 w e p r o p o s e s o m e m a t r i x - f o r m k r y l o v s u b s p a c e m e t h o d s f o r s o l v i n g l i n e a r l y c o n - s t r a i n e dm a t r i xl sp r o b l e m s b a s i c a l l y , t h e ya r et h ea l g o r i t h m sc g l s , g m r e s ，b i d i a g o - n a l i z a t i o nl a n c t _ d $ , a n dl s q ri nm a t r i x - i t e r a t i o n t h em a t r i x - f o r mk r y l o vs u b s p a c e m e t h o d sa r en o tt r i v i a lr e s e t t i n go ft h ev e c t o r - k r y l o vm e t h o d s t h em a t r l x - k r y o v m e t h o d sa 地d e r i v e db y t h e o r e t i c a l l yr e m o v i n g t h ec o n s t r a i n t s ( u s i n gb a s i so ft h ec o n - s t r a i n ts p a c e ) ，e m p l o y i n gk r o n e c k e rp r o d u c tt of o r mal i n e a rs y s t e mi nl o n g - v e c t o r f o r m , a n da p p l y i n gv e c t o r - f o r mi 无约束化后 成为一个通解易求的线性方程，则约束方程的通解是容易给出的然而这将不可避免的涉 及这样几个问题：无约束化过程带来的额外代价，我们在重构约束解的时候能否尽可能的 减少或者避免；通解的表示形式是否简洁在本文中，我们考虑两类特殊约束线性方程的 通解通过对约束条件中的矩阵进行特征值分解，我们实现约束方程的无约束化，同时将 原约束方程等价于个通解已知的无约束方程，然后再重构约束方程的通解通解的表示 形式是简单的，并且不涉及具体的特征值分解需要指出的是：以特征值作为过渡的这套 方法是对特殊问题采用的特定解法，不具有普遍性 4 第1 章引言 1 3 3 矩阵形式的迭代方法 借助于第2 章定义的基矩阵和k r o n e c k e r 积，我们将线性最小二乘问题( 1 2 ) 向量化， 同时对约束条件进行无约束化，从而得到无约束的向量形式最小二乘问题( 即对( 1 4 ) 无 约束化) 因j 比，从理论上求解该问题是容易的但是注意到k r o n e c k e r 积在实际计算中存 在巨大的缺陷，而矩阵形式的迭代方法在内存的需求和计算量的减少是明显的，因而，人 们更为感兴趣地是矩阵形式的迭代但是如何寻求适合的算法并将它表示成矩阵形式却 是不容易的注意到，i _ , t l o v 子空间方法f 2 ，4 5 1 ，6 0 ，6 1 ，6 3 ，删涉及到的主要运算只有 两种：矩阵和向量的乘积，向量和向量的乘积；再结合基矩阵的特殊性厩因此，是适合于 表示成约束空间上矩阵形式的迭代所以，我们用矩阵形式的k r y l o v 子空间方法求解最 b - - 乘问题( 1 2 ) 但是，在具体的矩阵迭代中，我们要求是不涉及k r o n e c k e r 积和基矩阵 的因此，这种向量到矩阵的对应是不平凡的在文中，我们利用定理5 2 刻划了给定向量 到约束空间上特定矩阵的1 - 1 对应，从而实现了k r y l o v 子空间方法从向量到矩阵形式地 等价转换常用的i 嘶l o v 子空间的方法有三种：共轭梯度法( c g ) 【3 4 ，3 5 ，7 川，广义极小残 量法( g m r e s ) 6 0 , 6 2 和基于l a n c z o s 双对角的l s q r 5 3 , 5 4 共轭梯度法和g m r e s 要 求系数阵是方的，而l s q r 则对系数阵没有任何的约束为此，我们从两大方面考虑待求 的约束最小二乘问题： 1 ) 由( 1 4 ) 无约束化后对应的正规方程和基矩阵的性厩我们得到矩阵形式的c g l s 和g m r e s ； 2 ) 而借助于l a n c z 0 8 双对角化直接求解最小二乘问题，并结合基矩阵，我们则可以得 到矩阵形式的i s q r 由于正规方程扩大了原问题的条件数，因此，c g l s 和g m r e s 在数值计算中存在着不足 但是作为求解约束最小二乘问题的一种方法，它们的操作过程是简洁的，几何意义是明了 的所以，如果在精度要求不是特别高的情形下，无论是在理论还是实际上这两种算法都 具有一定的意义而l ! s q r 是直接应用于原方程，不涉及到正规方程，因此拥有较好的数 值效果我们相信所提出的想法将适合于寻找别的矩阵形式的迭代法 1 4 本文的组织和结构 第1 章为引言；第2 章首先定义了基矩阵( 约束矩阵) ，然后介绍了几个特殊空间的基 矩阵；第3 章对于约束最小二乘问题考虑如何从弱约束的通解中重构出它的强约束通解； 第4 章讨论两类特殊约束线性方程的通解；第5 章讲述了如何用k r y l o v 子空间方法实现 约束最t b - 乘问题矩阵形式的迭代，并给出了具体的例子；最后一章给出了本文的总结， 并指出了未来研究的方向以下是关于各章内容的较为详细的介绍： 5 浙江大学博士学位论文 第2 章介绍线性空间的约束矩阵，并且给出常见的几个线性空间( 例如块对角，对称 反对称，只交换对称反对称，各种t o e p l i t z 等约束空间) 的约束矩阵，借此可以将长向量形 式的约束空间用一个短的自由向量空间刻划 第3 章对于约束最小二乘问题，考虑如何从弱约束解集中重构出它的强约束通解首 先，我们给出可以从弱约束的通解中重构出它的强约束通解的本质条件；其次，我们提出 了几个定理对这个条件进行具体的刻划，并将它归纳为定理3 髟最后，我们用几个例子说 明我们的想法 第4 章对两类特殊约束的特定方程的求解通过特征值分解我们实现约束方程的无 约束化，同时将原约束方程对应通解已知的方程，然后重构出原约束方程的解，在通解表 示中不涉及具体的特征值分解 第5 章介绍约束最小二乘问题的矩阵形式迭代，借助基矩阵的特殊性质和向量形式 的最小二乘问题，我们得到矩阵形式的k r y l o v 子空间方法：c g l s , g m r e s 和l j s q 并 对特殊的约束方程给出具体的算法和数值例子 最后一章，我们对全文所提到的线性方程及其最小二乘阿题的求解做一个总结，指出 不足之处，同时还展望了今后的工作 1 5 本章小结 本文对于一般的线性约束方程以及对应的最小二乘问题在理论和算法上给出了框 架式的研究方法通过对老问题从新的切入点和视角入手进行研究，希望对约束最小二乘 问题的求解能够提供帮助和启发 6 第1 章引言 本文采用符号及定义参见：7 扩“表示实m x 疗阶实矩阵，厶表示n 阶单位p e l 表 示厶的第i 列，最f = e t e x ，x + 和x t 分别表示矩阵x 的一般逆，m o o r e - p e n r o s e y - 义逆和转置，而x 一表示x 的一个g 逆，即满足x x x = x ，v e c ( x ) 表示x 按照列排 起来的长的列向量，i i x l l 2 和l i x l l f 表示矩阵x 的2 范数和f r o b e n i u s 范数对任意矩阵 a ，b ，矩阵迹t r a c e 记成t r ，且定义内积，b ) = t r ( b t a ) 另外，s y m ( x ) = ；( x + x t ) 和m y r a ( x ) = ( x x t ) 分别表示矩阵x 的对称和反对称部分l 支= i x + x ， 冗 = ，一x x + 分别表示用m o o r e - p e n r o s e 广义逆表出的x 列空问和行空间零空间上的 正交投影，它们对应的g - 逆形式记作醵= i x x 和硪= i x x 一 7 第2 章约束空间：坐标及正交投影的表示 在讨论矩阵约束最小二乘问题之前，仔细分析和刻翊一些线性约束空间及其基矩阵 ( 我们称之为约束矩阵) 的特点与结构，是非常有必要的在这一章中，我们介绍几种常 见的约束空间及其约束矩阵，例如对应于块对角，对称反对$ 钙p 交换对称反对张，各种 t o e p l i t z 等的线性约束空问通过约束矩阵( 基) ，我们用一个低维的列向量空问( 坐标空 间) ，来刻划该线性约束空间更为重要的是，我们可以给出一般矩阵到这个约束空间上正 交投影的矩阵表示本文的其他部分( 如在弱约束解集中寻求强约束解，以及矩阵形式的 k r y l o v 子空间方法) 中将多处用到这样的矩阵正交投影 2 1 坐标映射与正交投影 假设c 7 z ”是一个矩阵形式的七维线性约束空间如果已知c 上的一组标准正交 基( 矩阵) q 已”“，= l ，蠡 ，即满足 训g ：g i ) = 1 如筹， 那么c 上的任何矩阵x 都可以表示为 x = x l g l + + 钆g ， 其中z = ( z - ，$ ) t 冗为x 在这组基下的坐标向量它由 g 和x 唯确定： 巧= t r ( f 岛) ，j = 1 ，七 为明确起见，我们将坐标向量$ 记为9 c ( x ) ： 卵僻) = ( t r ( j f g l ) ，t r ( x t g k ) ) t ， ( 2 1 ) 骅渤g ，+ 蝴国，巧= 锣， 一， 浙江大学博士学位论文 定理2 1 - 设g 1 ，瓯是约束空间c c 缈。”的一组基，c = v e c ( v 1 ) ，v e c ( g k ) l 是向量形式的约束矩阵对任意的z 7 已m x z 在c 上的正交投影为 v c ( z ) = z i g l + + z k g k 则p c ( 刁的坐标向量g c ( z ) = ，张l t 可以表示为 g c ( z ) = c + v e c ( _ p c ( z ) ) ， ( 2 5 ) 并且v e c ( 忍( z ) ) = c g c ( z ) 特别地，如果g l ，g 相互正交( 不一定单位长) ，那么 勺= 丽t r ( z r a j ) 歹= 1 ，知( 2 6 ) 定理2 1 表明：坐标映射g c ( z ) 和正交投影尼( z ) 是依赖于约束空间基的选取如果 基是正交的，则鲫( 刁和正交投影恐喀) 可以借助( 2 6 ) 作简单的表示；而一旦基是不正交 的，需要先对基进行正交使之成为正交基，然后再进行表示，我们一般通过g r a m - s c h m i d t 方法实现正交化但是在考虑特殊约束空间c 时，我们往往选择平凡的正交基，至于正交 基是否要标准化，主要是看坐标映射和正交投影的表达是否简洁因此，在下面的章节中， 如非特别说明，约束阵c 是对c 中的正交基而言的 下面对一些特殊的约束空间d 例如块对角，对称反对称，p 交换对称反对称，各种 t o e p l i t z 等，我们给出正交基下任意矩阵的正交投影和坐标映射为方便起见我们约定 勖= 孵，其中e ，勺是单位阵厶的第硒列 2 2 块对角约束 考虑块对角矩阵空间 c = x ：x = d i 8 9 ( 噩，x 2 ) ，噩7 妒“m ，x 2 舻。1 2 ) ( 2 7 ) 记n = n 1 + 砌，则c 的标准正交基可以取为 g 巧= ，1 s i ，j n l ，或n l + 1 s i ，j n 其次序可确定为： g n ，g n l ，i ，g l ，h ，g t h h ，g m + 1 一l + l ，6 k 搠+ 1 ，i k + 1 一，g n ，矗 对任何z ，护。 若将其分块为 z = ( 乏乏) ， 第2 章约束空间：坐标及正交投影的表示 根据定理2 1 ，容易得到 绑，= ( = 锱) ，p c ( 耻 ( 玩锄) 2 3 对称和反对称约束 如果c 为7 p “上对称矩阵全体，则可取平凡的( 非标准) 正交基 瓯= 玩，t = 1 ，弼= 岛+ 啄，1 歹 t ( 2 9 ) 显然州g 钏刍= 1 川g 圳刍= 2 ，i j 我们可将它们排序为 g 1 1 ，瓯1 ，g 篮，g 帕， 根据定理2 1 ，对任何矩阵z 一( 锄) 7 。0 卵( z ) = ( 机下z 2 z + z z 2 ，z , n l 广f z l n 渤t z 2 3 + z 3 2 ，堑笋，) r 对任意的矩阵x 7 妒一，如果定义 黼。僻，：i ? x l ：n ，, 。ll 缈。， 一 员h 坐标映射如( z ) 有简单的表示形式 e c ( z ) = 瓯+ 半岛= s m ( z ) ， t = l，l 叫卦咿 1 1 浙江大学博士学位论文 则由反对称矩阵全体构成的约束空间cc7 妒。n 有如下平凡的( 非标准) 正交基 g o = 一啄， 1s j i 竹( 2 1 0 ) 显然川g 洲；= 2 ，i j 如果我们将基也作如下的排序 g 2 , ，g l ，g 3 2 ，g , a ，g n m 一1 ， 则由定理2 1 ，下面结论将成立 g c ( z ) = v e c 冠( 鼬y m ( z ) ) ，p o ( z ) = 髓y m ( z ) ( 2 1 1 ) 实际上，利用 z = s y m ( z ) + 蹭y m ( z ) 以及s y m ( z ) 与螂，m ( z ) 之间( 向量意义下) 的正交性： t r ( 8 y m ( z ) t 鸥y m ( z ) ) = 0 ， 很容易证明z 在对称矩阵空间上的正交投影为s y m ( z ) 同样，z 在反对称矩阵空间上的 正交投影为哪m c z ) 2 4 p - 交换约束 令p 是给定的n 阶方阵考虑与p 可交换的矩阵集合c ， c = xip x = x p 对实对称阵p ，由特征值分解得 p = ( d i a g ( a 1 ，a t ) 矿， ( 2 1 2 ) 其中，t 是它的不同特征值的个数，是凡的重数x 被称为和p 可交换的，当且仅当 x = q d i a g ( 墨，五) q t ， ( 2 1 3 ) 其中x 砂。毛，笔1 觑= n 显然，当没有其他约束的时候，五是独立的变量在下面的 部分，