（应用数学专业论文）两类矩阵的预条件迭代法的收敛性.pdf

赵丹：两类矩阵的预条件迭代法的收敛性 中文摘要 数学、物理、力学等学科和工程技术中许多问题的解决最终都归结为解一个或一些大 型稀疏矩阵的线性方程组，而对这种方程组人们一般采用迭代法求解，因此迭代法在求解 大型计算问题中正发挥着重要的作用不收敛或收敛速度慢的迭代格式是没有实用价值 的因此，寻求快速收敛的迭代格式，确定某些迭代格式中的参数，对迭代格式自身的改 进等都是近代寻求快速收敛的迭代格式的方式 对于求解这些大型稀疏线性代数方程组，人们最早发现的迭代法有j a c o b i 迭代法、 g a u s s s e i d e l 迭代法在引入松弛因子和加速因子之后，s o r 迭代法、a o r 迭代法等迭代 方法也出现了，这些迭代法我们统称为基本迭代法它们都是通过构造迭代数列，取数列 的极限得到方程组的精确解这些方法给我们解大型的线性方程组带来了很大的方便 近十多年，稀疏线性方程组的迭代解法有了很多新发展，特别是预条件矩阵的引入， 通过预条件矩阵的作用加快迭代的收敛速度 本文利用预条件矩阵，+ 最，对稀疏线性方程组讨论了当系数矩阵为日一矩阵时，预条 件s o r 迭代法的收敛性及预条件a o r 迭代法的收敛性，然后讨论了当系数矩阵为z 一矩阵 时，根据不同的分裂取两种不同的迭代矩阵得到相应的预条件a o r 迭代法的收敛性，并对 两种预条件a o r 法的收敛性进行比较，得到了相应的比较定理，从而推广和改进了原来已 有的结论 以下为本文的结构和主要内容： 第一部分是引言我们给出了预条件方法产生的背景，以及基本的s o r 迭代法，a o r 迭代法的迭代矩阵，引进预条件矩阵p ，并给出了预条件s o r 、预条件a o r 迭代法的迭 代矩阵 第二部分是预备知识这部分是第四部分和第五部分的准备，主要给出一些重要的定 义、引理，如矩阵、z 矩阵及矩阵分裂的定义等 第三部分是已有相关结论简要地说明了近几年来预条件理论的发展以及一些已取得 的重要成果 第四部分是本文的主要结论之一这一部分主要讨论当线性方程组的系数矩阵是h 矩阵时的预条件s o r 迭代法和预条件a o r 迭代法的收敛性，并且讨论了日矩阵及日矩 阵的比较矩阵在预条件s o r 迭代法下的收敛率的比较定理 第五部分也是本文主要结论之一主要研究线性方程的系数矩阵是非奇异z 一矩阵时， 扬州大学硕士学位论文 2 一 在两种不同的预条件a o r 迭代法下的收敛性然后讨论了这两种预条件a o r 迭代法与经 典a o r 迭代法的比较定理 第六部分是小结和前景展望对本文做了一定的总结并对预条件迭代法的前景进行展 望 关键词：预条件，z 矩阵，h 一矩阵，m 矩阵，收敛性 赵丹：两类矩阵的预条件迭代法的收敛性 a b s t r a c t 3 一 m a t h e m a t i c s ，p h y s i c s ，m e c h a n i c sa n de n g i n e e r i n gd i s c i p l i n e s ，s u c ha sm a n yp r o b l e m sa r e a t t r i b u t e dt ot h ef i n a ls o l u t i o no fo n eo ran u m b e ro fl a r g e - s c a l es p a r s em a t r i xo fl i n e a re q u a t i o n s ， w h i c ha r eg e n e r a l l ys o l v e db yu s i n gi t e r a t i v em e t h o d s t h e r e f o r ei t e r a t i v em e t h o d sf o rs o l v i n g l a r g ec o m p u t i n gp r o b l e m sa r ep l a y i n ga ni m p o r t a n tr o l e n o n - c o n v e r g e n c eo rs l o wc o n v e r g e n c e o ft h ei t e r a t i v ef o r m a th a sn op r a c t i c a lv a l u e t h e r e f o r e ，i no r d e rt os e e kt h er a p i dc o n v e r g e n c e f o ri t e r a t i v es c h e m e ，w en e e dt os e e kt h er a p i dc o n v e r g e n c et f o ri t e r a t i v es c h e m e ，w en e e dt o d e t e r m i n et h ep a r a m e t e ri nc e r t a i ni t e r a t i v es c h e m e ，a n ds oo ni nt h em o d e mt i m e f o rs o l v i n gt h e s el a r g es p a r s el i n e a ra l g e b r a i ce q u a t i o n s ，t h ef i r s ti t e r a t i o nw h a th a v ef o u n d a r ej a c o b ii t e r a t i v em e t h o da n dg a u s s 跆f 如，i t e r a t i v em e t h o d w i t ht h ei n t r o d u c t i o no f r e l a x a t i o nf a c t o ra n dt h ea c c e l e r a t i o nf a c t o r , s u c ha ss o ri t e r a t i v em e t h o d ，ao ri t e r a t i v em e t h o d h a v ee m e r g e d ，w ec a l lt h e s em e t h o d sa st h eb a s i ci t e r a t i v em e t h o d t h e ya r ec o n s t r u c t e dt h r o u g h t h ei t e r a t i v es e r i e s ，c h e c ko u tt h el i m i t so faf e wt ob ee x a c ts o l u t i o n so ft h ee q u a t i o n s t h e s e m e t h o d sg i v eu sab i gc o n v e n i e n c ew h e nr e s o l v et h el a r g e s c a l es y s t e mo fl i n e a re q u a t i o n s h e r ea r et h es t r u c t u r ea n dm a i nc o n t e n t so ft h i sp a p e r t h ef i n s tp a r ti st h ei n t r o d u c t i o n w eg i v em e t h o d so f p r e - c o n d i t i o n sf o rt h eb a c k g r o u n d ，a s w e l la st h eb a s i cs o ri t e r a t i v em e t h o d ，ao ri t e r a t i v em e t h o df o ri t e r a t i v em a t r i x ，t h e i n t r o d u c t i o no fp r e - c o n d i t i o n sf o rt h em a t r i xp ，a n dg i v eap r e c o n d i t i o no fs o r ，p r e c o n d i t i o n e d a o ri t e r a t i v em e t h o df o rt h ed i e g og e n e r a t i o nm a t r i x t h es e c o n dp a r ti st h ep r i o rk n o w l e d g e p a r to ft h i si st h ef o u r t hp a r to fa n dt h ef i f t hp a r to f t h ep r e p a r a t i o n ，i tm a i n l yg i v e ss o m ei m p o r t a n td e f i n i t i o n s ，l e m m a s ，s u c ha sh - m a t r i x ，z - m a t r i x a n dm a t r i xs p l i t t i n gd e f i n i t i o n t h et h i r dp a r ti st h a tt h e r ea r ea l r e a d yc o n c l u s i o n s b r i e f l yd e s c r i b e st h ep r e c o n d i t i o n si n r e c e n ty e a r sa n dt h ed e v e l o p m e n to ft h et h e o r ya sw e l la ss o m ei m p o r t a n tr e s u l t sh a v eb e e n a c h i e v e d p a r ti vi so n eo ft h em a i nc o n c l u s i o n so ft h i sa r t i c l e t h i sp a r to ft h em a i nd i s c u s s i o no f l i n e a re q u a t i o n sw h e nt h ec o e f f i c i e n tm a t r i xi st h eh - m a t r i xa tt h ep r e c o n d i t i o n e ds o ri t e r a t i v e m e t h o da n dp r e c o n d i t i o n e dao ri t e r a t i v em e t h o do fc o n v e r g e n c e ，a n dd i s c u s s e dt h eh - m a t r i x a n dt h eh - m a t r i xc o m p a r i s o nm a t r i xa ts o ri t e r a t i v em e t h o du n d e rt h ec o n d i t i o n so ft h e c o n v e r g e n c e r a t eo ft h ec o m p a r i s o nt h e o r e m p a r tvi st h eo t h e ro n eo ft h em a i nc o n c l u s i o n so ft h i sa r t i c l e i tm a j o r l ys t u d i e st w o d i f f e r e n tp r e c o n d i t i o n e dao ri t e r a t i v em e t h o do fc o n v e r g e n c ew h e nt h ec o e f f i c i e n tm a t r i xo f 扬州大学硕士学位论文 4 一 l i n e a re q u a t i o n si s n o n s i n g u l a rz - m a t r i x e v e nt h e nt h et w op r e c o n d i t i o n e da o ri t e r a t i v e m e t h o dw i t ht h ec l a s s i c a lao ri t e r a t i v em e t h o df o rt h ec o m p a r i s o nt h e o r e mw i l lb ed i s c u s s e d p a r tv ii sas u m m a r ya n do u t l o o k o ft h i sa r t i c l eh a sd o n eas u m m a r yo fc e r t a i n p r e c o n d i t i o n sf o rt h ei t e r a t i v em e t h o do fo u t l o o k k e yw o r d s ：p r e c o n d i t i o n ，z - m a t r i x ，h - m a t r i x ，m - m a t r i x ，c o n v e r g e n c e 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 3 6 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果 除文中已经标明引用的内容外，本论文不包含其他个人或集体己经发表的研究成果对本文 的研究做出贡献的个人和集体，均已在文中以明确方式标明本声明的法律结果由本人承担 学位论文作者签名： 起舟 签字日期：功圻年占月占 日 j 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关 部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅本人授权扬州大学 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文同时授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务 学位论文作者签名： 是护 蝴飙劢p 占月j 日 导师签名： 签字日期： 彳叩 耄二 需下 赵丹：两类矩阵的预条件迭代法的收敛性 1 引言 在对自然科学与社会科学中的许多实际问题进行数值模拟时，人们最终都归结求解一 个或者一些大型稀疏矩阵的线性方程组比如在结构设计、油气资源探测、数值天气预报、 数值风洞、恒星大气分析与模拟领域，常利用常微分或者偏微分方程作为数学模型而在 常微分方程或偏微分方程的离散求解中，稀疏线性方程组扮演十分重要的角色，因此研究 大型稀疏线性方程组的解法成了人们所关注的焦点 如l a p l a c e 方程 窘+ 雾一o ，加q ， 【u = f ( x ，y ) ，( z ，y ) 弛 这是椭圆型方程的d i r i c h l e t 边值问题，在对这个方程作差分模拟时，利用网格线方法，得 到l a p l a c e 方程的五点差分格式为 云( m + u l _ l , m + 肿1 + u 1 , , _ 1 - 4 u t 。册) = o ， 其中的辨表示差分方程在( ，朋) 处的解在区域内的每一内部结点u ，m ) 上 u = 1 ，2 ，m 一1 ；m = 1 ，2 ，m 1 ) 建立差分方程，由此在区域内部( m 一1 ) 2 个结点上有 ( m 一1 ) 2 个方程定义向量 u = 【u ，l ，1 ，- l ，l ；u i ，2 ，2 ，- 1 2 ；u ，肘小，肼_ 1 l ，- 1 肘一l 】2 ， 这样就得到一个线性方程，其矩阵形式为a u = k ，其中彳是( m 一1 ) 阶方阵， a = b - 1 一i b 这里彳中的块状矩阵曰是( m 一1 ) 阶方阵， b = 4 - i 一1 4 一i bi ib 一1 41 一l 4 扬州大学硕士学位论文 6 一 ，是( m 一1 ) 阶单位方阵，k 向量的元素由在正方形周界的结点上的边值决定 该方程组就是一个大型的稀疏线性方程组，求解这种方程组通常采用迭代法，不同的 迭代法有不同的迭代格式，所以这时迭代格式的收敛性和收敛速度成为判断迭代法好坏的 关键 对于求解大型稀疏线性代数方程组，人们最早发现的迭代法有j a c o b i 迭代法、 g a u s s s e i d e l 迭代法在引入松弛因子和加速因子之后，s o r 迭代法、a o r 迭代法等迭代 方法也出现了，这些迭代法我们统称为基本迭代法它们都是通过构造迭代数列，取数列 的极限得到方程组的精确解这些方法给我们解大型的线性方程组带来了很大的方便 考虑线性方程组 a x = b ，( 1 1 ) 其中a = ( ) 是，z 阶方阵，x ，b 是刀维向量 在用迭代方法解线性方程组时，一般都假设系数矩阵彳是非奇异矩阵，并且都是基于 对矩阵a 做分裂a = m n ，其中m 是非奇异矩阵我们对线性方程组( 1 1 ) 采用的迭代 法是 x 川= m 一1 n x + m b ，尼= 0 ，1 ，2 ，( 1 2 ) 其中m - 1 称为迭代矩阵，它的收敛性直接关系到方程组的求解，而矩阵的收敛性和迭代 矩阵的谱半径( p ( g 一n ) ) 密切相关，当谱半径小于l 时，迭代矩阵就收敛，否则就发散， 而且谱半径越小，迭代矩阵收敛速度就越快 在实际应用中，a 正常分裂成 a = d l u ， ( 1 3 ) 其中d ，一，一u 分别是么的对角、严格下三角和严格上三角矩阵结合矩阵变换总可以 将a 分裂为： a = j 一一u ，( 1 4 ) 其中一三，一u 分别是彳的严格下三角和严格上三角矩阵 在此基础上，几个基本迭代法的迭代矩阵如下所示： g a u s s - f 沈z 迭代法的迭代矩阵为 t = ( ，一三) 一u ，( 1 5 ) 基本的s o r 迭代法的迭代矩阵为 厶= ( ，一c o l ) _ 【( 1 一c o ) i + c o u 】，( 1 6 ) 基本的a o r 迭代法的迭代矩阵为 赵丹：两类矩阵的预条件迭代法的收敛性 7 一 l m ，= ( ，一r l ) - 1 ( 1 一缈) ，+ ( c o r ) l + c o u 】 ( 1 7 ) 但是在实际中，迭代矩阵的收敛性和收敛速度的改善不仅取决于迭代方法和迭代矩阵 中参数的选取，而且同方程组自身的某些变化也是密切相关的 近十多年来，稀疏线性方程组的迭代解法有了很多新发展，特别是预条件矩阵的引入， 通过预条件矩阵的作用加快迭代的收敛性和收敛速度 考虑把线性方程组( 1 1 ) 等价的转化为预条件形式 p a x = p b ，( 1 8 ) 其中p 是非奇异矩阵，则对应的迭代法为 x “1 = 乃x + m p p b ，k = o ，1 ，2 ，刀， ( 1 9 ) 其中乃= m p 1 ，是( 1 8 ) 的迭代矩阵 对于预条件矩阵尸的选取是一个令很多研究者感兴趣的课题1 9 9 7 年，t k o h n o e t a l 在文献 2 】中把a d g u n a w a r d e n s 等人的结果推广到了一般情形，提出了一种预条件 g a u s s - s e i d e l 代 - 法( i m g s ) ，取的预条件矩阵为p = ，+ & ，其中 & = 0 一口l q 2 00 0o 0o o 一a 2 3 o 0 0 o c 乙一1a n 一1 月 0 ( 1 1 0 ) 定义以= ( j + & ) 彳，于是 以= ，一l s l 一( u 一& + & u ) = d 一三一u ， 其中d ，厶u 分别是以的对角矩阵，严格下三角和严格上三角矩阵，则可得i m g s 方法的 迭代矩阵是 兀= ( 历一三) - 1 衫= ( ，一l 一& 三) - 1 ( u 一& + 最+ & u ) ， ( 1 1 1 ) 类似地，预条件a o r 迭代法( 以下简称p a o r 法) 的迭代矩阵是 z ，= ( 万一r z ) 一1 ( 1 一国) 石+ ( 彩一7 ) z + 缈西】= 一m ，口- i 丙，街， ( 1 1 2 ) 其中 砑m ：三( 历- 7 一l ) ，一n 脚：! ( 1 - - c o ) 万+ ( 一y ) z - - ( 1 ) - 0 ， c p珊 预条件s o r 迭代法( 以下简称p s o r 法) 的迭代矩阵是 z = 西一缈z ) 一1 ( 1 一c o ) b + c o u ( 1 1 3 ) 扬州大学硕士学位论文 另一方面，假定彳的对角元均为1 ，即分裂为： 8 一 a = 一三一u ，( 1 1 4 ) 其中一三，一u 分别是a 的严格下三角和任意非负矩阵，是单位矩阵， 则此时基本的a o r 迭代法的迭代矩阵为 。= ( j - y l ) 。1 ( 1 - c o ) + ( c o - ? ) l + c o u 】，( 1 1 5 ) 基本的s o r 迭代法的迭代矩阵为 乞= ( ，一c o l ) 一 ( 1 一c o ) i + c o u 7 】， ( 1 1 6 ) 定义以= ( j + & ) 爿，于是 以= ，一l 一- s 二一( u 7 一& + & u 7 ) = d l u ， 其中万= i s 1 ，一l = 三+ ，一u ：u 一& + s o u 7 ( & ：s + 是) 分别是以的对角矩阵，严格下 三角和任意非负矩阵，则对应的预条件a o r 迭代法( 以下简称u a o r 法) 的迭代矩阵是 三，= ( d z l ) 叫【( 1 一缈) d + ( c o - y ) l + w u 】= m ，毋n ，国，( 1 1 7 ) 1 一， 一 一 一 一， 一，一，一一， 其中 一， i 一一，一， l 一 一， 一， m r ，口= 二( d 一7 l ) ，n ，口= 二【( 1 一c o ) d + ( c o - z ) r c o u 】， c o0 3 对应的预条件s o r 迭代法( 以下简称u s o r 法) 的迭代矩阵是 其中 又定义 三国= ( d c o l ) 叫【( 1 一c o ) d + c o u = m ，n - - #， 一， 一一一， 一，一1 一， 一， l 一一，一， l 一一， m m = 二( d c o l ) ，n 国= 二 ( 1 - w ) d + w u 彩国 如= l l s ，l 一一一s 。+ s f 、) = i 一一o t ， ( 1 1 8 ) 其中三= 三+ 芝，矽7 = u 7 一& + & u 7 + s 1 ( 其中& 三= s + s o ，分别是以的下三角和任意非负 矩阵，则对应的预条件a o r 迭代法( 以下简称u u a o r ) 的迭代矩阵是 z ，= ( x - r z ) 一1 【( 1 一c o ) i + ( c o r ) z + 5 】- 以徊- 1 或，珊， ( 1 1 9 ) 其中 m m ：三( ，一7 z ) ，丙脚：1 1 ( 1 一国) j + ( w - z ) z + u 赵丹：两类矩阵的预条件迭代法的收敛性 9 一 在以上的条件下，本文主要研究线性方程组的系数矩阵彳是日矩阵时，p s o r 及 p a o r 方法的收敛性，还讨论了h 矩阵及口矩阵的比较矩阵在p s o r 迭代法下的收敛速 度的比较然后本文还研究了当线性方程组的系数矩阵彳是非奇异z 矩阵时，u a o r 、 u u a o r 迭代法的收敛性，并讨论了这两种预条件迭代法与基本a o r 迭代法的比较定理， 最后用数值例子来验证文章中的得到的相关结论 扬州大学硕士学位论文 2 预备知识 首先给出本文中常用到的一些矩阵的定义： 定义2 1 设a = ( ) r 脚，如果a u 0 ，i ，j = l ，2 ，刀，则称么是非负的，记为a 0 定义2 2 设a = ( ) r 取”称为是z 一矩阵，若嘞o ，i ，i ，j = 1 ，2 ，刀；若a z 砌， 且满足a 打 o ，汪1 , 2 ，n ，则称彳为一矩阵；若a z ，且有分解式a = s i - b ，b 0 ， 使得j 户( b ) ，则称a 为m 一矩阵 定义2 3 1 记h = ( i 嘞i ) ；设彳c ，如果彳的比较矩阵( 彳) = ( 聊盯) 是m 一矩阵，则 称彳为h 一矩阵，这里= i i ，m l = 一k l ，i 定义2 4 n 羽设么= ( ) ，b = ( ) 是同阶实矩阵，记号么b 表示v i ，j ，吩，a b 表 示v i ，j ，n q b u 下面给出迭代法中矩阵分裂的定义： 定义2 5 口3 1 钔如果彳是n 阶方阵，4 有分裂彳= m 一，其中m 非奇异，如果 p ( m 。n ) 0 ，使得a x 0 ； ( 3 ) 4 的所有主对角元为正 赵丹：两类矩阵的预条件迭代法的收敛性 引理2 9 h 羽设a 是日一矩阵，则p - 1 f ( 彳) 一 引理2 1 0 n 阳设彳，b 是实数域上的刀阶方阵，如果俐a ，则p ) p ( 彳) 引理2 1 1 n 羽设彳= m 一是彳o hm 一分裂，贝, l jp ( m l ) 0 ，使得 m n x = p ( m n ) x 引理2 1 4 n 刀令么一1 0 ，且彳= m i 一i = 鸠一2 是彳的两个弱正则分裂，则不等式 p ( m 1 1 ) 尸( 鸩q 2 ) m ；- 1 ，l 0 引理2 1 5 n 8 1 设彳是z 一矩阵，则a 是非奇异m 一矩阵当且仅当对v 【o ，1 】，其中 i = 1 ，2 ，力一1 ，以= ( ，+ & ) 爿也是非奇异m 一矩阵 扬州大学硕士学位论文 3 已有的相关结论 1 2 1 9 9 7 年，t k o h n o e t a l 在 2 】中把a d g u n a w a r d e n s 等人的结果推广到一般的情形，并 推出了一个新的m g s 法，预条件p = ，+ & ，这里 s 。= 0 一口1 q 2 00 oo o0 0 一a 2 s o o 0 o 一口p 1 一l h o 文中讨论了如果系数矩阵a 是非奇异对角占优z 一阵，那么存在口 0 ，对q o ，口】， ( ，+ & ) 彳也是严格对角占优z 一阵，并给出了最优参数的选择当时文献的一个主要结果 是： 定理3 1 乜1 设彳= ( 吻) 尺删”为对角元素为1 的非奇异对角占优z 一矩阵，且 o j = l 若对任意f o 令a = i - l - u ，和u 分别是严椅下三角和严 j = lj = l 格上三角矩阵，则( ，+ & ) 彳也是严格对角占优z 一矩阵，对0 1 ，0 f 有p ( - 口) l ， 其中t 口= ( i - l - & 三) _ ( v - & + & u ) 在2 0 0 0 年，w e i l i ，w e i w e is u n 在文献【8 】给出了是矩阵时更一般情形，并讨论了当 是矩阵时，预条件g a u s s s e i d e l 迭代法与基本g a u s s s e i d e ，迭代法的比较定理当时其 中的一个主要结论为： 定理3 2 嘲设彳= ( 吩) r 删，a = ，一一巩，其中厶是一个非负矩阵，是严格下 三角矩阵，则 ( a ) 对任意的0 l ，f _ l ，2 ，n - 1 ，如果p ( 丁) 1 ，则p ( 兀) 1 ；在此条件下，有 p ( 一t 口) p ( 丁) p ( ，) 1 如果a 是不可约的，则对任意0 口，l ，i = 1 ，2 ，力一1 ，有 夕( 于口) p ( 丁) ； ( b ) 对任意0 晖 l ，f = l ，2 ，刀一1 ，如果p ( 丁) = 1 ，则户( 兀) = 1 2 0 0 4 年，n i k i 嗍等人又引入了几种预条件子乞，e ，只，最，并讨论了相应的 g a u s s - s e i d e l 方法的收敛性，得到相应的比较定理主要结论是： 赵丹：两类矩阵的预条件迭代法的收敛性 1 3 ( 1 ) 设a 为不可约对角占优z 一矩阵，则4 ，= m m 一卅是g a u s s - s e i d e l 收敛分裂，其中 厶= 只a ( 2 ) 设彳为不可约对角占优z 一矩阵，则厶= m m 一掰和4 = 鸠一m 是g a u s s - s e i d e l 收 敛分裂，其中以= 己彳，4 = 只彳，如果q 斗。q “a i , k , a k ，j ，则p ( 坂- 1 虬) p ( 心_ 1 j ) p ( m 一1 n ) 1 2 0 0 6 年，l i y i n gs u n 在文献 5 中讨论了当线性方程组的系数矩阵是用途比较广泛的 h 一矩阵时，i m g s 迭代法的收敛性，并与其比较矩阵的收敛性比较得* ut 相应的比较定 理，主要结论是： 定理3 3 璐1 设彳= ，一一u 是日一矩阵，其中三是严格上三角矩阵，u 是任意矩阵如 果a = ( ，一三) 一u 是a 的一个日一相容性分裂，且对任意 0 ，l 】，江l ，2 ，n - 1 ，a 的i m g s 迭代法的迭代矩阵是兀= ( ，一三一& 三) 。1 一& + & u ) ，则p ( t d 1 进一步地，如果t 口是 的a 比较矩阵( 彳) 的i m g s 法的迭代矩阵，则p ( l ) p ( t 口) 1 本文第一部分的主要内容就是把上述结论推广到预条件s o r 迭代法和预条件a o r 迭 代法中，得到相应的结论并给出数值例子验证了这个结论 2 0 0 7 年，m e i j u nw u ，l iw a n g ，y o n g z h o n gs o n g 在文献 6 中给出了预条件算子为 p = ，+ & 时的预条件方法，其主要结论为： 定理3 4 呻1 设彳= ( ) 。r 删是非奇异z 一矩阵，并且a = j - l - u ，其中一l ，一u 为 与彳相对应的严格上三角和严格下三角矩阵，令0 y 彩 l ，则 ( 1 ) 对任意的 0 ，1 】，f _ 1 ，2 ，刀一1 ，如果p ( lm ) 1 ，则p ( l m ) 1 ；在此条件下，有 p ( l r ，国) p ( 。彩) 0 的，下面结论有且仅有 一个成立：( a ) 如果( m ) 1 ，则p 犯m ) l 且p ( l m ) p ( l r m ) 1 本文的另一个主要部分就是适当改变上述结论中的条件，并选择两种不同的的迭代矩 阵，得到相应的结论，并用简单的数值例子进行了验证，从而使已有的结论得到了一定的 推广和改进 2 0 0 8 年，j a eh e o ny u n ，s a n gw o o kk i m 在文献q b 1 9 1 讨论了不可约三一矩阵的两种预条 件a o r 迭代法的收敛性，其中预条件算子 扬州大学硕士学位论文 丑= i + 00 0 - a 2 1 0 0 一1 0 0 一l 0 0 ，昱= i + 0 一0 1 2 0 00 一a 2 3 ooo oo0 o 0 一一1 。n o 得到了这样的结论：当4 是一矩阵的时候，在一定的条件假设下，预条件a o r 法的收敛 性和基本迭代法的收敛性相同 赵丹：两类矩阵的预条件迭代法的收敛性 4 关于h 矩阵的预条件s o r 、a o r 法的收敛性分析 4 1 收敛性定理 本节我们主要讨论关于日一矩阵的p s o r 法的收敛性定理及与它的比较矩阵的p s o r 法之间的比较定理，接着讨论了一矩阵的p a o r 法的收敛性 定理4 1 1 设彳= ，一三一u 是h 一矩阵，其中，l ，u 分别是单位矩阵，严格下三角和 上三角矩阵，设a = ( j 一) 一u 是h 一相容性分裂，a 的p s o r 迭代法的迭代矩阵为 z 国= ( 万一c o s ) 一1 ( 1 一c o ) b 一彩万】，其中吒【o ，1 ，i = 1 ，2 ，刀，0 缈1 ，则p ( z 国) o ，i = 1 ，2 ，刀 扬州大学硕士学位论文 1 6 当q o ，1 】，0 0 由于( 砑m ) 是m 一矩阵，有砑m 是一矩阵， 所以由引理2 9 得，i 砺i - 1 ( 砺) ( 4 3 ) 又因为 ( 砑) = 去 ，一国( 陋+ & u i ) ，- - - 三国y 一国( h + i & 忆i ) 】， 所以m a 缈( 砑) ，而也，( 面) 是m 一矩阵，故砑口2 ( 砑。) ( 4 4 ) 结合( 4 3 ) 和( 4 4 ) 式知，i 砑埘l _ l 砑 ( 4 5 ) 另一方面，因为= - a u ( i j ) ，所以当o 1 ，o c o 1 时，l u s 。= l u l i & l ，则 得到 彩( 阿口i - n 一珊) = l ( 1 一缈) ，+ o ( u s o + s 口u ) 一【( 1 一r o ) i + c o ( u i & i + i & | i u | 】 ( 1 一缈) ，+ 彩l u 一& + s 口u - ( 1 - c o ) 一c o ( u i s o + s o lu i 国j u 一& i + 国l & u l _ 缈( i u l _ l 最i ) 一i & i i u i = 国( 1 & u l 1 叉1 1 u i ) 0 ， 所以j _ 。i n 一 ( 4 6 ) 根据( 4 5 ) 和( 4 6 ) 式及引理2 1 0 ，则有p ( i z 缈i ) p ( z a ) 又因为( a ) 是m 一矩阵，由引理2 1 1 知p ( z m ) 1 ，这样就证到了结论 口 推论4 1 2 设彳= ，一l u 是日一矩阵，其中i ，l ，u 分别是单位矩阵，严格下三角和 严格上三角矩阵，设a = ( ，一三) 一u 是h 一相容性分裂，a 的i m g s 迭代法的迭代矩阵为 瓦= ( 历一z ) 一l u ，其中qe o ，1 】，i = 1 ，2 ，力，则p ( 疋) 。， 嘞h - - 1 0 ( 江l ，2 ，力一1 ) 蚓，：+ a l l + 。h l ，i e i a , 州r j o ， j = i + 2 乃一l - ii 嘞i 乃一nf 嘞i 。+ i + 。i 。 j = lj = t + 2 ，= l 1 ，i = 1 ，2 ，n - - 1 口 引理4 1 4 设彳= ( 吩) 是日一矩阵，彰定义同引理4 1 3 ，则 o ，叫】时，以也是h 一 矩阵 证明：设以= ( 瓦) ，由以= ( ，+ s ：) 彳知，一a g = 吻一+ l a i ，+ ，l j ：, 1 刀 o ， j = l j i + l 若1 o 结合引理2 8 得到( 以) 是非奇异m 一矩阵，所以以是日- 矩阵 口 引理4 1 5 设0 ，国1 ，国0 ，则以= m m 一m 是h 一相容性分裂，即有 ( 以) = ( 瓦。国) 一陬1 证明：设以= ( 瓦) ，( 砺m ) 一阿胂l = ( 6 ：c ) ，若f = ， 则虿= l l 一a i i + 。口f + 小 = 去 1 1 一嘭嘞+ 。q + i _ ( 1 一国) i l 一q m q + | 】= 1 1 一+ 。q 埘i ， 若f ，则吻= 则i j 时， i _ ，时， 一l 吻一o f i a + 。，| ( 面m ) 一陆弓( 五一y z ) 一扣刊西如训z + 国西i ， 6 ：f = 丢 一1 7 ( 嘞一口，+ 。口f + 。，) i _ 一，) l _ 吻+ + 。哆州i = 一l 锡一+ 。哆州i ， 赵丹：两类矩阵的预条件迭代法的收敛性 2 去( o 一缈1 一q w i ) = 一i 嘞一哆q m ，l ， 因此( 以) = ( 砺脚) - im l ，以= 一m r , 埘- 一n m 是一相容性分裂 口 定理4 1 6 设彳= ( 吩) 是日一矩阵，彰定义同引理4 1 3 ，则 o ，口7 】，o 7 国1 ， 国0 时，n 有p ( 一l ，口) 1 证明：由 1 ，引理3 3 】，引理4 1 4 ，引理4 1 5 ，结论即可得 口 推论4 1 7 设4 = ( ) 是日一矩阵，口；定义同引理4 1 3 ，则口，【o ，口；】，o 国1 时， 则有p ( z ) 1 ，其中z 是对应的p s o r 迭代法的迭代矩阵 推论4 1 8 设彳= ( 嘞) 是日一矩阵，彰定义同引理4 1 3 ，则【o ，耐】时，则有p ( 力 1 ， 其中了是对应的预条件j o r 迭代法的迭代矩阵 4 2 数值例子 例4 2 1 设线性方程组a x = b 中， a = l10 0 2 51o 7 5 o0 1 2 51 0oo 0 5 0o0 oo 02 5 1 1 2 50 lo 1 0 11 经验证彳是日一矩阵，则取不同的，国，得到的预条件迭代法的谱半径为： 口国 p ( 出)p ( ) 1 缈= 0 2 o 9 0 1 40 9 0 1 4 够2i 二 缈= 0 5 0 7 2 1 90 7 2 1 9 = 0 8 0 4 7 9 30 4 7 9 8 缈= 1 0 2 3 0 30 2 3 8 3 q = 1 ( - 0 = 0 2 0 2 3 8 30 2 3 8 3 c o = 0 5 0 8 8 4 70 8 8 4 7 c o = 0 8 0 6 6 5 90 6 6 5 9 国= 1 0 3 7 0 80 3 7 0 8 扬州大学硕士学位论文 从上表可以看出，p ( z 口) p ( 三。) 1 ，即验证了定理4 1 1 的结论 同样对矩阵彳取不同的，7 ，缈，得到预条件迭代法的谱半径p ( l 肿) 为： 口 ( 7 ，彩) p ( 三m ) 1 ( o 4 ，0 9 ) 0 5 2 0 4 q 2 i z ( 0 2 ，0 8 ) 0 6 0 5 4 ( o 5 ，0 6 ) 0 6 6 6 3 = 1 ( 0 4 ，0 9 ) 0 4 2 5 6 ( o 2 ，0 8 ) 0 5 3 0 2 ( 0 5 ，0