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

摘要 摘要 随着计算机的发展，在许多实际应用和数学研究中，经常遇到求解线性方程 组的问题，而数值代数己经成为处理这些问题的强大工具。在本文中，主要研究 了对线性方程组的几种预条件迭代解法。使用预条件矩阵来加速迭代方法的收敛 性是通常所采用的方法，预条件迭代法对于解决系数矩阵是大型稀疏矩阵的情况 有较好的效果。 证明了当线性方程组的系数矩阵爿为不可约矩阵时的预条件a o r 方法，并 且证明了其收敛性，最后用数值试验验证所提出的理论结果。当选取最优参数时， 通过数值试验可看出我们的方法所得迭代矩阵的谱半径比小。 提出以s s o r 多分裂作为内分裂的松弛不定常二级多分裂法，然后研究了所提 出的方法在求解当系数矩阵为日矩阵的线性系统的收敛性，最后具体给出此方法 收敛性的论证及其应用。通过具体的数据实例，我们可以看出，当选取一组近似 最优参数时，所提出的方法的收敛速度要比松弛s s o r 多分裂法快。 关键词：l 矩阵，h 矩阵，m 矩阵，预条件a o r 法，s s o r 多分裂 a b s t r a c t 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 e r s ，n u m e r i c a la n a l y s i sc o n c e r n e dw i t ht h e s o l u t i o no fl i n e a rs y s t e m so fe q u a t i o n si sa l w a y su s e di nt h ep r a c t i c a la n dm a t h e m a t i c p r o b l e m s f o ral i n e a rs y s t e m , w es t u d yt h es e v e r a lp r e c o n d i t i o n i n gm e t h o di nt h i s p a p e r i ti sq u i t ec o l n m o nt ou s ep r e c o n d i t i o n i n gt oa c c e l e r a t et h ec o n v e r g e n c eo fa b a s i ci t e r a t i v es c h e m ew h i c hi sv e r yu s e f u lt os o l v et h el a r g es p a r s ec o e f f i c i e n tm a t r i x w ei m p r o v et h ep r e c o n d i t i o n e da o ri t e r a t i v es c h e m ef o ri r r e d u c i b l el m a t r i c e s c o n s i d e r e da n dt h e nw ep r o v et h ec o n v e r g e n c eo fo u rm e t h o d l a s t l y , n u m e r i c a l e x p e r i m e n t s t oi l l u s t r a t et h et h e o r e t i c a lr e s u l t sa lep r 0 v i d e d w h e nc h o o s i n gt h e a p p r o x i m a t e l yo p t i m a lp a r a m e t e r s , o u rs c h e m eh a ss m a l ls p e 脱r a lr a d i io ft h ei t e r a t i v e m a t r i c e st h a nt h es p e c t r a lr a d i io fa o ri t e r a t i v es c h e m e , w h i c hi ss h o w nt h r o u g h n u m e r i c a le x a m p l e s w ep r e s e n tt h er e l a x e dn o n s t a t i o n a r yt w o - s t a g em u l t i s p l i t t i n gm e t h o du s i n ga n o u t e rs p l i t t i n ga n dt h es s o rm u l t i s p l i t t i n ga si n n e rs p l i t t i n g t h e n , w es t u d yt h e c o n v e r g e n c eo ft h ep r o p o s e dm e t h o df o rs o l v i n gt h el i n e a rs y s t e mw h o s ec o e f f i c i e n t m a t r i xi sf i nh - m a r x a tl a s t ，w eg i v et h es p e c i f i cc o n v e r g e n c eo ft h i sm e t h o do f a r g u m e n t a t i o na n di t sa p p l i c a t i o n c h o s e nt h ea p p r o x i m a t e l yo p t i m a lp a r a m e t e r s ，t h e p r o p o s e dm e t h o dg e t sf a s t e rc o n v e r g e n tr a t et h a nt h ec o n v e r g e n tr a t eo fr e l a x e ds s o r m u l t i s p l i t t i n gm e t h o d , w h i c hw i l lb es h o w nt h r o u g hn u m e r i c a le x a m p l e k e y w o r d s l - m a t r i x ，h - m a t r i x ，m - m a t r i x ，p r e c o n d i t i o n e da o rm e t h o d s s o r m u l t i s p l i t t i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：鱼墨差日期： 砂歹年y 月刁日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 。 签名：自三男 导师签名：气渺 日期：力叨芬年岁月z 7 日 第一章绪论 1 1 引言 第一章绪论 求解线性方程组是数值线性代数的一个基本问题，即给定a c 删“，b c ”， 寻找解向量石c ”使得a x = b 。很多科学问题的解决都需要解这样一个线性方程 组，如力学、电磁学、经济学、数学物理以及数值代数本身等等。解线性方程组 的传统方法是用g a u s s i a n 消元法，假设系数矩阵彳是一个以以的非退化阵，这样用 g a u s s i a n 消元直接解法的运算量是o ( n 3 ) 。许多微分方程经过适当差分或有限元离 散所产生的线性代数方程组的系数矩阵，不仅具有大型稀疏的特性，而且常常呈 现出规则的分块结果。当1 1 很大且么稀疏时，用直接法就很不划算，而且需要很大 的存储空间，人们开始考虑和研究用迭代法求方程组a x = b 的近似解，即用某种极 限过程去逐渐逼近精确解，并发展了许多非常有效的迭代方法，常见的如j a c o b i 方 法、g a u s s s e i d e l 方法、s o r 方法、s s o r 方法，这几种迭代方法是最常用的一阶线 性定常迭代法。 即若系数矩阵彳的一个分裂：a = m n ，m 为可逆矩阵，线性方程组 彳工= b ( m 一柳工= bj m x = n x + b = 工= m 一1 k + m 一1 b 得到迭代方法的一般公式： x ( + 1 = 肋c ( ) + d 其中：h = m n ，d = m b ，h 称为迭代矩阵，它的收敛性直接关系到方程组的 求解，收敛性和迭代矩阵m 。1 的谱半径有关，谱半径小于1 时就收敛，否则就发 散，而且谱半径越小，迭代矩阵收敛速度就越快。 若假设彳是刀以阶矩阵，且a = i l u ，一l 和一u 分别是的严格下三角和 严格上三角部分，则经典的g a u s s s e i d e l 迭代法的迭代矩阵为h = ( ，一三) u 。迭代 法解线性方程组时都假设矩阵么是非奇异矩阵，当矩阵么是奇异矩阵时，可以通 过变换把a x = b 变为一个和它同解的新的系数矩阵为非奇异的线性方程组。 为改善迭代法的收敛性和收敛速度，h a d j i d i o m s t l l 于1 9 7 8 年提出一种快速超松 弛迭代法( 简称a o r 迭代法) ，它含有两个参数彩，f ，当时彩= f ，这种方法就变 1 电子科技大学硕士学位论文 为逐次超松弛迭代法( 简称s o r 迭代法) ；随着并行计算机的发展，1 9 8 3 年m i s i r l i s 1 提出一种解线性方程组的方法，称为并行j a c o b i 型方法，它的突出优点是适合大型 并行机的计算。胡家赣 1 在1 9 9 2 年提出了两参并行的j a c o b i 型方法( 简称2 p p j 型方 法) ，使m i s i r l i s 提出的方法成为2 p p j 型方法的特例。另外，结合实际的需要，还产 生了一些如s s o r 型迭代法、s a o r 型迭代法、p s d 型迭代法等一系列迭代方法， 目的都在于改善迭代矩阵的收敛性和收敛的速度。 1 2 常见的预条件方法 在实际的计算过程中，收敛性的改善不仅取决于迭代方法以及迭代矩阵中参 数的选取，而且同方程组自身的某些变化也密切相关，例如可以对方程组两边左 乘一个非奇异矩阵p ( 预处理) 。通过这种技巧，线性方程组a x = b 等价变为 p a x = p b( 1 - 1 ) 如果剐还有分裂黝= m 一m ，那么( 卜1 ) 对应的迭代格式为 x m = m 二1 n a x + m j l p b ， k = 0 , 1 ， ( 卜2 ) 式( 1 - 1 ) 称为预条件方法。1 9 9 1 年，g u n a w a r d e n a 等【嘲提出了修改的g a u e s s s e i d e l 方法( 简称m g s 方法) 如下：令( 1 - 2 ) 式中的p = 1 4 - s ，其中 s = 0 一a 1 2 0 0 0 一a 2 3 00o o0o o o 一a 一1 j l o 文献【4 】证明了该预条件用于g a u e s s s e i d e l 迭代法的收敛性。为了进一步研究m g s 方法并改善其收敛速度，1 9 9 7 年k o h n o 等吲利用带有n - 1 个参数的预条件矩阵 p = i + s ，其却 s = 0 一口i a l 2 oo 0o o o o 。0 1 2 a 2 3 0 o 0 o 一口n 一1 a 月一1 j l o 并采用与文献 4 】相同的迭代格式( 只把s 改成& ) ，将文献【4 】的结果进行了推广。 2 第一章绪论 随后文献 6 】将文献 5 】中的预条件方法应用到日- 矩阵类。国内外很多学者对于这类 方法都进行了进一步的研究，如g a o r 迭代法忉，并且给出了当a 为日矩阵时的 一些收敛性结论。 本文的第二章将考虑用如下两种预条件矩阵形式： p = p s i和p = p s 2 这里= ，+ 墨，& = ，+ s ：，其中 墨= o0 0 0 o 0 0 一口n 口 l 0 0 s 2 = 0 一口l 口1 2 0 o oo oo 0 a 2 a 2 3 o 0 o 0 一口h l a 月一1 h 0 并讨论了该预条件用于a o r 迭代法的收敛性。当选取不同的参数值时，通过实例 可以看出，我们所提出的预条件迭代矩阵的谱半径要比文献中所提到的预条件迭 代矩阵谱半径小的多，在一定程度上改进了迭代法的收敛速度。 若a = m 一是彳的一个分裂，则三角阵( m 。，m ，e k ) ，尼= 1 ，称为么的一 ， 个多分裂，b 是非负矩阵，并且臣= ，。由此多分裂，我们得到了求解线性系 k - i 统a x = b 的多分裂法，b a i ，s u n 和w a n g t s l 在统一的算法框架下建立了矩阵多分裂 迭代算法的收敛理论。多分裂法首先由0 l e a f y 和w h i t e 例所提出，后来又被许多 学者 1 0 - - 1 2 , 1 3 , 1 4 l 】进行了进一步的研究。多分裂法被广泛的应用于二级分裂迭代法中， 其中i l u t ”1 多分裂法在文献 1 6 】里对于系数矩阵为厚矩阵或胁矩阵等的收敛性以 及由此做出的预条件矩阵已做了深入研究和讨论，并得到了较好的收敛效果，但 还有许多分裂法仍可用于二级迭代法中，及其他一些特殊类型的矩阵的多分裂法 还可做进一步讨论。本文第三章将考虑当系数矩阵为犀矩阵时用s s o r 多分裂作 为内分裂的二级多分裂法的预条件法，并讨论了该预条件迭代法的收敛性，并与 s s o r 多分裂法进行了比较，数值表明我们的算法要优于s s o r 多分裂法。 3 电子科技大学硕士学位论文 2 1 概论 第二章预条件a o r 迭代法 在第一章中已经提到，当线性方程组a x = b 的系数矩阵彳是大型稀疏矩阵或具 有某些特殊性质时，对方程组的系数矩阵彳进行预条件处理呻1 是一种不但常用而 且较为有效的方法。其基本思想就是寻找一个特殊的可逆矩阵p ，左乘方程组 d r = b 后，使得矩阵p a 相应分裂的迭代矩阵的谱半径较小。近年有好多学者对系 数矩阵为特殊情形进行了深入的研究【1 8 1 。 在本章中，我们考虑当线性方程组的系数矩阵a 为不可约矩阵时，预条件 迭代法的构造及其具体应用。作者主要构造了二种预条件矩阵，把这二种预条件 矩阵应用到a o r 迭代法中，比较在此迭代法中的作用，还讨论了预条件a o r 迭 代法收敛性同预条件矩阵的参数之间关系。 考虑线性方程组 a x = b ( 2 - 1 ) 其中x ，b r ”，a = ( ) 舢在实际应用中，g a u s s 消去法及c h o l e s k y 分解法是常见 的直接解法，但当系数矩阵a 具有某些特殊性质时，这时迭代法具有了相当的优 势，相比之下，直接解法往往很不实用，效果不佳。 上面我们己就相关内容的展开作了铺垫性的说明，对于应具备的理论背景作 了扼要的介绍，下面我们就系数矩阵为不可约矩阵的线性方程组预条件矩阵的 选取作详细的论证。 为了更好的求解线性方程组a x = b ，这里a = ( a u ) 删。r 联“是非奇异矩阵，人 们常用某些非奇异矩阵p 对( 1 1 ) 式进行预处理，即考虑方程组 p a x = p b 这里p 称为预条件矩阵。1 9 9 1 年， g a u e s s s e i d e l 方法( 简称m g s 方法) 如下： 4 g u n a w a r d e n a 等【4 1 提出了修改的 令上式中的p = i + s ，其中 第二章预条件a o r 迭代法 s = 0 一a 1 2 0 00 一a 2 3 o00 ooo 0 0 一a 一i o 文献 4 】证明了该预条件用于g a u e s s s e i d e l 迭代法的收敛性。为了进一步研究m g s 方法并改善其收敛速度，1 9 9 7 年k o h n o 等嘲利用带有n 1 个参数的预条件矩阵 p = j + & ，其中 s 。= 0 一a 1 2 o0 0o 0o 0 & 2 a 2 3 o o o o 一口p i a n i ” o 并采用与文献 4 相同的迭代格式( 只把s 改成& ) ，将文献 4 】的结果进行了推广。 随后文献 6 】将文献 5 】中的预条件方法应用到日矩阵类。 本文则考虑用如下两种预条件矩阵形式： p = 足 和 尸= & 这里p s , = i + s l ，足= ，+ s 2 ，其中 墨= oo 0 一口2 a 2 l 0 0 一口3 a 3 l 0 0 一口n a 们0 0 s 2 = 0 一口l a l 2 oo o0 0o 并讨论了该预条件用于a o r 迭代法的收敛性。 2 2 预备知识 o a 2 a 2 3 o o o o 一口n i a n 一1 n 0 考虑线性方程组a x = b ，这里彳= ( 嘞) 脚r n x 是非奇异矩阵，我们考虑用迭 代法求解此方程组。对于矩阵彳的一个分裂彳= m - n ，其中l m l 0 ，则有求解线 性方程组( 2 - 1 ) 的基本迭代法为： x + 1 = m 一1 n x + m b k = 0 , 1 ， 不失一般性，设矩阵么的一个分裂形式为a = d l u ，这里d ，工和一u 分别是 5 一 电子科技大学硕士学位论文 二_ 二- _ 二二一一 彳的对角、严格下三角和严格上三角矩阵。不妨设d = i ，则定义彳的a o r 迭代矩 阵为： s=三妻：至；习s：=瞎一口12一口”；一口。喜。一，。 6 第二章预条件a o r 迭代法 令j = b ：彳和s 2 l = d + r ，其中d + 是对角矩阵，f 是严格下三角矩阵，则 我们可得到： a = ( j + s 2 ) ( ，一l 一= i 一三一u + 是一s 2 u = d l u ( 2 - 7 ) 其中西= j d ，云= 三+ f ，u 一= u s 2 + s 2 u 。 若我们将a o r 迭代法用在预条件线性系统( 2 4 ) ，则我们得到预处理a o r 迭代法，其迭代矩阵为： 霉珊= ( 6 一应) 一1 ( ( 1 一c o ) 1 5 + ( o j r ) l + o u )老i e = g ( 2 8 ) 或 霉珊= ( 万一r z ) - 1 ( ( 1 一) 万+ ( 缈一r ) l - + o u ) ，若p = 只， ( 2 9 ) 当国= ，时，则( 预条件) a o r 迭代法就是( 预条件) s o r 迭代法f 5 1 。对彩= ，及 迭代矩阵乙，元，己，由( 2 3 ) ，( 2 8 ) ，( 2 9 ) 可得到相应的迭代矩阵乙，瓦， 即： 乙= ( ，一儿) - 1 ( ( 1 一缈) ，+ c o u ) ( 2 1 0 ) l = ( d 一儿) - 1 ( ( 1 一国) d + o j u ) ( 2 - 1 1 ) 乙= ( d 一儿) - 1 ( ( 1 一r o ) d + 缈u ) ( 2 - 1 2 ) 2 2 1 本章中用到的定义 定义2 2 1 1 2 0 1 设a = ( a f ) 为t l l 的矩阵，若口玎o ( i j ) ，则我们称之为z - 矩阵。 定义2 2 1 2 【2 1 1 记所有n n 实矩阵a = 0 甜) 所组成的集合为r 雕露，r “的子集 为z 艄”= 即= 0 ) 陋e r i x n ，o , ( v i ，j f ，i ) ) 。当a z “”，且口驴 o ( v 0 成立时， 称矩阵彳为一矩阵。 定义2 2 1 3 嗽1 设彳= ( 口 f ) ，b = ( ) 是同阶矩阵，v i ，嘞，则称 a b ；若v f ，j ，a 盯 ，则称a b 。 2 2 2 本章中用到的定理 定理2 2 2 1 【2 0 1 设彳为r t 阶非负不可约方阵，则 ( a ) 以彳) 为a 的一个j 下特征值； ( b ) a 对于p ( a ) ，相应地存在一个正的特征向量x 0 ； ( c ) p ( a ) 为么的一个简单特征值。 7 电子科技大学硕士学位论文 定理2 2 2 2 f 2 3 】设彳为刀阶非负方阵，则有如下结论成立： ( a ) 若存在一非负向量x ，x 0 ，使得a x 肛，则有p ( a ) ； ( b ) 存在一正向量x ，使得a x 0 ，i = 2 , 3 9 oo ，万，使得 地 i 布t n l 一8 设( 2 3 ) f i = 1 1 ( 2 8 ) 定义的矩阵分别为乙和兑。若o ，c o - 1 o ，r 1 ) ，则有： ( a ) 若p ( t ) p ( z 甜) 。 证明 由( 2 3 ) ，乇可表示为 乙= ( 1 一彩) j + 缈( 1 一r ) l + t o u + h ( 2 1 3 ) 这里日是一个非负矩阵。由于彳是一个矩阵，故己和u 也是非负的。由( 2 1 3 ) 可得z 。0 。由于a ( 2 ：，l ，2 ：刀) 是不可约矩阵，对所有的f ，都有a i ，a n = o ，所 以可得矩阵彳也是不可约的。由于国0 ，1 ，彳是不可约矩阵，得缈( 1 一r ) l + 缈u 是不可约矩阵。故由( 2 一1 3 ) 得乙是不可约矩阵。由定理2 2 2 1 ，则存在一个正向 量z ，使得t r t a x l x ，这里允= p ( 乇) 。由于是一个严格下三角矩阵，故墨三= 0 。 由乙石= 2 x ，我们很容易的可得： ( ( 1 一彩) ，+ ( c o r ) l + c o u ) x = 五( ，一r l ) x t o s l u x = ( 见+ 缈一1 ) s l x( 2 - 1 4 ) 1 ：1 ：1 ( 2 8 ) 和( 2 - 14 ) 有： z 协x 一触= ( d 一儿) 叫( ( 1 一国) d + ( 彩一r ) l + c o u 一2 ( d r l ) ) x = ( d 一兀) _ 1 ( ( 1 一珊一2 ) d + ( c o 一，+ a r ) l + c o u ) x = ( d 一兀) q ( ( 缈+ 名- 1 ) d 。+ ( 彩一，+ 知) ( 三一s 1 ) + 国u 。) z 8 q l i 翟 第二章预条件a o r 迭代法 = ( d 一厄) 叫( ( z 1 ) d 。+ ( z 一1 ) 以+ ( ，一c o - 五r ) s , + c o s i u ) x = ( d r l ) - 1 ( ( 允一1 ) ( d + r l ) + ( 一办+ 允+ ，- 1 ) s 1 ) x = ( 旯一1 ) ( d 一厄) - 1 ( d + 以+ ( 1 一，) s 1 ) 石( 2 - 1 5 ) 由于o 0 ，j r 2 r 川 0 ，z 2 r ”q 0 是一非负向量。由( 2 1 5 ) - ( 2 1 8 ) ，得 艺z 一触= ( 力一1 ) z ，故 ( 1 一缈) 而+ 互2 x 2 = 旯 正2 屯一兄砭= ( a 一1 ) z 2 当见 1 时，由( 2 2 0 ) ，我们可得： 互：x 2 他 及 哎屯触： 由式( 2 2 0 ) 及定理2 2 2 2 ，有户( 艺) 见。由于o 1 一缈 力= p ( 乃m ) 当五 0 ，由( 2 - 2 2 ) 式及定理2 2 2 2 得 p ( 疋2 ) o ，有盂2 屯 0 。由( 2 1 9 ) ，( 1 一c o ) x i 2 x l ，及 l 一国 允 ( 2 - 2 4 ) 由于p ( 乙) = m a x ( 1 一c o ) ，p ( 疋2 ) ) ，由( 2 - 2 3 ) 及( 2 2 4 ) 得p ( 乃。) 0 ，f = 2 , 3 ，n ，使得 l0 口f 口l f 口n 1扯 f 【a al = 0一i l 一 设( 2 - 1 0 ) f q ( 2 1 1 ) 所定义的矩阵分别为兄和艺。若o 缈 1 ，则有： ( 1 ) 若夕( 乙) p ( 兀) 。 注3 3 若，= 彩= 1 时，则( 预条件) a o r 法就是我们所说的( 预条件) g a u s s s e i d e l 法。x c f f ：r = 0 9 = l ，由于在定理2 3 1 的证明中矩阵乙和夏：不一定可 约，故定理2 3 1 就不一定成立。因此，当，= c o = 1 时，推论2 3 2 就不一定成立。 在今后的工作中我们会进一步讨论当，= 缈= l 时推论2 3 2 成立的条件。 引理2 3 4 设a = ( a 盯) r 脒”是一个矩阵，假设存在一个非空集 厂c 2 = 1 ，2 ，3 ，n - 1 ) 和实参数 0 ，f = 2 ，3 ，n ，使得对所有的f 2 ，都有 口件q n 口m ， l 。设( 2 - 3 ) 和( 2 9 ) 定义的矩阵分别为乙和乇。如果 0 ，彩l ( c o o ，1 ) ，且彳是不可约的，对所有的i y ，令a m i = 0 ，则有乙 和元是非负不可约的。 证明 由已知对所有的f 7 ，a + l = 0 ，a 是不可约的，故彳= i - l u 是不 可约的。因此由( 2 1 3 ) ，咒是非负不可约矩阵。令： a = 最a = ( i + s 2 ) 么= d l u 这里万，三及扩为( 2 7 ) 式中所定义的矩阵。由于a 是矩阵，并且对所有的i n 2 ， 有口川a 讲，口州，j 0 ， i = 2 ，3 ，n ，使得对所有的i 2 ，都有口“l a “+ i a f + 1 f l 。设( 2 3 ) 和( 2 9 ) 所定义的 矩阵分别为乙和瓦。如果o ，彩l ( o j o ，1 ) ，且彳是不可约的，对所有的 i 厂，令口“+ l = 0 ，贝0 有： ( 1 ) 若p ( 乙) p ( 乙) 。 证明 由引理2 3 4 ，是非负不可约矩阵。由定理2 2 2 1 得，存在一个正 的向量x 0 ，使得乙x = a x ，这里名= 夕( r 彳) 。由x = 缸，我们很容易得到： ( ( 1 一t o ) i + ( t o - r ) l + ( o u ) x = 允( j r l ) x ( ( 五+ c o 一1 ) s 2 + ( ，一缈一办) s 2 l ) x = c o s 2 u x ( 2 2 6 ) 由( 2 9 ) 和( 2 2 6 ) 得： 霉二x 一触= ( 五一厄) - 1 ( ( 1 一缈) 万+ ( 国一r ) e + c o 可一允( 万一r e ) ) x = ( d i 一厄) 一1 ( ( 1 一c o 一允) 万+ ( 国一r + 2 r ) i , + t o f f ) x = ( 万一厄) 一1 ( ( 彩+ 旯一1 ) d + ( 缈一r + g r ) e + c o ( s 2 u 一是) ) x = ( 万一厄) 一1 ( ( 缈+ 五一1 ) ( d + s 2 ) + ( 缈一r + t r ) ( e s 2 ) 一c o s 2 ) x = ( 万一厄) 一1 ( ( 缈+ 允一1 ) d + g t 一1 ) 是一( 国一r + a r ) d + ) x = ( d 一厄) 1 ( ( 一办+ 兄+ ，- 1 ) d + ( 力- 1 ) s 2 ) z = ( a - 1 ) ( d r z ) 叫( ( 1 - r ) d + s 2 ) x ( 2 2 7 ) 由于o 1 时，由定理2 3 1 和定理2 3 3 ，我们可直接相应的得到z 。z = 缸及 t r , , x _ x x ( 霉。x 缸) 。当允 1 时，由( 2 2 9 ) 得t r 。x 触和死z 触。由引理2 3 3 可知霉。是不可约的，故由定理2 2 2 2 可得p ( 元) 0 ，f = 2 ，3 ，行， 使得对所有的f 2 ，都有口f + l 口“+ 。口， l 。设( 2 - 1 0 ) 禾1 ( 2 一1 2 ) 所定义的矩阵分别为l 和乏。如果0 缈 1 ，且彳是不可约的，对所有的f y ，都有口“= 0 成立，则有： ( 1 ) 若p ( 乙) p ( 兀) 。 注2 3 7 若，= 缈= 1 时，由于在定理2 3 4 的证明中矩阵乙和乙不一定可约， 故定理2 3 4 就不一定成立。因此，当，= 缈= 1 时，推论2 3 2 就不一定成立。在今 后的工作中我们会进一步讨论当，= 缈= 1 时推论2 3 6 成立的条件。 2 4 数值实验 在这一节中我们给出具体的数值实例来验证第三部分的结论。当我们选取一 组参数时，用我们的方法所得的迭代矩阵的谱半径比文献【1 9 】中的结果小，说明我 们的方法要优于文献 1 9 】中的方法。所有的数值实验都是在m a t l a b7 1 上实现 的。为简单期间，我们假设所有的参数口，都是相等的，即令口= 口，i = 2 ，3 ，甩。 当口= 1 时，用p ( 霉。) 和p ( 瓦) 表示相应迭代法的迭代矩阵的谱半径。当我们选取 最优参数口( ，和口) ，用( 乇) 和( 霉。) 表示相应迭代法的迭代矩阵的谱半 径。 例2 4 1 考虑一个4 4 阶矩阵彳，形式如下： 1 2 第二章预条件a o r 迭代法 a = 1 一o 3 0 一o 3 o l o 3 0 o o 3 1 0 3 一o 3 0 3 一o 3 1 很容易验证矩阵么满足定理2 3 1 和定理2 3 5 的条件，这里= 4 ) c l 和 7 = 2 ，3 ) cn 2 。当迭代矩阵的谱半径越小，其收敛速度越快，在表2 - l 和表2 2 中 我们比较了例2 4 1 的迭代矩阵的谱半径。 ，0 9p ( 乙)以乙)烈乙) p o p , ( 乃m )t 气)( 乙)口( ) 0 9l0 3 4 0 6 0 2 9 3 70 2 3 3 10 1 8 8 14 5o 1 5 5 72 3 o 810 3 8 5 20 3 3 7 70 2 8 4 40 2 2 9 04 0o 2 l l l2 1 0 7l0 4 2 0 10 3 7 2 l 0 3 2 4 00 2 5 9 9 3 7 0 2 5 4 62 o o 7o 80 5 3 6 10 4 9 7 70 4 5 9 20 3 6 6 27 20 3 6 7 94 5 0 6o 80 5 5 9 30 5 2 0 40 4 8 5 40 3 8 5 06 o0 3 9 5 23 7 o 5o 80 5 7 9 30 5 4 0 00 5 0 7 9 0 3 9 9 8 5 4o 4 2 1 43 3 0 5o 60 6 8 4 50 6 5 5 00 6 3 0 90 5 2 9 78 40 5 5 6 25 5 0 4o 60 6 9 7 60 6 6 8 0o 6 4 5 80 5 3 7 27 20 5 7 0 64 8 0 3o 60 7 0 9 30 6 7 9 5 0 6 5 9 00 5 4 2 56 50 5 8 5 54 2 o 3o 40 8 0 6 20 7 8 6 30 7 7 2 70 6 8 4 49 o0 7 2 0 95 7 o 2o 4o 8 1 3 30 7 9 3 30 7 8 0 70 6 8 5 57 9o 7 2 8 45 6 o 1o 40 8 1 9 70 7 9 9 7 0 7 8 7 90 6 8 5 27 1o 7 3 6 44 9 例2 4 2 考虑一个l r l n 阶矩阵4 ，形式如下： a = 乞c 3 c i c 2 1 c 2c 3 qc 2 其中c i = - 2 n ，c 2 = 0 ，c 3 = - 1 ( n + 2 ) 。显然矩阵a 满足定理2 3 1 和定理2 3 5 的条件，这里= 2 , 4 ，5 ，7 ，9 ，l o , ) c im r = 1 , 2 ，3 ，n - l cn 2 。当刀= 3 0 时，在 1 3 q q 乞q ， q q 白 q q q l 巳乞q 岛 电子科技大学硕士学位论文 表2 3 和表2 4 中列出了矩阵彳的预处理迭代矩阵的谱半径，在表2 5 和表2 - 6 中 列出了当n = 1 0 0 时相应的结果。 表2 - 2 对于c o 取小同的参数值兵迭代矩| 珲的谱半彳全p ( 7 名j ，纠。z 二j 捌p ( z 厶j c op ( r m ) p ( z 口)以乙)( 乙)口 )( 乙)口( 屯) 0 9 50 3 4 6 50 3 0 1 80 2 3 9 10 2 0 8 2 4 40 1 6 4 52 5 o 90 4 0 6 6o 3 6 4 30 3 0 9 80 2 5 8 55 50 2 2 7 33 2 0 80 5 0 8 l0 4 7 0 20 4 2 7 50 3 5 2 17 30 3 4 1 6 4 6 o 7 o 5 9 4 l0 5 6 0 40 5 2 6 80 4 3 9 68 60 4 4 6 05 3 0 60 6 6 9 50 6 4 0 30 6 1 4 00 5 2 3 09 50 5 4 1 65 4 0 50 7 3 7 io 7 1 2 50 6 9 2 40 6 0 3 61 0 10 6 3 0 l5 6 0 4o 7 9 8 40 7 7 8 60 7 6 3 80 6 8 2 41 0 50 7 1 2 9 5 5 o 30 8 5 4 70 8 3 9 8 0 8 2 9 50 7 6 0 71 0 5o 7 9 0 75 6 o 2o 9 0 6 60 8 9 6 70 8 9 0 30 8 3 8 21 1 00 8 6 4 l 5 9 0 10 9 5 4 90 9 4 9 9 o 9 4 7 0o 9 1 7 51 0 90 9 3 3 85 6 ， 缈p ( 乙)p ( z 。)以c m ) p o r t ( 乙) 口( )( )口( 瓦 o 910 9 0 7 60 9 0 4 7o 8 9 6 60 6 7 8 11 9 oo 1 5 5 72 3 o 81o 9 1 4 7o 9 1 2 00 9 0 5 40 6 9 0 61 9 30 2 1 1 12 1 o 7 l0 9 2 0 7o 9 1 8 20 9 1 2 80 7 0 3 21 9 60 2 5 4 62 0 o 7o 80 9 3 6 5o 9 3 4 50 9 3 0 20 7 6 2 41 9 60 3 6 7 94 5 o 6o 8 0 9 4 0 70 9 3 8 80 9 3 5 20 7 7 1 21 9 80 3 9 5 23 7 o 5o 8o 9 4 4 30 9 4 2 60 9 3 9 50 7 7 8 81 9 9o 4 2 1 43 3 o 5o 60 9 5 8 30 9 5 6 90 9 5 4 6o 8 3 4 01 9 9 0 5 5 6 25 5 0 40 60 9 6 0 70 9 5 9 4o 9 5 7 40 8 3 9 52 0 o0 5 7 0 64 8 o 3o 60 9 6 2 80 9 6 1 60 9 5 9 90 8 4 4 82 0 10 5 8 5 5 4 2 o - 3o 40 9 7 5 20 9 7 4 4 0 9 7 3 30 8 9 6 6 2 0 10 7 2 0 95 7 0 2o 40 9 7 6 50 9 7 5 70 9 7 4 70 8 9 9 92 0 2o 7 2 8 45 6 o 1o 40 9 7 7 60 9 7 6 90 9 7 6 10 9 0 3 22 0 3o 7 3 6 44 9 第二章预条件a o r 迭代法 0 9p ( c )p ( z 。)p ( z m ) p o p t ( f r o )口t 气)p o , ( r r 甜)口( 死) o 9 50 9 0 8 30 9 0 5 50 8 9 6 90 6 9 0 81 9 00 6 3 0 89 8 o 90 9 1 6 80 9 1 4 20 9 0 6 9o 7 1 0 91 9 oo 6 8 1 2 1 0 4 o 80 9 3 1 70 9 2 9 60 9 2 4 30 7 5 2 41 9 30 7 5 8 81 1 3 0 7 0 9 4 4 50 9 4 2 70 9 3 8 90 7 9 2 11 9 60 8 1 9 51 2 1 o 60 9 5 5 50 9 5 4 10 9 5 1 40 8 2 8 41 9 80 8 6 2 21 2 6 0 50 9 6 5 2o 9 6 4 l0 9 6 2 2 o 8 6 1 7 1 9 90 8 9 8 01 3 1 0 40 9 7 3 80 9 7 2 90 9 7 1 60 8 9 3 02 0 00 9 2 6 51 3 5 0 3o 9 8 1 40 9 8 0 80 9 8 0 00 9 2 2 42 0 10 9 4 9 31 3 8 o 2 0 9 8 8 20 9 8 7 80 9 8 7 40 9 5 0 02 0 20 9 6 9 01 4 1 0 10 9 9 4 40 9 9 4 20 9 9 4 00 9 7 5 82 0 30 9 8 5 81 4 4 ，缈p ( 乙)p ( 乙) p ( z 。) p 叫( 乇)口( )( z ) 口k ) o 9 l 0 9 7 0 50 9 7 0 2 0 9 6 9 40 8 2 0 87 5 o 0 8 5 7 63 8 8 o 8l0 9 7 2 90 9 7 2 60 9 7 2 00 8 2 2 87 5 20 8 9 8 l3 9 9 0 7lo 9 7 4 90 9 7 4 70 9 7 4 20 8 2 9 67 6 1o 9 2 1 04 0 5 0 7 o 80 9 7 9 90 9 7 9 70 9 7 9 30 8 6 3 77 6 10 9 2 5 94 5 4 o 6o 8o 9 8 1 30 9 8 1 20 9 8 0 80 8 6 8 77 6 80 9 4 1 94 5 8 0 5o 80 9 8 2 60 9 8 2 40 9 8 2 10 8 7 3 57 7 40 9 5 2 44 5 8 0 5o 60 9 8 6 90 9 8 5 80 9 8 5 50 9 0 5 l7 7 40 9 5 8 44 7 9 o 4o 60 9 8 7 7