（计算数学专业论文）一类奇异方程组的求解和扰动分析.pdf

一类奇异方程组的求解和扰动分析 摘要 本文主要研究奇异线性方程组的有关理论，在众多的奇异线性方程组中，一类 其系数阵是值域h e r m i t e 的奇异线性方程组近年来引起了许多学者的关注，这类 矩阵( 也称为e p 阵) 以及与其相应的线性方程组出现在许多应用问题中对其广 义逆的研究表明，其广义逆是保持正则逆最多性质的一类广义逆，另外其相应的方 程组的解的结构也有一些一般奇异线性方程组所没有的良好性质在奇异线性方程 组的求解方法中。我们提出了基于正则分裂的二级迭代法并给出收敛分析i 在论文 的第三章我们对奇异的结构化矩阵的置换秩进行了研究，得到了一些结论并给出了 应用在奇异线性方程组解的扰动分析方面，我们首先从最具有代表性的广义逆着 手，给出了扰动结果，并推广到加权广义逆，最后讨论了奇异线性方程组的条件数， 从而推广了非奇异线性方程组的条件数的一些结果，在论文最后一章，以n a v i e r - s t o k e s 方程为例，首先说明n a v i e r s t o k e s 方程经差分离散后所得的线性方程组是 e p 线性方程组，鞍点问题一般由n a v i e r - s t o k e s 方程、o s e e n 方程或s t o k e s 方程 引出对这类问题的求解，已经存在很多方法，其中包括直接法、u z a w & 类型算法 及k r y l o v 子空间方法本文回顾了已经存在的u z a w a 类型算法，将z u l e h n e r 在 【8 2 l 中提出的统一方法应用到广义鞍点问题，分析了算法的收敛性问题，并给出了 定理和结论 关键词：e p 阵；广义逆；u z a w a 方法；预条件；s y l v e s t e r 置换秩；鞍点问题； t h e o r ya n dp e r t u r b a t i o na n a l y s i sf o rac l a s so f s i n g u l a rl i n e a re q u a t i o n s a b s t r a c t t h ep r e s e n tp h d t h e s i si sc o n c e r n e dw i t ht h et h e o r e t i c a la n a l y s i sf o rac l a s s o fs i n g u l a rl i n e a re q u a t i o n s a m o n gs om a n ys i n g u l a rl i n e a re q u a t i o n sw ea r ev e r y i n t e r e s t e di nt h ee q u a t i o n sw h o s ec o e f f i c i e n tm a t r i c e sa r er a n g eh e r m i t i a n ( e pm a t r i - c 郫1 f i r s tw ew i l l8 e et h eg e n e r a l i z e di n v e r s eo fe pm a t r i xh a ss om a n yq u a l i t i e sa s s a m e 髂t h en o r m a li n v e r s e a n dt h es o l u t i o no fae pl i n e a re q u a t i o na l s oh a ss o m e g o o dq u a l i t i e st h a tt h ec o m m o ns i n g u l a rl i n e a re q u a t i o n sd on o th a v e f o rs o l v - i n gt h es i n g u l a rl i n e a re q u a t i o n s ，w ep r e s e n tt h ei t e r a t i v em e t h o d sb a s e do np r o p e r s p l i t t i n g sa n dg i v et h ec o n v e r g e n c ea n a l y s i s i nt h et h i r dc h a p t e rw em a k es o m e r e s u l t 3o fs y l v e s t e rd i s p l a c e m e n tr a n ko nt h ed i s p l a c e m e n ts t r u c t e ro fg e n e r a l i z e d i n v e r s e a st h ep e r t u r b a t i o na n a l y s i s ，w em a k er e s u l t so nt h ec o n d i t i o nn u m b e rw i t h t h eg e n e r a u z e di n v e r s ea n dw e i g h t e dg e n e r a l i z e di n v e r s e ，w h i c he x t e n dt h er e s u l t s o nt h en o n s i n g u l a rl i n e a re q u a t i o n s c o n d i t i o nn u m b e r ，t h e nw eg i v et h ep e r t u r b a - t i o n f i n a l l y , w e w i l l s e e t h e e q u a t i o n s f r o m t h e d i s c r e t e n e s s o f n a v i e r s t o k e se q u a t i o n a f ea l le pl i n e a re q u a t i o n s s a d d l ep e n tp r o b l e m sa r ei n d u c e df r o mn a v i e r - s t o k e s e q u a t i o n ，o s e e ne q u a t i o na n ds t o k e se q u a t i o n t h e r ea r em a n ym e t h o d sf o rs o l v - i n gt h e m a m o n gt h e mw em e n t i o nd i r e c ts o l v e r ，u z a w at y p ea l g o r i t h m sa n dk r y l o v s u b s p a c em e t h o d s w ef i r s tr e v i e wa ut h ee x i s t i n gu z a w am e t h o d s a n dt h e na p p l y z u l e h n e r su n i f i e da p p x o a c hi n1 8 2 t oa a a l y z et h es t a b i l i z e ds a d d l ep o i n tp r o b l e m s k e y w o r d s ：e pm a t r i x ；g e n e r a l i z e di n v e r s e ；u z a w aa l g o r i t h m s ；p r e e o n d i t o n e r ； s y l v e s t e rd i s p l a c e m e n tr a n k ；n a v i e r - s t o k e s 方程；s a d d l ep o i n tp r o b l e m n 第一章前言 近年来人们对类奇异线性方程组的求解有所关注p n b r o w n 和h f w a l k e r 2 2 】 d c a l v e t t i 2 5 ，以及s l z h a n g 8 1 】等均研究了一类系数矩阵为值域h e r m i t e 的奇 异线性方程组的求解问题，他们的研究结果表明这一类的奇异线性方程组的求解比 一般的奇异线性方程组的求解有更大的优点比如说对于相容的这类奇异线性方程 组，如果用g m r e s 方法来求解，那么求解情况完全等同于对非奇异线性方程组 的求解他们的工作引起了我们的极大兴趣，首先我们对这类矩阵本身进行了一些 探讨，结果发现这一类矩阵有广泛的理论和实际应用价值特别是众多的学者所研 究的一些所谓的结构化矩阵都和e p 矩阵有着很大的关系，再比如一些流体力学问 题经过离散后得到的线性方程组的系数矩阵也是e p 矩阵从广义逆的角度来看， e p 矩阵的广义逆可以说是目前为止最接近正则逆的一种广义逆 本篇论文以e p 矩阵为主线，围绕着奇异线性方程组的求解方法，解的性态， 奇异结构化矩阵置换秩，扰动分析以及e p 线性方程组的一个特殊模型鞍点问题 等内容逐一进行探讨 论文的第二章首先回顾了广义逆的概念。然后引进了e p 矩阵的概念，并扩 充了s l c a m p b e u 2 6 1 对e p 矩阵的等价描述，通过这些等价描述我们可以发现 e p 矩阵的广义逆是保持正则逆最多性质的一类广义逆在本章的第二节我们对奇 异线性方程组的研究可以看到它的解的结构有一些很好的性质，综合了g m r e s 方法求解e p 线性方程组的分析以及e p 矩阵广义逆的相关性质，从某种意义上 来说e p 矩阵是与非奇异矩阵非常接近的一类奇异矩阵本章的最后一节里我们在 b e r m a n 和p l e m m o n s 求解奇异线性方程组的正则分裂迭代方法的基础上提出了 二级迭代方法并给出了收敛性定理 在第三章里我们对结构化矩阵的广义逆有关置换秩的性质进行了研究，我们知 道利用结构化矩阵的特殊结构可以构造一些快速算法，在本章的前两节中主要对具 有s y l v e s t e r 置换结构的矩阵的广义逆的置换结构进行了分析，给出了其广义逆置 换秩的性质和有关结论第一节里我们对一类具有代表性的广义逆 1 ，2 ) 逆的置换 秩研究给出了 1 ，2 ) 逆的s y l v e s t e r 置换秩的结果，第二节对加权的广义逆带w 权 的d r a z i n 逆的置换秩同样给出了相应的s y l v e s t e r 置换秩的结果第三节里我们 对上面得到的结果的应用进行了介绍 在第四章里我们着重对奇异线性方程组进行了扰动分析由于奇异线性方程组 的解涉及到各种广义逆解，我们通过对上面各种广义逆概念的回顾知道，具有指定 值域和零空间的广义逆a 笋j s 是一类非常具有代表性的广义逆，其他几种常见的广 义逆如d r a z i n 逆等都是广义逆a 数的某种特例，因此本文中我们主要考察奇异 线性方程组a z = b 的系数矩阵广义逆a 数的扰动分析在第二节中着重对加权 广义逆的扰动作了分析，给出了扰动结果在本章的第三节里面我们引进了p q 范 数的概念，并推导了在p q 范数意义下奇异线性方程组的条件数的一些结论 第五章主要以n a v i e r s t o k e s 方程为例，首先说明n a v i e r s t o k e s 方程经差 分离散后所得的线性方程组是e p 线性方程组，鞍点问题一般由n a v i e r s t o k e s 方程、o s e e n 方程或s t o k e s 方程引出对这类问题的求解，已经存在很多方法。 其中包括直接法，u z a w a 类型算法及k r y l o v 子空间方法这一章中首先回顾了 已经存在的u z a w a 类型算法，应用z u l e h n e r 在【8 2 】中提出的统一方法分析了稳定 化的鞍点问题的两种算法的收敛性问题，并给出了定理和结论 2 第二章e p 阵与奇异线性方程组解的分析 对于线性方程组 a z = b ， ( 2 0 1 ) 我们都知道当a 是一个可逆阵时有唯一解z = a b ，故解一个非奇异线性方程 组实质在于求解系数矩阵的逆阵当a 是奇异阵或足长方阵时则可能无解也可能 有无穷多个解，这时如果方程组是相容的，我们希望类似于非奇异线性方程组能得 到一个精确解，即广义逆解如果方程组不相容，我们仍然可以求其在某种意义下 的近似解，该解也可以用广义逆表示例如常见的求方程组在最t j 、- - 乘意义下的解 z = a + b ，这里的a + 就是我们熟知的m o o r e p e n r o s e 广义逆总之，奇异线性 方程组的求解往往与一些广义逆有着紧密的联系 通常情况下，奇异方程组的求解往往要比非奇异线性方程组复杂的多非奇异 线性方程组的系数矩阵的逆是唯一的，因而解的形式也足唯一的但是奇异方程组 即使是相容的，其解也不唯一很多情况下我们很难具体求出方程组的广义逆解， 另外，奇异阵有多种广义逆，所以即使存在广义逆解，我们还必须知道是何种形式 的广义逆相比较而言，系数矩阵具有特殊结构的线性方程组的求解问题要简单一 些，例如最近很多学者在研究的h a n k e l 矩阵和t o e p l i z e 阵等结构化矩阵，已经得 到一些较快的算法 在这一章我们要讨论的e p 矩阵，它具有值域( 或零空间) 对称的性质在奇 异矩阵中，e p 矩阵在某种意义下足最接近非奇异矩阵的它的广义逆保持了正则 逆的很多性质 系数矩阵为e p 矩阵的奇异线性方程组的数值求解，特别是求其广义逆解，比 一般的奇异线性方程组求解有更多优点例如，g m r e s 方法对非奇异线性方程 组能不中断的产生唯一解，由文献【2 2 】我们知道对奇异矩阵，如果是e p 矩阵，则 对任意的右端项，g m r e s 方法也能产生一个最小二乘解若初值z o = 0 ，则产生 的解是广义逆解类似的在文献【2 5 】中值域限制广义极小残量法( r r g m r e s ) 在a 是e p 矩阵的条件下也产生最小范数的最小二乘解另外，一些算法也与系 数阵的值域对称这一性质紧紧相连例如在文献【8 l 】中，用o r t h o m i n ( k ) 法求解奇 异线性方程组其收敛性要求系数矩阵必须为e p 矩阵 本章的内容足这样安排的：第二节介绍以后要用到的广义逆及e p 矩阵的相关 概念和性质第三节介绍e p 阵的线性组和奇异线性方程组解的性态 3 2 1e 尸阵和广义逆 在这一节里我们主要介绍本论文中要用到的e p 矩阵及广义逆的概念，由于 广义逆的内容十分丰富，这里我们只介绍本论文所能涉及到的几种常用的广义逆概 念，详细的内容请参见文献( i s ，1 6 ，2 6 ) 定义2 1 1 设a c ”“，称满足下列条件的唯一矩阵x ( 1 ) a x a = a ，( 2 ) x a x = x ， ( 3 ) ( a x ) = a x ，( 4 ) ( x a ) + = x a 为a 的m o o r e p e n r o s e 广义逆，记为a + 上面定义中的四个条件通常称为p e n r o s e 条件当上述条件不全满足时，如只 满足第一个条件，则称为a 一个 1 ) 逆，记为a 1 ，显然a + = a o ，。3 ，4 1 相应的有 a 的“工惫) 逆，只不过当此四个条件不全满足时a 的广义逆是不唯一的 下面在介绍d r a z i n 逆之前先给出指标的定义 定义2 1 2 设a c m 一，称满足 r a n k ( a + 1 ) = r a n k ( a 。) 的最小非负整数k 为a 的指标，记为i n d ( a ) = k 定义2 1 3 设a c ”，i n d ( a ) = k ，若x 满足 ( 1 。) a 。x a = a ，( e ) x a x = x ，( 5 ) a x = x a 则称x 为a 的d r a z i n 逆，记作a d 或a ( 1 ，2 t 5 ) 方阵的a 的d r a z i n 逆足唯一存在的，当上述定义中a 的指标为1 时，此时 a 的d r a z i n 逆也称为群逆，记为舻或a 0 2 ) 下面我们再来介绍具有指定值域和零空间的广义逆 定义2 1 4 设a c “，t 和s 分别是c n 和眇”的子空间。d i m ( t ) = d i m ( s 上) = t r ，则称满足： 4 x a x = x ，r ( x ) = 正n ( x ) = s 的x 为以的具有指定值域和零空间的 2 ) 逆，记为4 呈： 易知存在满足上述定义的x 当且仅当 a i j 固s = u “ 且此时的x 是唯一的 若定义中的t = r ，则此时的x 还是 1 ) 逆，即x = 4 璺；是a 唯一的具有 指定值域t 和零空间s 的 1 ，2 ) 逆【1 6 ，5 ，1 1 】 在前面介绍的广种广义逆，都可以表示成广义逆a 乒的形式，事实上我们有 如下结果( 参见文献 5 】 a + = a 毁蜀，( 棚 a d = a ( j 4 。) a 9 = a 冗o ( , 2 ) ) ，( a ) 由此，有关奇异线性方程组及其广义逆的问题我们着重研究a 簧：，雀；等具有 代表性的广义逆 下面，我们来给出e p 矩阵的概念 定义2 1 5 【2 6 j 设a 伊一，若a + a ：a a + ，则称a 为e p 阵 我们知道正规阵成立a a = a a ，可逆矩阵有a i a = a a ，由上述定义 知道e p 阵就足乘法对a + 保持交换性质的矩阵，文献 2 6 1 中详细地给出了e p 阵的一些等价描述，事实上对e p 阵的刻画还不止这些，作为补充，我们把本论文 涉及的结果补充如下 定理2 1 1 设a c ”，则下列各式等价 ( 1 ) a 是e p 阵 ( 2 ) r ( a ) = r ( a + ) 5 ( 3 ) n ( a ) = n ( a ) ( 4 ) r ( a ) o n ( a ) = 伊 r 5 ) a + = a d ( 6 ) a + = 舻 ，7 ) a a 2 a + ( s ) a = a + a 2 ( 9 ) a z = a z 当且仅当a + z = a + z ( 1 0 ) 存在酉阵u 和可逆的r 阶方阵a 1 ，r = r a n k c a ) ，使得 a = u ( 吉：) c ， 注： ( 9 ) 式实际上是可逆阵a 的如下结论的推广； 这条性质一般矩阵的广义逆是没有的( 1 0 ) 式其实是矩阵a 的秩分勰，换言 之e p 阵是一类其秩分解可以通过酉相似变换实现的矩阵特别当a 1 为对角矩阵 时a 就是正规阵 一 文献【8 1 】也给出了e p 阵的_ 个充分条件 定理2 1 2 设a c - “，若m = ( a + a ) 2 是正半定的或足负半定的，则 4 是e p 阵 从上面的定理可知对e p 阵a ，前面所述的几种广义逆都是相同的即是 a + = a 。= = a 毁盈，。椰= u ( a 0 f 1 ：) u 也就是说，e p 阵的广义逆是一个 l ，2 ，3 ，4 ，5 ) 广义逆为了方便起见，我们统一 记为a ”e p 矩阵的范围是很广泛的，下面我们看几个例子非奇异阵，对称 阵，反对称阵，正规阵，实h a n k l e 阵等，这些常见的矩阵都是e p 矩阵 因为非奇异矩阵是最平凡的e p 矩阵，故我们对e p 矩阵更多的研究的是奇 异阵 6 z 妇 一 一 = 血 a 当仅且当 2 2 奇异线性方程组的解的性态 求解奇异线性方程组与广义逆有着十分紧密的联系，首先我们来看相容方程组 的解与广义逆的关系 定理2 2 1 1 1 6 设a “，x c ”。“，对一切使a x = b 相容的b 沪， x b 均是a x = b 的解当且仅当x 满足a x a = a 从这个定理我们可以看出任何一个相容线性方程组都有广义逆解，而对于下面 的约束线性方程组则有重要的结论如下， 定理2 2 2 1 3 1 】设a ”，t 和s 分别是c ”和c 的子空间，若 d i m ( t ) + d i m ( s ) = m ，a t o s = c ”，b a t ，则下面的线性方程组 在t 中有唯一解z = 雒6 a x = b x a t 上面两个定理描述了奇异线性方程组的广义解的存在性问题，我们知道，k r y l o v 子空间迭代方法对于求解线性方程组是一种很好的方法，而非奇异线性组a x = b 必有k r y l o v 子空间解，且此子空间的维数就是a 关于b 的最小多项式的次数， 而对于奇异线性方程组解的性态就有很大的差异，即使是相容线性方程组也不能保 证有k r y l o v 子空间解，对于奇异组我们发现其解与系数阵a 的指标有很大关系， 首先让我们看下述结果 定理2 2 3 【5 1 】设a c ”“，b c n ，m 为a 的最小多项式的次数， i n d ( a ) = k ，则有 ( 1 ) 若b r ( a ) ，则a x = b 有且只有唯一的k r y l o v 子空间解z = a d b ， x 甄。一) ( a ，b ) ； ( 2 ) 若bgr ( a ) ，则a z = b 不存在k r y l o v 子空间解 上述定理说明a x = b 有k r y l o v 子空间解当且仅当b r ( a ) ，另外我们知道 若a 关于b 的最小多项式的次数为p ，则巧一) ，b ) 是p 维的，从而有下述结论 定理2 2 4设a 伊“。b 伊，a 的最小多项式的次数为m ， i n d ( a ) = k ，a 关于b 的最小多项式的次数为p ，b r ( a ) ，则a = b 有且只有唯 一的k r y l o v 子空间解茹= a d b ( a ，b ) ，s = d i m k 。( a ，b ) = m i n ( p ，m k ) 7 上述定理表明了奇异线性方程组的k r y l o v 子空间解的存在性，但在具体求得 此解有时也不容易，下面我们对系数阵指标为1 的情况看g m r e s 方法的求解情 况 定理2 2 5 1 2 2 1 设a 伊“，b 伊，i n d ( a ) = 1 ，如果a x ：b 相容， 则g m r e s 方法会不中断的产生一个解，并且在下一步因k r y l o v 子空间的退化 而中断 更特殊地，对于系数矩阵为e p 阵则有如下结果 定理2 2 6 2 2 】设a c ”“，b c n ，用g m r e s 方法求解a x = b ，对 任意的b 即初始向量x o 均能无中断的产生该线性方程组的一个最小二乘解当且仅 当4 是e p 阵 若a 是e p 阵且在某步已经产生一个最小二乘解，则g m r e s 方法在下步 中断，且该线性方程组是相容的则中断是由于k r y l o v 子空间的退化产生，否则就 是由于秩亏损产生，并且若线性组相容且z o r ( a ) ，则此解就是广义逆解 由于a 是e p 阵，所以有 r ( a ) o n ( a ) = 伊 令t = r ( a ) ，s = ( a ) ，a t = a r ( a ) = r ( a 2 ) = r ( a ) ，从而由定理知有如下结 论 定理2 2 7 设a 是e p 阵，则相容方程组a 。= b 在r ( a ) 中有唯一解 z = a 印6 上述定理也表明e p 阵a 在其值域r ( a ) 上是非奇异的 结合这一节的内容我们知道，e p 阵的广义逆a e p 保持了一般广义逆所没有 的正则逆的一些性质，再由定理2 2 6 我们知道，用g m r e s 方法求解相容的e p 线性方程组a x = b ，会不中断地在某步产生广义逆解z = a e p b ，然后在下一步会 因为k r y l o v 子空间的退化而中断，也即其中断的特性与非奇异线性方程组是一样 的从这两方面情况说明在某种意义上，e p 阵是一类非常接近非奇异矩阵的奇异 矩阵 8 2 3 正则分裂迭代法求解奇异线性组 考虑线性系统 a z = 6 ， ( 2 3 2 ) 其中a 是m x 扎实的大型稀疏矩阵，z 是未知实n 一向量，b 为给定m 一向量 求解奇异线性系统( 2 3 2 ) 的广义逆解z = 。a 。z ( 1 , s 2 b ，类似b e r m a n 和p l e m m 帆s 在【1 5 】中介绍的求解广义逆解z = a + b 的非奇异线性系统迭代法，我们用下面的 迭代法； z 忙“k m r , o 2 z 。! + 蠼乳b k = o ，1 2 ， 1 ( 2 删 其中a = m n 是a 的正则分裂，即m 和n 是m n 矩阵且满足 r ( m ) = r ( a ) ，n ( m ) = n ( a ) 这里，r ) 是a 的值域， ( a ) 是a 的零空问在非奇异的情形，正则分 裂就是一般定义的分裂 和b e r m a n 和p l e m m o n s 对m o o r e p e n r o s e 广义逆和其他广义逆及广义逆 解的研究一样( 参见文献( 1 5 ，7 】) ，我们有类似的引理： 引理2 3 1 设a = m n 是正则分裂，那么： ( i ) a = m ( i 一蠼孑) ， ( i i ) ，一 4 磐是非奇异的， ( i i i ) 雒；m = ( ，一蠼；) 吧m t , 1 s , 2 ) ， ( i v ) 雒多b 是迭代z = ( 蠼乡n ) x + ( 蠼多6 ) 的唯一解 类似b e r m a n 和p l e m m o n s 1 5 中结果，我们给出了下面的收敛结果： 引理2 3 2 设a 是m 乱实矩阵，a = m n 是正则分裂，那么对任意的 初始向量扩迭代过程收敛到a 2 ；b 当且仅当p ( h a t ( 1 , 2 ) 1 我们称矩阵a = 陋u 】非负a 0 ，如果n 巧0 ，其中i ：1 ，2 ，m ， j 2 1 ，2 ，n 我们称a s b 如果b a 0 ，向量情形可类似定义 9 定义2 3 1 设a 是m n 实矩阵，a = m n 是一个正则分裂，m r , o , 2 ) 是矩阵m 的具有指定值域t 和零空间s 的( 1 ，2 ) 逆，我们称a = m n 是正规 的，如果满足条件m t ( , 2 0 且n 0 此外，我们称a = m n 是第一型弱非 负的，如果满足够学0 且m t ( i , 2 n 0 定理2 3 1 设a 是m n 实满秩矩阵，a = m 一是第一型的弱非负正则 分裂，那么下列条件等价： ( i ) 雒；0 ( 托) a 量；m l t l s , 2 ( 嘲a 墨；m 之0 ( t t ，) p ( 蠼爹) = p ( a ( 1 , 2 m 一1 ) 加( a 璺；m ) ( t ，) p ( 蠼；) = j 口( 蠼；) 1 ( 们) ( ，一m t , ( 1 2 ) ) 一1 0 ( v i i ) a 鬈n 0 ( 口蚴霹；n m r ( 1 , 2 n ( i 咖( 嚣) = p ( 雀；n ) ( 1 + p ( 雀字) ) 1 如果上面的定理去掉假设”a 满秩”，我们只能得到等价结果( i ) ，( i i ) 和 ( v ) 一( i ) ( ) 下面我们对二级迭代法进行考察给出收敛结果并加以证明 设a = m n 是a 的正则分裂，m f g 是m 的正则分裂如果我们 考虑分裂m = f g 的g 次内迭代，可以得到下面的二阶迭代法 q - 1 正州= ( 磺尹g ) 4 z 砷+ ( 磷尹g 尸f t c l ，, 2 ( n x 叼+ 6 ) ( 2 3 4 ) j = 0 现在，由引理2 3 1 和引理2 3 2 和定理2 3 1 我们可以得到下面的收敛结果 定理2 3 2 设a = m n 为一正规的正则分裂，m = f g 是第一型的 弱非负正则分裂，那么定常二阶迭代方法对任意的初始向量z ( o ) 收敛到线性系统的 解 证明 因为m a , 。( 1 , 2 n = n ，碍苫m = f t ( 1 , 2 f 一巧苫g ，磴孑f = m t ( 1 ，, 2 m 由定理2 3 1 ，可得 1 0 ( 础g ) p + ( 磷g ) j 磷 j = o 口一1 ( f l 2 g ) p + ( 只秽g ) ，f t o , m m 。o ，尹n 2 = 0 p - 1 0 ，, 2 g ) p + 、k - f t 1 , s 埘g ) ( 碍苫f f t i , 2 g ) 峭于 3 = 0 p ( 1 , 2 g ) 9 + ( 磴多f 一( 噬孑g ) ，) 蠼；n = ( 艘尹g ) p + 艘孑f 蠼尹n 一( 艘乎g ) ，蠼尹n = ( 磺爹g ) + 蠼雪m 蠼孑n 一( 蠼孑g ，i ph f ( 1 , 2 n = 0 , 2 g ) nm t ( 1 , 2 n 一( 噬孑g ) p 蠼乎 = ( j 1 ；苫g ) p + ( ，一( j 翟爹g ) 9 ) a 蠼雪n = ，一j + ( 只譬g ) p + ( ，一f 一( 1 , 2 g ) p ，。z ( 1 s , 2 n = ，一( ，( f ；苫g ) 一) ( ，一m t o , 2 ) = j 一( 碍苫g ) ( ，一f 。( i , 2 g ) ( ，_ m t l ，, 2 ) ，= 0 考虑a = m n 和m = f _ g 是收敛的，如果暑，20 ，那么 因而， z = ( j - 一 蠼雪) 一1 ( f f 彩g ) 一1 y 0 这表明p ( 耳) 1 口 p - 1 0 写z = z 一厶、f ( l s 2 g ) ! ， z i = 0 接下来类似的，对非奇异矩阵的弱非负分裂，我们可以通过a 的多重分裂平行 迭代方法得到方程的解 定义2 3 2 设a 是m 礼的实矩阵， ( 蚴，m ，蜀) ) p _ 1 是4 的个多重正则 分裂如果a = 尬一m 是一个正则分裂，z = i ，p ，蜀是m x m 阶的非负对角 矩阵，f - 1 ，p ，忽1 蜀= k 这里，m 是mx f f a 阶单位矩阵 作为定义2 3 1 的推广，我们定义正则多重分裂是正规的或是第一型弱非负的， 如果其中每一个正则分裂都是正规的或屉第一型弱非负的 若 ( 蚴，肌，局) 翟1 是a 的一个正则多重分裂，我们可以考虑迭代 z ( + 1 ) = h x 。+ g b ，k = 0 ，1 ，2 ( 2 3 5 ) 对于上面的迭代，在给出定理2 3 3 的收敛结果之前，我们还需要下面的引理 结果： 引理2 3 3 设a 为mxn 阶实矩阵， ( 脱，肌，局) 冬l 是a 的第一型的正则 多重分裂，那么 ( o h 0 ，h j 之0 ，j = 0 ，1 ， p ( i i ) 局( 磷) f a = ( ，一日) a 蹭a 1 = 1 ， ( i i i ) ( s + h + h 2 + + 日”) f f 一日) ；，一日”件1 证明( i ) 是矩阵h 定义的直接结果，由第一型弱非负正则的定义即得( i i i ) 可由( i ) 得到 下面我们来证明( i i ) 成立 因为 尬( 啦；) 幽= f = f ( 嗡；) z 尬， 以及 可知 因而 ( 雌1 , 2 s h 蚴= ，a z ( 1 , s 2 ) a ，f _ 1 ，2 ，p a = m l 一l = m , c x 一( 磷爹) f ) ，f = 1 ，2 ，p 1 2 ”噼 日 ， i i gm 0 s蠼 目 ，m = 日 中其 p 蜀( 蠼乳m l ( i - ( 蠼乳m ) i = 1 = 岛( ( 删苫) z 尬一( 磷尹) z 她( 皑尹) z 1 ) 1 = 1 p = ( ( 卜a a r ( l ，2 ) z 1 ) ( 磷) 尬) f = l p = ( 卜日( 蠼尹) t n t ) a ( t i , ；a 1 = 1 一( ，一h ，、a ( l 2 a 这就表明，( i i ) 成立口 定理2 3 3 设aim x n 实矩阵， ( 尬，m ，局) ) p = 。是a 的第一型的正则多重分 裂，那么正则多重分裂迭代法对任意的初始向量$ ( o ) 都收敛到方程组( 2 3 2 ) 的解 且 以及 证明应用引理2 3 3 ，考虑到 ( 蠼乳尬( 磷热= ( 蠼乳，j _ 1 2 ，p ， 尬( 磷乳= a a ( l 2 ，f = 1 2 ，p 雒多a 雀；= a 鬈 1 3 = a 二s蝼 磁 ，m m 0 s蝼 嵫 0 s峨 一 0 s峨“ 岛 ，m = 可得 0 ( j + 日+ h 2 + + t m ) 蜀( m ：；j ：尹) l 1 = 1 = ( j + 日+ 日2 + 十日”) e l ( m 船) l 舰( 蠼尹h l = 1 = ( ，+ 日+ 日2 + + 日”) 。7 k 。v 。z t 1 , s 埘k aa o ，, 。2 = ( ，+ 日+ 日2 + + 日m ) ( ，一日) a 冀；a a t ( 1 , s 2 ：( ，+ h + h 2 + + h ”) ( ，一日) 鸳； = ( j 一日”件1 ) a 乒；a ； 因而，h m 的元素必保持有界，从而日是收敛的故正则多重分裂迭代法对任意 的初始向量霉( o ) 都收敛到线性系统( 2 3 2 ) 的解口 第三章结构化矩阵广义逆的置换秩 这一章我们主要研究结构化矩阵的广义逆的置换秩性质，首先介绍置换结构相 关的概念和性质【5 3 1 ，【5 4 】 矩阵a 称为置换矩阵( 【4 8 】，【4 9 】) 当且仅当矩阵a u v a 或a v a u 的秩与 矩阵a 的阶数相比要小矩阵a u v a 的秩称为a 的s y l v e s t e r v v 置换秩，矩 阵a v a u 的秩称为a 的s t e i n v v 置换秩，这里的a 分别是s y l v e s t e r 方程和 s t e i n 方程的解 我们知道如果矩阵a 具有置换结构，那么可以构造相应的一些快速算法我 们更关注置换秩尽可能小的广义逆的置换秩的性质，在第一节中我们对矩阵4 的 s y l v e s t e r 置换秩即置换a 璺；u y a 璺；的秩给出了估计结果，在第二节中我们研 究加权的广义逆的s y l v e s t e r 置换秩的性质，在第三节中我们给出了前两节的结果 的一些应用下面先简单介绍本章要用到的一些概念和性质： 设g c m “，g 满足兄( g ) = 正( g ) 一s ，那么 a a 争0 ) = a g ( a g ) 9 ，a 黯a = ( g a ) 口g a 这里( a a ) f 和( g a ) 9 分别是矩阵a g 和g a 的群逆 由矩阵秩的分解理论，对任意复m n 矩阵a ，且r a n k ( a ) = r ，存在非奇 异矩阵r 和成立 a = r 一1 ( 名1 ：) ，g = - 1 ( 1 ：) r c s 。- ， 这里r 是m m 非奇异阵，是几n 非奇异阵，a 1 1 ，g l l 都非奇异因而 a o , 2 ) 可以表示为 a 璺争= n - 1f ，a o 、lr “。 0 ( 3 0 2 ) 设 q = 雒；a ，p = 厶一q ，q 。= a 篮；， 只= m q 。( 3 0 3 ) 显然q 和p 为斜投影，易得下面各式 r ( q ) = 兄( 碑0 ) = 只( g ) ，r ( q 。) = r ( a ) ， r ( p ) = ( a ) ，只( 只) = ( a 璺；) = ( g ) 3 1 1 ，2 ) 逆的s y l v e s t e r 置换秩 ( 3 0 4 ) ( 3 0 5 ) 本文中u c ”和v “”，算子d ( 以v ) = a u v a 为a 的u v 置 换我们知道对非奇异的矩阵a 如果具有y 置换结构的话，其逆阵4 - 1 就具有 y u 置换结构，其关系如下 r a n k ( a 一1 v u a 一1 、= r a n k ( a u v a ) 要估计矩阵a 的 l ，2 逆的霉换秩，首先我们先来看看一a _ o , s 2 的置换结构 命题3 1 1 设a c m 一，u c “x n ，v c ”。m ，雒；是a 的 l ，2 逆那么 。a z o s , 2 矿一a 墨字= a o ，, 。2 v p , 一p u 篮0 一a 。o ，, 。2 ( a u y a ) a 字 ( 3 1 6 ) 证明这个关系式可由下面的式子直接得到 a 璺；( a u v a ) a 器= ( ，一p ) u a 鬈一n a l ( 1 s , 2 v ( x 一只) ( 3 1 7 ) 口 由( 3 0 4 ) 可得下面的推论 推论3 1 1a ( 1 , 2 的v u 置换秩满足下面估计： r o 礼( a 乒；y 一u a l o , s 2 ) r a n k ( a u v a ) + r a n k ( q 。y 只) + r a n k ( p u q ) ( 3 1 8 ) 证明我们只要证明 出m ( 尸u a 墨；) = r 口n k ( p u q ) 和r 口竹七( a 正( 1 s 2 v p ) = r 。n k ( q v p ) 即可 1 6 易证第一个式子，即 r a n k ( p u a 挈, ；) = 疵m ( r ( 尸u a 躲) = 也m 【p u 兄( 雒；】 类似可证第二个等式 r a n k ( q + v 只) = = d i m r ( p u q ) 】- r a n k ( p u q ) r a n k ( ( q 。y 只) + ) d z m 【( p i ) v r ( q + ) + ) 1 = 出仇【r ( ( 只) v z 1 0 , 2 ) ) 】 = r o n 七( ( 只) v ( 霹；) ) = r o n 七( a l ( 1 s 2 y 只) 下面我们将对推论3 1 1 右端的第二，第三两项给出估计 推论3 1 2由上面的定义，可得估计 r a n k ( q 。y 只) + r a n k ( p u q ) r a n k ( u g g v ) 证明令f = u g g v 及矩阵分块 u 以= 巩：笼 , r v r - 1 = u 2 芝： l ，lik 1 由( 3 0 1 ) ，利用f 的分解式可得 n f r 一1 ：n u n 一1 n g r 一一n g r 一1 r v r 一1 = v 踢i i 。圳1o _ c 0 1 雌吲 由【5 9 1 可知 = 皂z 1 1 ( 3 1 9 ) ( 3 1 1 0 ) ( 3 1 1 1 ) ( 3 1 1 2 ) ( 3 1 1 3 ) ( 3 1 1 4 ) ( 3 1 1 5 ) ( 3 1 1 6 ) ( 3 1 1 7 ) ( 3 1 1 8 ) 1jlj 2nn 0 g 一 r 帆后i 巩1 g 1 17 1 1 1 一g 1 1 k 2i r n k ( - g 1 1 m 2 ) + r n 后( 如1 g 1 1 ) l u 2 1 g 1 l 0 l = r a n k ( 2 ) + r a n k ( 沈1 ) 这里g ，- 非奇证明完毕 = r 口n 七 ：2 + r 甜n m r a n k ( q 。v 只) + r a n k ( p u q ) 由上面的两个命题，马上我们可以得到下面的第一个主要的结论 定理3 1 1 设a c m 一，a o , 2 为其 1 ，2 ) 逆，那么 r a n k ( a 挈, ；v 一。u 。a 0 2 s ) r a n k ( a u v a ) + r a n k ( u g g v ) 命题3 1 2 若矩阵a 成立a u = u g ，v a = g v ，则可得估计式： r 帆七( a z ( 1 s 2 y u a o , 2 ) 2 r a n k ( a u v a ) 纠 口 ( 3 1 1 9 ) 为了将定理3 1 1 进行推广，我们先要引入广义置换的概