（应用数学专业论文）线性方程组迭代求解及相关问题的研究.pdf

摘要 摘要 随着计算机技术的发展，线性方程组的迭代法求解在科学与工程计算中 起着越来越重要的作用本文主要研究了线性方程组、鞍点问题、线性互补问 题( l c p ) 的迭代算法及相关的误差估计和预处理技术，主要内容和创新点包括： 研究了求解线性方程组的u s a o r 迭代法的误差界在线性方程组似= 6 的系 数矩阵对称正定及具有( 1 ，1 ) 相容秩序的条件下，我们得到了u s a o r 迭代法的误差 的上界估计由于许多实际问题如偏微分方程的求解最后常转化为解大型稀疏线性 方程组，因而该结果具有实际应用价值数值结果表明估值有效 研究了d j e v a n s 和n m m i s s m i s 等学者提出的预条件同时置换迭代法的误差 界在系数矩阵对称正定及具有( 1 ，1 ) 相容秩序的条件下，我们获得了预条件同时置 换迭代法的误差上界 将线性互补问题将其转化为等价方程组，应用矩阵分裂和迭代算法的思想， 我们给出了求解该问题的预条件同步置换迭代算法并在日矩阵的条件下，建立 了该数值迭代算法的收敛理论 针对鞍点问题的结构特点，我们给出了m a o r 型迭代算法并证明该方法的收 敛性该结论推广了g h g o l u b 等知名学者2 0 0 1 年和2 0 0 4 年的结果 我们研究了鞍点线性系统的迭代法，给出了鞍点线性系统m p s d 迭代解法， 并证明了m p s d 型迭代法的收敛性 对线性方程组求解，给出了预条件a o r 迭代算法，我们的结果显示在系数矩 阵为l 一矩阵等条件下，预条件a o r 迭代算法比经典a o r 迭代算法的收敛速度快 建立了线性方程组的一类预条件s a o r 迭代算法，并证明了在系数矩阵为不 可约对角占优z 一矩阵的条件下该方法收敛 关键词：日矩阵，迭代法，预处理，鞍点问题 a b s t ra c t a b s t r a c t w i t l lt h ed e v e l o p m e n to ft h ec o m p u t e rt e c h n o l o g y t h ei t e r a t i v em e t h o d sf o r t h el i n - e a rs y s t e mt a k eam o r ea n dm o r ei m p o r t a n tr o l ei nt h ec o m p u t a t i o ni ns c i e n c ea n de n - g i n e e r i n g i nt h i st h e s i s ，t h ei t e r a t i v em e t h o d sf o r t h el i n e a rs y s t e m ，e r r o rb o u n d sa n d p r e c o n d i t i o n i n gt e c h n i q u e sh a v eb e e nr e s e a r c h e d t h em a i nr e s u l t sa n di n n o v a t i o n sa r e a sf o l l o w s ： t h ee r r o rb o u n df o rt h eu s a o rm e t h o di ss t u d i e d w 色a s s u m et h a tt h ec o e f f i c i e n t m a t r i xo fa x = bi ss y m m e t r i c ，d e f i n i t ea n dc o n s i s t e n t l yo r d e r e ds ot h a tt h ep r a c t i c a l e r r o rb o u n di sd e r i v e d s i n c em a n yp r a c t i c a lp r o b l e m ss u c ha st h es o l u t i o nt ot h ep a r t i a l d i f f e r e n t i a le q u a t i o n sc a l lb et u r n e dt ot h ei t e r a t i v em e t h o d sf o r t h el a r g el i n e a rs y s t e m s ， t h e no u rr e s u l ti su s e f u l t h en u m e r i c a le x a m p l ep r o v e st h a tt h ee r r o rb o u n df o rt h eu s - a o rm e t h o di se f f e c t i v e 既h a v es t u d i e dt h ee r r o rb o u n df o rt h ep r e c o n d i t i o n e ds i m u l t a n e o u sd i s p l a c e m e n t m e t h o dw h i c hi sp r e s e n t e db yd j e v a n sa n dn m m i s s i r l i s i ft h ec o e f f i c i e n tm a t r i x i ss y m m e t r i c ，d e f i n i t ea n d c o n s i s t e n t l yo r d e r e d ，w eo b t a i nap r a c t i c a le r r o rb o u n d f o rt h e p r e c o n d i t i o n e ds i m u l t a n e o u sd i s p l a c e m e n tm e t h o d t h el i n e a rc o m p l e m e n t a r yp r o b l e mi sc h a n g e dt ot h ee q u i v a l e n te q u a t i o n s o nt h e b a s i so ft h em a t r i xs p l i t t i n ga n dt h ei t e r a t i v em e t h o d ，w ep r e s e n tt h ep r e c o n d i t i o n e ds i m u l t a n e o u sd i s p l a c e m e n tm e t h o df o rt h el i n e a rc o m p l e m e n t a r yp r o b l e ma n dp r o v et h e c o n v e r g e n c eo ft h em e t h o d f o rt h es a d d l ep o i n tl i n e a rs y s t e m ，t h em a o r - l i k em e t h o di sp r o p o s e d ，a n di t s c o n v e r g e n c ei so b t a i n e d ，w h i c hg e n e r a l i z e st h er e s u l t so fg h g o l u be ta 1 i n2 0 0 1a n di n 2 0 0 4 t h em p s dm e t h o di sc o n s i d e r e df o rs o l v i n gt h es a d d l ep o i n tl i n e a rs y s t e ma n dt h e m p s d l i k em e t h o di sd e r i v e d w et h e o r e t i c a l l yp r o v et h ec o n v e r g e n c eo ft h i sm e t h o d n ea o rm e t h o df o rt h ep r e c o n d i t i o n e dl i n e a rs y s t e mi ss t u d i e da n do u rr e s u l t s s h o wt h a ts o m ei m p r o v e m e n t si nt h ec o n v e r g e n c er a t eo ft h i si t e r a t i v em e t h o de a r lb eo b t a i n e do nb a s i so fh m a t r i c e s w ep r e s e n tt h em o d i f i e ds a o rm e t h o df o rt h ep r e c o n d i t i o n e dl i n e a rs y s t e m s ，a n d p r o v et h ec o n v e r g e n c eo ft h em e t h o do nc o n d i t i o nt h a tt h ec o e f f i c i e n tm a t r i xi sa ni r r e 一 a b s t r a c t d u c i b l ed i a g o n a ld o m i n a n tz m a t r i x k e y w o r d s ：日- 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 i n g ，s a d d l ep o i n tp r o b l e m m 主要符号对照表 r r + 0 c n r n c m n r m n i 4 t a h 川 i i a i l 2 | i a i l 。 ( a ，b ) a 0 a 0 a 三o a 卜0 p ( a ) n u l l ( a ) d i a g ( d l ，d 竹) t r i d i a g ( a ，b ，c ) 圆 主要符号对照表 自然数集 1 ，2 ，n ) 实数集 正实数集 空集 复礼维列向量空间 实钆维列向量空间 m n 复矩阵集 m 佗实矩阵集 单位矩阵 矩阵a 的转置 矩阵a 的共轭转置 矩阵a 各元素取绝对值的矩阵 矩阵a 的谱范数 矩阵a 的无穷大范数 向量a ，b l 拘e u c l i d e a n 内积 矩阵a 是非负矩阵 矩阵a 是正矩阵 矩阵a 是h e r m i f i a n 正半定矩阵 矩阵a 是h e r m i f i a n 正定矩阵 方阵a 的谱半径，若a 为非负矩阵，即为p e r r o n 根 矩阵4 的零空间 以d 1 ，如为对角元的对角矩阵 以b 为主对角元，口为下次对角元和c 为上次对角元的三对角矩阵 为k r o n e c k e r 积符号 v u 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：日期： 7 年厂序7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：力归了年矿月7 日 第章绪论 1 1 广义对角占优矩阵 第一章绪论 在科学和工程计算上，偏微分方程常常通过区域分解算法、差分方法、有限 元法、边界元法等方法离散化处理后将原方程化为的稀疏的线性方程组，然后通 过求解该方程组得到相应的数据因而稀疏的线性方程组求解一直是一热门研究课 题 在实际问题中，线性方程组的系数矩阵常常具有某种特殊形式或者具有某些 数值特征如，在投入产出分析、均衡论、轴承油墨振荡的研究中产生的m 一矩 阵；在神经网络大系统的稳定性、控制论以及线性时滞系统的稳定性研究中 的日矩阵、正稳定矩阵由于日矩阵理论在线性时滞系统的稳定性、神经网络大 系统及控制论的稳定性研究中的重要性，引起了越来越多的科技工作者的兴趣 1 9 3 7 年a m o s t r o w s k i 率先引入日矩阵的定义并研究了它的一些性质随着研 究的深入，人们对日一矩阵的认识已越来越深刻日矩阵的一种定义是其比较矩阵 为m 矩阵在研究对角占优矩阵时，人们又定义了广义对角占优矩阵，即存在一 个正对角矩阵q ，右乘q 后变为严格对角占优矩阵后来证明了广义对角占优矩阵 与日矩阵是等价的概念随后人们又相继提出了半严格对角占优矩阵、不可约对 角占优矩阵、具有非零元素链对角占优矩阵、q 一对角占优矩阵、q 一链对角占优 矩阵、双q 一对角占优矩阵、双q 一链对角占优矩阵等概念f r o b e r t 在文 1 6 中研 究线性方程组的块迭代算法的收敛性时提出了块日矩阵此后许多数学工作者对 此做了大量细致深入的研究 日一矩阵之所以引起很多研究者的兴趣，另一个很重要的原因就是对线性方 程组的求解当线性方程组的系数矩阵为日矩阵时，很多传统的迭代法( 如j 迭代 法、g s 迭代法、s o r 迭代法、a o r 迭代法、s a o r 迭代法) 等都收敛，并且很多修 正的迭代法诸女i m a o r 迭代法、g a o r 迭代法、u s a o r 迭代法等以及相关的多分 裂并行算法也收敛 既然日矩阵具有如此重要的作用，那么日矩阵实用判据就变得很有实际研究 价值尤其是一些实际问题中产生的一些上百万阶的大规模稀疏矩阵能否找到简 便、实用而又有效的日矩阵判据就显得尤为重要 电子科技大学博士学位论文 1 2 线性方程组的预条件迭代法 对于线性方程组a x = b ，将系数矩阵a 进行分裂a = m 一( m 非奇异) ，则 有求近似解的迭代格式 。七+ 1 = m 一1 n x 七+ m 一1 6k = 0 ，1 ，2 ， 若取非奇异矩阵尸左乘该线性方程组两端，即p a z = p b ，再做分裂p a = m r 一 p ( 坼非奇异) ，由此构成的迭代格式 z 七十1 = 蚱1 n p x 七+ 蚱1 bk = 0 ，1 ，2 被称为预条件迭代法 对迭代法进行预处理的目的是为了改善求解线性方程组的迭代法的收敛速 度，或者使得原来不收敛的变得收敛对迭代法进行预处理的关键是在于如何选取 预条件矩阵一般来说，预条件矩阵p 的选取要么能降低矩阵p a 的条件数，要么 使得预处理后的迭代矩阵的谱半径变小文 6 9 】提出了对对角占优的z 矩阵做预处 理的两种方法，随后文 7 0 ，7 1 又通过引入参数对该方法进行了推广由于在实际 讨论中，均对z 一矩阵附加条件使之变成日矩阵所以，实际上是对这种特殊日矩 阵的预处理迭代进行讨论 文 7 2 用，+ u 对矩阵a 做预处理，其中j 为n 阶单位矩阵，一u 为a 的严格上三 角矩阵，并证明了：对于严格占优的z 矩阵，就g a u s s s e i d e l 迭代而言，经预处理 后迭代的收敛速度比预处理前迭代的收敛速度快文 7 1 】用j + p u 对矩阵a 做预处 理，证明了对严格占优的z 一矩阵，在0 1 的条件下，( ，+ p 沙) ( ，一l u ) 仍 然是一个严格占优的z 矩阵，同时也证明了一些收敛性问题 m i l a s z e w i c z 在文献 7 0 ，7 1 用矩阵圪( 见1 1 ) 作为预条件子对矩阵a = i l u 进行预处理则 a c = ( i + c ) a = i l u + c c u = m c 一 其中 m c = ( ，一d c ) 一( l c + 如) ，c = u + 乃 而d c ，昆和岛分别为矩阵c u 的对角、严格下三角和严格上三角部分从而建立预 条件g a u s s s e i d e l 迭代算法 2 第章绪论 m c l n c = ( ，一d c ) 一( l c + 助) 】一1 ( u + f c ) 尼= ( ，+ c ) = 1 一n 2 1 - - a n l 0 1 ： ： 0 0 0 ： ： 1 ( 1 - 1 ) 1 9 9 1 年，a d g u n a w a r d e n a 等人提出了修改的g a u s s s e i d e l 方法( m g s 方法) 取 矩阵p = i + s ，其中 s = 0 - a 1 2 0 - a 2 3 0 一一1 仃 0 则 a s = ( i + s ) a = i l u + s s l s u = m s 一 其中 m c = ( i d s ) 一( l + b ) ，帆= u s + s u 而d s ，e s 分别为矩阵s l 的对角和严格下三角部分, 贝i j p a x = p b 的g a u s s s e i d e l 迭 代格式为 x k + 1 = 蜂1 n s z 七+ 石k = 0 ，1 ，2 其中，a 缮1 s = 【( ，一d s ) 一( l + 毋) 】一1 ( u s + s u ) ，b = ( j d s ) 一( l + 毋) 一1 p b a d g u n a w a r d e n a 证明了该方法的收敛性并指出m g s 方法优于g a u s s s e i d e l 方法 和j a c o b i 方法 为了进一步研究修改的g a u s s s e i d e l 方法及改善收敛速度，1 9 9 7 年，k o h n o 等 人提出用，+ & 对矩阵a 做预处理，并采用迭代格式 x k + l ：元奄+ 石知：0 ，l ，2 其中，t = ( ，一s 二l l ) 一i ( u 一& + & u ) ，石= ( 一l l ) 一1 尸6 ， 3 电子科技大学博士学位论文 & = 0 - - q l a l 2 0 - - o 。2 a 2 3 一o ! 竹一l a n 一1 n o 将a d g u n a w a r d e n a 的相关结果进行了推广，给出了当a 是某类对角占优z 矩阵时 的一个收敛定理，并从数值上说明所给出的方法优于s o r 方法 2 0 0 0 年，w l i ，w w s u n 及2 0 0 4 年，h n i k o 等研究者进一步给出了当系数 矩阵a 为z 矩阵时更一般的情形，并讨论预条件g a u s s s e i d e l 迭代法和经典g a u s s s e i d e l 迭代法的比较定理 2 0 0 1 年，d j e v a n s 等人提出了预条件a o r 迭代法分别取了预条件矩 阵p ：j + s ，其中 s = 00 00 00 一口n 1 0 和预条件矩阵p = ，+ s ，其中 s 7 ： 00 00 0 0 - a n l 0 0o 00 00 00 00 00 00 00 对于预条件方程组( ，+ s ) a x = ( ，+ s ) b ，设a = j l u ，且令 彳= ( j + s ) a = ( j + s l s u ) 一u = 一d z 一一u 其中，一d = d i a g ( 1 ，1 ，1 一a l n a n l ) 则预条件a o r 迭代格式为 z 七+ 1 ：磊七+ 苫k = 0 ，1 ，2 4 第一章绪论 其中， 于= ( 万一- r e ) 一1 【( 1 一u ) 面+ w 一7 ) 乙+ u _ 】 类似地，对预条件方程组( ，+ s 7 ) a x = ( i + s 7 ) 6 应用a o r 迭代法，也相应地得到 其对应的预条件a o r 迭代格式 1 3 线性方程组的迭代算法的误差估计 误差界问题是数值计算中重要而又有实际意义的研究课题用迭代法求解之前 并不知道线性方程组的精确解，而每一次迭代得到的都仅仅是一近似解，那么何 时得到的近似解才是满足需要精度的数据是一必须考虑的问题误差界问题的研究 正是对这一问题的有效解决办法1 9 8 2 年，t r h a t c h e r 研究了s o r 迭代法的误差 界，并且得到了如下的结果【7 5 1 l i 岛1 1 2 w 一1 ) 4 i i 如1 1 2 2 一1 ) 2 ( 如，矗+ 1 ) + i i 民+ 1 1 1 2 d 2 其中，= z + 一扩为第礼次迭代结果与精确解的误差向量，如为第佗次迭代结果与 第n 一1 次迭代结果的差向量，d = u 2 ( 1 一p ；) ，p 1 为j a c c o b i j 迭代矩阵的谱半径，u 为 松弛因子 1 9 9 6 年，m a r t i n s 研究了s s o r 和u s s o r 迭代法的误差界【7 6 1 1 9 9 9 年，宋永忠讨 论了a o r 迭代法的误差界【7 8 】并证明了 1 i i 佗1 1 2 号茜 【( u 一1 ) 2 + i u ( u 一7 ) i p ；】2 i l 如1 1 2 2 ( u 一1 ) 2 ( 如，既+ - ) + 2 i u ( u 一，y ) i p ；( 1 如i ，l 厶+ 1 i ) + i i 如+ 1 1 1 2 ) 1 4 线性互补i = - j 题, ( l c p ) 孰，。 电子科技大学博士学位论文 非常浓厚兴趣，很多人纷纷参与这项研究到8 0 年代中后期，经过2 0 来年的努力， 线性互补问题在算法研究方面取得了丰硕成果很多实际问题最后都能转化为互 补问题近年来，对线性互补问题l c p ( a ，6 ) 的研究，国内外有很多研究者进行了 大量的研究 8 5 t8 6 ，9 9 , 1 0 1 , 1 0 4 ，给出了很多的求解法大致可分为置换法和迭代法，其 中，迭代法对大规模、稀疏矩阵的互补问题尤其有效 线性互补问题在计算几何、马尔科夫链、市场平衡理论，最优不变资本理论 等诸多方面有重要应用关于线性互补问题的解的唯一性、存在性以及高效的数值 计算方法，是较困难却十分有意义的研究工作，已经有许多学者的致力研究白中 治在文 8 5 通过将线性互补问题等形变形为不动点问题，构造了一类解线性互补 问题的迭代算法，研究了保证线性互补问题的解存在唯一的充分条件，并且证明 了新算法的收敛性白中治在文 8 6 采用逐次松弛加速技巧，构造了求解线性互补 问题的两类加速超松弛迭代算法，完整地建立了新算法的收敛性理论，详细地刻 画了算法的渐进收敛速度对松弛参数的依赖关系 1 5 鞍点线性系统 鞍点线性系统( s a d d l e p o i n tl i n e a rs y s t e m s ) ：# 要讨论如下稀疏线性系统的迭代解 法 ( b a t 乞) ( ：) = p ) ( 1 2 ) 其中矩阵a m 对称正定，b r m 竹为列满秩，即秩( b ) = 佗，向量z ，p 胛，向量秒，q 舻基于如上条件，鞍点线性系统存在唯一解 鞍点线性系统( s a d d l ep o i n tl i n e a rs y s t e m ) ，或称为k k t 系统，或又称之为扩展 系统( a u g m e n t e ds y s t e m ) 在最小二乘问题、最优化问题和鞍点型偏微分方程等领 域都有非常重要的应用 1 6 本文研究的内容、方法与主要贡献 针对上述问题，并结合一些实际中线性系统的特点，本文就科学计算中特殊 矩阵的迭代算法及其误差估计问题、鞍点线性系统和预处理技术进行了若干研究 其内容主要涉及非奇日矩阵的研究、线性方程组迭代算法的误差上界、鞍点线性 系统的迭代算法求解、线性互补问题的迭代算法以及线性系统预处理技术等等 本文所采用的研究方法包括： ( 1 ) 线性代数的基本理论； 6 第一章绪论 ( 2 ) 非负矩阵、非奇日矩阵、m 矩阵等特殊矩阵理论； ( 3 ) 矩阵分块和矩阵分裂技术； ( 4 ) 迭代算法； ( 5 ) 线性矩阵不等式理论； ( 6 ) 预条件处理技术； ( 7 ) 微分方程的差分法等等 主要内容和创新点包括：本文主要研究了线性系统的迭代算法及相关的误差 估计和预处理技术，主要内容和创新点包括： 1 研究了求解线性方程组的u s a o r 迭代法的误差界在线性方程组a x = 6 的 系数矩阵对称正定及具有( 1 ，1 ) 相容秩序的条件下，我们得到了u s a o r 迭代法的一 个的上界估计由于许多实际问题如偏微分方程的求解最后常转化为解大型稀疏线 性方程组，因而该结果具有实际应用价值数值结果表明估值有效 2 研究了d j e v a n s 和n m m i s s i r l i s 等学者提出的预条件同步置换迭代算法 及m p s d 迭代法的误差界在系数矩阵对称正定及具有( 1 ，1 ) 相容秩序的条件下获得 了该算法的一个误差上界估计 3 将线性互补问题将其转化为等价方程组应用矩阵分裂和迭代算法的思 想，提出了求解该问题的预条件同步置换迭代算法并在日矩阵的条件下建立了 该迭代算法的收敛理论 4 针对鞍点问题的结构特点，我们给出了m a o r 型迭代算法，并证明该方法 的收敛性推广了g h g o l u b 等学者2 0 0 1 年和2 0 0 4 年的结果 5 研究了将预条件同步置换迭代算法应用于鞍点线性系统的求解，并讨论了 鞍点线性系统的预条件同步置换迭代算法的收敛性 6 研究了求解线性方程组的预条件a o r 迭代算法，我们的结果显示在系数矩 阵为三一矩阵等条件下，预条件a o r 迭代算法比经典a o r 迭代算法的收敛速度快 7 建立了求解线性方程组的一类预条件s a o r 迭代算法，并证明了在系数矩 阵为不可约对角占优z 一矩阵的条件下该方法收敛 1 7 本文的结构安排 本节将对本文所做工作作以简单介绍除本章对本文的研究背景、对象和研究 方法给出了概要性介绍外，下面的第二章到第六章主要总结了迄今作者本人在这 一领域所作的几点工作其主要内容已在前面作了介绍，各章的结构安排如下： 第二章中主要研究非奇日矩阵的性质，获得了一种改进的非奇日一矩阵判别算 7 电子科技大学博士学位论文 法 第三章中主要研究线性方程组求解的u s a o r 迭代算法、m p s d 迭代法及预条 件同步置换迭代算法的误差估计问题在线性方程组a x = 6 的系数矩阵对称正定 及具有( 1 ，1 ) 相容秩序的条件下分别得到了u s a o r 迭代法、m p s d 迭代法和预条件 同步置换迭代算法的实用的上界估计 第四章研究了鞍点问题的m a o r 型迭代算法和m p s d 型迭代法，并证明它们 的收敛性 第五章研究了线形互补问题的预条件同步置换迭代算法，并证明预条件同步 置换迭代算法的收敛性 第六章研究了求解线性方程组的预条件a o r 迭代算法在系数矩阵为l 一矩阵 等条件下，证明了预条件a o r 迭代算法比经典a o r 迭代算法的更好的收敛速度； 同时又给出了线性方程组求解的一类预条件s a o r 迭代算法，并证明了在系数矩 阵为不可约对角占优z 一矩阵的条件下该方法收敛 在第七章中对全文进行了总结，并提出了对今后进一步工作的展望 8 第_ 章，“义对角占优矩阵的研究 2 1 引言 第二章广义对角占优矩阵的研究 广义对角占优矩阵是应用性很强的矩阵类在生物学、控制论、神经网络系 统、线性时滞系统的稳定性等方面起着重要的作用；其次对线性方程组a x = b ， 当系数矩阵a 为广义对角占优矩阵时，许多经典的迭代法，s o r 迭代法、a o r 迭 代法等都收敛；另外，广义对角占优矩阵类包含着许多其它矩阵类，如m 矩 阵类、严格对角占优矩阵类、按环路严格对角占优矩阵类、具有非零元素链 的对角占优矩阵类等因此，在理论上及实际应用上都很有价值，引起了许多 研究者的兴趣，近些年来出现了大批的研究成果 1 2 4 1 日矩阵自1 9 3 7 年由a m o s t r o w s k i z 提出至今已近七十年特别是近十年，随着电子计算机技术的迅猛发 展，日矩阵的简捷判据、迭代算法、不等式及奇异值估计理论也得到了长足的进 步1 9 7 4 年，s h i v a k u m a r 与k i nh oc h e w 提出了非零元素链的对角占优的概念，将 经典的不可约对角占优概念加以推广，成为一个重要的阶段性成果 定义2 1 1 记n = 1 1 ，2 ，礼) ，a = ( a i j ) c 似n ，h i ( a ) = l a j l ，j = n ：i a i i i i a , j l 若a 满足：1 ) i a i i l 几( a ) ；2 ) j 0 ；3 ) 对任意ig j ， 有a 的非零元素链 a i i x a i l i z a i p j ， 使，j ，则称a 为非零元素链的对角占优矩阵 设( c ) 表示n 阶复矩阵的集合，对任意矩阵a = ( a i j ) 螈( c ) ，n = 1 ，2 ，n ) ，记 人t ( a ) = i a i j ，& ( a ) = l 奶t i ，i ； j tj t 1 = t ：i 。衍i 争赴( 4 ) + & ( a ) 】，i ) ， 2 = i ：l a 托i 争a t ( a ) + 最( a ) ，i ) ， 9 电子科技大学博士学位论文 则= 1 + 2 又记 瓦= ( i 口巧i + l a j i l ) ，v i 1 ； j 1 玩= ( f o 玎i + i a j t i ) ，v i n 2 ， 2 一m 蚋a x 掣 a 的比较矩阵记为m ( 4 ) = ( 嘞) ，其中佻i = l a i i i ，嘞= 一a 巧j ，t ，j n ，i j 定义2 1 2 设a = ( ) ( c ) ，若v i n ，有l a 杌i a t ，则称a 为严格对 角占优矩阵，记为a d 若存在正对角阵x ，使a x 是严格对角占优矩阵，则 称a 为广义严格对角占优矩阵( 即非奇h 矩阵) ，记作a d 2 2 广义对角占优矩阵的判据 引理2 2 1 5 3 设4 = ( o 订) m n ( c ) ，b = m ( a ) + m 丁( a ) ( 其e e m r ( a ) 表 示m ( 4 ) 的转置) ，若b d + ，则a d 定理2 2 2 设a = ( a 纡) 地( c ) ，n 2 历，若对忱l ，有 。i i 互1b + 蒹卅等】， ( 2 1 ) j 2 一f j j 则a d + 证：设b = m ( a ) + m t ( 4 ) = ( 6 巧) n x n ，记 1 = _ i n ：吲1 6 巧i ) ， j t 2 = t n ：i b i t i i b t j l j i 不失一般性，我们假设对任意t 有凡( b ) 0 如果对某一个i 有九( b ) 0 ，则 去掉矩阵a 的第i 行与第i 列，进而研究其子矩阵 对任意i l ，由式( 2 1 ) 得 1 0 彩 嘶 + + 一” 一叼 b 陋 锴繁 = = 锄 屁 第二章广义对角占优矩阵的研究 令 r i t l + i t l i b i 篆1 6 巧i + 三吲上1 丁一 ( 2 2 ) j 1j 2 “。 由( 2 2 ) 知，对任意v i 1 ，存在 0 满足 r i b j 小卜i b i t i i 羡蚓+ ( 1 托) 吲羔1 丁一j e nj 1 2 。 f7 。邑1 6 “l + 。吾。i b i 婉： ( 1 + ) 型l r ，i 2 i 1 ， i 1 构造正对角阵x = d i a g ( x t ) ，记b x = c = ( ) n n ，下面证明c d + 如果i 1 ，贝0 r i 幻t l + i 如t l i c t , l 啪i 阱( 1 + e ) 磊1 6 巧i 旦丁2 萎j 1j v 2 ，产t 如果i n 2 ，贝0 r 1 6 让l + i i c 。, l 刊( 1 + ) 兰矿_ ( 1 托驴“+ 三慨d ) 因为7 1 ，所以，当i b i t i o 时，有 t e n 2 t t r 酬+ i b j t l 酬+ 陈i = a j ( b ) t 2t e n l t n 2t e n l t c j t # j 于是得 r i b j t l + el b i t i t 2 t e n l 磊蚓= e n l j em + ( 1 + 引，2 吲兰矿歹和 ，2 。 i 电子科技大学博士学伉论文 孰q i + ( 1 a 巧l + i ；1 ) 笔若孚 ) d ，且对v i 1 z j e n 2 。 有毗n a n t 2 a i n j 0 ，使歹j ，则a d + 证：设b = m ( a ) + m t ( a ) = ( ) n n ，记 1 = t ：i b i i l i b , j 1 ) ， j t 2 = n ：i b i i i 蚓) ， j t r i 幻t i + i 幻t 7 = t 1 ：1 6 “l 吲+ i j e n lj 2 j t t e n 2挺1 t j 显然对1 z 有啦t ，n t ，t 。j 0 ，使歹z 由( 2 3 ) 可知，对任意i 1 ，有 r l b t i + 1 t i 1 6 “i j e n l 卅姚i b , j l 矿j 川2 。 令 f 戤2 t r 1 6 “l + 1 6 “ t e v 2 t e n l t # 1 l 阮i 1 ，i 1 i n 2 ) 0 构造正对角阵x = d i a g ( x i ) ，记b x = c = ( ) n n ，下面证明g d 4 如果i 1 ，则 r 1 t i + i 幻t i t e n 2 t n i 蚓刊三吲+ 三i 旦丁2 萎h i j 1j v 2 。 j 产o j t 电子科技大学博士学何论文 由于丁= i 1 ：i q 一ei i ) 0 ，并且对v i l 7 ，有，龟，t 。j 0 ， t 卸 所以歹歹 如果i n 2 ，贝0 r 1 6 计i + 1 6 计i 悱i 上矿一篆卅龇e 1 | 当ei b i t i o 时，有 t 2 t t rei b t l + e1 6 j t i j e t i 岛j l 2 j e 。i i + ，吾n 2i i j 盟 砑厂j tj 1 强 。 l j 丢 q 3 + ( i n 3 。i + l 。，3 1 ) 三乌丢三产+ ( 1 。3 2 i + i 。2 3 i ) 三鲁丢予】= 2 6 7 1 4 3 制 弘i4 地。4 1 ) 酱讹2 4 i ) 智 - 2 7 5 7 3 由定理2 2 2 可知，矩阵a 为非奇异日矩阵 1 5 电子科技大学博士学位论文 第三章迭代算法的误差界研究 3 1 引言 随着计算机技术的发展，在计算机上可以求解的线性方程组的规模越来越大 众所周知，许多实际问题如偏微分方程的求解最后常转化为解大型稀疏线性方程 组线性方程组的解法主要有直接法与迭代法这两类迭代法由于能保持线性方程 组系数矩阵的稀疏性、对累积误差的不敏感而成为数值代数中一个非常重要的研 究课题 迭代法是按一定规则构造一个向量序y u ( x k ，使其极限向量z + 是方程组a z = b 的精确解因此，对迭代法来说一般有下面几个必须面对的问题： ( 1 ) 如何构造迭代格式； ( 2 ) 构造迭代格式的收敛问题； ( 3 ) 构造迭代格式如果收敛，收敛的速度如何? ( 4 ) 因为计算次数总是有限，所以必须讨论近似解的误差估计 因而误差界问题是数值计算中重要而又有实际意义的研究课题由于用迭代法求解 之前并不知道线性方程组的精确解，而每一次迭代得到的都仅仅是一近似解，那 么何时得到的近似解才是满足需要精度的数据是一必须考虑的问题误差界问题的 研究正是对这一问题的有效解决办法 1 9 8 2 年，t - r h a t c h e r 研究了s o r 迭代法的误差界，并且得到了如下的结果 i i 1 1 2 一1 ) 4 l i 如1 1 2 2 一1 ) 2 ( 如，如+ 1 ) + l i 如+ 1 1 1 2 d 2 其中，= z + 一x n 为第亿次迭代结果与精确解的误差向量，如为第佗次迭代结果 与第凡一1 次迭代结果的差向量，d = u 2 ( 1 一肛；) ，p 1 为j a c c o b i 迭代矩阵的谱半 径，u 为松弛因子 1 9 9 6 年，m a r t i n s 等研究了s s o r 和u s s o r 迭代法的误差界1 9 9 9 年，宋永忠讨 论了a o r 迭代法的误差界并证明了 i k n i l 2 壶( 【一1 ) 2 + l u 一7 ) i p ； 2 i i 矗1 1 2 2 一1 ) 2 ( 如，如+ 1 ) 十2 i u ( u 一7 ) i p ；( i 如i ，i 如- i - 1 1 ) + i i 如+ 1 i | 2 ) 本章我们将讨论u s a o r 迭代法、预条件同步置换迭代算法和m p s d 迭代法的 误差估计 1 6 第二三章迭代算法的误芳界研究 3 2u s a o r 迭代法的误差界研究 3 2 1u s a o r 迭代法 为了求解线性方程组 a x = b ( 3 1 ) 其中a 为竹阶非奇异实矩阵，提出了u s a o r 迭代法如果矩阵a 的对角元都不等 于0 ，那么对矩阵a 进行如下的分裂 a = d 一既一劬， 其中d = d i a g ( a ) ，一魄和一c v 分别是矩阵a 的上三角和下三角矩阵记l = d c l ，u = d c v 则u s a o r 迭代法定义如下 z n + = l - n , w l z n + u 1 ( 1 7 1 l ) 一1 d 一1 b ， z n + 1 = v , 2 ，屹z 钆+ + o j 2 ( 1 一 y 2 l ) 一1 d b ， 即， z 七+ 1 = 岛1 ，u 1 ；倪，屹x 血+ ，k = 0 ，1 ，2 ， ( 3 2 ) 其中 q 1 ，y 2 ，u 2 = u 毛，u 2 l l 1 。，u ，= ( i 一7 1 l ) 一1 ( 1 一w 1 ) i + ( 0 2 1 7 1 ) l + w l u ， v o , 2 ，u ：= ( i 一7 w ) 一1 ( 1 一w 2 ) + ( 0 2 一仇) u + u 2 纠， ，= ( i 一他u ) 一1 ( u 1 + 0 2 2 一j 1 w 2 ) i + ( d 2 ( w 1 一o i ) l + u 1 ( 0 9 2 一仇) 矿】( ，一- n l ) 一1 d 一1 b ， m ，姚( t = 1 ，2