（计算机软件与理论专业论文）大型线性方程组的迭代解法.pdf

东北大学博士学位论文摘要 大型线性方程组的迭代解法 摘要 随着计算技术的发展，从偏微分方程、线性规划、网络分析、结构和非结构问题的 有限元分析等领域中提出了求解大型稀疏线性方程组的问题。 本文就是针对大型线性代数方程组的求解问题进行了系统的研究。 首先针对两种特定线性方程组一正实线性系统和广义严格对角占优线性系统进行了 分析和讨论。针对正实线性系统给出了一种新的迭代解法。该迭代法的构成是基于系数 矩阵的混合形式的分解。迭代法需要选择一个对称正定矩阵历通过适当选取矩阵口新 迭代法是收敛的，并且以定理的形式给出了两种选择口的方法，又通过例题给出了迭代 法的计算过程。可以看出，对于用迭代法求解正实线性系统，新迭代方法要比其它的迭 代方法如s o r 法更容易实现。 其次利用阶梯矩阵及其一般性的定义和性质构造出一种新的迭代法。基于此新矩阵 类的迭代方法的显著特征是它对于并行计算很容易被实现。特别地，关于a o r 方法的一 些性质都被延伸到该新方法中，并针对h e r m i t i a n 正定矩阵进行了新方法收敛性的分析。 最后，给出了一些例子来表明新方法的优越性。 文中以n a v i e r - s t o k e s 方程和s t o k e s 方程作为模型问题，介绍了带稳定化的混合有 限元离散方法和m a c 格式的有限差分离散方法，由此引出了鞍点形式的方程组。利用 模型分析给出了鞍点问题的类型及特点，分析了常规的迭代解法失效于求解鞍点问题的 原因。寻找具有更简单的计算格式或收敛更快的迭代格式，成为热门的研究课题。 针对鞍点问题给出了新的有效求解方法。新方法是通过对近年来发展起来的广义 s o r 方法，s o r l i k e 方法及广义a o r 方法进行了分析和总结，并针对对称鞍点线性系 统的特有的结构特点而得到的含有两个迭代参数的迭代方法，称之为广义s o r l i k e 方 法，并对广义s o r 1 i k e 方法进行了收敛性分析，最后又通过数值算例的分析指出广义 s o r l i k e 方法同s o r 1 i k e 方法相比，收敛速度大大提高。在s o r l i k e 方法，广义a o r 方法及广义s o r l i k e 方法的基础上，又给出了一种求解鞍点问题新的迭代方法。通过 分析指出新方法实际上是s o r l i k e 方法和广义a o r 方法的推广，从而为求解鞍点问题 提供了又一种有效且可行的迭代解法。 i i 东北大学博士学位论文摘要 关键词：鞍点线性系统，s o r l i k e 方法，广义s o r l i k e 方法，广义a o r 方 法，阶梯矩阵，正实线性系统，对称正定矩阵，n a v i e r s t o k e s 方程。 一i i i 东北大学博士学位论文 a b s t r a c t i t e r a t i v em e t h o d sf o rl a r g e l i n e a rs y s t e m s a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t i n gt e c h n o l o g y , s o l v i n gt h el a r g el i n e a rs y s t e m si s o b t a i n e df r o mm a n ys c i e n t i f i cr e s e a r c ha n de n g i n e e r i n gc o m p u t a t i o ns u c ha s p a r t i a l d i f f e r e n t i a le q u a t i o n s ，l i n e a rp r o g r a m m i n g ，n e t w o r ka n a l y s i s ，t h ef i n i t ee l e m e n ta n a l y s i so ft h e c o n f i g u r a t i o na n du n c o n f i g u r a t i o np r o b l e m i nt h i st h e s i s ，t h es o l v i n go ft h el a r g el i n e a rs y s t e m si sc o n s i d e r e d f i r s t ，t w os p e c i f i cl i n e a re q u a t i o n s - - - - t h ep o s i t i v er e a ll i n e a rs y s t e m sa n dt h eg e n e r a l i z e d s t r i c t l yd i a g o n a l l yd o m i n a n tl i n e a rs y s t e m sa r ec o n s i d e r e d f o rt h ep o s i t i v er e a ll i n e a r s y s t e m s ，an e wi t e r a t i v em e t h o di sg i v e n t h en e w i t e r a t i v em e t h o di sb a s e do nam i x e dt y p e s p l i t t i n go ft h ec o e f f i c i e n tm a t r i x t h ei t e r a t i v em e t h o dn e e dc h o o s eam a t r i xdw h i c hi s s y m m e t r i ca n dp o s i t i v ed e f i n i t e ( s p d l i ti ss h o w nt h a tt h ep r o p e rc h o i c eo fm a t r i xdc a n m a k es u r et h ec o n v e r g e n c eo ft h en e wi t e r a t i v em e t h o d h e r et w oc h o s e nm e t h o d so ft h e m a t r i xdi sg i v e ni nt h ef o r mo ft h e o r e m ，a n dt h ec o m p u t i n gc o u r s eo ft h ei t e r a t i v em e t h o d w a sg i v e nb yt h ee x a m p l e f o rt h ep o s i t i v er e a ll i n e a rs y s t e m ，t h en e wi t e r a t i v em e t h o di s m o r ee a s yr e a l i z e dt h a nt h eo t h e ri t e r a t i v em e t h o d ss u c ha ss o rm e t h o di nt h el i t e r a t u r e s e c o n d l y , t h ed e f i n i t i o n sa n ds o m ep r o p e r t i e so fs t a i rm a t r i c e sa n dt h e i rg e n e r a l i z a t i o n s a r ei n t r o d u c e d t h i sc l a s so fm a t r i c e sp r o v i d e db a s e so fm a t r i xs p l i t t i n g sf o ri t e r a t i v e m e t h o d s t h er e m a r k a b l ef e a t u r eo fi t e r a t i v em e t h o d sb a s e do nt h ed e wc l a s so fm a t r i c e si s t h a tt h em e t h o d sw e r ee a s i l yi m p l e m e n t e df o rp a r a l l e lc o m p u t a t i o n i np a r t i c u l a r , s o m e t h e o r i e so ft h ea o rm e t h o dw e r ee x t e n d e dt ot h eg e n e r a l i z e dm e t h o dt oi n c l u d eaw i d ec l a s s o fm a t r i c e s t h ec o n v e r g e n c eo ft h en e wm e t h o dw a sd e r i v e df o rh e r m i t i a np o s i t i v ed e f i n i t e m a t r i c e s f i n a l l y , t h ee x a m p l e sa r eg i v e ni no r d e rt os h o wt h es u p e r i o r i t yo ft h en e wm e t h o d i nt h i st h e s i s ，w et a k en a v i e r - s t o k e se q u a t i o na n ds t o k e se q u a t i o na st h es t a n d a r dm o d e l p r o b l e m sa n di n t r o d u c et w om e t h o d st od i s c r e t et h e m ：t h em i x e df i n i t ee l e m e n tm e t h o dw i t h s t a b i l i z a t i o na n dt h ef i n i t ee l e m e n td i f f e r e n c em a c ，t h u sg i v i n gt h es a d d l ep o i n tp r o b l e m s t h es t y l ea n dc h a r a c t e r i s t i co ft h es a d d l ep o i n tp r o b l e m si sg i v e n ，t h es p e c i a ls t r u c t u r eo ft h i s s y s t e mm a k e ss o m ew e l l - k n o w na l g o r i t h m si n v a l i d t of i n dt h ea l g o r i t h mw h i c hh a sas i m p l e r f o r m a ta n dh i g h e re f f i c i e n c yi sa no p e np r o b l e m f o rt h es a d d l ep o i n tp r o b l e m s ，t h en e wi t e r a t i v em e t h o dw i t ht w or e a lp a r a m e t e r si s g i v e nb yt h ea n a l y s i so ft h eg e n e r a u z e ds o rm e t h o d ，s o r l i k em e t h o d ，t h eg e n e r a l i z e d 一一 东北大学博士学位论文 a b s t r 。t a o rm e t h o d ，a n dt h es t y l ea n dc h a r a c t e r i s t i co ft h es y s t e m s ，i ti sc a l l e dt h e g e n e r a l i z e d s o r l i k em e t h o d t h ec o n v e r g e n c ea n a l y s i so ft h eg e n e r a l i z e ds o r l i k em e t h o di sd e r i v e d f i n a l l y ，n u m e r i c a lc o m p u t a t i o nb a s e do nap a r t i c u l a rl i n e a rs y s t e mi s 舀v e n ，w h i c hc l e a r l y s h o wt h eg e n e r a l i z e ds o r l i k em e t h o do u t p e r f o r m st h es o r 1 i k em e t h o d o nt h eb a s eo f s o r l i k em e t h o d ，t h eg e n e r a l i z e da o r m e t h o d ，t h eg e n e r a l i z e ds o r 1 i k em e t h o d ，a n o t h e r n e wm e t h o di sg i v e n b ya n a l y z i n g ，w ek n o wt h en e wm e t h o de x t e n ds o r l i k em e t h o da n d t h eg e n e r a l i z e da o rm e t h o d i ti st h ee f f e c t i v ei t e r a t i v em e t h o df o rs o l v i n gl a r g es p a r s e s a d d l ep o i n tl i n e a rs y s t e m k e y w o r d s ：s a d d l ep o i n tl i n e a rs y s t e m s ，s o r - l i k em e t h o d ，t h eg e n e r a l i z e ds o r 1 i k e m e t h o d ，t h eg e n e r a l m e da o rm e t h o d ，s t a i rm a t r i c e s ，t h ep o s “i v er e a ll i n e a r s y s t e m s ，s y m m e t r i ca n dp o s i t i v ed e f i n i t em a t r i x ，n a v i e r - s t o k e se q u a t i o n v 一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 签字日期； 鼢慧 j 抄石、7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流 学位论姗垆惫善师签名：苍挽卸 签字 e l期 ：a 形多、7 签字日期： 咖g 、) 东北大学博士学位论文 第一章绪论 1 1 研究背景 第一章绪论 大型线性方程组的求解是大规模科学与工程计算的核心。随着计算机的飞速发展， 需求解的问题的规模越来越大，同时线性方程组的解法也在不断更新。十几年来，从微 分方程数值解、线性规划、网络分析、结构和非结构问题的有限元分析等领域提出了求 解阶数是上千阶直至几十万阶的线性方程组的问题而当实际的线性方程组的阶数很高 时，其矩阵一般是稀疏的。所谓稀疏线性方程组就是其系数矩阵的绝大多数元素是零。 一般说来，一个弹x 一阶矩阵，倘若其非零元总数a 0 0 ) ，就可称之为稀疏矩阵。稀疏 矩阵技术是理论发展、数值经验和实际考虑的有机结合，其应用是极为广泛的，除了上 述的有限元分析领域，还应用于工程技术计算机辅助网络设计、电子和电气网络、 频域分析、电子网；应用科学化学工程，数据处理、遗传学；理论科学化学、 物理、反应动力学：人文科学汽车的发展、商务管理、经济学、城市规划等等。 稀疏矩阵技术不仅在广大应用领域中是一种重要的计算工具，其对计算机科学的发 展也是一个有价值的贡献。因为在实际应用中，当我们想利用计算机做任何一件事情( 包 括传统的各种数值计算与越来越多的非数值计算) 时，首先会考虑的是所给问题能不能 用计算机解决? 若能解决，则总是希望在内存空间占用量尽可能少的同时，用尽可能短 的时间来完成其求解任务。这一要求引出一系列相互联系而又非常实际的问题，如：怎 样设计出满足要求的求解算法；如何分析、区别算法的好坏；可否改进现有的算法使其 更有效；求解所给问题最好可能的算法会是什么，等等，而稀疏矩阵技术恰好可以解决 这些问题。 求解线性方程组，通常采用直接法和迭代法，对于中等规模的方程组来说，直接法 常常有其优越性。但对于大型稀疏线性方程而言，迭代法已取代直接法成为最重要的一 类求解方法。因为若用直接法求解，比妨说用高斯消去法，则一个突出的缺点是将很多 零值变为非零值，将简单的非零元素变得复杂，这样就需要过多的存贮空间和算术运算 量，所以是不可能的或者效率不高的。近年来各种新的迭代法不断涌现，对各类矩阵问 题设计出许多近似优化算法，方法的实施和理论分析也获得了很大的进展，在许多领域 中应用得很活跃，应用范围也将继续不断地扩大，稀疏矩阵计算也将会不断地完善和发 一1 一 东北大学博士学位论文 第一章绪论 展。 当然，任何一种方法都不是万能的。不同的迭代解法适用于不同的线性系统。某些 具有特殊结构的线性系统很难应用常规的迭代算法来进行求解，而这些系统往往具有很 广泛的应用背景。因此，为这些特殊的大稀疏线性系统找到适当的迭代解法，成为重要 的研究课题帅1 。 1 2 研究现状 目前，人们已经得到了一些较为成熟的线性方程组的迭代解法，从某种意义上讲它 们都可归结为分裂法，其中包括古典的s o r 方法和a o r 方法。 1 2 1 正规分裂 设线性代数方程组为 4 x 一6( 1 1 ) 常常将系数矩阵4 分裂成两个矩阵肼和之差，即 彳一 ( 1 2 ) 且用迭代 缸( i + n n x ( k ) + 6 ( 1 3 ) 来解线性方程组( 1 1 ) 。将此迭代方法称为分裂法、而将j i f 。1 称为迭代格式( 1 3 ) 的迭代矩阵啪。 然而迭代法需要解决的首要任务是迭代格式是否收敛的问题，于是有如下的结果： 定理i 1 迭代格式( i 3 ) 收敛的充分必要条件是迭代矩阵膨1 的谱半径， p ( m j ) 1 ，而且p ( m 。1 l v ) 越d 、，收敛越快 对于矩阵a 的分裂应该说是有很多形式，但并不是所有分裂形式产生的迭代格式都 有意义。于是有了正规分裂的概念： 定义1 1 对于实方阵彳，若矩阵m 和满足4 - m - n ，且m l 土0 ，n o 一2 一 东北大学博士学位论文 第一章绪论 称a - m n 是爿的一个正规分裂。 那么正规分裂与其他分裂形式相比到底有什么优势呢? 于是有定理有： 定理1 2 若4 - m n 为爿的正规分裂，且一。1 之0 ，则 p ( m - 1 ) 一p ( a 1 ) 1 + p 。1 ) ) 从而p ( 膨。l ) t 1 ，此时相应的迭代格式( 1 3 ) 必收敛。 如果针对矩阵爿给出两种正规分裂，如何来衡量它的好坏呢? 定理1 3 若矩阵有两个正规分裂，设彳- m , 一i ，a - m z 一2 且彳1 土0 ， 2 1 o ，l o ，l - 2 ，则有 o p 似i 1 1 ) s 户似；l 2 ) c 1 _ ， 1 2 2s o r 方法 在迭代法的历史中，d m y o u n g 提出的s o r 方法( s u c c e s s i v eo v e r r e l a x a t i o n m e t h o d ) 曾经以其优雅简洁的格式而备受青睐，是一种经典的迭代方法m 。 对于给定的线性方程组( 1 1 ) ，将矩阵a 分解为 a - d l u ( 1 4 ) 其中，d 拙g 瓴，4 。，口。) 为a 的对角矩阵，- l 是由a 的下三角部分元素所构成的 严格下三角阵，u 是由a 的上三角部分元素所构成的严格上三角阵，于是求解方程组 ( 1 1 ) 的s o r 迭代算法为 z 州- p + 毗) 1 ( 1 一m ) d n i 【，】+ 叫p + 础) 。1 b ( 1 5 ) 相应的分裂为 m 三d + 工。 仁一1 ) d u 其中脚是实数，称为松驰因子，令 。- ( d + 埘) 1 【( 1 一) d n 盯】 称l 为s o r 方法的迭代矩阵 一3 一 东北大学博士学位论文第一章绪论 将一般迭代新的收敛定理1 1 应用到s o r 方法就得到如下定理 定理1 4 s o r 方法收敛的充分必要条件是p ( k 。) t 1 。 在s o i i 方法中，松驰因子m 并不能随意选择，下述定理给出了的取值范围 定理1 5s o r 方法收敛的必要条件是0 2 。 利用方程组系数矩阵a 的性质，还可得到下述收敛性结果： 定理1 6 设系数矩阵a 是严格对角占优矩阵，且o c 珊1 ，则s o r 方法收敛。 定理1 7 设系数矩阵a 是对称正定矩阵，且0 t t 2 ，则s o r 方法收敛。 1 2 3a o r 方法 经典的s o r 方法产生之后，派生出一系列的迭代方法，但其中较为有影响的是1 9 7 8 年由a h a d j i d i m o s 给出的a o r 方法( a c c e l e r a t e do v e r r e l a x a t i o nm e t h o d ) 旧若系数 矩阵4 采用( 1 4 ) 的分裂形式，则a o r 方法的迭代格式为： z 隹+ 1 - ( d 一厄) 4 【( 1 一w ) d + ( c a - r ) l + a 9 1 x 恤+ ( d - r l ) 。1 b ( 1 6 ) 令 、 。- ( d 一，正) 1 【( 1 一p l d + ( n ，一，弘+ a 。盯 ( 1 7 ) 则称k ，是a o r 方法的迭代矩阵，称为加速因子，而称为松驰因子 当参数r 和甜取特殊值时，a o r 方法就变为一些著名的迭代法，即 _ 方法是j a c o b i 方法，k 方法是g a u s s - s i c d c l 方法， z 方法是s i m u l t a n e o u s o v c r r c l a x a t i o a 方法， l 方法是s u c c e s s i v e o v c r r c l a x a t i o n 方法 应当指出，除非r - - o ，否则a o r 方法实质上是带有松弛因子r 和外推因子s - 譬的 外推s o r 方法，且易知 ，一啦，+ o - s ) l ( 1 8 ) 其中i 表示单位矩阵，表示以r 为松驰因子的s o r 方法的迭代矩阵如果v 和a 分别 为，( r 一0 ) 和，的特征值，有如下关系式： 一4 一 东北大学博士学位论文第一章绪论 a - w + ( 1 一s ) ( 1 9 ) 将一般迭代法收敛定理1 1 应用到a o r 方法便可得到如下定理。 定理1 8 a o r 方法收敛的充分必要条件是p 以) 1 和l 时分别称为超松驰法和低松驰法。我们只关心超松驰法。这里每步迭代也都要解形如 ( 2 3 0 ) 的子方程组。 利用( 2 2 8 ) 的矩阵记号，s o r 法( 2 4 6 ) 可以写成 j d k + 1 - 鹕】一+ 1 + g z 加+ + ( 1 一) j 孰一 改写一下就有 工o + 1 ) 置加+ 七箩 ( 2 4 7 ) 其中 篇t a d ：叫m 旺 磴- ( ，一毗) 。1 。协 工和u 由( 2 4 5 ) 给出。矩阵乞称为s o r 迭代矩阵。 s o r 法的分裂矩阵是 一d c l ) ，与g a u s s s e i d e l 法一样，它不是s p d 矩阵。 1 时的s o r 法是不可对称化的。而且，超松驰的矩阵乞一般总有某些特征值是复数。因 此，当m ，1 时外推法不适用于s o r 法 由于a 和d 都是s p d 矩阵，可以证明s o r 法对任何满足0 c 2 的都收敛，而且 常可选择适当的使s o r 法快速收敛，例如可以比j a c o b i 或g a u s s s e i d e l 法要快得多。 如果系数矩阵a 对于所作的划分具有性质月并有相容次序，那么通常可以给出使s o r 法收敛最快的“最优”值的表达式。 2 3 5 切比雪夫半迭代方法 另一种加速迭代收敛速度的方法是利用切比雪夫多项式。假设石( 1 ) ，工，工i 是由 迭代膨“+ 1 一胁+ 6 产生希望确定系数y ( 七) ，- o ：k ，使得 ) ，m 荟啦妒 2 比工隹更好。若工旧一- 工耻) - 毒，很自然要求y 耻) - 工，因此要求 一1 5 东北大学博士学位论文第二章基本迭代法概述 v j ( 七1 - 1 2 5 0 ) 在此限制下，考虑如何选取匕似) 使得_ - 的误差能够最小。 因工“一工- ( m 。1 r 一呻，其中一0 一工一工，可知 y m 一工一蹇v ，忙) ( x o ) - x ) 妻叶似) ( m 。l ) e ( o ) 两边取范数0 4 ：得 i y ( k ) - x bh p , ( c ) n ：p 1 1 2 ， ( 2 川 其中g - m 1 ， 见( z ) 。善9 小) z 由条件( 2 5 0 ) 知仇( 1 ) - 1 在此基础上假设g 是对称的且特征值满足： 一l 0 ) 吼“= + u k = k + 1 r k = a q k 、 f o r i = 1 ：k j = 彩气 r k ；r k j q j 一2 3 东北大学博士学位论文第二章基本迭代法概述 e n d 魄+ 址= i i , , i i ： 7 吒= + q k y k ，其中阮而一百t l i ：= r a i n e n d 工2 x k 容易证明| | 6 一他8 ：一噍+ 1 i 上h e 豁e b e i g 矩阵的最小二乘问题能用g i v e n s 旋转有效求 解。在实际计算中，只有当残量达到我们所希望的范围时，才需要形成五 。无界的g m r e s ”的主要问题是：在第七步迭代中，需d ( h ) 个f l o p 。因此，与 a m o l d i 方法一样，一个实际的g m r e s 方法运行起来需要采用重开始技巧，以避免过 多的计算量和存储量。例如，若最多可容许计算历步，则k 可作为下一个g m r e s 序 列的初始向量 2 5 其他方法 2 5 1 基于近似因子分解的基本方法 在2 2 节中，曾假定任何基本方法都可用分裂矩阵q 唯一地定义。令这种矩阵q 是 通过把系数矩阵a 分解成a - q r 而确定的，则由( 2 4 ) 可知，对应的基本迭代法( 2 2 ) 可以写成形式 i 啦- + 1 ) - r x 伽+ 6 ( 2 6 0 ) 其迭代矩阵为g - ，一q - i a q 境。现在考虑矩阵q 具有形式q 上的方法。这时，非 奇异矩阵h 和k 的选择既要使它们易于求出，又要使矩阵q 是。容易求逆的”。此外， 为了使收敛速度尽可能高，矩阵j j r 和k 的选择还应迭代矩阵g 的谱半径尽可能小 如果a 是对称正定的，则一种选择办法是取日- 上和k - l ，其中工是由a 的 c h o l c s k 7 分解a f 工确定的上三角矩阵。这时r 一0 ，过程经一步迭代就由敛。实际上， 这不过是g a u s s 直接解法的另一种形式。这种解法，当彳为大型稀疏矩阵问题时，矩阵 日- 工可能不再稀疏，甚至可能不容易算出。 一2 4 东北大学博士学位论文第二章基本迭代法概述 为了避免完全分解爿带来的这些问题，办法之一是取h 和k 分别为下和上三角矩 阵，但其乘积h k 只近似地等于a 。通常的做法是：首先规定日和x 的特定稀疏形式， 然后确定日和x 的非零元素，使得乘积h i ( 尽可能接近于a 。这种方法包含一系列迭代 技术，它们之间的差别主要在于日和x 的选择。d u p o n t 等学者将此方法称之为近似因 子分解法。 如果爿是对称正定矩阵，那么通常可以采用不完全对称因子分解q 删7 。如果q 是正定的，那么基本方法( 2 6 0 ) 是可对称化的，从而可以用切比雪夫和共轭梯度过程 来加快收敛速度。 2 5 2 交替方向隐式法 d o u g l a s 1 9 5 5 ，p c a c e m a n 和r a c h f o r d 1 9 5 5 ，以及d o u g l a s 和r a c h f o r d 1 9 5 6 i j i 进 了一类叫做交替方向隐式法的技术。这里介绍其中的一个h a o 咖a n - - r a c h t o r d 方法 如果( 2 1 ) 的矩阵a 可以表示成和式 一- - + y ( 2 6 1 ) 其中假定爿，儿y 都是s p d 矩阵，那么p e a c e m a n - - r a c h f o r d 方法的定义是 ( i - i + a j ) x 争b 一缈一q ，如町 ( 2 6 2 ) + q ，j p 扣哪- b - ( 日一- 弦了 ，+ l 、 这里假设对任何正数q 和口l ，从第一个方程容易由已知的z o 求出x 争，从第二个方 程容易由已知的工争求出石加1 ) 。如果线性方程组是以椭圆型偏微分方程得出的，那么 在这种典型情况下h 和矿可以取三对角矩阵，或者至少是窄带宽矩阵。对于矩形网格 剖分上的有限差分方法来说，日是对应于水平差分的矩阵，矿是对应于垂直差分的矩阵 人们通常乐于循环使用一组特定的参数q ，可，吒，口一，口一口的值 一般与日和y 的特征值的界有关 p c , c m a n - - r a c h f o r d 方法的基本理论仅当矩阵日和y 可交换时成立。对于椭圆型 偏微分方程，这一要求意味着差分方程是可分的，而且区域是矩形的。w i d l u n d 把该理 论推广到矩形域上的不可分方程。有许多情形，虽然现有理论不严格适用，但这种方法 一2 5 东北大学博士学位论文第二章基本迭代法概述 也很成功。p r i c e 和v a r g a 还构造出了p e a c e m a n r a c h f o r d 理论根本不适用的例子。尽 管对p e a c e m a n - - r a c h f o r d 方法的分析作出了许多努力，但至今没有建立起稳固的理论基 础 2 5 3 快速直接法 最后简单提一下一类非常快速的方法，它们经常用于求解特定类型的线性方程组。 在求解矩形域上的常系数椭圆型偏微分方程时，这类线性方程组经常出现。快速方法的 根据是，离散化问题存在封闭形式的解。这种解与从“可分离”连续问题得到的f o u r i e r 级数解的形式相似。对于离散化的情形，把解表示成具有特定性质的有限和形式，这些 性质使我们能很快找到该有限和。这类方法通常称为快速f o u r i e r 方法。 快速直接法是可考虑用于更一般的线性方程组，其条件这些方程组可用某种矩阵变 换逐次减半地降低阶数。于是有所谓的循环收缩法，奇偶收缩法等等。 对于那些不能直接用快速法求解的问题，通常可以把快速直接法与其它方法结合起 来使用。例如，c o n c u s 和o o l u b ，c o n c u s 等曾混合使用快速直接法与切比雪夫或共轭梯 度加速法求解了某些偏微分方程。p r o s k u r o w s k i 和w i d l u n d 讨论了用容量矩阵处理非矩 形区域的问题。其它快速直接法还有b a n k 的前进式算法，关于此法还可参阅b a n k 和 r o s e 及b a n k 一2 6 东北大学博士学位论文 第三章特定系教矩阵线性方程的迭代解法 第三章特定系数矩阵线性方程的迭代解法 数值线性代数中许多带有倾向性的研究都是在具有特殊形式结构的矩阵问题上集 中起来。本章就讨论其中的两种特定线性方程组正实线性系统和广义严格对角占优 线性系统的解法与判定问题。 3 1 模型问题 在用有限差分法对偏微分方程求其数值解时，常常产生线性方程组： a x - b ( 3 1 ) 假定我们给出简单的对流扩散方程 ( + u 。) + c ，( + ，) - ，o ，) ，) ( 3 2 ) 该方程在单位正方形上满足d i r e c h l e t 边界条件且仃 0 是常数。 取定沿x 轴和y 轴方向，步长均为i l - 万1 石，作两族与坐标轴平行的直线，将单位 正方形用网络进行覆盖。 。 令而- h ，f - 0 , 1 , 2 y i j h ，i - 0 , 1 , 2 两族直线的交点为，妒) ，记为“，y ，) 。沿x ，y 方向分别用二阶中心差商代替k 和口， 用一阶中心差商代替及耻，则得 一如例饥m 1 + ”鸭】+ ( 3 3 ) 品一n j 一+岷ii-n|,i-i卜，“，yilt-，,j j ) 瓦h n 厂 + 岷 j 。，瞒，j j 其中表示节点x - 而，) ，- y ，上的网函数这样我们便得到了形如( 3 1 ) 式的线性方程 组，且 a - m s ( 3 4 ) 其中肘是对称正定矩阵，s 是反对称矩阵，且 一2 7 东北大学博士学位论文第三章特定系数矩阵线性方程的迭代解法 m - d 缸g ( - 1 ，b ，一j ) ，s 一口d 缸g ( 1 ，c ，) ( 3 5 ) ，表示n n 阶单位矩阵，b 和c 均为n x n 阶矩阵，且 丑- 咖( 一1 ，4 一1 ) ，c - d a g ( l o , 一1 ) ，扣p h 2 ( 3 6 ) 若用d i a g ，y ，z ) 表示如下矩阵 y z xyz x yz x yz zl r 该矩阵是块还是点三对角矩完全依赖于x ，y 。z 表示的是实数还是矩阵，此处可 知( 3 1 ) 中的系数阵a 的阶数是h - 2 f h - y h 亩1 _ 通常取较小的数，故而方程组 ( 3 1 ) 中彳的阶数一般都很大，故而不可能采用直接方法求解。又由于彳是稀疏的， 故采用迭代方法来求解咖m 3 2 正实线性系统的迭代解法 定义3 1 对于线性方程组( 3 1 ) ，若其系数矩阵a 是大型稀疏非对称的，且a + 是对称正定矩阵，称矩阵a 为正实矩阵，而方程( 3 1 ) 为正实线性系统。 对于正实线性系统而言，不能用g a u s s - s e i d e l ( g s ) 方法和s o r 方法来求解，因为 没有相应的理论去保证迭代法的收敛性。本节的主要目的就是针对正实性系统给出一种 行之有效的新的迭代方法，该方法将在3 2 1 节给出，新方法的收敛性分析将在3 2 2 节中给出。 下面给出在本节中将要使用的符号：令矩阵g 是一个方阵，那么p ( g ) 表示矩阵g 的谱半径；矩阵g 7 表示矩阵g 的转置矩阵；矩阵g 表示矩阵g 的共扼矩阵；矩阵g ”表 示矩阵g 的共轭转置矩阵。如果x 表示一个向量，那么向量，i ，分别有着和矩阵 g 7 ，丘，g ”相同的含义。l 卅：和l g l ：分别表示向量r 和矩阵g 的2 一范数- 令a + 如， 其中， ，九是两个实数，且i 2 一一1 ，那么h 表示譬+ 墨。如果 是实数，那么 一2 8 东北大学博士学位论文 第三章特定系数矩阵线性方程的迭代解法 表示a 的绝对值。 3 2 1 迭代法的构造 假设方程( 3 1 ) 的系数矩阵爿有如下的分解形式 a - m s ( 3 7 ) 其中，矩阵m 是对称正定矩阵，矩阵s 是反对称矩阵。令p 墨+ & ，其中，矩阵是和品 满足如下式子 咒- ( 3 8 ) 而且矩阵是由矩阵s 的下三角部分构成的。选择一个对称正定矩阵d ，那么求解方 程( 3 i ) 的迭代格式构造如下 ( 肼+ d 一p 耻哪- b + ( d + 置p m ，七一o 1 ， ( 3 9 ) 这里需要指出，矩阵d 的选择必须满足如下条件； ( 1 ) m + d 一& 是非奇异的。 ( 2 ) 对于一给定的c ，方程( m + d 一咒讧一c 要比方程( 3 1 ) 更易于求解。 ( 3 ) p ( a ) 1 ，其中占是由( 3 9 ) 定义的迭代法的迭代矩阵，且 g 一+ d - s 。广f d + 品) ( 3 - l o ) 这里还要指出，s o r 迭代法或者是点形式或者是块形式，但由( 3 9 ) 定义的迭代方法 是一个混合形式的分解形式，这是因为肘可以是点形式也可以是块形式，但和品却 总是点形式。 3 2 2 迭代法的收敛性分析 令a 是迭代矩阵g 的任一个特征值，向量工是与之对应的特征向量并且满足 一2 9 东北大学博士学位论文 第三章特定系数矩阵线性方程的迭代解法 m ：= 1 。又因为迭代法收敛的充要条件是p ( 口) t1 ，这就要求矩阵g 的任意非零特征值a 均要满足h t l 不妨假设a ，0 ，由式( 3 1 0 ) 有如下式子 ( d + s 。) x - x ( m + d - s l ) x ( 3 1 1 ) 在上式两边分别左乘向量j 。得 x “( d + s 。) x - x “( m + d - s l ) x ( 3 1 2 ) 尽管矩阵a 是实矩阵，从而迭代矩阵g 也是实矩阵，但是特征向量工可以是复向量，那 么j 。毛工也可以是复的。然而由于矩阵肘和d 是对称正定的，j “口+ 缈j 和j 。占k 必 是实的，故令 、 a _ 毒打d x ，_ 善( 时+ d ) x ，x h s w x - 口l + i c t 2 ，( 3 1 3 ) 那么 。 ，s 一- ，掣工一吨”s ， ( 3 1 4 ) 于是有 z ”s l x 一- ( a 1 + i a 2 ) - ：- a l + i a 2 ，( 3 1 5 ) 又因为 工日( f + d s 工) x - 工日p + ( d + 5 。) x 】- x ! t b + x ( d + 毛 m , x ”a x + x ”( d + 瓯如( 3 1 回 所以必有 工片( f + d s ) x ，0 成立。否则，由式( 3 i i ) 有 工日( d + e p - 0 ， 由式( 3 1 6 ) 必有 x n 4 x 0 ： 一3 0 东北大学博士学位论文第三章特定系数矩阵线性方程的迭代解法 而另一方面， 工a x 一工j j r m x 一工s x - 工珂m x - ( x 冉s 。工+ 工s l j ) l 工h a 缸一2 a 一 又因为矩阵m 是对称正定矩阵， 所以 这就导出矛盾。那么由于 j ”膨r 0 ， 工”a x _ 0 。 工抒( m + d s 弦一0 ， 再利用式( 3 1 1 ) 就有如下式子： 所以 a ；挈芋苦! 也， ( 3 1 7 ) 工“( m + d s l 弦芦- l - , f f l 一i a 2 、7 i 刈2 一踹 于是若要使i 州t 1 成立当且仅当 ( 卢+ a 1 ) 2 一( 口+ 口1 ) 2 _ ( 卢一口卢+ a + 2 口1 ) - 工甘 缸【卢+ 口+ z 口l 】 0( 3 1 8 ) 或者说t 1 成立当且仅当 由式( 3 1 0 ) 有： 卢+ 口+ 2 a l 0 x h ( 2 d + m + s i + s ：| 口+ a + x h s i x + x h s ：x ( 3 1 9 ) ，+ 口+ z 圩s x + x 抒s , x 户+ 口+ 2 口1 ( 3 2 0 于是h t l 成立当且仅当2 d + m + s 。+ s ：是对称正定矩阵 因此就证明如下定理： 定理3 1 假设矩阵4 是正实矩阵并且a - - m s ，其中矩阵m 是对称正定矩 一3 1 东北大学博士学位论文第三章特定系数矩阵线性方程的迭代解法 阵，矩阵s 是反对称矩阵。设矩阵s 有形如( 3 8 ) 式