（计算数学专业论文）h矩阵方程组的预条件迭代法和预条件对角占优性.pdf

摘要 摘要 本文主要做了以下工作： 首先、我们给出了一种建立对角占优矩阵的方法，若系数矩阵爿为日矩阵， 可通过适当选取预条件矩阵p 和q ，使p a q 是严格对角占优矩阵，且讨论了当a 为 m 矩阵时对角占优性和参数之间的关系。数值试验结果也表明了我们方法的有效 性。 其次、我们基于n s 类预条件矩阵引入了另一种预条件矩阵p 证明了若系数 矩阵a 为日矩阵，通过适当选取参数，可使p a 仍是h 矩阵。 最后、我们考虑了对线性方程组a x = b 的预条件迭代法，推广了z h a n g 等人提 出的方法。并且证明了当a 为非负h 矩阵时的收敛性，数值试验结 果也表明了我们方法的有效性。 关键词：h 矩阵，预条件，迭代法，收敛，对角占优 a b s t r a c t a b s t r a c t t h i sp a p e rm a i n l yi n c l u d e st h r e ep a r t s ： f i r s t l y , w ep r o p o s e dam e t h o dt oc o n s t r u c td i a g o n a l l yd o m i n a n tm a t r i xa n dp o i n t o u tt h a ti ft h ec o e f f i c i e n tm a t r i xai sa nh - m a t r i x ，t h e np a qi sa l s oa nd i a g o n a l l y d o m i n a n tm a t r i x ，a l s ow ed i s c u s st h er e l a t i o nb e t w e e nd i a g o n a l l yd o m i n a n c ea n d p a r a m e t e r sw h e nai sa dm - m a t r i x n u m e r i c a le x a m p l e sa r ea l s og i v e n ，w h i c hs h o w t h ee f f e c t i v e n e s so fo u rm e t h o d s e c o n d l y ，t h ep r e c o n d i t i o n i n gm a t r i x pb a s e do np r e c o n d i t i o n e ri + si s i n t r o d u c e d i ft h ec o e f f i c i e n tm a t r i xaj sa nh - m a t r i x t h e np ai sa l s oa n - - m a t r i x b ya p p r o p r i a t et a k i n gp a r a m e t e r s a tl a s t ，w ec o n s i d e rap r e c o n d i t i o n e di t e r a t i v em e t h o df o rs o l v i n gl i n e a rs y s t e m a x = b ，w h i c hi sag e n e r a l i z a t i o no fm e t h o dp r o p o s e db yz h a n ge ta 1 ，a n dp r o v ei t s c o n v e r g e n c ef o rt h e c a s ew h e nai san o n n c g a t i v eh m a t r i x n u m e r i c a le x a m p l e s a r ea l s og i v e n ，w h i c hs h o wt h ee f f e c t i v e n e s so fo u rm e t h o d k e y w o r d s ：h m a t r i x ，i t e r a t i v em e t h o d ，p r e c o n d i t i o n ，c o n v e r g e n c e ，d i a g o n a ld o m i n a n t i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书面使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：圭箧堑日期：刎年月t 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：篁鲞塑导师签名： 日期：d 7 年3a2 6 日 第一章引言 1 1 选题背景 第一章引言 随着计算机技术的发展和科学技术的进步，科学与工程计算( 简称科学计算) 的 研究受到科学技术人员的极大重视，其应用范围己渗透到许多学科领域。矩阵计 算的理论和方法与方程组的求解是数值代数的核心方向之一，已经成为经济学、 生物学、现代物理学等领域处理数学问题的不可缺少的强大工具，成为“大规模 科学工程计算理论”的一个重要组成部分。譬如，在均衡论、投入产出分析和增 长模型的研究中产生的m 矩阵( 1 9 3 7 年由o s t r o w s k i 提出) ；在控制论及神经网络大 系统的稳定性、线性时滞系统的稳定性研究中需要的日矩阵及正稳定矩阵等等。 其中日矩阵是近年来计算数学研究的较为热门的一类特殊矩阵，目前对它的研究 主要集中在两个方面：一是研究它本身的数学性质；二是研究与它有关的迭代矩 阵的谱半径的估计、收敛性分析以及计算机算法。 众所周知，在求解一个大型线性方程组时，我们经常选用合适的迭代方法求 其近似解。对于系数矩阵为严格对角占优矩阵，当方程组阶数较低时，人们常常 选用j a c o b i 迭代法和g a u s s s e i d e l 迭代法。但是，我们在实际问题中经常碰到的 矩阵不一定是对角占优的，因此把一个非对角占优的矩阵转化为对角占优矩阵就 显得尤为重要，很多学者对这一问题进行考虑。但是他们考虑范围一般是肘矩阵。 本文的第2 部分试图从更广泛的矩阵类日矩阵条件下通过预条件技术来研究它 们并得到了比较好的结果。 当方程组的阶数较高时，这两种方法的收敛速度较慢。因此许多学者便提出 了收敛速度更快的预条件j a c o b i 、预条件g a u s s s e i d e l 、预条件s o r 和预条件a o r 等方法。这样这些迭代法的迭代矩阵的谱半径估计显得尤为重要。因为一方面谱 半径估计式的给出可以直接判断其相应的迭代法是否收敛；另一方面这些方法一 般含有一个或多个参数，而参数的选择范围与最优参数的选取，关系到迭代法的 收敛性。但是，这些方法一般是在严格对角占优或者是m 矩阵和z 矩阵的条件下 得出的谱半径估计式和参数范围，在使用中有一定的局限性。本文的第3 部分试 图从更广泛的矩阵类日矩阵条件下来研究它们并得到了比较好的结果。 电子科技大学硕士学位论文 1 2h 矩阵概述 非奇日矩阵又称广义对角占优矩阵，是一类范围较广的特殊矩阵，因此在此 节中仅将本文所涉及的有关概念简述一下： 定义1 2 1 【9 】 设a 一( a i j ) r ，若a 可表示为a = s l 一曰，其中，b2 0 则当s ，p p ) 时，称a 为非奇异的m 矩阵，简称膨矩阵；若a 满足 4 u 0 ，1 i - jsn ， 则称a 为z 矩阵；若爿z 且满足 a 口 0 ，f = 1 ，2 ，雄 则称a 为l 矩阵。 定理1 2 1 【i l 设a 一 。) e r “”是膨矩阵的充分条件是a 为l 矩阵，且1 苫o 定理1 2 2 1 8 j 设a 一0 。) r ”是z 矩阵，则a 为m 矩阵的充要条件是有一 正向量r 彤，使得a r o 。 定义1 2 2 州设a 一心) c “，令d ；d i a g ( a ，4 。) ，c ；d a ，则称 矩阵ldi _ i cl 为a 的比较矩阵，记作( 4 ) ： 即 ( 4 一 若( 4 ) 是非奇异的m 矩阵，则称a 为非奇异的h 矩阵，简称h 矩阵。 定理1 2 3 t 8 1 设a - 0 。) c ，若a 满足 1 - 1 k 扛荟+ 乏。，f 一1 ，2 ，叫 j 。1j i l + i 且至少有一个f 使上述不等式严格成立则称a 为弱严格对角占优矩阵，如果上述 n 个不等式都严格成立，则称a 为严格对角占优矩阵。 定义1 2 3 t 7 l 设a 一瓴) c ，若有正对角矩阵q ，使得a q ( q a ) 为行( 列) 严格对角占优矩阵，则称a 为行( 列) 广义对角占优矩阵。 定理1 2 4 1 7 1a 为行( 列) 广义对角占优矩阵等价于a 为日矩阵。 2 第一章引言 1 3 迭代法简介 迭代法一般可表述为： 矿- q t ( x - 1 ，工一) ，七覃f ，z + 1 ， ( 1 - 1 ) 其中妒。称作迭代算子，x ( 0 ) ，x o ) ，x ( z - z ) 为迭代初值，通常称迭代法( 1 - 1 ) 为z 步迭代 法；f 。1 时，亦称为单步迭代法。如果迭代算子讫与后无关，即尹i 矿，则称 迭代法( 1 1 ) 为定长迭代；否则称为不定长迭代。 下面讨论单步定长迭代法： 矿“；i z ，+ c ，七一1 ，2 ，( 1 2 ) 其中g e r 称为迭代矩阵，x ( o 称为初值。 定义1 3 1 如果存在工彤，使得对任意的初值x o e r ”，由迭代法( 1 2 ) 产生的序列缸耻都收敛到x ，即 l i m 矿a 并， t 呻。 则称迭代法( 1 2 ) 是收敛的；否则称之为发散的。 如果迭代法( 1 - 2 ) g 收敛的，则必有 x g x + c ， 记 “件) 一工o ) 一x ， 则易证 越非) 。g 距( o ， 由此可知，迭代法( 1 - 2 ) 收敛的充要条件是： l i m g 一0 。 i _ o 定理1 3 1t 1 】迭代法( 1 1 ) 收敛的充要条件是 j 口( g ) t 1 。 在实际应用中，由于p ( g ) 一般难以求出，我们通常不利用p ( 6 ) 是否小于1 来判定迭代法( 1 2 ) 式是否收敛，而是利用一些易于计算的矩阵的范数来判定。 设已给定线性方程组 a m - 6 其中彳r 一_ j f 【j b e r “已知，x 掣未知。现在我们讨论如何构造迭代法( 1 2 ) 来 求线性方程组a x b 的解。 3 电子科技大学硕士学位论文 首先我们自然希望构造出来迭代法如果收敛，其极限就是方程组的解。这就 需要其迭代矩阵g 和常量c 满足 a a i g 和q b c( 1 3 ) 其中q r 一是某一非奇异矩阵。如果( 1 3 ) 成立，则称迭代法与方程组是相容的。 现假定a 有如下分裂： a m - n 其中膨为非奇异矩阵。令g m 一1 ，c m 一协则由此产生的迭代法是相容的。 基于这种思想，对a 进行不同的分裂，就可以构造出各种各样的相容的迭代 法。现简单举例如下： 设矩阵4 为 令 彳； q 1a 1 2 a 2 1a 2 2 a n la 2 钆 。a 2 n ： 4 m d d i a g ( 4 1 l ，a 2 2 ，a 。) ， 巴一 g 一 000 一口2 1 00 一d l 一口 2 0 0 一q 2 一口h 00 一4 2 。 0o 0 = d 一1 c ，uz d 一1 c 。 则 a - d c l c ，一d 一1 ( ，一l u ) 1 3 1j a c o b i 迭代法阶，】 其中 矩阵4 分裂为 a mj n j 4 第一章引言 m j d ，n j c l + c v ， 迭代矩阵为 ，= m i - t n i = d 4 ( q + g ) = l + u i - d 一1 a ( 1 4 ) 迭代格式为： o d “一( c i + c o h + 6 ，k 一1 2 ，( 1 - 5 ) 设x 。是一个任意的初始迭代向量，然后由公式( 1 - 5 ) 作出向量序列 x 0 ) ，石( 2 ， 这种迭代法称为j a c o b i 迭代法，或简称为j 方法，矩阵( 1 4 ) 称为对应于矩阵4 的 迭代矩阵。 1 3 2g a u s s s e i d e l 迭代法1 2 , 2 7 1 矩阵a 分裂为 a m 一n 其中 m 一d c l ，n 一c u 迭代矩阵为 g j 一( d 一巴) 。1 g 一( i - l ) 。1 u 迭代格式为： z + 1 - ( i l ) - 1 v x k + ( ，一工) b ，k - l 2 , ( 1 6 ) 其中矩阵( ，一三) 4 u 称为对应于矩阵a 的g a u s s s e i d e l 迭代矩阵。 1 3 3 超松弛迭代法( 简称为s o r 迭代法7 1 ) 矩阵4 分裂为 a m 一n 其中 m m ! d c l n 。；1 - t o d c u 为非零实数，称为松弛因子。 迭代矩阵为： l 。一m 。- 1 n 。；q - t o l ) i q - t o ) l + d j ) ， 当= 1 时，s o r 迭代法就是g a u s s s e i d e l 迭代法。因此适当选取参数c o 5 电子科技大学硕士学位论文 可望s o r 迭代法比g a u s s s e i d e l 迭代法具有更快的收敛速度。 1 3 4 快速超松弛迭代法( a o r 迭代法) h a d j i d i m o s 子1 9 7 8 年提出了快速超松弛迭代法【3 ，2 7 ，其后许多学者对它进 行了讨论。a o r 迭代法的迭代矩阵为 m ，。一( d - o c l ) 一1 ( ( 1 - m ) d + ( a - o ) c l + n ，u ) 其中，a e r ，0 9 0 。易知 当o r = 时，a o r 法即为s o r 法； 当盯一一1 时，a o r 法即为g s 法； 当盯一0 时，a o r 法即为j o r 法； 当仃一0 ，一1 时，a o r 法即为j a c o b i 法。 1 4 预条件迭代法简介 我们在迭代矩阵的时候，经常出现迭代矩阵谱半径小于1 的情况，但是数值和 1 非常接近，那样迭代过程非常缓慢，效果不好，这时往往采用其它办法，其中一 种方法就是对系数矩阵a 进行预处理，然后对预处理矩阵进行分解迭代。 目前，预条件的方法在迭代中运用的很广泛，比如在a o r 、g s 迭代法中，在 迭代前，先对系数矩阵4 尺乘上一个预条件矩阵，这样往往会改变迭代法的收 敛性。因此对预条件矩阵的选择是一个重要的课题。 设已给定线性方程组 a x = b 其中爿尺和b 已知，x e r “未知。在实际的计算过程中，收敛性的改善不仅 取决于迭代方法以及迭代矩阵中参数的选取，而且同方程组自身的某些变化也密 切相关，例如可以对方程组两边左乘一个非奇异矩阵p ( 预处理) 。通过这种技巧， 线性方程组a x b 等价变形为： p a x b ， ( 1 7 ) 如果b 4 还有分裂p a m ，一，那么( 1 7 ) 的迭代格式为： 矿“一m ；1 + m ；, i p b ，k to ，1 ， 同样可以对线性方程组a x b 等价变形为 a e y = 6 ，x 。，y( 1 8 ) 如果爿_ p 还有分裂a p m ，一j r , ，那么( 1 8 ) 的迭代格式为： 6 第一章引言 工“11 m ；1 一+ m ；墙，k = 0 3 , 或者对线性方程组a x = b 等价变形为 p a q y p b ，x = q y( 1 - 9 ) 如果剧q 还有分裂刚q 一肘尸口一艘，那么( 1 - 9 ) 的迭代格式为： x “1 - m g 蚀+ m 品乃，k o ，1 ， ( 1 7 ) 、( 1 - 8 ) 和( 1 9 ) 统称为预条件迭代法。p ，q 称为预条件矩阵。 对p ，q 的选取方式有很多，例如s a i 、i l u 类、s s o r 等等。现在已有很多 形式上比较简单的稀疏预条件矩阵，例如1 9 8 7 年，m i l a s z e w i c z 在文【2 5 】中提出了 预条件矩阵 置一i + 墨一 1 一a 2 1 1 一a 3 l 1 ： 一n 1 ； 一口 1 1 在1 9 9 1 年ad g u n a w a r d e n a 等人在 4 1 d p 提出了一种比较简单的预条件矩阵为 p 一，+ s 一 1 - a 1 2 01 ： ； 0 1 9 9 7 年，t k o l m o 等人在 1 3 1 中提出带有 p i + 殳， 1 一4 1 2 o1 0 曩斗001 。1 ， 。一以山l j 曩as_；1a01。山1， 一 山l j 其中口“吒，c r 2 ，4 r ，q o ，i * l 2 , ，l 一1 。很明显，当口一。时，p - 1 。当a 一1 时，+ s 。一j + s ，相比较p - i + s ，p - i + & 具有更强的使用性。u 和s u n 对 此预条件矩阵，当q o ，1 时，也进行考虑。并得到了一些有趣的结论 2 0 0 2 年，h n i k i 等人在【5 】中构造出另一种预条件矩阵，+ s 。，其中 7 电子科技大学硕士学位论文 。眇r 江苫孑u “， f 1 这里t = m i n w j i m 弘1 4 # i ，f c ，l 。 ，+ s m 缸只与线性方程组a x = 6 的系数矩阵a 的上三角部分每一行的最大元素 有关，这个结果比ad g u n a w a r d e n a 构造出的，+ s 适用性强，由于，+ s 一的良 好性质，h i s a s h ik o t a k e m o f i 等把，+ s 。应用到g a u s s s e i d e l 迭代法中去，取得一 系列重要结果。 在2 0 0 3 年，a h a d j i d i m o s e ta 1 在【1 8 】中用参数作用于号得到 置( a ) 一i + 墨( 口) = 1 一口2 口2 1 - - c f 3 a 3 1 一a f 口n g f n a n l 其中a - a 2 ，码，o9 r ，2 0 ，i 一2 ，3 ，厅。很明显，当口一。时，最 ) = ，。当a ；1 时，日 ) 一只a 寻求一种新的预条件矩阵应该说比较困难，我们也可以考虑研究预条件方法 和一般迭代法收敛性关系，或者，考虑对参数加以新的约束，得到更好的条件， 使得预条件迭代法收敛。 在文献【6 】中有一个关于a o r 迭代法的较好的结论。在文献 2 8 ，2 9 ，3 0 中也有对 这些预条件矩阵的其它一些讨论。 1 5 本文的主要工作 1 、在第二章我们给出了一种建立对角占优矩阵的方法，若系数矩阵a 为h 矩 阵，可通过选取p 和q ，使的p a q 是严格对角占优矩阵，且讨论了当爿为膨矩阵 时对角占优性和参数之间的关系。数值试验结果也表明了我们方法的有效性。 2 、在第三章中，我们基于，+ s 类预条件矩阵引入了另一种预条件矩阵p ，证 明了若系数矩阵彳为日矩阵，通过适当选取参数，可使p a 仍是日矩阵。 3 、在第四章中，我们考虑了对线性方程组a x b 的预条件迭代法，推广了 8 1 l 第一章引言 z h 姐g 等人在【1 6 】中提出的方法。并且证明了当4 为非负日矩阵时的收敛性，数值 试验结果也表明了我们方法的有效性。 9 电子科技大学硕士学位论文 2 1 概论 第二章h 矩阵的预条件对角占优性 我们先看下面两个定理： 定理2 1 1 1 7 l 若a x = b 的系数矩阵a 为严格对角占优矩阵，则j a c o b i 和 g a u s s s e i d e l 迭代均收敛。 定理2 1 2 【7 捌若a x ；b 的系数矩阵a 为严格对角占优矩阵，则当0 c 珊主1 ， s o r 迭代收敛。 由上面的两个定理，我们很容易看到a x = b 的系数矩阵a 为严格对角占优矩 阵时，j a c o b i 迭代法、g a u s s s e i d e l 迭代法和s o r ( 0 0 和q d i a g ( r ) ，其中e g ，1 y ，当 a i a f l a “，1 i 一2 ，甩。( 西一三) 。1 存在，这样我们就可以定义p a qi 拘g a u s s s e i d c l 迭代矩阵丁。函一z ) 4 驴。 2 2 预备知识 引理2 , 2 1 ”m 。3 2 q 彳是日矩阵的充要条件是存在r ，0 使得似) ， 0 ，其中 r 一“，2 ，r y 。 引理2 2 2 “町a - i b ( b 0 ) 是m 矩阵的充要条件是p ( b ) 1 ，其中 p ( ) 表示矩阵的谱半径。 引理2 2 3 ”弘州若p p ) t 1 ，那么( ，一b ) 一一二 引理2 2 4 “4 1 若爿是对角元全为1 的h 矩阵，让( 爿) 一一( ，嘞) ，那么下面 的关系满足： ：。m 。乩f 一2 ，叫a 证明：由印) - i b ( b 苫o ) 是一个m 矩阵，根据引理2 2 2 我们有p p ) 1 ，那么 “只d ) ，九= 1 - - a t ) 1 4 ni + 1 4 hi - - a ii a i l a “l r j 一聂i 一以，b # ( 1 a 1 r , 印著呲) 一q “讹ii + 荟i q ，b ) 一o + 2 l a 。l r o - a ，i a 。l ( 轨一1 ) o 因此，掣是日矩阵，并且剐a 是严格对角占优矩阵。 定理2 3 3 若4 是对角元全为1 的h 矩阵。如果 。 o 。当f j 】 + l ，厅 时，证明同定理2 3 2 。 由定理2 3 2 和定理2 3 3 ，我们立即可得下面的定理。 定理2 3 4 若a 是对角元全为1 的日矩阵并且满足定理2 3 2 和定理2 3 3 的 条件，那么掣q ( p k a q ) 是严格对角占优矩阵，并且p ( 一z ) 。1 d ) c 1 。 下面我们将表明若a 是肘矩阵，“掣) r x 是关q ( 呸s o ，1 】) 的增函数。 定理2 3 5 若4 是对角元全为1 的m 矩阵，让 o ，o 】g 口= 【吃，rs 舀_ 【西：，屯r b ，玎 那么 ( ( p 1 1 a ) r ) is ( ( 掣) r ) f ，i 一1 ，n 。 其中日与上面定理中的相同，在只中用幺代替q ，即可得到丘。 证明：根据定理2 3 2 的证明，我们知道 “掣) ，九- l - a l a f l 和 “写4 ) r x ；1 - d j q l ，i 一2 ，n ， 由于呸l s0 ，0 s qe d i 五1 ，我们有 “掣) r ) 。s ( ( 号爿) ，x 当i 一1 时 ( 【暑爿) ，) 。= ( ( 掣) ，) 1 1 因此 “掣) ，) ，主( ( 只4 ) r x 同样我们可以表明若4 是m 矩阵，“掣) r ) ；是关q ( q ，1 ) 的减函数。 定理2 3 6 若4 是对角元全为1 的m 矩阵，让 阻，砰c 口一【a ：，】rj d 一【d ：，龟r ， 并且 1 4 10； 第二章h 矩阵的预条件对角占优性 。，。；。，11 + 轨1 4 i l i 、 s 咖石a n a 瓦可筠1 i 【z 一 那么 “e 4 ) ，x 芑“掣) ，) ，i = 1 ，以， 其中只和丘同定理2 3 5 。 证明：由假设掣和翩的对角元素为正，第一列元素非负，其它元素非正。 即 f 0i ， 掣( 掣) 一 ) ) ) z 0i 一1 , j ；1 i s 0 ，1 ，j ，i 因此， “0 ，4 ) ，) ；= ( 1 2 a f ) + q 4 i l ( 2 一1 ) ， 和 ( ( 。f 弘) ，) f 一0 2 a ； ) + 匾4 f 1 ( 2 r l 一1 ) ，i = 乏，n 由于( 轨一1 ) ，o 和s 0 ，根据假设可知 “掣) r ) ；= ( ( 掣) r 九，f 一2 ，n ， 当i 一1 时 “掣) ，) 。一( ( 翩) r ) 。一1 因此 “掣) ，x 苫“号爿) ，) ；，f 一1 ，n ， 说明：从定理2 3 5 和定理2 3 6 ，我们注意到若a 是对角元全为1 的m 矩阵， 当口一1 时p a q 的对角占优性最强，且g a u s s s c i d c l 迭代法的收敛率比其它的口 要快。 2 4 数值例子 首先，我们运用提出的方法对下面的测试矩阵去建立对角占优矩阵，不失一 般性，我们取q ；1 ，f 一2 ，n 。让 彳皇 1 0 0 0 - 0 9 0 0 0 o 1 0 0 0 0 3 0 0 0 0 1 0 0 0 1 o ( ) o - 0 1 0 0 0 - - - 0 5 0 0 0 - 0 2 0 0 0 o 7 0 0 0 1 0 0 0 0 2 0 ( ) 0 0 1 0 0 0 - 0 8 0 0 0 0 3 0 0 0 1 0 0 0 可以证明a 是一个h 矩阵，通过运用预条件矩阵e 和q ，我们得到下面的矩阵： 电子科技大学硕士学位论文 掣q 一 1 6 4 2 7 5 0 0 0 6 6 1 8 3 7 2 1 3 9 7 - - 7 2 8 0 2 - 3 5 0 7 7 1 很明显p a q 是严格对角占优矩阵。 下面我们对( 2 4 ) 测试了它的g a u s s s e i d e l 迭代法，为了比较我们也测试了( 2 1 ) 的g a u s s s e i d e l 迭代法。对下面的日矩阵： 彳= 其中，c 1 。i 苦，c 25 寺，c 34 i - 五1 ，我们选择6 使得( 2 - 1 ) f l x = o , z ，1 ) 7 ， 让收敛准则为与篙云俨s 1 。- 6 ，对n 一4 ，1 0 ，1 5 ，2 。，5 0 0 我们在下面的表格中表明了 系数矩阵a 和号彳q 的g a u s s s e i d e l 迭代的谱半径和迭代次数。让g s 研) 表示系数 矩阵4 的g a u s s s e i d e l 迭代，g s ( p t a q ) 表示系数矩阵只彳q 的g a u s s s e i d e l 迭代。 如下表2 - 1 ： 从表2 - 1 ，我们可以看出系数矩阵为耳4 q 的g a u s s s e i d e l 迭代要好于系数矩阵 为爿的g a u s s s e i d e l 迭代。 在本章中，我们选取只作为考虑的对象，若取在第一章中提到的其他的p ， 我们可得相似的结论。 表2 - 1 谱半径和迭代次数 g s ) a s ( 暑a o ) n 谱半径 迭代次数 谱半径 迭代次数 40 5 2 2 52 90 2 8 7 11 5 1 00 3 2 3 01 8 0 3 0 1 2 1 3 1 50 2 8 7 01 70 2 6 1 21 1 2 00 2 6 8 51 60 2 5 2 91 1 5 00 2 9 1 41 7 o 2 8 5 3 1 0 1 6 嫩一嬲梢禾也铊 一一一 q乞q；乞qq乞q 雅 纠 乞 q 11勺乞q； 砒乞q 。 q色q勺吒q 巳吒q 撕 第三章h 矩阵方程组预条件迭代法收敛的参数选取 3 1 概论 第三章h 矩阵预条件迭代法收敛的参数选取 考虑线性方程组 a x b ( 3 1 ) 其中彳r ”和b r4 已知，石r 4 未知。求解( 3 1 ) 的基本迭代解法是 m x “- n x + 6 ，七= o , l ( 3 2 ) 其中a m 一且m 是非奇异矩阵。这样( 3 2 ) 也可被写成 矿“一a + c ，七一o ，1 ，( 3 3 ) 其中z = 肘一1 ，cz m 一协。假设4 为对角元均为1 的方阵，且a 。，一l 一【，一l 和一【， 分别是矩阵a 的严格下三角和严格上三角部分。那么g a u s s s e i d e l 迭代格式为 t = 仃- l ) u 为了更好的解( 3 1 ) ，引入非奇异预条件矩阵p ，即考虑 p a x p b ( 3 4 ) 那么( 3 4 ) 的g a u s s s e i d e l 迭代格式为： m p 矿+ 1 一p z 。+ 肋，七= o ，1 其中p a 。m ，4 ，m ，是非奇异矩阵。 g u n a w a r d e n a 等人提出了修改的g a u s s s e i d e l 迭代法如下：令( 3 4 ) 中的 p i + s ，其年 s 一 0 - a l 。0 00 - a t j 0 在s 中，如果所有的4 是非零的n z , ， , i x - ( ，+ s ) a x p - l s l - 缈一s + s v ) l ， 若q “l a i + u 一1 ，( f 一1 ，n 一1 ) 那么( ，一l s l ) 4 存在，因此，对矩阵j 可以定义它 的g a u s s s e i d e l 迭代矩阵。即 f ，( ，一l s l ) 一1 9 ，一s + s u ) 1 7 o；oo 一 电子科技大学硕士学位论文 并且把于叫做修i e l 拘g a u s s s e i d e l 迭代矩阵。k o h n o 等在文【1 3 】中对上面的预条件矩 阵p ；j + s 引入参数来提高迭代法的渐进收敛率。在本文中，我们对( 3 - 1 ) 中系数矩 阵爿是日矩阵的情形进行了考虑。 3 2 预条件迭代法 若令 s ：= 0 一层4 1 。0 0 一i 口2 4 z l 0 一p 2 a ； 0 一吒4 3 2 0 i。 一成一一。 00 一c 0 吒。- 1 0 p ；，+ 3 1 1 ，同样可取p 为a 的预条件矩阵，令形= p a ，则 a ：；q + s ：、a 。i - l u + s ：一s ：t l + u 、， 让霹仁+ u ) ；西+ 三+ 疗，其中西，三，疗分别是碟( l + u ) 的对角，严格下三角和严 格上三角部分，那么鬈一( f 一西一l + 是) 一一s 4 + d ) ，这儿& ，s 是碟的下三 角和上三角部分。若 层口1 2 a 2 l 1 i 一1 a i a u _ 1 a j v + 屈4 j “i a i + u 一1 i 暑2 ，玎一1 a n a n 4 - 1 a a 一1 i 一打 那么( ，一西一l + s a ) 4 存在，这样我们可以定义群l 抟j g a u s s s e i d e l j 塞_ 代矩阵，即 z ? ；( f 一西一l + & ) 一1 ( 【，一s 4 + 疗) 引理3 2 1 7 , 2 1 , 2 3 , 2 4 a 是h 矩阵的充要条件是存在， o ，使得臼) r ，0 。其中( 彳) 是4 的比较矩阵。 引理3 2 2 m 1 2 3 2 4 1 a 是对角线元素为1 的日矩阵，则p 以一工) 。1 u ) 1 。 引理3 2 3 【i 1a 是对角线元素为1 的h 矩阵，f l ：r 一“r z ，) 7 一似) e ， 那么，2 1 ，i 一1 ，巩并且l i 1 + 2 1 4 1 2 i r 2 一( 1 +) ( 2 r 2 - 1 ) a 。 苫1 + l q 。i 一1 = i ：f i ! i i ： 赫) ( 2 i i ( 4 ) 一1 i i 。一1 ) 1 4 - 。i j 。 所以( 钟) ，) 1 ，0 同理可证对f = n ，( 似：) ，l ，0 。 ( 2 ) 对f = 2 ，n - l ，有 ( ( 鬈) ，) f - 1 1 一o r i a l t _ l a t _ “局钆“吩一i 一j 吼，一q q 。q 一，一层q m 。q 。，h 乏一q k 。k 一层k + 。i 一荟k ，一q 吒，一。，h 一乏屏k + 。忆州i o 计地北一。川训- 一q h ，量h h ，毳k t 忆肛 一层“，i r , + ，三。酏“肛+ 2 ，吨。) - 1 + c t ；l a i ，。+ l a f 。j 【( 1 一q ) 一1 1 一q i k 。- 鼻, l a ；。i ( 2 + 。一1 ) 电子科技大学硕士学位论文 由。q 名，。s 孱t 1 + 1 = i ： a i i 三l a i = i j q 面币 + l “4 ：) r ) ；1 + q i a t 。i - p , i a i 。i ( 2 五+ 。一1 ) ，1 + qi a t z _ l l i a i 。+ l | 【2 | | 似) 4 卜i i = 0 由q ，t 且q k 。i + 屈k 。i o 综合( 1 ) 、( 2 ) p - i l l “形) r 九，0 ( i = 1 ，2 ， n ) 所以形) 是m 矩阵即形是h 矩阵且 p ( 鬈) 1 。 从上面定理的证明可以看出我们是通过先取定啦然后通过q 来确定的屈取 值，同样我们也可以先取定屈然后通过屈来确定q 。可得下面的定理。 定理3 2 2a 是对角线元素为1 的h 矩阵，当满足下列条件时： ( 1 ) 。s 岛c l + i = i ：f i 1 i a 乙l 2 i 而+ 1 ，。量t 1 + i = = ：i t i a n i n i _ j l l 丽+ 1 ， ( 2 ) 。g 局s l ，。qc l + j = i ：端，或者尼，1 ， 口，k 。i + 展k 。i c 时( i = 2 3 ，n - 1 ) ， 形是日矩阵且p ( ) c l 。 证明：同上。 在定理3 2 1 中若取屈= 0 ( f = l 2 , n - 1 ) 。这也是一种改进的g a u s s - - - s e i d e l 迭 代法，令p = i + & ，以一刚则可以得到： 推论3 2 1a 是对角线元素为1 的日矩阵，且 0 啦 0 使得臼r 0 ，其中 ，。“，r 2 ，：i ) 1 引理4 2 2 阱1 , 2 3 , 2 4 a i b ( b 0 ) 是m 矩阵的充要条件是p p ) 1 ，其 中m 表示矩阵的谱半径。 引理4 2 3 1 7 孔2 ”4 j 若爿是对角元全为1 的日矩阵，让( 彳) - 1 一如口) ，那么下面 的关系满足： _ m 。乩i - 1 , 2 , ，行。 引理