（计算数学专业论文）几类线性系统的预处理和矩阵的hadamard积.pdf

p h d d i s s e r t a t i o no f2 010 s c h o o lc o d e ：1 0 2 6 9 a c a d e m i cn u m b e r ：5 2 0 7 0 6 0 1 0 1 2 e a s tc h i n an o r m a l u n i v e r s i t y p r e c o n d i t i o n i n gf o rs o m el i n e a r s y s t e m sa n dh a d a m a r dp r o d u c t s 0 fm a t r i c e s d e p a r t m e n t ： m a j o r ： s u b j e c t ： s u p e r v i s o r ： p h d c a n d i d a t e ： m a t h e m a t i c s c o m p u t a t i o nm a t h e m a t i c s s c i e n t i f i cc o m p u t i n g p r o f g u o l i a n gc h e n q i n g b i n gl i u 2 0 1 0 4 56 9川34m 7il-帅y 学位论文独创性声明 郑重声明：本人呈交的学位论文几类线性系统的预处理和矩阵的h a d a m a r d 积，是在华东师范犬学攻读博士学位期间，在导师的指导下进行的研究工作及取 得的研究成果除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明 确说明并表示谢意 作者猕犁 喃加年朋弓日 学位论文著作权使用声明 几类线性系统的预处理和矩阵的h a d a m a r d 积系本人在华东师范大学攻读学位 期间在导师指导下完成的博士学位论文，本论文的研究成果归华东师范大学所有 本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关 机构如国家图书馆、中信所和”知网”送交学位论文的印刷版和电子版；允许学位 论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全 国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出 版，采用影印、缩印或者其它方式合理复制学位论文 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的”内部”或”涉密”学位论文事，于 年月日解密，解密后适用上述授权 2 不保密，适用上述授权 导师签名：丝本人签名：三瓣 加，d 年妒日 涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员 会审定过的学位论文( 需附获批的( 华东师范大学研究生申请学位论文”涉密”审 批表方为有效) ，未经上述部门审定的学位论文均为公开学位论文此声明栏不 填写的，默认为公开学位论文，均适用上述授权) - o _ _ _ _ _ _ o _ _ _ _ _ _ _ _ o - - _ _ _ _ _ _ _ _ - _ _ _ - _ _ - _ _ _ _ _ - _ _ - _ - _ _ _ _ _ _ - _ _ - _ _ - _ _ _ - _ - _ _ _ _ _ _ - 博士学位论文答辩委员会成员名单 姓名职称单位备注 薛军工教授复旦大学主席 魏木生教授上海师范大学 ，吾，取教授华东师范大学 薛以锋教授华东师范大学 刘永辉教授上海金融学院 徐洁研究生秘书华东师范大学秘书 摘要 科学与工程的众多领域如高阶偏微分方程、计算流体力学、电磁学、约束优化 和线性互补问题等都离不开大型线性系统的求解研究这些大型线性系统的快速迭 代方法具有重要的理论意义和应用价值本文对m 一( 日) 矩阵线性系统和鞍点系统 的迭代求解和预处理技术进行了深入的研究同时研究了矩阵的h a d a m a r d 积的谱 半径的估计本文的研究成果可以分为三大类 1 m 一( h - ) 矩阵线性系统的预处理 本部分的研究共有两章，主要讨论了m ( ) 矩阵线性系统的预处理技术在 第二章主要研究了m 矩阵线性系统的预处理技术根据m 矩阵的结构特点，给 出了几个新的预处理子，分析了预处理g a u s s s e i d e l 迭代法的收敛性同时，利用 矩阵分裂和比较定理，理论上证明了所提预处理迭代法具有较好的收敛速度数值 试验也表明了方法的有效性 第三章研究了日一矩阵线性系统的预处理技术首先给出了日一矩阵线性系统 的广义预处理子利用日一分裂和h 一相容分裂理论，给出了预处理矩阵的收敛性 分析和参数的收敛区间 2 鞍点系统的预处理 第四章主要研究鞍点系统的预处理技术建立在正稳定和不定块预处理子的基 础上，首先讨论了由麦克斯韦方程离散出来的对称鞍点问题的预处理技术，提出了 带有参数的块三角形和块三对角预处理子对于非对称鞍点问题，给出了带有参数 的增广块三角形和块三对角预处理子同时，详细分析了预处理鞍点矩阵的谱和参 数的选取理论分析表明只要参数取适当的值，预处理鞍点矩阵的谱将高度聚集于 1 附近数值试验也表明所提预处理子的有效性 3 非负矩阵和m - 矩阵的h a d a m a r d 积 第五章主要讨论了非负矩阵和m - 矩阵的h a d a m a r d 积的谱半径的估计对于 两个非负矩阵，利用h a d a m a r d 积的性质和非负矩阵的谱半径的估计，给出了两个 非负矩阵h a d a m a r d 积的谱半径的上界对于两个m 矩阵，利用f a n 积的性质和 特征值的c a s s i n i 卵形包含定理，给出了两个m 一矩阵f a n 积的最小特征值的新的下 界这些界改进了已有的结果 华东师范大学博士论文 几类线性系统的预处理和矩阵的h a d a m a r d 积 关键词m 矩阵，h 矩阵，矩阵分裂，迭代法，预处理迭代法，收敛性，非负矩 阵，h a d a m a r d 积，f a n 积，鞍点矩阵，块预处理子，增广矩阵，k r y l o v 子空间法， 谱半径 a b s t r a c t s o l u t i o n so fl a r g e s c a l el i n e a rs y s t e m sa r ed e e p l yi n v o l v e di nm a n ya r e a so fs c i e n c e a n de n g i n e e r i n g ，s u c ha sh i g h - o r d e rp a r t i a ld i f f e r e n t i a le q u a t i o n s ，c o m p u t a t i o n a lf l u i d d y n a m i c s ，e l e c t r o m a g n e t i c s ，c o n s t r a i n e do p t i m i z a t i o na n dl i n e a rc o m p l e m e n t a r i t yp r o b _ l e m s r e s e a r c ho ff a s ti t e r a t i v em e t h o d sf o rs o l v i n gl a r g e - s c a l es y s t e m sh a si m p o r t a n t t h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a la p p l i c a t i o n s t h i sd i s s e r t a t i o nd e e p l ys t u d i e si t e r i a t i v es o l u t i o n sa n dp r e c o n d i t i o n i n gt e c h n o l o g i e so fm 一( 日一) m a t r i c e sl i n e a rs y s t e m sa n d s a d d l ep o i n ts y s t e m s m e a n w h i l e ，t h ee s t i m a t eo ft h es p e c t r a lr a d i u so fh a d a m a r dp r o d u c t so f m a t r i c e sa r es t u d i e d t h r e em a i nk i n d so fp r o b l e m sh a v eb e e ns t u d i e sa n dr e s o l v e d a sf o l l o w s ： 1 p r e c o n d i t i o n i n gf o rm - ( h - ) m a t r i c e sl i n e a rs y s t e m s t h i sp a r tc o n s i s t so ft w o c h a p t e r s ，p r e c o n d i t i o n i n gt e c h n o l o g i e sf o rm - ( h 一) m a t r i c e s l i n e a rs y s t e m sa r es t u d i e d i nt h es e c o n dc h a p t e r , p r e c o n d i t i o n i n gt e c h n o l o g i e sf o rm m a t r i c e sl i n e a rs y s t e m sa r er e s e a r c h e d a c c o r d i n gt ot h es t r u c t u r eo fm m a t r i c e s ，s o m e n e wp r e c o n d i t i o n e r sa r ep r e s e n t e da n dt h ec o n v e r g e n c ea n a l y s i so ft h ep r e c o n d i t i o n e d g a u s s s e i d e li t e r a t i v em e t h o d si sg i v e n m e a n w h i l e ，u s i n gt h em a t r i x s p l i t t i n g sa n dc o r n p a r i s o nt h e o r e m s ，w ep r o v et h e o r e t i c a l l yt h a tt h ep 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 d sh a v e b e t t e rc o n v e r g e n c es p e e d n u m e r i c a le x p e r i m e n t sa r eu s e dt oi l l u s t r a t eo u rr e s u l t s i nt h et h i r dc h a p t e r , p 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 d sf o rh m a t r i c e sl i n e a rs y s t e m s a r er e s e a r c h e d f i r s t l y ，g e n e r a l i z e dp r e c o n d i t i o n e r sf o rh m a t r i c e sl i n e a rs y s t e m sa r e g i v e n a c c o r d i n gt ot h eh s p l i t t i n ga n dt h eh c o m p a t i b l es p l i t t i n gt h e o r y , t h ec o n v e r - g e n c ea n a l y s i so ft h ep r e c o n d i t i o n e dm a t r i c e sa n dt h ec o n v e r g e n c ei n t e r v a lo fp a r a m e t e r s a r eg i v e n 2 p r e c o n d i t i o n i n gf o r s a d d l ep o i n ts y s t e m s i nt h ef o r t hc h a p t e r , p r e c o n d i t i o n i n gt e c h n o l o g i e sf o rs a d d l ep o i n ts y s t e m sa r er e _ s e a c h e d b a s e do nt h ep o s i t i v es t a b l ep r e c o n d i t i o n e ra n dt h ei n d e f i n i t ep r e c o n d i t i o n e r , p r e c o n d i t i o n i n gt e c h n o l o g i e sf o rs a d d l ep o i n tp r o b l e ma r i s i n gf o r mad i s c r e t i z a t i o no f t h e m a x w e l l se q u a t i o n sa r ed i s c u s s e d b l o c kd i a g o n a la n db l o c kt r i a n g u l a rp r e c o n d i t i o n e r s w i t hp a r a m e t e ra r eg i v e n f o rn o n s y m m e t r i cs a d d l ep o i n tp r o b l e m ，a u g m e n t a t i o nb l o c k d i a g o n a la n db l o c kt r i a n g u l a rp r e c o n d i t i o n e r sw i t hp a r a m e t e ra r eg i v e n m e a n w h i l e ，t h e a n a l y s i so ft h es p e c t r u mo ft h ep r e c o n d i t i o n e ds a d d l ep o i n tm a t r i xa n dt h ec h o i c eo ft h e 1 1 1 华东师范大学博士论文几类线性系统的预处理和矩阵的h a d a m a r d 积 p a r a m e t e ra r eg i v e n n u m e r i c a le x p e r i m e n t ss h o wt h a tt h eq u a l i t yo ft h ep r e s e n t e db l o c k p r e e o n d i t i o n e r si sb e t t e rt h a nt h a to ft h ec o r r e s p o n d i n gb l o c kp r e c o n d i t i o n e r s 3 h a d a m a r dp r o d u c t si n v o l v i n gn o n n e g a t i v em a t r i c e sa n dm - m a t r i c e s i nt h ef i f t hc h a p t e r , t h ee s t i m a t eo ft h es p e c t r a lr a d i u so fh a d a m a r dp r o d u c t so fn o n n e g a t i v em a t r i c e sa n dm m a t r i c e si sd i s c u s s e d f o rt w on o n n e g a t i v em a t r i c e s ，u s i n gt h e p r o p e r t i e so ft h eh a d a m a r dp r o d u c t so fm a t r i c e sa n dt h ee s t i m a t eo ft h es p e c t r a lr a d i u s o fn o n n e g a t i v em a t r i c e s ，a nu p p e rb o u n d sf o rt h es p e c t r a lr a d i u so fh a d a m a r dp r o d u c t s o ft w on o n n e g t i v em a t r i c e sa r eg i v e n f o rt w om m a t r i c e s ，u s i n gt h ep r o p e r t i e so ft h e f a np r o d u c t so f m a t r i c e sa n dt h eo v a l so fc a s s i n io fe i g e n v a l u e s ，t h en e wl o w e rb o u n d so f m i n i m u me i g e n v a l u eo ff a np r o d u c to ft w om m a t r i c e sa r eg i v e n s o m eb o u n d si m p r o v e t h er e s u l t i n gr e s u l t s k e yw o r d s ：m - m a t r i c e s ，m a t r i xs p l i t t i n g ，h m a t r i c e s ，l 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 e di t e r a t i v em e t h o d ，c o n v e r g e n c e ，n o n n e g a t i v em a t r i c e s ，h a d a m a r dp r o d u c t s ，f a n p r o d u c t ，b l o c kp r e c o n d i t i o n e r , a u g m e n t a t i o nm a t r i c e s ，k r y l o vs u b s p a c em e t h o d ，s p e c - r a lr a d i u s 第一章 1 1 1 2 1 3 第二章 2 1 2 2 2 3 2 4 目录 绪论 研究问题和背景 本文的主要研究内容。 符号表 m - 矩阵的预处理技术 经典迭代法介绍 预备知识 m 一矩阵的预处理及其收敛分析 小结和展望 第三章h - 矩阵的预处理技术 3 1 预备知识 3 2 日一矩阵的预处理及其收敛分析。 3 3 小结和展望 第四章 4 1 4 2 4 3 4 4 第五章 5 1 5 2 5 3 5 4 鞍点问题的预处理技术 预备知识 对称鞍点问题的预处理技术。 非对称鞍点问题的预处理技术 小结和展望 非负矩阵和m - 矩阵的h a d a m a r d 积 预备知识 非负矩阵的h a d a m a r d 积的谱半径的估计 m 一矩阵的f a n 积的最小特征值的估计 小结和展望 参考文献 读博士期间的科研成果 致谢 v 1 ，4 5 6 6 加h n 勉砣弘卯 铝勰如碣 缈矽记眩好 舛 惦 第一章绪论 5 1 1 研究问题和背景 在自然科学研究和工程技术的应用中，许多问题的解决最终都要归结为一个线 性方程组的求解： a x = b ( 1 1 ) 其中系数矩阵a c 似”非奇异，b c ”已知，z c n 未知比如，核物理和计 算流体力学，结构和非结构问题的有限元分析，电磁学中能量守恒方程，油藏模拟 等科学和工程领域；投入产出模型，线性互补问题，约束优化等经济和金融领域都 离不开线性方程组的求解【参见文献2 ，7 ，1 8 ，2 3 ，2 6 2 9 ，4 4 ，4 6 ，5 2 ，8 0 ，1 0 7 ，1 3 7 ，1 5 0 关于如何求解线性方程( 1 1 ) 的问题我们并不陌生，在初中就已经熟悉了二元一 次和三元一次线性方程组的解法，而且也没有感到有什么太大的困难然而随着有 限元在偏微分方程的重要应用，实际问题离散出来的未知数个数不断增加，求解就 会变得越来越困难，当n 很大时，用手工计算已经变得不可能，只能借助于计算机， 而计算机只能表示有限精度的数，计算过程必然要有误差出现这样一来，如何快 速有效地利用计算机来求解大型线性方程组就成为科学与t 程计算领域研究的核心 问题 求解线性方程组的方法一般可以分为直接法和迭代法两大类直接法的主要思 想是利用方程组的同解变形，逐步将原方程组转化为一个简单的、易于求解的特殊 形式的线性方程组【参见文献3 5 如g a u s s 消元法、c h o l e s k y 三角分解法等这种 方法一般比较稳健，适用于规模较小，系数矩阵为低阶或稠密线性方程组而对高 阶稀疏线性方程组来说，由于直接法有存储量大、程序复杂、不能保持系数矩阵稀 疏性等不足和问题规模的限制，迭代法就成为求解线性方程组的必要选择渗见文 献9 ，1 8 ，4 2 ，5 3 ，6 5 ，7 0 ，9 5 ，1 0 0 ，1 4 4 ，1 5 5 ，1 6 3 ，1 6 6 1 迭代法就是从给定的一个初始值出发，按照某种规则构造一个向量序列，使其 极限向量足方程组( 1 1 ) 的精确解迭代法一般可以表述为； x k = 五( x k 一1 ，x k z ) ，k = l ，l + 1 ，( 1 2 ) 其中五称作迭代算子，x k 一1 ，x k z 为迭代初值，通常迭代法( 1 2 ) 为f 步迭代 法；z = 1 时，迭代法称为单步迭代法如果迭代算子瓦与k 无关，迭代法称为定 常迭代法，否则称为非定常迭代法迭代法发展已有久远的历史五十年代到七十 1 华东师范大学博士论文 几类线性系统的预处理和矩阵的h a d a m a r d 积 年代，随着电子计算机的迅速发展和工程科学的实际需要，构造有效迭代法求方程 组的近似解成为了科学与工程的重要课题因此这期间发展了很多有效的迭代法， 如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 o r 迭代 法等许多定常迭代法【参见文献1 ，9 ，1 5 ，5 3 ，6 5 ，8 4 ，1 3 1 ，1 4 4 后来，迭代法又出现 了另外一个重要的发展时期，在这一时期，发展了被称为二十世纪十类最重要的数 值方法之一的k r y l o v 子空问方法【参见文献5 1 1 早在五十年代早期，h e s t e n e s 和 s t i e f e l 就提出来共轭梯度法( c g ) 【参见文献s 4 ，当时c g 被作为直接法并没有引起 人们很多的注意直到1 9 7 1 年，r e i d 将c g 作为迭代法并与预处理进行结合才开 始了广泛的研究【参见文献1 3 9 之后以c g 法为代表的k r y l o v 子空间方法的研究 便如雨后春笋般出现，比如研究对称情形的极小残量法( m i n r e s ) 、研究非对称情 形的广义极小残量法( g m r e s ) 、以及c g n r 、c g n e 、c g s 、q m r 、b i c g s t a b 等子空间方法的出现【参见文献4 ，5 5 ，5 9 ，6 4 ，7 0 ，7 4 ，1 4 3 1 4 5 ，1 5 4 给定一个初始近似解向量x o ，定义初始误差r 0 = b a x o 如果第k 步迭代z 詹 满足 其中 x k x o + l c k ( a ，伯) ，k = 1 ，2 ，( 1 3 ) 瓦缸( a ，r 0 ) 兰s p a n r o ，a r o ，a 奄一1 r o )( 1 4 ) 表示由a 和7 0 产生的第k 个k r y l o v 子空间易知d 兰d i m 咒n + m ( a ，r 0 ) 佗+ m ，即 k ：i ( a ，r 0 ) c ck , d ( a ，r o ) = = k + 仇( a ，伯) ，r k - l - c k ( 1 5 ) 其中瓯是k 维空间如果瓯是k r y l o v 子空间，则上述投影方法称为k r y l o v 子空 间方法瓯选取的不同将会产生不同的如上所述的k r y l o v 子空间方法 求解线性方程组( 1 1 ) ，如果系数矩阵是低阶或者稠密的，一般采用直接法；对 于大型稀疏方程组，一般来说迭代法比较受欢迎但是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 o r 迭代法往往依赖于参数，而 且收敛较慢，甚至发散由于许多大型问题的系数矩阵的不定性和坏的谱性质，直 接使用k r y l o v 子空间方法，收敛比较慢有的甚至出现停滞这就促使人们发展预处 理技术渗；见文献9 ，1 7 ，1 4 0 ，1 4 4 预处理就是要找到合适的预处理子p ，将方程( 1 1 ) 变为等价的形式 p 一1 a x ：p 一1 6 2 ( 1 6 ) 华东师范大学博士论文几类线性系统的预处理和矩阵的h a d a m a r d 积 对大型稀疏线性方程组来说，如果考虑使用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 o r 迭代法等定常迭代法，主要是希望能减小预处 理矩阵的迭代矩阵的谱半径如果考虑使用k r y l o v 子空间方法，一般说我f j 希望能 够改善系数矩阵的谱性质如果p 。a 的谱在远离原点的地方聚集，使用k r y l o v 子 空间方法往往有较快的收敛速度一般选取预处理子应满足下列条件： 1 预处理子p 是矩阵a 的一个较好的近似； 2 预处理矩阵p a 的条件数较小或者其谱半径较小； 3 预处理矩阵p _ l a 的谱比较集中 此外，预处理子的选取除了尽量满足上面的条件，一般还要考虑实际问题比 如对于m 一( 日一) 矩阵方程，预处理子的选取如果从减小谱半径出发，可以从m 矩 阵本身的特点选择稀疏的预条件像j a c o b i 预处理子、g a u s s s e i d e l 预处理子和s o r 预处理子等；如果从减少a 的条件数出发，可能会选取近似逆预处理子对于具有 特殊结构的鞍点问题的预处理的研究已经相当成熟，像块预处理子、近似逆预处理 子、h s s 预处理子和约束预处理子等【参考文献5 ，1 2 1 4 ，1 7 ，1 9 2 l ，2 3 2 5 ，3 0 3 3 ， 3 7 - 3 8 ，4 1 ，5 4 ，7 6 ，11 7 ，1 2 3 ，1 2 7 ，1 4 4 ，1 6 9 由于线性方程组在科学工程中的重要应用，我们的论文主要从三章来考虑三种 形式的线性方程组，系数矩阵为m ( 日) 矩阵的线性方程组和鞍点形式的线性方程 组的预处理技术我们的主要目的足建立在已有研究的基础上，通过对实际问题的 考虑，探索合适的预处理子，以达到提高计算效率的目的 3 华东师范大学博士论文几类线性系统的预处理和矩阵的h a d a m a r d 积 1 2 本文的主要研究内容 本节我们介绍本书的基本内容 第一章给出了本书中常用到的符号与记号，介绍了本书的基本内容以及研究的 问题和背景 第二章主要研究了m 矩阵线性系统的预处理技术根据m 一矩阵的结构特点， 给出了几个新的预处理子，分析了预处理g a u s s s e i d e l 迭代法的收敛性同时，利 用矩阵分裂和比较定理，理论上证明了所提预处理迭代法具有较好的收敛速度数 值试验也表明了方法的有效性 第三章研究了h 一矩阵线性系统的预处理技术首先给出了h 一矩阵线性系统 的广义预处理子利用日一分裂和日- 相容分裂理论，给出了预处理矩阵的收敛性 分析和参数的收敛区闻 第四章主要研究鞍点系统的预处理技术建立在正稳定和不定块预处理子的基 础上，首先讨论了由麦克斯韦方程离散出来的对称鞍点问题的预处理技术，提出了 带有参数的块三角形和块三对角预处理子对于非对称鞍点问题，给出了带有参数 的增广块三角形和块三对角预处理子同时，详细分析了预处理鞍点矩阵的谱和参 数的选取理论分析表明只要参数取适当的值，预处理鞍点矩阵的谱将高度聚集于 1 附近数值试验也表明所提预处理子的有效性 第五章主要讨论了非负矩阵和m 一矩阵的h a d a m a r d 积的谱半径的估计对于 两个非负矩阵，利用h a d a m a r d 积的性质和非负矩阵的谱半径的估计，给出了两个 非负矩阵h a d a m a r d 积的谱半径的上界对于两个m 一矩阵，利用f a n 积的性质和 特征值的c a s s i n i 卵形包含定理，给出了两个m 一矩阵f a n 积的最小特征值的新的下 界这些界改进了已有的结果 4 华东师范大学博士论文 几类线，| ! 生系统的预处理和矩阵的h a d a m a r d 积 ( 扎) r “( c n ) r + 兄” g ”x ” ( a ) a i ，j d e t ( a ) i a 丁 a 何 a i a - 1 ”0 a 0 a o p ( a ) a ( a ) d i a g ( d l ，如) 0 = y + z 口 1 3 符号表 5 自然数集 1 ，2 ，几) 实( 复m 维空间 正实数集 mx n 实矩阵集 ? 7 2 扎复矩阵集 巴拿赫空间 占上的有界算子 a 的零空问 矩阵a 的第i ，j 个位置的元素 方阵a 的行列式 钆阶单位矩阵 矩阵a 的转置 矩阵a 的共轭转置 a 的元素取绝对值得到的矩阵 矩阵a 的逆矩阵 f r o b e n i u s 范数 矩阵a 是非负矩阵 矩阵a 是正矩阵 矩阵a 的谱半径 矩阵a 的谱 以d ，如为对角元的对角矩阵 矩阵的h a d a m a r d 积 矩阵的f a n 积 向量z 和y 的e u c l i d e a n 内积 表示证明结束 第二章m 一矩阵的预处理技术 2 1 经典迭代法介绍 m 矩阵是计算数学中的重要矩阵类，它在生物学、数学物理、金融数学和社 会科学等众多领域都有重要的应用如经济价值模型矩阵和反网络分析的系数矩阵 以及偏微分方程离散后的系数矩阵、经济学中的投入产出分析模型矩阵、最优化中 的线性互补问题和概率统计中的m a r k o v 链等问题都和m - 矩阵有着非常密切的联 系作为矩阵理论的一个重要分支，经过数学家和经济学家的共同努力，m - 矩阵的 研究得到迅速发展和不断完善【参考文献3 ，1 0 ，2 2 2 3 ，2 6 ，5 6 5 7 ，8 2 ，8 6 8 7 ，1 4 4 ，1 5 5 ， 1 6 1 ，1 6 4 ，1 6 6 随着计算机技术的发展，计算机的存储量日益增加，计算速度也迅速加快由 于直接法大多数需要对系数矩阵进行分解，因而不能保持系数矩阵的稀疏性然而 实际应用中，特别是偏微分方程求解时，往往是大型稀疏线性方程的求解问题因 此寻求能够保持稀疏性的有效算法足科学与工程计算研究的一个重要课题 目前最常用的求解大型稀疏线性方程的方法是迭代法我们这节介绍几个基本 的迭代法并讨论其收敛性【参见文献9 ，8 2 ，1 4 4 ，1 4 8 1 4 9 ，1 5 5 ，1 6 3 给定非奇异线性方程组 a x = b ，z ，b r n ， ( 2 1 ) 其中a 是非奇异矩阵，且其对角元足非零数，b 即是一个给定的列向量 我们将a 作如下分裂 a = d 一三一u 其中d ，l ，u 分别是矩阵a 的对角形、严格下三角和严格上三角矩阵 贝| l 等式( 2 1 ) 可以等价的写为 d x = ( l + u ) x + b ( 2 2 ) 从等式( 2 2 ) ，可以从选定的初始向量x 0 出发，迭代地产生向量序列 z 麾) ： d x k + 1 = ( l + u ) x k + b ( 2 3 ) 由于d 是非奇异矩阵，式( 2 3 ) 可以变为 。k + 1 = d 一1 ( l + u ) x k + d b ，庇0 6 华东师范大学博士论文几类线性系统的预处理和矩阵的h a d a m a r d 积 我们称这种迭代法为j a c o b i 迭代法，b = d _ 1 ( l + u ) 称为j a c o b i 迭代矩阵 如果我们将等式( 2 1 ) 等价的写为 ( d l ) x = u x + b ( 2 4 ) 从等式( 2 4 ) ，选定初始向量x 0 ，迭代地产生向量序列 ) ： ( d l ) 2 7 k + 1 = u x k + b ( 2 5 ) 由于d l 是非奇异矩阵，式( 2 5 ) 可以等价的变为 x k + l = ( d l ) 一1 己厂z 七+ ( d l ) 一1 b ( 2 6 ) 我们称这种迭代法为g a u s s s e i d e l 迭代法，b = ( d l ) _ 1 u 称为g a u s s s e i d e l 迭 代矩阵 对g a u s s - s e i d e l 迭代法来说，它的一个明显好处足在编写程序时存储量减少了， 但是计算分量的次序是不能改变的为此，在g a u s s s e i d e l 迭代中令z = z 七+ l 一矾， 则有 2 7 k + i = 2 7 k + x x ( 2 7 ) 也就是说，对g a u s s s e i d e l 迭代法来说，+ l 可以看作在向量2 7 k 上加上修正项z 而碍到的若在修正项前面加上一个参数u ，便得到松弛法的计算公式 其中u 称为松弛因子，该迭代法称为s o r 迭代法当u 1 时叫超松弛法；当u 1 时叫低松弛法；u = 1 时就是g s 迭代法因为( i w d - 1 三) _ 1 存在，所以( 2 8 ) 式 可以改写为 z 七+ 1 = k z + w ( d w l ) 一1 b ，( 2 9 ) 其中l 。= ( d w l ) 以【( 1 一w ) d + u 明称为松弛法的迭代矩阵 为了求解方程( 2 1 ) ，a h a d j i d i m o s 【8 1 】根据矩阵a 的不同分裂，给出了更为一 般的含有两个参数的a o r 迭代法，并获得了有关a o r 迭代法的一些收敛理论 a o r 迭代法的迭代矩阵为 正，u = ( d 一7 l ) 一1 ( 1 一w ) d + ( 叫一，y ) 三+ u u 】，( 2 1 0 ) 7 d + ud + ldu 缸时 e u + 一 巩0 i | = 华东师范大学博士论文几类线性系统的预处理和矩阵的h a d a m a r d 积 其中u 和7 两个非负实数，并且u 0 ，0 7 u 1 易知当u = - r 时，a o r 迭 代法就变成了s o r 迭代法；= 7 = 1 时，a o r 迭代法就变成了g a u s s - s e i d e l 迭 代法 我们将上面的迭代法给出一般的形式 x k + l = s x k + c ，k = 0 ，1 ，2 ，( 2 1 1 ) 形如( 2 1 1 ) 式的迭代法称为单步线性定常迭代法其中s 称为迭代矩阵，c 称为常 数项，x 0 称为初始向量如果迭代法( 2 1 1 ) 是收敛的，记其产生的向量序列的极限 为矿，则z 4 必须满足 x = s x + c ，k = 0 ，1 ，2 ， ( 2 1 2 ) 假定矿足方程( 2 1 2 ) 的解，称向量玑= x k 一矿为的误差向量则迭代法( 2 1 1 ) 收敛的充要条件是对任意给点o 都有l i m 七一o o 讥= 0 而且得到y k + 1 = s 玑，忌= 0 ，l ，从而我们得到 玑= 铲y o ，k = 0 ，1 ，2 ，( 2 1 3 ) 由此可见，对任意的加都有玑啼o ( k 辛。c ) 的充要条件是妒，0 ( 七斗o 。) 由矩阵分析的理论可知，这等价于s 的谱半径p ( s ) 1 则迭代法( 2 1 1 ) 收敛的充 要条件是p ( s ) o ) 同样的，对矩阵a = ( a t j ) 研加，如果 对所有的 ，j ，a i j o ( a t j 0 ) ，则称矩阵a 称为非负( 正) 矩阵，记为a o ( a 0 ) 设b = ( b i j ) r 似“，如果对所有的i ，j ，a i j b i j ( a i j 岵) ，则a b ( a b ) 矩阵 a 的绝对值记为i a i = ( i o t ，j 1 ) 如果一个矩阵a 的有向图是强连通的，则矩阵a 是 不可约的 设是实巴拿赫空间，7 是它的对偶，( ) 是从投影到的有界线性算 子对于空间上的范数之间我们不加区别，一般简单的记为| 1 当表示n - 维实 空间舻时，z ( ) 表示一个由n 阶矩阵组成的空间 假定是由正规锥k 生成的空间，其中k 具有下列性质：( 1 ) k + kck ；( 2 ) 对n 0 ，a kck ；( 3 ) kn ( 一k ) = o ；( 4 ) g = k ，其中k 表示k 的闭包；( 5 ) 对任 何z ，y k ，存在盯 0 满足忙+ y l i 盯忙m 当= 舻，由它生成的锥是一个非负向 量的集合k = 毗 对所有的x k ，k 7 = z 7 7 ：( x ，x 7 ) = x t ( z ) o ) 可以证明7 是由闭正规 锥k 7 生成的空间如果a 7 在对偶锥上存在一个f r o b e n i u s 特征向量，则称a z ( 纠 具有性质”口，即存在x 7 k 满足a 7 2 7 = p ( a ) x 7 ，其中p ( a ) 表示a 的谱半径当 = 舻，k = 墩，z ( ) 上的所有算子也就足矩阵具有性质”口【参见文献2 6 ，8 6 - 8 7 ， 1 1 9 下面我们给出一些定义和引理： 定义2 2 1 【1 5 5 】设a j 妒n 为z 一矩阵，如果a 一1 o ，则称a 为m 一矩阵 定义2 2 2 f 1 5 5 1 设a 舻跏为z 一矩阵，则a 为非奇异m 矩阵当且仅当； 仃) a 的所有主子式都是正的； 纠a 的