（计算数学专业论文）相容和不相容奇异线性方程组的算法与扰动分析.pdf

相容和不相容奇异线性方程组的算法与扰动分析 摘要 本文主要怒一类奇异线性方程组的理论分析及其数值算法。与非奇异线性方程 缎不同酌是并菲所有的奇异线性方程组都蔗相容的，从而针对相容的和不相容的这 两种情况我们分别进行探讨在众多的奇界线性方程组遗中，一类其系数障是值域 h e r m i t e 的奇完筑往方程组日 起了我们极大的兴趱，因为值域h e r m i t e 的矩阵( 也称 为e p 阵) 以及岛其相应的线性方程组很广泛地存在着。对e p 阵的广义逆的研究表 萌，其广义逆蕊保持正刚逆簸多惶旗的一樊广义逆，另外e p 线性方程组的解的结 构也有些一般奇异线性方穰组所投有的良好性质。在奇异线性方程组解的拢动分 祈方面，我们曾先反觳其有代表惶的广义逆肖着手，建立了有关求解奇异线性 力“程组的条件数的表逃式，从而推广r 非奇异线性方程燃的条件数的些结果，然 后我们对e p 线性方稷组的广义逆解的相对扰动误差界给出一个估计式。在算法方 磷，我们以p o i s s o n 方程和n a v i e r s t o k e s 方程为例，首先我们说明这两个方程经蓑 分格式离散后所得到的线性方程组均是e p 线性方程组，当方程组不相容时我们通 过求其最小 范数解来获得一个比较好的停机标准。对n a v h u 。s t o k e s 方程的求 解，我们萋点愁比较不同预条件的g m r e s 方法，对基于对称- 反对称分裂( h s s ) 的预条件“1 5 1 ) ，我们提出几种变形，本论文分别用a 靠 一 来表示，并用它们 和约束预条件激比较，结果表明，猩计算时间上 乱i 蔑最少的，最厝我们对e p 线 性方程缎妁广义逆解的扰动分析的某些结果也通过数值实验给予验证 a l g o r i t h m sa n dp e r t u r b a t i o na n a l y s i sf o rs o i i n g c o n s i s t a n ta n di n c o n s i s t a n ts i n g u l a rl i n e a r e q u a t i o n s a b s t r a g 譬 t h e p 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 sa n dn u m e r i c a i a l g o r i t h m sf o rac l a s so fs i n g u l a rl i n e a re q u a t i o n s ， a sw ek n o wn o tl i k ew i t h n o n s i n g u t a r l i n e a re q u a t i o n s ，s o m e s i n g u l a rl i n e a re q u a t i o n s a r ei n c o n s i s t a n t s ow ew i l ld e a lw i t ht h et w oc i r c u m s t a n c e s a m o n g s om a n y s i n g u l a r l i n e a i e q u a t i o n sw ea r ev e r yi 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 e r a n g eh e r m i t i a n e pm a t r i c e s ) f i r s tw ew i l ls e et h e g e n e r a l i z e di n v e r s e o fe pm a t r i xh a ss om a n y q u a l i t i e sa ss a m e a s 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 s t h a tt h ec o m m o n s 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 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 es o m er e s u l t so nt h es 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 rc o n c e r n e dw i t ht h eg e n e r a l i z e di n v e r s e a i ，z ) s ，w h i c he x t e n dt h e r e s u l t so n t 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 nb o u n d f o rt h es o l u t i o n so fe pl i n e a re q u a t i o n s 。 a tl a s tw ed os o m ei m m e r i c a la l g o r i t h m s ，w ew i l ls e et h el i n e a re q u a t i o n sf r o mt h e d i s c r e t e n e s so fp o i s s o ne q u a t i o na n dn a v i e r s t o k e se q u a t i o na x ea l le pl i n e a re q u a t i o n s ， w h e nt h ee q u a t i o n sa r ei n c o n s i s t a n tw ew i l lm a k eag o o dt o l e r a n c et h r o u g ht h em i n i - m a i ”j i mn o r ms o l u t i o n p a r t i c u l a r l yf o rn a v i e b s t o k e se q u a t i o n ，w ew i l lc o m p a r et h e g m 拽e sm e t h o d sw i t hd i f i e r e n tp r e c o n d i t i o n e r s w en l a k es o m ev a r i a n c e sf r o mt h eh s s p r e c o n d i t i o n e r ( 弘鼋) ，t h a ta r e 地1 墙蠡4i n0 1 1 1 p a p e r c o m p a r i n gw i t hb l o c kt r i a n g u l a r p r e e o n d i t i o n e rw e w i l lf i n dt h a tt h ec p ut i m ef o r 魄ii st h es m a l l e s t 溉a l s om a k e , s o m e e x p e r i m e n t sf o rt h ep e r t u r b a t i o nt h e o r yo fe p l i n e a re q u a t i o n s ， l i 第一章绪论 近年来，人们对奇异线性方程组的求解有所关注。我们知道k r y l o v 子空间方法 是求解线性方程组的一类常用的迭代法，对于非奇异线性方程组a z = 6 必有k r y l o v 子空间解，且此子空间的维数不超过系数阵 的最小多项式的次数。从而用g m r e s 方法( ( 3 9 ) 求解非奇异线性方程组都能收敛到真解。而对奇异线性方程组的求解使 用k r y l o v 子空间方法则情况就比求解非奇异线性方程组要复杂的多，比如当奇异 线性方程组不相容时我们要求其近似解，而此近似解究竟是按何种标准去衡量的? 这就是一个值得我们思考的问题，如通常我们所说的最小二乘解其实也就是谱范数 下的最优逼近解；即便是相容的奇异线性方程组，也未必有k r y l o v 子空间解，同时 即使有k r y l o v 子空间解也不是所有的方法都能求出该解针对奇异线性方程组的 这些情况下面我们举一例子( 3 2 】) 。 设z = c 是相容的线性方程组，其中v 是幂零阵且c 0 ，这也即意味着 存在某个i 满足：n 。= o 但n 仁1 0 假如该方程组有k r y l o v 子空间解。，即 z = e i - - ：1 0 靠c ，则c = n x = e 高矗k + l c ，从而 但另一方面由于是幂零阵，从而括号中的矩阵其特征值均为1 ，也即是非奇异 的，故c = 0 反之也即是说若c 0 则上述线性方程组即使是相容的也不会有 k r y l o v 子空间解事实上，奇异线性方程组是否有k r y l o v 子空间解与系数阵零特征 值的指标有关系，这在后面的章节中还将更详细地介绍 我们知道k r y l o v 子空间方法是一类含义很广泛的方法，它的本质是要在某个 k r y l o v 子空间中寻求所求解的线性方程组的( 近似) 解，而随着寻求这个解所按的标 准的不同，就得到各种不同的方法，比如g c r 、o r t h o m i n ( k ) 、g m r e s 、c g 、 b i c g 、c c s 、q m r 、f o m 、c o n j u g a t er e s i d u a l 、l a n c z o sb i o r t h o g o n a l i z a t i o n 以 及a c o n j u g a t ed i r e c t i o n 等等较非奇异线性方程组而言，有关k r y l o v 子空间方法 求解奇异线性方程组方面的文献不是很多，理论也不是很完善，下面我们简单回顾 一下这方面已有的一些工作i c f i p s e n 和c d m e y e r 在 3 2 】中对k r y l o v 子 空间方法有比较深入的研究，阐述了k r y l o v 子空间方法的一些优点，特别是比较 了用k r y l o v 子空间方法求解非奇异线性方程组和奇异线性方程组的异同，并针对 奇异线性方程组求解的特有困难，探讨了改用求d r a z i n 逆来代替m o o r e - p e n r o s e 逆 分析解的性态对于求解奇异线性方程组的d r a z i n 逆解，a s i d i 也做了很多工作 ( 4 0 4 1 4 2 1 ) 此外，在奇异线性方程组求勰方面，p n b r o w n 和h p w a l k e r t 9 】、 d c a l v e t t i 等f 2 0 】、以及s l z h a n g 等【5 4 均研究了一类系数阵为值域h e r m i t e ( e p 阵) 的奇异线性方程组的求解问题，他们的研究结果表明这一类奇异线性方程组的 0 = c + 靠 ：3 ：脚 一， 求解比一般的奇异线性方程组的求解有更大的优点。比如说对于相容的这类奇弊线 性方程组鼹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 l l 2 1 】对e p 阵的一些等价描述，通过这些等价描述我们还发现e p 阵的 广义逆是缳持正裂遂最多瞧质的一类广义递在奉章第三节我f f j 对奇异线性方程短 解的性态进行分析，尤其怒对系数阵为e p 阵的奇异线性方程组我们发现它的解的 结穆有一些炎好淫获练会g m r e s 方法求解e p 线性方程组酶中断分帮予戳及e p 阵的广义逆的一些结论，从某种意义上说e p 阵是与非奇异阵非常接近的类奇异 方阵 在第三章我们着重对奇异线性方程组进行扰动分析，由于奇异线性方程组的解 渗及裂各静广义遂解，焉澄过第二章对广义邀的奔绍我稍箱遭吴有指定值域和零 空间的广义逆月5 1 1 1 0 是一类非常具有代表性的广义逆，其它几种常见的广义逆诸如 蠢 、a d 等都是广义逆童戮的菜静特铡，霞盘艺我稻着熏考察奇异线性方程缀a 。= b 的广义逆解a ( 2 j b 的扰动分析谯本章第一节内容我们主要是推广了d j 。h i g h a m 渗霹有关菲奇异线馁方程组豹条 夸数的一些结论第二节我们引进了p q 范数的概 念，并推导在p q 范数意义下奇异线性方程组的条件数的一嫂结论，同时讨论了条 侔数的穰枣性质。在本章第三节我们黄簋对e p 线往方程经进行扰动分析。前两节 内容对e p 线性方程俎自然成立，特别是前两节的一些假设条件本笼必然联系，健 在e p 线往方程组这里它确是等价的，蔺时因为e p 阵的良好性质，有些假设条件 较一般的奇异线性方程组要放宽一些，最后我们对e p 线性方程组a x = b 的广义 递鹬嚣。a e p b 的褶对抗动误差界缭出一个估计掰： 第四章主要是以p o i s s o n 方程觏n a v i e r - s t o k e s 方程为倒，对展k r y l o v 子空间方 法静求解迸符算法分析辩上述两种方撩分剐用不同形式的有限差分离散盾，得到 的两个线性方程组都是e p 线性方程组，对这两个e p 线性方程组我们分别得到其 激小 | | m 范数解的表达式，从而对不褶容的方程组求其近似解时，我们套得到一 个比较好的停机标准在本寒第三节我们着重进行算法分板，重点是对求煞n a v i e r - s t o k e s 方程的预条伴g m r e s 方法进行分析f l l 】、【1 5 j 研究了基予对称，反对称 分裂( h s s ) 的交替迭代法，进一步 1 5 l 提出了基子这种分裂黪预条 串，我嬲把它麓 称为h s s 预条件由于h s s 预条件对求解n a v i e r - s t o k e s 方穗不是很实用，因此针 2 对h s s 预条件我们提出几种变形，本论文分别用 靠1 一眠4 来寝示，然后研制这 些强条锌懿g m r e s 算法以便逡行数债实验。 在第五章我们将分别对p o i s s o n 方程和n a v i e r s t o k e s 方程进行数值实验。首先 我嬲寒求麓p o i s s o n 方程，这郄分淘容的一个主要强豹是搽讨在求解不穰容方程组 的近似解的过程中，如何确定停机准则，也即验证我们在第四章中提出的一个停机 建则是否霹霉亍。在第二节我】来术餐n a v i e r s t o k e s 方程，烹要是托较不麓预条 年的 g m r e s 算法，鉴于预条件虼1 一心4 带有参数，因此连同u z a w a 算法我们首先 来比较它秘各皇对参数静敏感度，为了跑较不餍疆条件豹傀劣，我靛对h c e l m a n 和d a v i ds i l v e s t e r ( 2 7 ) 所提出的约束j 贯条件一起进行数值实验，对于第三章中的有 关e p 线方程组的挽动分析的结果我们也给予验证投据这些蜜验数糖最后我们 进行小结，并对后续工作提出一些新的问题 3 第二章e p 矩阵与奇异线性方程组解的性态分析 2 1 引言 对于线性方程组 a x = b ( 2 1 ) 我们知道当a 是一个可逆方阵时有唯一解z = a b 换言之要求解一个非奇异线 性方程组实质上是要求其系数矩阵的逆阵而当以是奇异方阵或者a 是长方阵时， 上述方程组可能无解也可能有无穷多个解 是奇异方阵时，方程组( 2 i ) 如果相容，类似于非奇异线性方程组我们希望 能得到其一个精确解z ，该z 能用a 的某个广义逆表示，比如z = x b ，其中x 是 a 某个广义逆。如果方程组( 2 1 ) 不相容，我们仍然可以求其在某种意义下的近似 解，且该解也用且的广义逆表示比如众知的方程组( 2 1 ) 在最小二乘意义下有解 。= a i b ，a t 就是熟知的m o o r e - p e n r o s e 广义逆总之奇异线性方程组的求解往往 与一些广义逆有紧密的联系 通常地，奇异线性方程组的求解情况要比非奇异线性方程组复杂得多。非奇异 线性方程组其系数矩阵的逆阵唯一，解也存在且唯一。而奇异线性方程组即使是相 容的，其解也不唯一。很多时侯我们难以求出上述的广义逆解。另外，奇异阵有多 种广义逆，所以即使存在广义逆解，我们还必须知道是何种广义逆 对于一些有较特殊结构的系数矩阵a ，( 2 1 ) 的求解会有一些改进比如众多 学者在研究的h a n k e l 阵、t o e p l i t z 阵等一些所谓的“结构化矩阵”，相应的方程组 求解会有一些较快的算法本章要讨论的e p 矩阵，它具有值域( 或零空间) 对称 的性质我们会发现在奇异矩阵当中，在某种意义下e p 阵是最接近非奇异阵的 它的广义逆保持了正则逆的很多性质文献( 【1 9 ， 2 0 】，1 5 4 】) 都研究了这类方程组的求 解问题 我们知道若a 是非奇异矩阵。则对方程组( 2 1 ) 的任意右端项b ，g m r e s 方 法( i 3 9 】) 都能不中断地产生解z = a 。6 。由文献f 1 9 】我们知道对奇异线性方程组 ( 2 ，1 ) ，如果a 是e p 矩阵，则对任意的右端项b ，g m r e s 方法也能产生一个最小二 乘解且当方程组相容时，此g m r e s 最小二乘问题的条件数由，c 2 ( a i r ( a ) ) 界定，其 中一2 ( a i r ( a ) ) 是a 的最大奇异值和最小正奇异值的比值进一步若g m r e s 方法的 初值。o r ( a ) ，则产生的解是广义逆解类似地文【2 0 】的值域限制广义极小残量法 ( r r g m r e s ) 在a 是e p 矩阵的条件下也产生最小范数的最小二乘解另外还有一 4 浆算法也与系数阵的值域对称这性质紧密相逢。比如文f 5 4 l 表明用o z f 1 - o m i n ( k ) 求瓣毒簿线性方程鬣( 无论樱容与否) ，冀牧敛性要求系数阵必须为e p 怒阵。 以上表明系数阵为e p 阵的奇异线性方程组其数值求解( 特别是求广义逆解) 较一觳的奇羿线性方程组有趸多 芄点现在要闻系数酶为e p 阵的线性组赣解与一 般的奇异组的解究竟肖何差异，如何表永? 换言之e p 阵的广义逆赵什么? 它与一 般短阵的广义逆有何区别? 这些国题将在本章第二节、第三节给予回答。下面的内 容是这栉安排的。第二节回顾矩障的广义遵，介绍本论文所涉及的各种广义逆，g l 进e p 缀阵的概念并描述其广义逆；第三节介绍奇异线性方程组解的性态；第四节 邋过几个注记寒进一步如深糖剿谈本章主要悫容。 2 2e p 斑阵及其广义逆 本节我们来介绍e p 矩阵及萁广义逆的概念；为了便于比较e p 矩阵的广义逆和 其它广义逆的嫠异，我们还是首先缭出通常奇异矩阵的几种广义逆的概念，当然鉴 于广义逆的内祷十分丰富，这里只简单介绍本论文所涉及到的几种常见的广义逆， 更详缨懿内容碍参见文瓤( 酬，【1 4 】，f 2 1 1 ) 定义2 , 1 设a c ”，称满足下列条l 牛的唯一黪矩终x ( 1 ) a x a = a ，( 2 ) x a x = x ， ( 3 ) ( a x ) + = a x ，( 4 ) ( x a ) zx a 为直黪m o o r e 。p e n r o s e 广义邀，记为 t 上逡定义审戆露个短阵方程遴誊弥为p e n r o s e 条件。嚣上述四个条 孛不全满慰 时，比如x 只满足( 1 ) ，则称x 为a 的一个( 1 逆，记为a ( ”， za ( 1 ，2 t 3 舢，榴 应建有硅豹 矗女 邀，只不蓬墨毙四条 孛苓全满足时盖豹义逆怒不唯一豹 在介绍d r a z i n 逆之前，先给出方阵的指标的定义。 定义2 2 设a e “，称满足 r a n k ( a + 1 ) = r a n k ( a ) 的最小非负整数为a 的指标，记为t n d ( a ) = 5 定义2 8 设a c “，i n d ( a ) = 女，若x 满足 ( 1 2 ) a 。x a = a 2 ，( 2 ) x a x = x ，( 5 ) a x = x a 则称x 为a 的d r a z i n 逆，记作a d 或4 ( 1 ，2 ，5 ) 。 方阵a 的d r a z i n 逆是存在且唯一的当上述定义中a 的指标为1 时，此时a 的d r a z i n 逆也称为群逆，即 定义2 3 ，设a 伊“，若x 满足 ( 1 ) a x a = a ，( 2 ) x a x = x ，( 5 ) a x = x a 则称x 为a 的群逆，记作舻或a ( 1 ，2 ，孙 下面我们再来介绍b o t t ，d u f f i n 和广义b o t t d u f f i n 逆 定义2 4 设a 伊“，l c n ，p l 和p l i 分别是工和上1 上的正交投影， 若ap f + p l - 非奇异，则称p l ( a p l + p l - ) “为a 关于l 的b o t t d u f f i n 逆，记作 a ( ( l - ) 1 ) 。 定义2 5 设a c “，l c “，p l 和尸l - 分别是l 和l 1 上的正交投影， 则称p l ( a p l + p l - ) + 为a 关于l 的广义b o t t - d u m n 逆，记作以出 下面我们来介绍具有指定值域和零空间的广义逆 定义2 6 设a g ”“，r a n k ( a ) = r ，r e “，s c “，d i m t = d i m s l = t5 r ， 则称满足 x a x = x ，n ( x ) = l n ( x ) = s 的x 为a 的具有指定值域和零空间的 2 ) 逆，记为a 熟。 易知存在满足上述定义的x 当且仅当 a t o s = ( 2 2 ) 且此时的x 是唯一的 若定义2 6 中的t = r ，则此时的x 还是 1 ) 逆，即x = 。a t ( i s , 2 ) 是a 的唯一的 具有值域t 和零空间s 的 1 ，2 ) 逆 在前面介绍的诸广义逆中，均可以统一地表示成广义逆a 呈| 的形式，事实上 我们有如下结果( 参见 9 ) ： 6 月t = “a ( r 1 ( 2 叭) ( ) 舻= 以。】 舻= a ( ) a 斟= a 毁。 锚= 删删 由此，有关奇异线性方程组及广义逆的问题我们着重研究a 关这一具有代表性的 下面我们来引进e p 矩阵的概念 定义2 7 2 l 】设a c “”，若a t a = a a l ，则称4 为e p 阵 我们知道正规阵有a a = 且a + ，可逆阵有a - i a = a a ，由上述定义知e p 阵 是乘法对a 保持交换性质的矩阵，文( 2 1 】，p 7 4 一p 7 5 ) 的定理4 3 1 和定理4 3 2 还给出e p 阵的一些等价描述，事实上对e p 阵的刻画还不只这些，作为该定理的 补充并结合已有的结论，我们给出如下结果 定理2 1 设a c “，则如下各项等价： ( 1 ) a 是e p 阵 ( 2 ) r ( a ) = r ( a + ) ( 3 ) n ( a ) = n ( a + ) ( 4 ) r ( ) 奋n ( a ) = c n ( 5 ) a t = a d ( 6 ) a t = a 9 ( 7 ) a = a 2 a t ( 8 ) a = a * a 2 ( 9 ) a x = a z 当且仅当a f z = a t x ( 1 0 ) 存在酉阵u 和可逆的r r 阶方阵a l ，r = r a n k ( a ) ，使得 a = u ( ：) u + 7 诚明：由于a 以t 稠a t a 分别是到r a ) 鞠n ( a + 刊二她正交投澎，坟丽璐翻 ( 1 ) 、( 2 ) 、( 3 ) 、( 4 ) 式等价，下面再证( 1 ) 、( 5 ) 、( 6 ) 式等价。 ( 5 ) = 寻( 1 ) ：由定义2 3 翡最爱一式戋拜( 1 ) 式成立。 ( 1 ) = 寺( 6 ) ：由于a f 满足定义2 3 的所有条件，敞a 十一a 9 ( 5 ) ：显然下证( 1 ) 和( 7 ) 等价 ( 1 ) = 辛( 7 ) ：a = a a 以= a a a t = a 2 a t ( 7 ) 日( t ) ： a a 2 j 4 f 茸a + = a a j = ( a a l ) + a = a a t a + 焉壶 r ( a a f | a + ) r ( 以) ， i l r a n k ( a a * a 。) = r a n k ( a ) 知 r ( a ) = r ( a 4 从而( 1 ) 成立，另外( 1 ) 和( 8 ) 的等价关系同理可证余下( 9 ) 、( 1 0 ) 和( 1 ) 的等价 关系懿涯明参觅【2 1 ( p 7 4 一p 7 5 ) 。 o 勇姊，文【5 4 j 毪络出了e p 箨豹一个充分条箨。 定理2 2 。a c “，若m = ( a + a ) 2 是正半定我爱半定的，剿a 是e p 阵。 定理2 1 中的( 9 ) 式实际上是可逆阵a 的如下结论的推广； a z = a z 当且仅当a 一1 z = - i z 选条性质一般矩阵的广义邋是没有的 定理2 1 申戆( 弱) 式其实是a 豹秩分解，换言之e p 薄怒一类英获分解可以遥 过酉相似变换实现的矩阵特别当a l 为对角矩阵时。a 就题正规阵 勇夕 扶上述定瑾瓣，对予e p 簿且，翦嚣繇述酶咒释广义遵都怒裙阕的，即有 a = a 口= a 9 = a i 罱t 一 2 a 袋菊，t 椰2 u a ：1 ：) u ( z - 。) 邵a 的广义逆其实是一个 l ，2 ，3 ，4 ，5 ) 逆本文为了方便，统一地把这些广义 逆记为a 。 念 e p 矩阵的存在也很广泛，下面仅举几个例子首先我们引进反序单位阵的概 称 j = 为n 阶反序单位阵。易知一个矩阵左乘j 产生行翻转，右乘。，产生列翻转，如 j ( 1 ，2 ，n ) 丁= ( n ，2 ，1 ) 7 ( 1 ，2 ，n ) l ，= ( n ，2 ，1 ) 另外j 是对合矩阵，即( j j ) ( ，+ j ) = 0 同时j 还满足 j = ，：j - 1 j 2 ；j ，：j t j ：i 例1 若a f 非奇异阵，对称阵，反对称阵，正规阵，实h a n k e l 阵) ，则a 是e p 阵 例2 若a 广对称阵，实t o e p l i t z 阵，实循环阵) ，则，a 和a j 均是e p 上述广对称阵是指满足a = j a r j 的矩阵a ，其中非奇异阵是最平凡的e p 阵，因此对e p 阵而言我们更加关注的是奇异阵 2 3 奇异线性方程组解的性态 求解奇异线性方程组与广义逆有着十分密切的联系，首先我们来看相容方程组 的解与( 1 ) 逆有如下关系 定理2 3 1 4 设a c ”“，x 伊，对一切使a x = b 相容的b c m ，x b 均是a x = b 的解当且仅当x 满足a x a = a 9 该定理意味着任何相容方程组均有 1 ) 逆解，而对于约束线性方程组则有如下 重要结论 定理2 4 2 4 设a c ”，t c ”，s c “，若d i m s = m d i m t ，a to s = c m ，b a t ，则下述线性方程组 a x = b ，xe t( 24 ) 在t 中有唯一解z = a 0 ) b 。 上述二定理描述了奇异线性方程组的广义逆解的存在性问题另外对于求解线 性方程组来说，k r y l o v 子空间迭代法是一类很不错的方法我们已经知道，非奇异 线性组a z = b 必有k r y l o v 子空间解，且此子空间的维数就是a 关于b 的最小多 项式的7 欠数。而对于奇异线性组解的性态就有很大的差异，即使是相容方程组也不 能保证有k r y l o v 子空间解。对于奇异组我们发现其解与系数阵a 的指标有很大关 系。首先让我们看下述结果。 定理2 5 【3 2 1 设a c “”，b c “，m 为a 的最小多项式的次数，i n d ( a ) = ， 则有 ( 1 ) 若b r ( a ) ，则a x = b 有且有唯一的k r y l o v 子空间解z = a d b 厄m k ( a ，b ) ； ( 2 ) 若b 隹r ( a ) ，则a = b 不存在k r y l o v 子空间( a ，b ) 中的解。 上述定理说明a z = b 有k r y l o v 子空间解当且仅当b r ( a ) ，另外我们知道 若a 关于b 的最小多项式的次数为p ，则厄。( 扣) ( n p ) 是p 维的，从丽有下述结 论。 定理2 5 设a c “，b c n ，a 的最小多项式的次数为m ，i n d ( a ) = k ， a 关于b 的最小多项式的次数为p ，b r ( a ) ，则a x = b 有唯一的k r y l o v 子空间解 z = a d b s ( a 6 ) ，3 = d i m i c s ( a ，b ) = m i n ( p ，m 一七) 上述定理表明了奇异线性组的k r y l o v 子空间解的存在性，但在具体求得此解 有时也不容易。下面我们对系数阵指标为1 的情况看g m r e s 方法的求解情况 定理2 6 1 9 】设a c “”，b c “，l n d ( a ) = 1 ，如果a x = b 相容，则g m r e s 会不中断地产生一个解，并且在下一步因k r y l o v 子空间的退化而中断 1 0 更特殊地，对于系数阵为e p 阵则有如下结果 定理2 7 【1 9 设a c ”“，b c “，用g m r e s 方法求解a z = b ，对任意的 b 及初始向量x o 均能无中断地产生该线性组的一个最小二乘解当且仅当a 是e p 阵。 若a 是e p 阵且在某步已产生一个最小二乘解，则g m r e s 方法在下一步中 断，且若该线性组是相容的则中断是由于k r y l o v 子空间的退化产生，否则就是由于 秩亏损产生。并且若线性组相容且z o r ( a ) ，则此解就是广义逆解。 下面我们进一步来分析方程组a z = b 解的结构。首先来看a 是e p 阵的情形。 由于a 是e p 阵，所以有 r ( a ) o n ( a ) = c ” 令t = r ( a ) ，s = ( a ) ，a t = a r ( a ) = r ( a 2 ) = r ( a ) ，从而由定理24 知有如 下结论。 定理2 8 a 是e p 阵，则相容方程组a x = b 在r ( a ) 中有唯一解= a 8 p b 。 上述定理也表明e p 阵4 在其值域r ( a ) 上是非奇异的 由于a 有分解式 a = f ( ：) 矿+ ，其中a e g 7 r ，r = r n n * e a ， 。、i 旷f ：o 毽 “= 0 y = 矿( o t ，z 己r ) 7 ，v z n 一，舒一7 ( a ) ：s p n u ( o t ，e ，一r ) t ) 7 ) ，i ：l ，2 ，n n 其中e 一7 为g ( n r ) 中的第i 个坐标向量从而a x = b 的任一解。均可写成如下 形式： z = 对古圣= ( ，一a e 9 ) 。吉且a e p z 1 l 舢0 ，ii、 讳a ，k 得 f 可 叉 则 t rt 卜 z t r z = 勺 知 易 令 甘 甘 a 可 而从 且i i x l l ；= 睦+ 蚓曜瞎，这样我们就得到下述结论。 定理2 9 a 是e p 阵，则 ( 1 ) 若a x = b 相容，则= a 8 p b 是其最小范数的广义逆解，且对该方程组的 任一解z 均有a a 。p x = o ， ( 2 ) 2若a x = b 不相容，则是其最小范数的最小二乘广义逆解，且对其任一 最小二乘解均有a a 。= 从定理2 9 我们知道，对a x = b 的任一解( 或最小二乘解) z 都可通过投影得 到其最小范数的广义逆解，这对一般非e p 阵是办不到的，原因就在于一般矩阵a 其乘法对a t 没有交换性 注：结合本章第二节内容我们知道，e p 阵的广义逆a 印保持了一般广义逆所 没有的正则逆的一些性质，再由定理2 7 我们又知道，用g m r e s 方法求解相容的 e p 线性方程组a x = b ，会不中断地在某步产生广义逆解4 印6 。然后在下一步会因 k r y l o v 子空间的退化而中断，也即其中断的特性与非奇异线性方程组是一样的。从 这两方面情况说明在某种意义上，e p 阵是一类非常接近非奇异矩阵的奇异矩阵。 下面我们再简单回顾一下如何从a x = b 直接寻求最小范数解。 a z b h l = 其中 ；= 矿+ z 三( 。二，) ，s = v + 。；c 三，) 从而 m i n l a x 一圳2 = 1 1 6 。一，1 1 2( 2 5 ) 且无论方程组相容与否其最小范数解( 或最小二乘解) 均为 e = ，( a ：靠) = 印s 值得注意的是在具体问题上，我们在求某种最小范数解的过程中有时对a 的秩分 解用不着作酉相似变换，而只需做合同变换即可( 参见第四章) 。 舟ik 、 “ ” 0 ：， 瞎 6 一 吖 一、怫 u ；h 叶 卜，u惦 o o、-、-b ； m o r ，一m o 涵 u，a 以上我们分析了系数降指标为i ，尤其怒e p 阵的奇异线性组的解的性态。这 恩我们耍指出的是矩阵的搬标不象其秩那样在线性变换下保持不交。事实上我们可 以通过线性变换把一个指标为k 的矩阵变成一个e p 阵，当然其指标变为1 。 首先矩降的奇异值分鳃就是一倒。a = ，y + ，则u a v = 裁是e p 蓐。 再者设a 有如下分解 a ；p | g 。；p - i o 其中g 为r 狯可莲方阵，r = r a n k ( a ) ，n 巍a 静零特征撮秘掰有j o r d a n 浃缀 成，n = d i a g ( q t ，q 2 ，一一，0 。) ， 0 t = 令五题与q 同阶的反序单位阵，r = d i a g ( j l ，如，五) 。再令 g = ( 则 g p 一1 a p = ( ：) ( ：) = ( ：二) 盘五 淀意到c 非奇异，r n 对称，故五是e p 阵从而求解a x 。b 现转化为求解 五童= 5 其中5 = g p l b ，= p l 2 4 几点注记 本节我们通过几点注记来例证本章内容首先祷弓l 起注意的是不同形状的矩阵 在数值计算上有时会有差异。特别是一个矩阵缀黎反謦单位终j 以鼹，尽管矩阵元 1 3 索没有任何变化，毽矩阵的形状产生改变。比如下述矩阵a 。 a 的形状为 ( 0 ，0 ，0 ，1 ) a = o1 l 2 1 ，f n i ) 0 1 1 2 ， 1 2 1 0 ，丽烈的形状为c ：；) 。取肆= t 。，e ：嚣= e ( 1 0 l o o o 。o ) ，下蕊用精度为1 0 6 重感动的g m r e s 方法分别求解 a z = b ( 2 6 ) 和 j a x = j b ( 2 7 ) 数谴实验表明方程缝f 2 ，6 ) 在乡 迭技4 步砖裁捧游了，越酵残定量终为1 ；焉方程 组( 2 7 ) 运行1 8 秒后残向量即达1 0 事实上，方程组( 2 6 ) 在_ c 。( a ，6 ) 中无解， 麓( 2 。7 ) 在瞻，) 孛有唯一辩( 冤奉章悫理2 , 5 ) ，其中五= 朋，5 一j b ，这里j a 把且的指标由竹降为1 再如令 b = n 竹 由文【3 3 】知b 在谱范数下的正规偏移度是，另一方面，无论有多大，j b 的 委怒镳移凄始终是零，瞧即了b 是蓬规阵这堇了使一个特征德极度号损静矩阵变 为可对角化，而在文 4 6 中糖出通过作相似变换来使一个矩阵正规化( 或增加正规 性，遣邵减少正规偏移度) 。毽在这里我们看到, i b j 一1 = j b j = 口7 ，从而此相似 t 4 、a = + ，口 v ， 变换未使b 的正规偏移度有任何减少这说明要增加矩阵的正规性，有时做单侧的 线性变换就足够了，作双侧的相似变化反而没有效果。 另外上述矩阵日当a 0 ( 此时b 非奇异) 时我们还可以改进 3 3 中的一个结 果事实上我们令 t = = 叱0 。) 即正+ l 是取t 的后i + l 列，并令 k i ( b ，6 ) = f 6b 6b i - lb ) ，t 1 k ；( b 1 6 ) = s p a n b ，b b ，一，b 。一1 b ) ，i 1 定理2 1 0f 3 3 设 0 ，若k i + l ( b ，b ) 列满秩，则 z 蕊，。，- 而需告郦，r = ； 其中常数c i - e 1 依赖于i 和b 且 赢鲰t s 面i i t + d 1 2 而 设a 正规，其特征值为a ，a 。，设反是b 到a 的相应于丸的特征子空间 的投影的范数，a 的相异特征值个数为s ，a 的那些特征子空间与b 正交的特征 值个数为，d = s t 定理2 1 1 3 3 a 正规，1s i sd l 。若甄+ l ( a ，b ) = ( 6 6 肼) 列满 秩，则 ze 醌= c i + l 1 篷 赢。塞，掣) ， 1 5 其中六r j 曼、门再1 而f 可， ”一，a 州是a 的相异特征值并使 达极大，砭( a ，b ) = s p a n b ，a b ，a b ) 。 足理2 1 0 干日足理2 1 1 分别表不了损阵干口正规阵的k r y l o v 于至i 司方法中的残向 量误差界对上述b 和b ，记矗( 雪，5 ) = s p a n ，亩5 ，亩“研，其中亩= j b ，5 = j b z i q ( b ，6 ) 雠的界由定理2 1 0 表达，当q 很大时效果较差，同时尽管 z 层n b ，。) 竖帚警业= = e 忍，。) 业帚孝韭， 但 ，嚣4 7 占i 、胪一b = 1 1 2 蚝k ( 即筲 却可由定理21 1 来表示。 1 6 第三章扰动分析 在这一章，我们将对奇异线性方程组的扰动问题给出一些结果奇异线性方程 组的扰动和系数阵的广义逆的扰动有很多相似之处，本论文只讨论奇异线性方程组 的扰动，有关广义逆的扰动结果可参见 5 2 5 3 】在第一节我们主要探讨谱范数和 f r o b e n i o u s 范数意义下的扰动情况，而在第二节我们主要讨论p q 范数意义下的扰 动，并给出条件数的极小性质。最后我们对e p 线性组给出更特殊的一些结果。 3 1谱范数和f 范数意义下的扰动分析 我们知道非奇线性方程组a z = b 的解对系数阵以或右端项b 的扰动的敏感程 度是由条件数来刻画的，通常条件数越大，则解对系数阵 或右端项6 的扰动的敏 感程度也越大，也称a 越病态 我们知道a 的条件数通常按如下定义 定义3 1 。对非奇异矩阵a ，称 “2 ( a ) ：= i i a i l 2j | a 一11 1 2( 3 1 ) 为矩阵a ( 关于求逆) 的条件数 同时我们也可按如下定义a 的条件数为c o n d 2 ( a ) 。 定义3 2 对非奇异矩阵j 4 的条件数按如下定义 e 删。( 叭= 。骧陋儿s 纠u p ，。世寿出 ( 3 z ) 对上述定义31 和定义3 2 中的条件数有结论