（基础数学专业论文）线性系统的预条件解法.pdf

赵海燕线性系统的预条件解法 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律结果由本人承担。 学位论文作者签名：赵瘴赢 签字日期：工。口墨年6 月l 咱 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借 阅。本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国 科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网 络向社会公众提供信息服务。 学位论文作者签名：起稼燕 签字日期：z 阳客年占月f 日 导师签名：袁写，旆 别程轹芬写，祥 签字日期：耐年占月f 日 3 7 赵海燕 线性系统的预条什解法 中文摘要 本文主要讨论了对于大型的线性方程组而言，如何加快收敛速度问题。众所 周知，在现实生活中，很多实际问题都归结为解一个或多个大型( 很多情况下为稀 疏矩阵) 线性方程组，对于这种方程组我们一般采用迭代法求解，因而讨论迭代法 的收敛性以及收敛速度成为一个值得关注的问题。不收敛或收敛速度慢的迭代格式 是没有实用价值的。因此，寻求快速收敛的迭代格式，确定某些迭代格式中的参 数，对迭代格式自身的改进等都是近代寻求快速收敛的迭代格式的方式。本文中采 用的是对迭代格式自身的改进，具体来说，在预条件矩阵只= ，+ 巳作用下改进 的双媳迭代法。 正文包括五章。第一章是引言部分，主要讨论了几种常见的迭代法以及预条 件理论以及引用了h a 西i d m o s 提出的预条件矩阵乞= j + c 口；第二章是预备知识主 要列出了本文中所要使用的数学定义以及数学论据；第三章是已有相关结论简要说 明近几年来预条件理论的发展以及一些已取得的重要成果；从第四章开始就是本文 的核心部分，下面将作详细说明。 在第四章中，作者叙述了预条件矩阵只= ，+ c 口在系数矩阵4 是严格对角占 优的三一矩阵或日- 矩阵时，在一定条件下预条件矩阵只= ，+ c 口的s 锨迭代法 ( 彪s 锨迭代法) 的是收敛的。并简要说明了预条件矩阵只= j + c 。中参数口的最佳 选取范围，最后，在数值上说明了理论的有效性。 第五章，从几个方面讨论了预条件矩阵乞= ，+ 巳在加快迭代法的收敛性方 扬州入学硕士论文 面的优越性。首先，作者说明当系数矩阵4 是非奇异的m 矩阵时，在一定条件 下，预条件只增强了s 锨迭代法的收敛性，并给出了删迭代法中参数国的最 佳选取；然后，讨论了删方法比快速松弛彳锹迭代法的收敛速度更快，体现 了预条件的优点；接着我们更换方式，自己构造一系列的预条件矩阵圪，证明了 预条件只。同样能够增强双理迭代法的收敛速度，但是对于s 锹迭代法而言，其增 强效果没有只好，说明了预条件只的在预条件矩阵中也是比较好的。最后对本章 中的主要定理给出了数值例子，从实际上加以验证。 最后，作者简要第说明了本文的具体思路以及研究前景。 关键词：预条件方法，非奇异m 矩阵，双理迭代法，收敛性，比较定理 2 一 赵海燕线性系统的预条件解法 三 a b s tr a c t t h et h e s i sm a i l l l vd e a l s 砌l h o w t 0a c c e l e r a t et l l er a t eo fc o n v e 玛e n c ef o rt 1 1 el a r g e s c a l el 硫a re q 似i o i l s a si sw e l lk n o w n ，m a n yp r o b l e m sa r er e d u c e dt oo n eo rm o r eo f 1 a r g e ( 1 l s 砌1 ys p a r s e ) l m e a re q m t i o n s a sam a 钍e ro ff a c t 1 h ei t e r a t i v em 砒o di s 也eu s 砌 w a yt os o l v et l l ee q m t i o n s ，i t sc o n v e r g e n c ea i l di t sr a t eo fc o n v e r g e n c ea r eg r e a ts i 鲥丘c a - n c e a i li t e r a t i v em e t h o dd o e s n t 、o r k ，w h j l em a th a sal o wr 砒eo fc o n v e 唱e n c ei sn o p r a c t i c a l 砌u e a ni t e 矾v ef o r n l a tt 1 1 a th a sa b e 仕e rr a t eo fc o n v e 唱e n c e n l s tb ef o u n d ， t h ep a r a m e t e r si i lt h ef o r m a tb ed e t e m i n e d ，a i l dm ea u t 0 1 0 9 0 u si i n p r o v e m e n t so n 吐1 e i t e r a t i v ef o n i l a t ，a r l do n eo ft l l e s ew a y si st os e e kb e t t e ri t e r a t i v em e t h o dw i l i c hh a sa f 瓠t r a t eo fc o n v e r g e n c e c o n c r e t e l y ，t h ep r e c o n d i t i o n e r 兄= j + c 窿i sa p p l i e dt os ( 次 i t e r a t i v em e m o d ( 肋r 5 1 c 飧i t e r a t i v em e m o d ) 1 1 1 i st e x ti r i c l u d e sf i v ec h a p t e r s c h a p t e ro n ei st h e 诂缸o d u c t i o no f 廿1 ep 印e r ，m a i l l l yt 0 d i s c u s ss o m ec o m m o ni t e r a t i v em e m o d sa n dt oi 1 1 _ 仃o d u c ep r e c o r l d i t i o n e d 协e o r ya i l dc i t e d m e p r e c o n d i t i o n e d m a t r i x 只= ，+ c 。t o p r o p o s e b y h 喇i d r i l o s m c h a p t e r 咖，n l e 嘶t e rp r o v i d e st h eb a s i ck n o w l e d g ea 1 1 dt h eb a s i cl e 删n ar e q u i r e di i lt h j sp 印e r t h e “r d c h a p t e ri sa 1 1o u t l i n eo fm ec o n c l l l s i o n sa b o u tp r e c o n d i ：t i o n e rf o rt h ed e v e l o p m e n to ft 1 1 e m e o 巧洫r e c e my e a r s f r o mm eb e g i 硼血go f c 毗r f o u ri st h ee s s e n c eo f t l l em e s i sa n d h e r e 、e 西v ed e t a i l sf o rc i l a p t e rf o l 】ra n d 丘v e mt l l ef o u r c l lc h a p t e r ，t 1 1 ea u m o rd i s c u s s e sm ec o n v e 唱e n c eo f t h em o d i f i e d 双理i t e r a t i v em e m o dw m c ht 1 1 ep r e c o n d i t i o n e r 只i sa p p l i e dt o & 旭i t e r a t i v em e t l l o d ，w h e n 吐l em a t r i x 彳 i s s 仃i c t l yd i a g o n a l l yd o m i n a n t 一m a t r i xo r 日- m 撕x 加1 dab r i e f d e s c r i p t i o n o ft l l ep 搠e t e r s 口f o r吐l eb e s ts e l e c t i o nf o mt h ep r e c o n d i t i o n e r 乞= n c 口a t1 a s t ，肌m e r i c a le x 锄p l e sa r ea l s o 西v 吼砌c hs h o w 恤e 能c t i v e n e s s o f o u rn l e m o d c h a p t e rf h e ，、张d i s c u s st ：h ep r e c o n d i t i o n e r 只= j + c 。w h i c h a c c e l e r a t e sm er a t e o fc o n v e r g e n c ef o ri t e r a t i v em e m o d f i r 瓯m ea u 1 0 rd i s c u s s e sn l ec o n v e 唱e n c eo ft 1 1 e m o d i f i e d ，s g 恹i t e r a t i v em e t h o dt oa c c e l e r a t e & 豫i t e r a t i v em e t l l o d ，w h e nt h em a t r i x 彳i st h en o n s i n g u l a r m - m a t r i x ，a n d 百v e st h eb e s tp a r 锄e t e r s 彩o ft l l e 脸( 旭 扬州大学硕十论文 i t e r a t i v em e t l l o da i l dt h e nw ed i s c u s st h a tt h er a t eo fc o n v e r g e r l c eo f 死艿( 豫i t e r a t i v e m e t h o di s 缸t e rt h 觚n l e 么( 垠i t e 洲v em e t l l o dw h e r er e n e c t s 吐l ea d 【v ；m t a 萨o f t l l e 4 一 p r 枷c a lv a l u eo f 最觚d d l e n 、ec h a i l g ea 、 ，a yt 0s t r u 孤鹏as 嘶e so f p d e c o n d i t i o n e r 只也a tp r o v e st l l es 锄em e t l l o dt 0e n h a l l c et l l ec o n v e 唱e n c er a ：c eo f 舣豫i t e r a t i v e m e m o d ，b u tt h ec o m r e r g e n c er a _ t e o fm er n e t h o dw l i c hm ep r e c o r l d i t i o n e r s 乞a r e a p p l i e dt o 舳ri t e 枷v em 砒o d ( 删i t e r a ：t i v em e 也o d ) i sl o w e rm a i l 解锨 趾d 吐l e nn u m e r i c a le x 弧p l e sa r ea l s og i v e n ，w h i c hs h o wm ee f f e c t i v e n e s so fo u r m e m o d f i n a l l v ，1 ea u m o rd e s c r i b e s 1 em a t e r i a l 仃a i l lo ft h o u g h ta i l dr e s e a r c hf o r e g r o u n do f h i sa n i c l e k e y w o rd s ：p r e c o n d “i o n e di n e t h o d ；n o n s i n g u l a rm - m a t r i x ；s c 坎i t e r a t i v cm e t h o d ； c o r e 玛e n c e ；c o m p a r i s o nt l l e o r e m 赵海燕线性系统的预条件解法 1 引言 许多实际问题常常都归结为解线性方程组 血= 6( 1 1 ) 其中，彳= ( ) 删，z ，6 r ”，z 为未知向量，6 为已知向量对上述方程组求解时， 常用的解法有直接法求解和迭代法求解。直接法求解是经过有限步的运算就得到精 确解的方法，但在实际中有舍入误差的影响，这类方法只能求近似解；迭代法求解 是构造适当的近似解向量序列，用某种极限过程去逐步逼近精确解的方法。在实际 计算中根据精度要求控制计算有限步终止，获得满足精度的近似解。但迭代法不能 通过有限步求得精确解，只能逐步地逼近它，因此凡迭代法都存在收敛性与误差估 计的问题。此外，每一种迭代方法都有一定的应用范围，对同一方程组，有些迭代 法收敛，有些不收敛，而且在收敛的迭代法中，有些收敛的快，有些收敛的慢，这 些为迭代法的研究提供了广阔的空间。 我们知道当么是大型矩阵时，用直接法求解比较繁琐，正常用迭代法。迭代 法解线性方程组时都假设矩阵么是非奇异矩阵，迭代法求解都是基于对矩阵4 做 分裂么= m 一，m 是非奇异矩阵，对线性方程组( 1 1 ) 采用的迭代法是 x ( 。+ 1 ) = ，一1 x ( 。+ ，一1 6 ，后= 0 ，l ，2 ，( 1 2 ) 其中，m q 就称为迭代矩阵，它的收敛性直接关系到方程组的求解，收敛性和迭 代矩阵的谱半径( p ( m 。1 ) ) 有关，谱半径小于l 时就收敛，否则就发散，而且谱 半径越小，迭代矩阵收敛速度就越快。 在实际应用中，彳正常分裂成 么：d 一三一u( 1 3 ) 其中d ，一，一u 分别是彳的对角、严格下三角和严格上三角矩阵。结合矩阵变换 总可以将4 分裂为： 4 ：，一三一u( 1 4 ) 其中一工，一u 分别是彳的严格下三角和严格上三角矩阵。 在此基础上，几个经典迭代法如下所示： 劬姗一& 娩，迭代法的迭代矩阵为 r = ( ，一三) - 1u ( 1 5 ) 基本的s 锨迭代法的迭代矩阵为 扬州人学硕十论文 匕，= ( 7 一国三) 1 【( 1 一缈) ，+ 缈u 】 ( 1 6 ) 基本的彳锨迭代法的迭代矩阵为 三吐，= ( j y 三) - 1 ( 1 一国) z + ( 缈一y ) + 缈u 】 ( 1 7 ) 随着计算机的发展，越来越多的入在经典的迭代法基础上提出了许多改进的 迭代法，目的是改善迭代矩阵的收敛性和收敛速度。 但是在实际中，迭代矩阵的收敛性和收敛速度的改善不仅取决于迭代方法和 迭代矩阵中参数的选取，而且同方程组自身的某些变化也是密切相关的，许多文 章 1 ，2 ，3 ，4 ，5 都考虑求解线性方程组( 1 1 ) 的同解方程，即对线性方程组( 1 1 ) 的 两边同时左乘一个非奇异矩阵尸，使( 1 1 ) 变为同解方程 剐x = 尸6( 1 8 ) 其中彳= ( 劬) r “”是非奇异矩阵，z r ”是未知向量，6 r ”是已知向量，尸 为与4 同阶的非奇异方阵。对任一分裂彳= m 一，预条件系统的迭代格式为 x ( + 1 ) = m ；1 p x + i 1 尸6 ，后= 0 ，1 ，2 ， ( 1 9 ) 其中刚= m ，一p 是剐的分裂且m ，是非奇异的。 找一个好的预条件矩阵是大家比较感兴趣的，本文中采用2 0 0 3 年，h a d j i d i m o s 在 6 中提出的预条件矩阵只： p ，= i + c ：= 一口2 口2 l 1 一口3 口3 1 1 一口 口n l ( 1 1 0 ) 其中口，o ，f _ 2 ，3 ，z 。 现考虑预条件矩阵只作用的方程组( 1 1 ) 上，首先 记彳口= 只么= ( 1 + c 口) 彳= ，一三一u + c 口一c 口一c 口u ，其中c 口三= 0 ，若令 巳u = l + 见+ 疋，那么预处理后的么。可以写成如下分裂： 彳。= ( ，一歹口) 一( 一c 口+ e 。) 一( u + 只) ( 1 1 1 ) 其中( ，一，口) ，一( 三一c 口+ e ) ，一( u + 只) 分别是矩阵彳。的对角线部分，严格下三角部 分和严格上三角部分。将预条件矩阵作用到尺方法得到新的算法记为 i 浪， 则删的迭代矩阵记为三鼽。 赵海燕 线性系统的预条件解法 三。，。= ( ，一，口) 一缈( 三一c 口+ e ) 】q 【( 1 一) ( j j 口) + ( u + ) ( 1 1 3 ) 其中m = 古【( ，一乞) 一缈( 三一q + e ) ( 1 1 4 ) = 吉【( 1 一彩) ( j j 口) + 缈( u + 兄) 】 ( 1 1 5 ) 预条件方法由于其实际应用性，已经得到许多方的关注，在 7 中，作者给出 了预条件，s 锹方法在z 一矩阵下的收敛性以及和标准的。s 0 只方法收敛速度的比较。 在 8 中作者比较了预条件阳足方法和标准舳足方法以及国姗一& 娩，方法的敛 散关系。 在本文中我们主要研究了预条件矩阵= ，+ c 。的优越性。首先我们说明了 预条件矩阵只= ，+ c 。不仅能够增强单松弛因子s 锨迭代法的收敛性而且给出预 条件s 锨方法的最佳松弛因子，以及谱半径随着松弛因子的变化规律。随后我们 将预条件& 旭的收敛性与快速松弛方法么锨相比较，我们都知道彳锨方法的提出 是为了改善迭代法的收敛性和收敛速度，但是我们的预条件s o r 迭代法的收敛速 度比彳d r 迭代法的收敛速度快得多，体现了预条件的优越性。最后我们换个角 度，将预条件矩阵只= j + c 。作用的预条件s 锨迭代法与我构造的一系列预条件 矩阵圪相比较，前者的收敛速度比较快，再次用实际理论证明了预条件矩阵 只= j + c 。的优越性。最后用数值例子验证了本文的结论。 7 一 扬州人学硕士论文 2 预备知识 首先我们给出本文中常用的矩阵定义以及一些引理。 定义2 1 【9 1o 】设彳= ( q f ) r “，如果o ，f ，= 1 ，2 ，z ，则称彳是非负 的，记彳0 。 定义2 2 网 爿= ( q ，) r 称为是z 矩阵，若q ，0 ，f ，f ，= 1 ，2 ，甩；若 彳z ，且满足口， o ，f = 1 ，2 ，刀，则称彳为一矩阵；若彳z 肼”有分解式 么= 盯一e b o ，使得j p ( b ) ，则称彳为m 一矩阵。 下面是关于证明m 一矩阵的一些已有结论。 引理2 3 【9 ，1 0 】令彳z ，则么是m 一矩阵的充要条件为彳可逆且彳_ 1 o 。 引理2 4 【1 0 1 令彳z 脚，则彳是膨一矩阵的充要条件为： ( 1 ) 彳是一矩阵； ( 2 ) 令q = j 一( 威铿4 ) _ 1 么，有p ( q ) 0 。 引理2 6 【9 】设么是z 一矩阵，那么下面几个命题等价： ( 1 ) 彳是非奇异的m 一矩阵； ( 2 ) 存在向量z 0 ，使得出 o ； ( 3 ) 彳的所有主对角元为正。 在证明预条件s 锨方法的收敛性，给的前提条件基本上是保证( 1 1 ) 的系数矩 阵彳为日一矩阵或严格对角占优的三一矩阵。 定义2 7 1 0 1 设彳c ，如果彳的比较矩阵( 4 ) = ( 聊) 是m 一矩阵，则称么 为日一矩阵，这里= j i ，m 扩= 一i ，f 。 引理2 8 【1 2 】如果彳是对角元素全为1 的日一矩阵，让 8 一 赵海燕线性系统的预条件解法 7 = ( 乃，心) r = ( 彳) p ，那么以l ( f - 1 ，2 ，2 ) 且8 ( 彳) 。1 也1 ，其中 9 一 p = ( 1 ，1 ) 。 引理2 9 【1 1 1 3 1 4 】如果彳是对角元素全为1 的日一矩阵，让( 彳) = ( 历，) ，则 聊口1 ，f = 2 ，3 ，聆。 = l 引理2 1 0 旧彳是h 一矩阵的充要条件是存在向量x o ，使得( 彳) x o 。 定义2 ”设彳= ( q ，) c “”，彳称为是按行对角优势矩阵，如果 i l i i ，江1 ，2 ，z 。若上式全部成立严格不等式，则称彳是按行强( 或严 j = l j 亭| 格) 对角优势的。 弓l 理2 1 2 【1o 】令彳0 r ”，贝0 ( 1 ) p ( 么) 黝的一个特征值； ( 2 ) 么有一个相应于p ( 么) 的特征向量x o 。 在这篇文章中，我主要采用矩阵分裂的思想以及相关结论比较方法之间的收敛 速度。 定义2 1 3 【1 叼如果4 是方阵，彳有分裂么= m 一，则 ( 1 ) 如果m 一1 o ，o ，那么这种分裂叫正则分裂； ( 2 ) 如果m 一1 0 ，m 。1 0 ，那么这种分裂叫弱正则分裂； ( 3 ) 如果m 是m 一矩阵且o ，那么这种分裂叫m 分裂。 定义2 1 4 【9 1 设么是z 一矩阵，那么下面几个命题等价： ( 1 ) 彳是非奇异的m 一矩阵； ( 2 ) 存在向量x o ，使得4 x 0 ； ( 3 ) 彳的所有主对角元为正。 引理2 1 5 【1 7 1 设彳：m 一是正则分裂或弱j 下则分裂，则p ( m - 1 ) 0 能使( 2 1 ) 中不等式严格成立，那么就有 p ( m ；1 2 ) p ( m f l 1 ) 。 引理2 1 9 18 】矩阵么= m l 一1 = m 2 一2 是彳的两个正则分裂，且彳一1 o ， 如果2 1 o ，就有o p ( 膨f 1 1 ) p ( m i l 2 ) o ，f = 1 ，2 ，刀一1 ，且 o 口1 ，口f 1 1 ，扛1 ，2 ，z ，o 国1 ，则标准飧迭代法和预条件s 锹迭代法的 迭代矩阵丁和于都是非负不可约的。 这篇文章中在同样的条件下，给出了双姬迭代法和预条件s 锹迭代法的迭代 矩阵谱半径的关系。 定理3 2 【7 】同定理3 1 的条件，则 ( 1 ) 若p ( 丁) p ( 丁) 。 在此基础上作者又讨论了在预条件只作用后。s 锨迭代法的谱半径的范围。 定理3 3 【7 】若么是三一矩阵，且口l i o ，f _ 2 ，3 ，z ，口l f 川口i + l ， o ， f 1 ，2 ，z 一1 ，则下面结论成立。 ( 1 ) 若0 口“日n 1 或口f l 0 ，口l ，= 0 贝00 口，1 ； ( 2 ) 若口1 ，日，1 = l ，则o 口， 1 则o o 。 且丁和于是非负不可约的，其中丁和于分别是标准s 锨和删迭代法的迭代矩 阵。 再次基础上作者也给出了两种方法谱半径之间的关系。 定理3 4 【刀条件同定理3 3 ，则有 ( 1 ) 若p ( 丁) p ( 丁) 。 本文中我采用比较定理的方式证明了预条件只的优越性，并且说明了在不同 的条件下，解锨迭代法的收敛性。 以上是近来一些前人对于预条件e 的简要成果，其实好的预条件矩阵还有很 多。如1 9 9 7 年k o h l l o 【2 3 1 等人取预条件矩阵p = 只= 歹+ s 口提出了一种预条件 g 口螂s 一& f 沈，迭代法，其中 s 。= o 一口l 口1 2 0 一口2 口2 3 一口月一1 吼一1 0 1 2 其中口，f = 1 ，2 ，3 ，刀一1 为非负实数。 在文献 2 3 中，k o h o 等人证明了如果彳是一个非奇异严格对角占优z 一矩阵且 满足一定条件，则存在口7 1 ，使得对于任意的口， o ，口】，【j + s 。】彳仍然是严格 对角占优z 一矩阵，并且对于参数口，的最有选择也做了一些探讨。近来w | e nl i 【2 l j l ix i n g s u n 【8 】运用这个预条件矩阵得出了一些关于预条件搬迭代法比较定理。 定理3 5 【8 】 么是非奇异的m 矩阵，0 缈1 ，o 口，1 ，f = 1 ，2 ，z 一1 ， p ( 咒) p ( 乙) 1 ，其中疋是预条件p = 兄= 歹+ s 口的s 锨迭代法的迭代矩阵， z ，是s 锹迭代法的迭代矩阵。 定理3 6 【8 】4 是非奇异不可约的m 矩阵，0 缈1 ，0 口，1 ， f _ 1 ，2 ，2 1 ，p ( 疋) p ( 乙) 1 ，其中瓦是预条件尸= 乞= ，+ s 口的- s 锹迭代 赵海燕线性系统的预条件解法 1 3 法的迭代矩阵，l 是s 锨迭代法的迭代矩阵。 本文中我结合前面的结论给出预条件s 锹在不同的条件下具备很好的收敛 性，进而说明预条件矩阵只的实用性。 当然预条件理论还有一些其它的发展方向。 1 9 9 2 年，胡家赣提出两参并行如c d 6 f 方法( 简称2 尸方法) 2 4 ，随后李宏峰 等人给出了在预条件矩阵p ，= ，+ c 的作用下的预条件2 即7 方法。 2 0 0 1 年，d j e v a n s 【2 5 】提出一类预处理矩阵只：j + 和乓= ，+ 每，其中 s = 00 oo 0 0 0 o 一口。1 0o o s = 0oo 一q 。 0 oo 0 0 oo o 它们在一定条件下能够加速彳a 喂迭代法的收敛性。此外还有一些不多见的预条 件矩阵，+ j s i + r ，+ r 等，在一定条件下也能够加速一些迭代法的收敛性。 扬州人学硕士论文 4 朋s 锹预条件法收敛性的分析 1 4 引理4 1 令么z ，若彳为非奇异m 一矩阵，0 国1 ，三。由( 1 6 ) 定 义，则户( 三掰) 0 ，f = 1 ，2 ，3 ，行口玎o ，f 歹，贝0 0 ； 因而当0 国1 时m _ 1 存在； 由( 2 1 ) 知m 一= ( j 一础) = 缈( ，+ 础+ ) 0 ，= ( 1 一缈) ，+ u 0 ； 结合定义2 1 3 知s 锹中的彳= m 一分裂为正则分裂，又因为彳为非奇异m 一矩 阵，则么- 1 0 ； 由引理2 1 5 知：p ( m 一1 ) 1 ，即p ( 。) 0 所以彳。是三一矩阵； 下证彳。是严格对角占优的， 对第一行来说，显然有k 2 + q 3 + + 口1 。 1 对第f ( f = 2 ，3 ，刀) 行来说，对角元素和的绝对值为： 1 5 对彳口来说第一行显然满足对 ( 4 2 ) ( 4 3 ) i ( 口订一口，口f l 口1 1 ) + ( 口，2 一口，口，1 口1 2 ) + + ( 口j f l 一口，口，l 口1 ，1 ) + ( 口u + l 一口，口，】口1 ，+ 1 ) + + ( 口一口j 口，l = 一( 口f 1 + 口f 2 + + a ，。f - l + a i 。f “+ + 口加) + 口f 乜f l ( 口1 1 + 口1 2 + + 口lr 一1 + 口1 f “+ + 口m ) = 一( 口f l + 口f 2 + + 口f ，f 一1 + 口f ，f + l + + 口加) + 口，口1 1 ( 口1 l + 口1 2 + + 口1 f 一1 + q f + 口l f + 1 + + 口m ) 一口i 口n 口“ 一( 口f l + 口f 2 + + 口，f l + 口f ，+ l + + 口i h ) + 2 口，口f 1 一口l a f l 口l 一( 口，l + 口j 2 + + 口f f i + 口+ l + + 口衍) + 2 口j 口，1 一口，a ，1 a l f 1 + 2 q 口，1 口f 口f 1 口1 ， 1 一口。口f l q l 从而彳。是严格对角占优的则得到结论。 口 引理4 3 若么严格对角占优的三一矩阵，对于( 1 1 1 ) 定义的以，则以是 日一矩阵。 证明：由( 4 2 ) ，( 4 3 ) 知 聊( 彳。) = 彳。，由定义2 7 知要证明以是日一矩阵， 只要证珑( 以) 是m 一矩阵，即证明在此条件下么。是m 一矩阵。因为么严格对角占 优的l 一矩阵，由定理4 2 知以也是严格对角占优的一矩阵，肌( 么。) 的对角元素不 为零； 令彳口= 抛( 以) 一c ，显然q = f 坊昭( 彳。) - 1c o ，且恻j 。l ，由此推出p ( q ) 1 缕堂堡主笙塞 堕 若p ( q ) = l ，由于q o ， 由引理2 1 2 知，存在向量x o ，x o ，满足 9 2 p ( 9 ) x = x ，即 ，一 施曙( 彳。) 】1 彳。扣= x ，从而 历昭( 彳口) 】1 以：o ，这与 么。，旃昭( 么。) 的非奇异性矛盾； 据定义2 7 得：以是膨一矩阵，于是， z ( 彳口) 是m 一矩阵，则以是日一矩阵。口 引理4 4 令彳z 脚， 若彳为日一矩阵，0 彩1 ，三。由( 1 6 ) 定义，则 户( 。) 1 。 证明：由4 = 一三一u 2 考( ，一础) 一去 ( 1 一彩) ，+ 力u 是日一矩阵，又因为o 国l 缈 功 。 一一 则可知m ：! ( ，一础) 也是一个日一矩阵： 缈 并且( 彳) 2 去( ，一缈h ) 一吉 ( 1 一国) ，+ f u i 】是一个m 一矩阵因此 觚丢( ，一缈坳1 ( 丢( ( 1 一州+ 国m ) 1 又因为( ，础) 1 ( ，一缈h ) ，( 1 一缈) ，+ 缈u ( 1 一彩) ，+ 国m 于是 卜础) 一( ( 1 一彩) ，+ 缈u ) 腓，一础) 一1 i j ( 1 一彩) ，+ 彩u 诽，一彩陟1 | f ( 1 一彩) ，+ 缈例 此小觚，一础广( ( 1 刊，+ 蝴) 纠( 丢( ，一榔) - 】e ( ( 1 刊，+ 国m ) 1 口 定理4 5 如果彳对角元全为1 的何一矩阵，若口l ，0 ，汪2 ， ，且 。口， o ，f ：l ，2 ，甩， 赵海燕 线性系统的预条件解法旦 当f = 1 时，( ( 彳) r ) ，= 1 ，且( ( 彳。) ，) 。= 1 o ； 当f ：2 ，刀时，( ( 彳口) 厂) ，：一i ( 1 一口，) 口f 1 | 1 + i 口。一口，口n 口j 一窆l 口l 一口。口订口，i 。 歹f ，1 若0 o ，1 酆q 小赫吼 ( ( 彳) ，) ，：( 1 一口f ) i 1 1 + | 口，i 一口肚瓶卜窆k 一叩。加 j f ，1 1 + 口，f 口f l l + i 口n i ( 2 2 口，) l + 。= 1 + 2 l 口，l l 一口，1 日，l ( 2 l + 。一1 ) l 1 + k l q l l + 1 诽2 一忆 据引理2 1 0 知爿口也是日一矩阵； 据引理4 4 的证明知p ( 三彻) o 口 推论4 6 若么是严格对角占优的三一矩阵，若口。，o ，江2 ，刀，且 。s 1 + 赫= 2 ，则以是严格对角占优的三一矩阵 p ( ) 一 r ， 。刚 扬州人学硕士论文 4 2 数值例子 考虑线性方程组血= 6 ，其中 彳= 1 0 1 o 5 o 2 0 8 1 o 4 o 9 o 2 o 6 1 0 6 o 5 0 7 o 3 0 1 经验证：彳是对角元为l 的一矩阵，其比较矩阵的逆矩阵的无穷范数 l i ( 彳) 叫忆= 2 7 ，所以据定理4 5 的条件有 。口z1+赫2375，。口s168，。口。236 在此范围中取口= ( 1 6 ，1 1 ，1 8 ) 7 国 p ( 伽) o 20 9 6 3 8 o 6 o 9 0 3 8 0 8o 8 7 8 6 则验证了定理4 5 。 赵海燕线性系统的预条件解法 5 比较定理 5 1 预条件s o r 迭代法最佳参数的选取 1 9 引理5 1 设方程组( 1 1 ) 的系数矩阵4 为非奇异的m 一矩阵，那么在预条件矩 阵只= ，+ 巴后，彳口= 只4 = ( ，+ c 。) 彳= m 口一虬，其中 m 。：坠羔塑坚趔 ( 5 1 ) 一 缈 。：坠丛_ 丛型生型 ( 5 2 ) ” 缈 其中m 口，口是彳。的s 锨分裂， 0 缈l ， 口= 缸2 ，口3 ，口。) r ，0 口f 1 ， 0 口订q ， o ，使得血 o 又 因为c 。 o ，则( 爿口一么) x = ( j + c 口) 彳一4 】x = c 。彳x 0 ，即么。x 么x 0 ，据引 理2 6 ，我们知道彳。也为非奇异的m 一矩阵。 口 定理5 ，2 设方程组( 1 1 ) 的系数矩阵么为非奇异的m 一矩阵，那么在预条件矩 阵艺= ，+ c 口后，s 伽迭代矩阵三蚴的谱半径满足： 扬州人学硕士论文 2 0 p ( g s ) = 户( 三1 口) p ( m 口) 1 即当国= 1 时，预条件后的蛐的谱半径p ( 三邺) 达到最小，其中0 缈1 ， 口= ( a 2 ，口3 ，a 。) 7 1 ， 0 口f 1 ，o 口，l 口l f o ，( f - 2 ，3 ，船) ，即m f l o ，因此 赵海燕线性系统的预条件解法 2 1 m f 1 o ； 并且m 。一1 = ( ，一，。) 一( 三一q + 以) 一( u + 冗) = i l 。一l + c 。一e q u f ， = ( ，一，口) ，一( ，一，。) 叫( 一c 。+ 包+ u + 只) = ( ，一，口) ( ，一眈) = 以 其中吃= ( j j 口) 卅( 一巳+ e + u + 只) 据定义2 1 3 知么口= m 。一。是一正则分裂，即以= m 一l = 收一心是彳口的两 个不同的j 下则分裂； 因易知预条件后彳。= 乞么= ( ，+ 巴) 彳是非奇异的m 一矩阵，所以 吃= ( ，一l ) 。1 ( 三一c 口+ e + u + 兄) 0 ，贝0 彳：1 = 【( 一l ) _ 1 ( ，一吃) 】= ( ，+ 吃+ b ：+ ) ( ，一，。) - 1 o 又因为0 缈1 ，o o 由引理2 1 9 可知，户( m f l 1 ) 夕( m ：1 口) 1 。 综上所述即得：p ( g s ) = p ( 厶口) p ( ) l ，口= 他2 ，口3 ，口。) r ，口，是常数， f = 2 ，3 ，刀。 口 以上定理说明了在预条件矩阵只= ，+ c 。后的双斌迭代法，在一定条件下， 当缈= 1 时，预条件后的三蝴的谱半径p ( 三邺) 达到最小，其中o 彩1 ， 口= ( 口2 ，口3 ，口。) r ，0 口j 1 ，扛2 ，2 ，即预条件只= ，+ q 后的预条件 g 口娜一& f 沈，迭代法，即取最佳松弛参数为缈= 1 。下面我们说明预条件矩阵加快 了舳足方法的收敛速度。 5 2 预条件乞：，+ c 。增强标准腓方法的收敛速度 定理5 3 假定4 = ( ) 尺职”是非奇异的m 一矩阵，设彳= m 一和 彳口= m 口一口，分别是彳和彳口的& 理分裂，其中 m ：三( ，一础) ( 5 5 ) 扬州人学硕士论文 = 二 ( 1 一缈) ，一彩u ( 5 6 ) 倒 m 。，口由( 5 1 ) ， ( 5 2 ) 给出。若0 彩1 ， 口= ( 口2 ，口3 ，口。) r ， 0 口，1 ， 0 口，1 口1 j 1 ， f = 2 ，z ，贝0 p ( m ：1 。) 户( m 。) o ，f - 1 ，2 ，以以及假设 0 口，1 口1 ， 0 ，f = 2 ，刀， 因而( j l ) 一和m ：1 都存在； 若o 0 也非奇异 令m 。= ( ，+ 巴) 一肘口，。= ( ，+ 巳) _ 虬； 贝0 m j l = m ：1 ( ，+ c 乙) o m j l c = m ：1 ( j + 巳) ( j + c 口) 一1 以= m ：1 口o ，又因为以= ( ，+ 巴) 么，则有 m 。一札= ( ，+ 巴) 。1 ( m 口一虬) = ( j + c 口) 。1 ( ，+ c a ) 么= 彳= m 一 则彳= m 一= 必一c 是么的两个弱正则分裂； 1 m 。= ( ，+ e ) 。1 m 口= ( ，一巳) 【( ，一l ) 一国( 三一巳+ 瓦) 】 1 = 二 ( ，一c 。) ( ，一，口) 一彩( ，一c 乙) ( 三一c 。+ 占二) 】 叫 1 = 二 ( ，一l ) 一国( 一c 。+ e ) 一c 口( ，一l ) + 以口( 一c 口+ e 。) 】 叫 1 = 二【( 一，。) 一功( 三一c 。+ e 。) 一c 。 叫 1 = 二 ( ，一，。) 一功( 三+ 反) 一( 1 一缈) c 。】 w 易知( j + c 口) 一膨。是一个三一矩阵，并且 m 。一= 【( ，+ q ) 。1m 口一= 肘二1 ( ，+ c 口) o 所以m ，= ( ，+ q ) 一m 口为m 一矩阵； 另一方面m = 二( ，一越) 也是一个一矩阵； 赵海燕线性系统的预条件解法 则 ( ，一缈) 一( j + c 。) 1m 口= ( j m ) 【( ，一j 口) 一缈( 三+ e 口) 一( 1 一国) c 。】 = i 一国l i + i ，+ l + e 。+ c 。一以。 = l + 髓垣0 + ( 1 一缈) c 乙o 因为o 国l ，则m m 。，由引理2 5 知m j l m 一，由4 是非奇异m 一矩阵， 则么- 1 0 ，据引理2 1 6 ，得到结论p ( m 二1 口) p ( m - 1 ) 1 。 口 由定理5 3 可以得到以下两个结论。 推论5 4假定彳= ( 口。) r ”是非奇异的m 一矩阵，设么= m 一和 么。= m 口一心，分别是彳和彳口的g 口z 郴一& f 沈，和& 豫分裂其中m = ，一三， = u ， m 口，虬由( 5 1 ) ， ( 5 2 ) 给出若o 国1 ， 口= (