（计算数学专业论文）线性方程组的一类预条件解法.pdf

线性方程组的一类预条件解法 雷刚 摘要：随着电子计算机的出现和迅速发展，在各门自然科学和工程技术科学 的发展中，“科学计算”已经成为平行于理论分析和科学试验的第三种科学手段。 数值计算是科学计算中的一个必不可少的环节，而在数值计算中，一类很重要的 问题就是线性方程组的求解。 对线性方程组a x = b 的求解，主要有直接法求解和迭代法求解。对于阶数不 太高的线性方程组，用直接法比较有效，如果系数矩阵为无规律的大型稀疏矩阵 ( 即矩阵中的许多元素为0 ) ，直接法就很难克服存储问题。而在求解线性方程组 的许多实际问题中，尤其在偏微分方程的差分方法与有限元方法求解问题之中， 方程具有重要的特征，一是多为大型稀疏矩阵；二是满足一些条件如对称正定、 对角占优等，这使迭代法得到广泛的应用。另外，与直接法相比，迭代法还具有 一些明显的优点，比如占用计算机的内存单元少、计算程序比较简单、收敛速度 比较快等，从而成为近年来解线性方程组采用较多的方法。本文主要讨论的是用 迭代法求解线性方程组，特别是在迭代法收敛的情况下，如何加速迭代法的收敛 速度。 本文中线性方程组都有形式a x = b ，其中爿= ( ) 。，x ，6 r ”，x 为未知向 量，b 为已知向量。正文内容部分从第一章到第五章，详细内容说明如下： 第一章，主要叙述在线性方程组的求解过程中，迭代法的求解方法；同时叙 述近年来一些迭代法的发展概况，特别是预条件方法在迭代法求解线性方程组中 的作用。 第二章，给出本文所需要的基本知识和引理。包括有关的分裂理论和方法及 预条件的一些结论。 第三章，也是本文的主要组成部分，叙述预条件矩阵只= ，+ c 在系数矩阵爿为 严格对角占优的l 一矩阵时能够加速a o r 迭代法、对称的s o r 迭代法( 即s s o r 迭代 法) 的收敛性，同时含参数的预条件矩阵忍。= ，+ c ( 叻在系数矩阵a 为严格对角 占优的l 一矩阵时能够加速2 p p j 迭代法的收敛性，最后给出预条件只= i + c 下a o r 迭代法中参数珊和_ 的最优参数的选取。 第四章，讨论在第三章提到的预条件异= ( ，+ c ) 在加速迭代法收敛性方面要 优于预条件乓= j4 - j ，预条件b = ，+ s 在加速某些迭代法收敛性方面要优于预条 件b = i - i - s ，同时在数值上说明本文讨论的预条件最在加速某些迭代法收敛性方 面要优于预条件b = i + s 。 第五章，对文章的主要定理给出数值例子，从数值上加以说明。 关键词：预条件方法： 严格对角占优；l - 矩阵；谱半径；迭代法。 t t ak i n do fp r e c o n d i t i o nm e t h o do ft h el i n e a rs y s t e m l e t g a n g a b s t r a c t ：f o l l o w i n gt h ee l e c t r o n i cc o m p u t e r si n v e n t i o na n dq u i c kd e v e l o p m e n t , c a l c u l a t i o no f s c i e n c eh a sb e c o m et h et h i r dm e t h o d ，p a r a l l e l e dt oa n a l y s i so f t h e o r ya n d e x p e r i m e n to fs c i e n c ei na l lk i n d so fn a t u r a ls c i e n c ea n de n g i n e e r i n gt e c h n i q u es c i e n c e a tt h es a m et i m ec a l c u l a t i o no fn u m e r i c a lv a l u ei san e c e s s a r yl i n ks o l v i n gt h el i n e a r s y s t e mo fe q u a t i o n s ，w h i c hi sav e r yi m p o r t a n tq u e s t i o ni nc a l c u l a t i o no fn u m e r i c a l v a l u e t h e r ea r et w om e t h o d st os o l v et h el i n e a rs y s t e mo fe q u a t i o n s t h e ya r ed i r e c t s o l v i n gm e t h o da n di t e m t i v es o l v i n gm e t h o d i f t h es t e po f t h el i n e a rs y s t e mq u e s t i o ni s n o tv e r yh i g h ，d i r e c ts o l v i n gm e t l l o di sb e t t e r ；i fc o e f f i c i e n tm a t r i xo ft h el i n e a rs y s t e m q u e s t i o ni sn o tr e g u l a ra n dl a r g e - s p a r s em a t r i x ( al o to f e l e m e n ti se q u a lz e r o ) d i r e c t s o l v i n gm e t h o d d o e sn o ts e t t l et h es t o r a g eq u e s t i o n h o w e v e r , i nm a n yp r a c t i c a l p r o b l e mo ft h el i n e a rs y s t e mq u e s t i o n ，t h el i n e a rs y s t e mo fe q u a t i o n sh a ss o m e i m p o r t a n tc h a r a c t e r i s t i ce s p e c i a l l yi nl e a n i n gd i f f e r e n t i a le q u a t i o nm e t h o da n dl i m i t e d e l e m e n tm e t h o d t h ef i r s tc h a r a c t e r i s t i ci sl a r g e - s c a l ea n ds p a r s em a r x ；t h es e c o n di s s a t i s f a c t o r yw i t hs o m ec o n d i t i o n s ，f o re x a m p l e ，d i a g o n a la d v a n t a g e ，s y m m e t r ye t c c o m p a r i n gw i t l ld i r e c ts o l v i n gm e t h o d t h ei t e r a t i v es o l v i n gm e t h o dh a ss o m eo b v i o u s a d v a n t a g e s t h i st h e s i sm a i n l yd e a l sw i t ht h ei t e r a t i v em e t h o dt os o l v et h el i n e a rs y s t e m o fe q u a t i o n sa n dd i s c u s sh o wt oa c c e l e r a t et h er a t eo fc o n v e r g e n c ei nt h ec o n d i t i o no f p r e c o n d i t i o n t h r o u g h o u tt h et h e s i s ，al i n e a rs y s t e mm a m xi s o ft h ef r o m a x = b ，w i t h a = ( d d ) m 。，x ，b er ”，工i sa nb n k n o w nv e c t o r ，b i sak n o w nv e c t o r t h et h e s i s p r o p e rc o n t a i n sf r o mc h a p t e ro n et oc h a p t e rf i v e ，n o wg i v ed e t a i l s ： c h a p t e ro n ee x p l a i n st h a tt h ei t e r a t i v es o l v i n gm e t h o dh a sm u c hs u p e r i o r i t yi n s o l v i n gt h el i n e a rs y s t e mo f e q u a t i o n sa n di n t r o d u c e st h ed e v e l o p m e n t i np r e c o n d i t i o n e d t h e o r yi nr e c e n ty e a r s i nc h a p t e rt w o ，t h ew r i t e rp r o v i d e st h eb a s i ck n o w l e d g ea n dt h eb a s i cl e m m a r e q u i r e di nt h i sp a p e r i l i i nc h a p t e rt h r e e ，i ti st h ee s s e n c eo ft h i st h e s i s i td i s c u s s e st h ep r e c o n d i t i o n e r 乓= i + ca c c e l e r a t et h ec o n v e r g e n c eo ft h ea o ri t e r a t i v em e t h o da n ds s o ri m r a t i v e m e t h o dw h e nt h em a t i xai sas t r i c t l yd i a g o n a l l yd o m i n a n tl - m a t r i x ，a n da tt h es a m e t i m ei td i s c u s s e st h ep r e c o n d i t i o n e r 忍( m = i + c ( 叻a c c e l e r a t et h ec o n v e r g e n c eo f t h e 2 p p ji t e r a t i v em e t h o d a tl a s ti tg i v e st h ep a r a m e t e r 0 9 = f = 1 ，t h ec o n v e r g e n c eo ft h e a o r i t e r a t i v e m e t h o d i s t h e q u i c k e s to n e i n p r e c o n d i t i o n e r 只= i + c c h a p t e rf o u rd i s c u s s e sw h i c hp r e c o n d i t i o n e ri sm u c hq u i c k e ri na c c e l e r a t i n gt h e r a t eo f c o n v e r g e n c e i ns o m e p r e c o n d i t i o n e r t h e p r e c o n d i t i o n e r 足= i + ci s b e t t e r t h a n t h ep r e c o n d i t i o n e r 只= 1 + 3i n a c c e l e r a t i n g g a u s s s e i d e li t e r a t i v em e t h o d t h e p r e c o n d i t i o n e rp s = j + si sb e t t e rt h a nt h ep r e c o n d i t i o n e r p i = l + i i na c c e l e r a t i n g g a u s s s e i d e l i t e r a f i v e m e t h o d a t l a s t g i v i n g t h e p r e c o n d i t i o n e r 足= ，+ c i s b e t t e r t h a n t h e p r e c o n d i t i o n e rb = l + si n a c c e l e r a t es o m e i n t e r a t i v e m e t h o d i nn u m e r i c a l c h a p t e rf i v eg i v e ss o m en u m e r i c a li n s t a n c et oe x p l a i nt h ec o n c l u s i o n so ft h i s 山e s i s k e y _ m r d s ：p r e c o n d i t i o n e dm e t h o d ；s t r i c t l yd i a g o n a l l yd o m i n a n t ；l m a t r i x ； s p e c t r a lr a d i u s ；i t e r a t i v em e t h o d 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 作者签名：塑! 出 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版。 作者签名： 第一章概论 1 1 迭代法求解线性方程组的方法 在数学、物理学中的许多问题常常都归结为解线性方程组 血= b ( 1 1 ) 其中，彳= ( a v ) 。，6 r 4 ，x 为未知向量，b 为已知向量。对上述方程组 求解时，常用的解法有直接法求解和迭代法求解。直接法求解是经过有限步的运 算就得到精确解的方法，但在实际中有舍入误差的影响，这类方法只能求近似解： 迭代法求解是构造适当的近似解向量序列，用某种极限过程去逐步逼近精确解的 方法。在实际计算中根据精度要求控制计算有限步终止，获得满足精度的近似解。 但迭代法不能通过有限步求得精确解，只能逐步的逼近它，因此凡迭代法都存在 收敛性与误差估计的问题。此外，每一种迭代方法都有一定的应用范围，对同一 方程组，有些迭代法收敛，有些不收敛，而且在收敛的迭代法中，有些收敛的快， 有些收敛的很慢，这些为迭代法的研究提供了广阔的空间。 我们知道当矩阵a 是大型稀疏矩阵或具有某些特殊性质时，通常都和计算机 相结合采用迭代法求解，而不用直接法求解。迭代法解线性方程组时都假设矩阵a 是非奇异矩阵，当矩阵a 是奇异矩阵时，可以通过变换把( 1 1 ) 变为一个和它同 解的新的系数矩阵一为非奇异的线性方程组a x = b 。 迭代法求解都是基于对矩阵爿做分裂a = m n ，m 是非奇异矩阵，对线性方 程组( 1 1 ) 采用的迭代法是 + 1 ) = m 一服( + m bk = 0 ，1 “2 ( 1 2 ) 其中，m “就称为迭代矩阵。它的收敛性直接关系到方程组的求解，收敛性和迭 代矩阵m 。的谱半径有关，谱半径小于1 时就收敛否则就发散，而且谱半径越 小，迭代矩阵收敛速度就越快。 在实际应用中，为了讨论方便，常常对矩阵a 的分裂采用下列方式 a = d l u( 13 ) 这里d 、一三和一u 分别是矩阵a 的对角线部分、严格下三角部分和严格上三角部 分。结合矩阵的变换，( 1 3 ) 总可以变为 4 = j 一一u( 1 4 ) 即对角线元素全部变为1 。为了方便，本文讨论的矩阵a 都是形如( 1 4 ) 的形式。 常见的迭代法有j a c o b i 迭代法、g a u s s s e i d e l 迭代法，为改善迭代法的收敛 性和收敛速度，h a d j i d i o m s t ”1 于1 9 7 8 年提出一种快速超松弛迭代法( 简称a o r 迭 代法) ，它含有两个参数埘，f ，当埘= f 时，这种方法就变为逐次超松弛迭代法( 简 称s o r 迭代法) ；随着并行计算机的发展，1 9 8 3 年m i s s i r l i s t 川提出一种解线性方 程组的方法，称为并行j a c o b i 型方法，它的突出优点是适合大型并行机的计算。 胡家赣”2 1 在1 9 9 2 年提出了两参并行的j a c o b i 型方法( 简称2 p p j 型方法) ，使 m i s s i d i s 提出的方法成为2 p p j 型方法的特例。另外，结合实际的需要，还产生了 一些如s s o r 型迭代法、s a o r 型迭代法、p s d 型迭代法等一系列迭代方法，目 的都在于改善迭代矩阵的收敛性和收敛的速度。 1 2 常见的预条件方法 但是在实际中，迭代矩阵的收敛性和收敛速度的改善不仅取决于迭代方法和 迭代矩阵中参数的选取，而且同方程组自身的某些变化也是密切相关的，许多文 章 9 ，1 3 ，1 4 ，1 5 ，1 8 都考虑求解线性方程组( 1 1 ) 的同解方程，即对线性方程组( 1 1 ) 的两边同时左乘一个非奇异矩阵p ，使变为同解方程 p a x = m ( 1 5 ) 这时线性方程组( 1 5 ) 系数矩阵就是剐，对刚作分裂p a = m ，一n p ，那么用迭 代法解线性方程组( i 5 ) 的迭代格式为 工( 。“) = m p - ! n p 工。) + m p - i p b k = o ，l ，2 ，- ( i 6 ) 一般地，式( 1 5 ) 称为预条件方程组，用迭代法求解它的过程就是用预条件 方法求解线性方程组，也就是本文要讨论的方法。非奇异矩阵p 通常称为预处理 因子或者预条件矩阵。 常见的预处理因子有1 9 9 1 年a d g u n a w a r d e n a ，s k j a i n ”1 等人提出的预条件 矩阵b = ，+ s ，其中 s = 0 - q 2 0 0 0 一- oo0 000 0 0 ： 1 0 1 。 0 ( 1 7 ) 黔融0 0 0 000 0j 吨口，l 。 l s = ooo o oo o0 0 吒1 00 站慝 o 0 0 o _ 0 o 0 o _ q 。 0 o o ( 1 9 ) 它们在一定条件下能够加速a o r 迭代法的收敛性。此外，还有一些不多见的 预条件矩阵如，+ s + r ，i + r 等，其中r 是最后一行非零，其它元素都为零的方阵， 在一定的条件下也能加速一些迭代法的收敛性。 第二章准备知识 一、基本符号及定义 定义2 i - 记所有h h 实矩阵a = ( ) 所组成的集合为r “4 ，r “”的子集为 疋“”； = ( 嘞) i 爿r 棚，a i i o ，( v 0 ) z “4 = 一= ( 嘞) i 一r “”，嘞 0 ( v f ) 成立时，称矩阵爿为l 一矩阵。 同样，记所有n x n 复矩阵4 = ( ) 所组成的集合为c ，其子集为 c ：”= 爿= ( 吩) l 爿c ”期，a i i o ，( v i ) 定义2 2 ：如果矩阵a e r ，并且爿能表示为a = s l b ，i 为n 阶的单位矩 阵，b 0 ，当s p ( b ) 时，称a 为m 一矩阵，特别当s p ( b ) 时，称4 为非奇异的 m - 矩阵；当j = p ( 口) 时，称爿为奇异卅矩阵。其中p ( b ) 为b 的谱半径。 定义2 3 ：如果矩阵a e z “，a 可逆且a - 1 0 ，称a 为非奇异的m 一矩阵。 定义2 4 ：设一= ( d f ) ，b = ( ) 均为同阶的实矩阵， ( 1 ) 如果满足对v j ，都有吩 i “f i ，称一是严格对角占优的：如 葛 果k l i 嘞l ，称一是对角占优的；如果一l - 矩阵，且爿_ 1 o ，称a 为m - 矩阵。 篇 定义2 7 ：矩阵a e c “”，d = d i a g ( a ) ，a = d - c ，称i d 卜j c | 为a 的比较矩阵 且记为烈4 ) ，如果硝一) 为m - 矩阵，就称a 为h 一矩阵。 二、分裂方式 ( 1 ) 如果m 是非奇异”阶方阵，则称是一的分裂；若p ( m 1 n 1 0 ； ( 3 ) 如果对某个正向量x ，有血肚，那么就有p ( a ) ；另外，如果4 还 是不可约的，且对某个非负向量x 0 ，有0 船a x p x ，满足帆a x ， a x 肛，那么就有口 0 ； ( 2 ) p ( a ) 0 是矩阵爿的特征值； ( 3 ) 存在x c ”，适合j 0 ，f la x = p ( a ) x ： ( 4 ) p ( a ) 0 是矩阵一的单重代数特征值。 引理4 “：如果矩阵a 是实矩阵，设爿= m 一是矩阵一的一个分裂，那么 ( 1 ) 如果这个分裂是正规分裂或弱正规分裂，那么p ( m - 1 n 1 1 的充分必要 条件是a 。0 ； ( 2 ) 如果这个分裂是m 一分裂，弗且一具有形式a = i - l - u ，那么p ( m “) l 的充分必要条件是p ( l + u ) 1 ； ( 3 ) m - 分裂都是正规的分裂。 弓| 理5 ：矩阵一= m 一l = 鸩一m 是一的两个正规分裂，且彳_ 1 0 ，如果 2 l o ，就有0 p ( 酾。i ) 茎厦材，2 ) l ； 特别，如果还满足一l 譬0 ，l 0 ，那么就有o p ( 甄。啊) p ( a 是4 2 ) 0 成立。 引理7 1 ：矩阵a = m 一l = 峨一2 是一的两个正规分裂，且爿- 0 ，如果 有m 1 鸩一，且圻1 蛭1 ，那么就有。蔓p ( m _ 1 ) - 0 ，并且一= 厨一= m 一是矩阵爿的两个弱正规分裂， 如采有村一面- 1 ，且0 ，刚p ( 厨一1 莉p ( m 。柳。 菩l 理1 0 “：如果a 、b 为同阶方阵，且i 别a ，尉p ( 动p ( 由。 弓l 理l l ”：如果一、b ，c 、d 为同除方阵，满足0 a b ，并且0 c d ， 则就有 ( 1 ) 0 a c 蔓b d ： ( 2 ) 0 一+ c s b 十d ： ( 3 ) 对a ，b 0 ，就有卅+ 船0 ； ( 4 ) 0 一”b ，对所有的m = 1 , 2 ，都成立。 引瑷1 2 ”：如果省是严格对角占优的卜矩阵，则a 是m 一矩阵。 引理1 3 ”：设一= 0 。) z “”为菲奇异m - 矩阵，鼠d z “满足d 爿，那么就 有 ( 1 ) a 。与d 。都存在，并且还有a “d “0 ： ( 2 ) d z “的每一个特征值都为正值： ( 3 ) d e t ( d ) d e t ( a ) 0 。 引理1 4 ”：设爿= ( ) z n x n ，则下列命题等价 ( 1 ) a 为非奇异的m 一矩阵，一1 0 ； ( 2 ) 如果b = ( ) z “，且有b 一，那么b 也是一个非奇异m - 矩阵； ( 3 ) a 的任意主子矩阵的每一个实特征值都为正数； ( 4 ) 一的每一个实特征值都为正数： ( 5 ) 存在一的一种分裂a = p - q ，使得p 。0 ，q 0 ，r p ( p 。1 q ) 0 ，使 0 4 x 4 z ，那么就有 l i 鸩。2 卜阻。1 删， ( 2 1 ) 特别，如果m - 1 l 还有一个正特征向量，那么就有p ( m 2 1 2 ) p ( m , - 1 1 ) ，而 且，若还有m - 1 的一个正特征向量x 0 能使式( 2 1 ) 中的不等号严格成立，那 么就有p ( m 2 1 2 ) 0 ，所以a c 是l 广矩阵。 下证一，也是严格对角占优的。 对第一行来说，显然有h 2 + a 1 3 + - - t 7 1 1 。l 1 对第i a = 2 , 3 ，”) 行来说，非对角线元素和的绝对值为 l ( 口，2 一a i l d l 2 ) + - + ( 口一i 一口l q 卜i ) + ( 口州“- - g j i 口l ，h 1 ) + + o 。一口n 口l 。) l = 一( 口1 2 + 。+ a i ，l q + a u 十l + _ _ + + a i n ) + 口i ( 口1 2 + + a l 卜l + 口1 件l + + a 1 月) = 一 2 十。+ q 川+ q ，h + + c ) + q i ( 口1 2 + + 口i ，卜i + q + q ，+ l + - + 口h ) 一a i l a i j 一( a 2 + + 口“一l + 口十i + + 。) + l q l l - - q 口l 。 = 一( a ，l + a i 2 + 。+ 口i f q + a j + f 。+ 口。) 一a i l a l ， 1 一a d a i 从而a ，为严格对角占优的l _ 矩阵。 第三拳预条件己= ，+ c 对迭代法的加速 3 1 概论 前面已经提到，当线性方程维( 1 i ) 的系数矩阵a = ( 魄) 。是太塑稀疏箍阵或 具有某些特殊性质时，迭代法具有根强的优势，特别是随着近年来计算机技术的 飞速发震，先迭代法的广泛应崩提供了很大的空问，丽一些预条件方法具膏加速 迭代法的优势，引起众多学者的关注。在本章中。我们考虑当线性方程组( 1 - 1 ) 的系数矩阵a 为严格对角占傥的。矩阵时，类预条 孛选代法的具体应用。 对线性方程组( 1 1 ) 来说，在求解的过程中，g a u s s 消去法及一些三角分解 法是常晃的直接解法，但当线性方程组的系数矩蓐正羁有菜些特殊性质时，迭代 法具有很强的优势，随着并行计算机的发展，选代法可以和计算机结合，解线性 方程缀其有搴半功倍昀效果。 对线性方程组( 1 1 ) 考虑预条件线性方程组p a x = p b ，本文讨论的矩阵a 都 具有式( 1 4 ) 豹形式，即 a = i l u( 3 1 1 ) i , - l 和一u 分剐是矩阵a 的对角线部分、严格下三角帮分和严格上三蹙部分。其 中p e r “是非奇异矩阵，取p 为文 1 6 中提到的类预条件矩阵只= 1 4 - c c = 000 4 2 l 00 0 0 一口。一1 t 000 一“0 0 0 ( 3 1 。2 ) 此时，线性方程组( 1 1 ) 的系数矩阵“经过预处理园子足之后变为 4 = b = ( + o 爿 = ( “c ) ( ，一l u ) ：，一一u - 6 c 一毗一c u ( 3 1 3 ) 其中，e z = 0 ，相采令c u = 如+ 岛+ ，那么预处理后的矩阵如就可以写成如 0 下的形式 4 = ( j i c ) 一( 三一c + 上) 一( u + u c ) ( 3 1 4 ) ( ，一) ，一( 工一c + k ) t n - ( u + u c ) 分别是矩阵4 的对角线部分、严格下三角部分 和严格上三角部分。给出预条件已能够加速a o r 迭代法和s s o r 迭代法的收敛性。 同时给出含参数的预处理因子弓( = + c ( 叻，其中 a 功= o 吨呸1 口0 l j 飞q l o0 0o o0 00 ( 3 1 5 ) 那么线性：b - 程g l i ( 1 1 ) 的系数矩阵彳经过预处理因子足。之后变为 a c ( 神= 足( 砷一= ( ，+ c ( n 。) 4 2 ( ，+ c ( ) ( ，_ 一u ) ( 3 1 6 ) = i - l - u + c ( 6 r ) 一c ( 叻工- c ( a ) u 其中，c ( a ) t = 0 ，如果令c ( a ) u = i c ( 神+ k f 。，+ ( 神，那么预处理后的矩阵以( 鲫 就可以写成如下的形式 a c t 。) = ( j 一，c ( 砷) 一( 三一c ( 叻+ l c t a ) ) 一( u + u c ( 鲫) ( 3 1 7 ) ( j 一丘( 却) 、一( 三一c ( o t ) + l c ( ) 和一( u + u c ( 砷) 分别是矩阵如( 的对角线部分、 严格下三角部分和严格上三角部分。给出预处理因子p c ，。= ，+ c ( 能够加速2 p p j 型方法的收敛性。 2 p p j 型方法的迭代格式为 x “= z “一叫i + r j ) d 一( a x “一b ) ( 3 1 8 ) 其中脚、f 为参数，a = d c o ，j = d c o ， j 是j a c o b i 迭代矩阵。d 是矩阵 一的对角线元素，c o = d a 。则其迭代矩阵为 g o , ，= ，一( ，+ r 1 ) d a = ，一e o ( t + 仃) ( ，一j ) = ( 1 一c o ) i + 峨 ( 3 1 9 ) 其中 t = 【( 1 一f ) ，+ t ，】j ( 3 1 1 0 ) 3 2 预条件最加速a o r 的收敛性 定理1 如果线性方程组( 1 1 ) 的系数矩阵爿= ( 口。) 。为非奇异的m 一矩阵并 且钆 l ，f _ 2 , 3 ，h 。用表示矩阵一的a o r 迭代法的迭代矩阵，最。表示预 条件足= ( ，+ c ) 后矩阵4 的a o r 迭代法的迭代矩阵，则对v o y o j - l ， o ) ， 就有p ( 最。) p g , 。) 0 o = 2 ，3 ，”) ，即e c “0 ，因此k 。1 疋0 另外，1 + c 0 也是非奇异的令 m c = ( j + c ) 一e cn c = ( ，+ c ) 一疋 贝0 m c 一= e c - 1 ( + c ) 0 ，且m c n c = e c 1 尼0 又由于a 。= ( ，+ c ) a = e 。一疋，所以有 a = ( j + c ) 一a 。= ( ，+ c ) 。1 ( 民一疋) = 心一c 由上知a = m c 一 0 是a 的弱正规分裂 另一方面 a ：上( ，一皿) 一土i ( 1 一曲，+ ( 一n 工+ 洲】：m n 其中材：三( ，一皿) ，：三【g 一掰) ，+ 细一力+ 洲1 贝4 当v o y c o - l ，( 0 ) 时，m _ 1 0 ，且n 0 于是a = m c n c = m - n 是a 的两个弱正规分裂，且0 。 再证在两个弱正规分裂中有m 。1 蔓蚝。 由 ( i + 6 3 1 品：i ( i c o ( 一l c ) 一，( 上一c + k ) 】 = 土【( ，一毛) 一硝一c + l c ) 一c ( i 一毛) + 麒三一c + l c ) 】 珊 = 去咿一毛) 一艇一c + 三c ) 一c 】 2 去 u i c ) 一h 三十l c ) 一( 1 一r ) c 】 易知( ，+ c ) - l 乓是一个l - 矩阵，并且+ o 。r = 1 ( j + c ) o ，所以 ( j + c ) - 1 为m _ 矩降； 另一方面，j 一儿也是l 一矩阵，同时满足 ( j 一牡) 一 ( j + c ) “乓】= u r l ) 一【( z 一毛) 一残三+ 岛) 一( 1 一z ) c 】 = i c + r k + ( 1 一z ) c 0 结台引理 1 3 就有 m 一1 e c _ 1 ( ，+ o = m c 。 综上所述，由引理 9 知 p ( 最。) p ( 。) 按题设a 为m 矩阵，结合渺矩阵的性瑷及引理 1 7 知 厌t 。) 1 综上可得 p ( ) p ( 。) 1 推论1 如果a 为非奇异m 母阵，鼠。q 。 1 ，i = 2 , 3 ，h 用7 表示矩阵一 的s o r 迭代法的迭代矩阵，f 岛表示矩障4 在颈条件乓= u + c ) 嚣矩阵如的s o r 迭代法的迭代矩阵，则对v o 国l ，有p ( r ) 茎p ( z ) 1 证明：在卜述定理豹证明中只要驭，= 删目可 注：当，和掰取不同的特定值时，还可得到g u e s s s e i d e l 和j a c o b i 的情形 定理2 如果a 为非奇异不可约m 一矩阵，且口j l 1 。 l ，i = 2 , 3 ，”。用。表示 矩阵彳的a o r 迭代法的迭代矩阵，最。表示在预条件足= ( + c ) 后矩阵4 的a o r 迭代法的迭代矩阵，则对v 0 y 国1 ，徊o ) ，有p ( t 。) p ( 。) 1 证明：由定理l 的证明有 _ ：三( ，一皿) 一! ( 1 一回，+ ( 一r ) l + 洲】：m n 则m 是对角线元素为正的三角矩阵，从而m 是非奇异的m 一矩阵同时，n 0 故 a = m n 是矩阵a 的m _ 分裂于是由文 1 8 定理3 6 知，存在正向量z 使得 m n x = p ( m n ) x ，即0 。x = p ( 。) 石 所以，在预条件以后 4 x = ( i + c ) a x = ( ，+ c ) ( ，一皿) ( ，一弓。) i x 。 ；= 1 ( ，+ c ) ( ，一r t ) 1 一p ( ) i x 珊 = - - ( i + c 一牡) 1 一p ( 。) 珊 ” 去 k + ( 7 一i c ) 一牡+ ，c 一牡1 一p ( t m ) 】 = 石1 ( l + 蛾) 1 一p ( 弓。) i x 另方面，由定理1 的证明知4 = 一最= & ( ，一置。) ，并且k 。0 ，从而 如工= ( 1 一曩。) x 去( ，c + n 嵋。) 1 一p ( i ，。) i x 8 p ( ，一最m ) z 去。 1 一p ( 弓，。) i x + 1 一p ( 弓。) z 由于o 0 ，e c _ 1 o ，p ( 。) 【l p ( 。) 】x 从而 p ( t 。) x p ( 。，) _ 由文 5 的定理2 1 _ l l 有 p ( 。) p ( 乃。) 综上所述，结合定理1 可得 p ( 。) p ( 。) 1 推论2 如果矩阵a 为非奇异不可约m _ 矩阵，且a i 。 1 ，i = 2 ，3 ，, 用r 表示矩阵a 的s o r 迭代法的迭代矩阵，表示矩阵一在预条件足= ( ，+ c ) 后矩 a c 的s o r 迭代法的迭代矩阵，则对v 0 翻 l ，有p ( ) p ( ) 1 证明：在上述定理的证明中只要取y = 翻即可 注：当y 和倒取不同的特定值时，还可得到g u e s s s e i d e l 和j a c o b i 的情形 3 3 预条件只加速s s o r 的收敛性 设线性方程组( 1 1 ) 的系数矩一具有式( 3 1 1 ) 形式，对s s o r 的迭代矩阵 有 正= ( j 一棚) 。1 ( 1 一m ) l + o j l ( 1 一w z ) 1 【( 1 一c o ) 1 + o j u 】 = ( i - a j ) - 1 ( i - t o l ) 。【( 1 一却j + t o l 0 一t o ) ，+ 脚u 】 如果令 m 2 面两1 ( 卜越) ( ，一棚) l = 面熹面 ( 1 - 神，+ 越】 ( 1 _ 奶，+ 础 则线性方程组( 1 1 ) 的系数矩彳可以表示为 a = m 一l ( 3 3 1 ) 定理3 如果线性方程组( 1 1 ) 的系数矩阵一为严格对角占优的l 矩阵， 并且口j l q ， l ，i = 2 , 3 ，”。用z k 表示矩阵a 的s s o r 迭代法的迭