（应用数学专业论文）线性方程组和鞍点问题的松驰型迭代算法与预条件技术.pdf

摘要 摘要 线性代数方程组的求解是科学与工程计算领域中最常见的一个问题，因而线性 代数方程组求解方法的研究是大规模科学与工程计算的核心，具有非常重要的理论 价值和应用价值本文深入地研究了求解线性代数方程组的迭代解法，特别地，系统 分析了基于矩阵分裂迭代法的收敛性和比较理论，并且讨论了求解鞍点问题的迭代 方法 提出了一种迭代算法用来搜寻使得矩阵a d 为严格对角占优的正对角矩阵d 对于任意的不可约m 矩阵( 或者日矩阵) a ，利用矩阵a 的特殊性质和矩阵中元素之 间的关系，改进了已有的算法，找到一个正对角矩阵d ，使得矩阵a d 是一个严格对 角占优矩阵进一步通过获得的结果得到了对日矩阵谱半径上界的估计 基于求解微分方程的波形松弛方法，结合两步迭代法和多分裂方法，研究了两 步波形松弛方法的相关理论首先，完善了定常的两步波形松弛方法的研究，分析了 当系数矩阵是日。矩阵时迭代法的收敛理论，以及在h e r m i t i a n 正定矩阵的情况下，给 出关于比较理论的一种新的证明方法其次，系统地分析了非定常的多分裂两步波 形松弛方法深入地研究了当系数矩阵是一些特殊矩阵时，迭代法的收敛理论和比 较理论，数值实验显示了理论的有效性这些成果为迭代法的选择提供了一定的理 论依据 研究了鞍点系统的迭代解法首先基于求解鞍点问题的s o r 1 i k e 迭代法，建立 一类修正的广义s s o r 方法，研究分析了使得此方法收敛的松弛因子的取值区域其 次，通过构造不同的矩阵分裂，建立了两类新的广义s o r 方法给出了两种相对应的 算法，并且讨论了两种算法收敛的参数的取值区域同时通过对参数进行具体地选 取，给出相对应的算法，并且在数值实验中得到了验证 研究了一类交替的修正预条件g a u s s s e i d e l 迭代法，给出了收敛理论和比较理 论，进而说明对于此类修正预条件子迭代法的收敛速度比经典的s o r 算法的收敛速 度要快同时又分析了多分裂情况下修正的g a u s s s e i d e l 迭代法的收敛性其次，对 于奇异线性系统，研究了当分裂矩阵也是奇异情况下的收敛性 关键词：m 矩阵，日矩阵，h e r m i f i a n 正定矩阵，对角占优，矩阵分裂，两步迭代法，鞍 点问题，奇异矩阵 a b s t r a c t 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 i s ew i d e l yi nv a r i o u ss c i e n t i f i ca n de n g i n e e r i n gf i e l d s r e s e a r c h e so fm e t h o d sf o rs o l v i n gl a r g e - s c a l es p a r s es y s t e m so fl i n e a ra l - g e b r a i ce q u a t i o n sh a v ei m p o r t a n tt h e o r e t i cs 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 i nt h i s d i s s e r t a t i o n , w ed e 印l ys t u d yt h ei t e r a t i o ns o l u t i o n so fl i n e a ra l g e b r a i cs y s t e m s ，i n v e s t i g a t et h ec o n v e r g e n c ea n dc o m p a r i s o nt h e o r e m so fm a t r i xs p l i t t i n gm e t h o d sa n dd i s c u s s t h ei t e r a t i o ns o l u t i o n so fs a d d l ep o i n tp r o b l e m s a ni t e r a t i v em e t h o di ss t u d i e dt os e a r c ha s c a l i n gm a t r i xf o rd i a g o n a ld o m i n a n c e f o r a n y i r r e d u c i b l em - m a t r i xa ，a ni m p r o v e di t e r a t i v em e t h o db a s e do nt h es p e c i a ls t r u c t u r e s o fm - m a t r i c e si sp r e s e n t e dt of i n dap o s i t i v ed i a g o n a lm a t r i xds u c ht h a ta di ss t r i c t l y d i a g o n a l l yd o m i n a n c e f u r t h e r m o r e ，f r o mt h i si t e r a t i v ea l g o r i t h m ，al o w e rb o u n df o rt h e s p e c t r a lr a d i u so fh m a t r i xi sg i v e n t w o - s t a g ei t e r a t i v em e t h o da n dm u l t i s p l i t t i n ga l g o r i t h mf o rw a v e f o r mr e l a x a t i o n m e t h o da r ei n v e s t i g a t e d a l s ot h ec o n v e r g e n c ea n dc o m p a r i s o nt h e o r e m sb yc h o o s i n g d i f f e r e n ts p l i t t i n g so fm a t r i c e sa l eo b t a i n e d w cf i r s tp r e s e n tac o n v e r g e n c et h e o r e mo f t w o - s t a g ew a v e f o r mr e l a x a t i o nm e t h o d w h e nt h ec o e f f i c i e n t m a t r i xi sa nh - m a t r i x m o r e - o v e r , c o m p a r i s o nt h e o r e mf o rt h i si t e r a t i v em e t h o do fh e r m i t i a np o s i t i v ed e f i n i t em a t r i x i sa l s oo b t a i n e d ，w h i c he n r i c h e ss o m e e x i s t i n gl i t e r a t u r e s s e c o n d l y , w ec o n s i d e ra n o n - s t a t i o n a r ym u l t i s p l i t t i n gt w o s t a g es t r a t e g yf o rw a v e f o r mr e l a x a t i o ni t e r a t i o n ，s o l v i n gt h e i n i t i a lv a l u ep r o b l e mo fo r d i n a r yd i f f e r e n t i a le q u a t i o n s t h ec o n v e r g e n c et h e o r e m sa n d t h ec o m p a r i s o nt h e o r e m sa l ed i s c u s s e di nd e t a i lw h e nt h ec o e f f i c i e n tm a t r i xh a ss o m e s p e c i a lp r o p e r t i e s ，w h i c hp r o v i d et h e o r e t i c a lb a s ef o rt h ec h o i c eo fi t e r a t i o nm e t h o d s n ei t e r a t i v es o l u t i o n so fs a d d l ep o i n tp r o b l e m sa l es t u d i e d am o d i f i e dg e n e r a l i z e d s y m m e t r i cs o rm e t h o dw h i c hg i v e st h r e ep a r a m e t e r st of i n dt h es o l u t i o no fa u g m e n t e d s y s t e m si sf i r s t l yp r o p o s e d t h i sm o d i f i e dg e n e r a l i z e ds s o r m e t h o di st h ee x t e n s i o no f t h es o r - l i k em e t h o d a n dt h ec o n v e r g e n c eo ft h i sn e wa l g o r i t h mi sd i s c u s s e du n d e rs u i t - a b l er e s t r i c t i o n so nt h ep a r a m e t e r s s e c o n d l y ，t w og e n e r a l i z e ds o rm e t h o d sf o rs o l v i n g t h es a d d l ep o i n tp r o b l e m sa r ep r e s e n t e db yd i f f e r e n ts p l i t t i n g so ft h ec o e f f i c i e n tm a t r i x a n dt h ec o n d i t i o n so ft w oa l g o r i t h m sf o rt h e i rc o n v e r g e n c ea r ed e r i v e & r e s p e c t i v e l y f u r - t h e r m o r e ，b yc h o o s i n gd i f f e r e n tp r e c o n d i t i o n i n gm a t r i c e s ，w eg e td i f f e r e n tg e n e r a l i z e d a b s t r a c t i t e r a t i o ns c h e m e sw i n ld i f f e r e n tc o n v e r g e n tr a t e s a na l t e r n a t i n gi t e r a t i v em e t h o db a s e do nm o d i f i e dg a u s s s e i d e lm e t h o di si n v e s t i - g a t e d n es p e c t r a lr a d i u so fi t e r a t i v em a t r i xo f t h i sn e wm e t h o di sp r o v e dt ob es m a l l e r t h a nt h a to ft h es o rm e m o d i ta l s oi n d i c a t e st h a tt h ea l t e r n a t i n gm o d i f i e dg a u s s s e i d e l m e t h o di sc o n v e r g e n t t h e nt h ec o n v e r g e n c et h e o r e mf o rt h en o n s y m m e t r i cp o s i t i v e s e m i d e f i n i t el i n e a rs y s t e mi ss t u d i e dw h e na = m n ，w h e r em i sn o ta l w a y sn o n s i n g u l a r n en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rs e r n i n o r mc o n v e r g e n c ea r eg i v e n k e y w o r d s ：h m a t r i x ，m - m a t r i x ，h e r m i d a np o s i t i v ed e f i n i t em a t r i x ，d i a g o n a ld o m i n a n t ， m a t r i xs p h t t i n g ，t w o s t a g ei t e r a t i o n ，s a d d l ep o i n tp r o b l e m ，s i n g u l a rm a t r i x r r l 主要符号对照表 n r r + 0 c n r 竹 c m n r m n i a t a 日 i a l l i a i i z l i a l l ( a ，b ) a 0 a 0 a 0 a - 0 p ( a ) 死( a ) ( a ) d i a g ( d l ，d t z ) t r i d i a g ( a ，b ，c ) q 主要符号对照表 数集 1 ，2 ，佗) 自然数集 实数集 正实数集 空集 复n 维列向量空间 实佗维列向量空间 mx 佗复矩阵集 仇x 死实矩阵集 单位矩阵 矩阵a 的转置 矩阵a 的共轭转置 矩阵a 各元素取绝对值的矩阵 矩阵以的谱范数 矩阵a 的无穷大范数 向量a ，6 的e u c l i d e a n 内积 矩阵a 是非负矩阵 矩阵a 是正矩阵 矩阵a 是h e r m i t i a n 正半定矩阵 矩阵a 是h e r m i t i a n 正定矩阵 方阵a 的谱半径，若a 为非负矩阵，即为p e r r o n 根 矩阵a 的值域 矩阵a 的零空间 以d l ，厶为对角元的对角矩阵 以b 为主对角元，o 为下次对角元和c 为上次对角元的三对角矩阵 为k r o n e c k e r 积符号 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：砷年d 月子日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：叠墨导师签名： 嗍唧即月3 日 第一章绪论 第一章绪论 1 1 研究背景和意义 科学技术的进步和信息技术的迅猛发展，使得现代社会正经历着由工业经济向 知识经济的转交，以计算机为载体的信息技术正逐渐改变着人们的生活方式，思维 方式和工作方式计算机最明显的功能就是高速度地进行大量的数值计算因此，在 计算机这一强大工具的支持下，数学的独特魅力在解决科技生产生活等重大实际问 题中得到了充分的体现，其中与计算机算法有着紧密联系的计算数学显得尤为突 出当今计算数学的研究领域中，大型稀疏线性方程组的高效求解方法是重要的研 究课题之一，同时也是现代科学工程计算和许多应用领域遇到的一个共同问题，比 如，在流体力学，计算电磁学，油藏模拟以及金融工程等领域建立的数学模型中常常 需要求解微分方程，一般采用差分和有限元等方法，将原方程转化为求解大型稀疏 线性方程组的问题 尽管计算机技术有了很大的发展，并行计算技术和并行计算机也在日益普及， 但是大量的在应用领域产生的问题要求建立更为精确和复杂的模型，同时也需要对 数学模型进行高精度求解这样往往使得求解线性方程组所需要的时间在整个问题 的总计算时间中占有很大比重，成为快速计算的瓶颈，所以探讨方程组的高效解法 非常重要高效不仅仅是希望能够提高计算的速度，而且也希望可以减少计算机的 存储量 线性代数系统的求解方法一般分为直接法和迭代法两类对于一些中小型线性 系统，比如维数在1 0 0 0 阶以内，常常选用直接法来求解直接法的优点是在不计舍入 误差的情况下可以得到准确解，但是如果系数矩阵的条件数很大，舍入误差就会影 响所求出解的准确性同时由于存储的问题，直接法往往不能保持系数矩阵的稀疏 性。导致需要耗费大量的计算时间和存储空间，这对于求解过程是很不理想的 与直接法相比，迭代法能够充分地利用矩阵的稀疏性来减少计算量，能很好地 满足对快速计算的需要在迭代过程中只需要存储系数矩阵，以及对应预处理的辅 助矩阵和向量，所以目前对迭代法的研究已经成为国内外研究的热点，在实际应用 中，迭代法也已经取代直接法成为求解大型稀疏线性方程组的类最重要的方法 迭代法的种类很多，般分为定常迭代法和非定常迭代法，每种迭代方法都有其优 势和不足同时，迭代法的收敛性又依赖于方程组系数矩阵的性质，因此迭代法的适 用性，系数矩阵特征值的分布等都成为很多学者致力研究的热点问题 电子科技大学博士学位论文 1 2 研究的现状 1 2 1 线性方程组的迭代解法 大型稀疏线性方程组的求解问题一般有如下形式： a z = 6 其中，a c 似竹是非奇异的，b c n 已知和z c n 未知对于方程组( 1 1 ) 的求解，一 般采用迭代法在上- - d , 节中可知迭代法通常分为定常迭代法和非定常迭代法，如 果迭代式有如下的表示： z = 妒七( z 七一1 ，z 七一。) ，k = 2 ，f + 1 ， ( 1 2 ) 其中称作迭代算子，z 七一，x k - l 是迭代初值若迭代算子慨与七无关，即兰垆， 则称迭代式( 1 2 ) 为定常迭代法，否则称为非定常迭代法如果从迭代步数的角度考 虑，迭代式( 1 2 ) 又可以称为2 步迭代法，当2 = 1 时就是单步迭代法 基于矩阵分裂的定常迭代法形式简单，易于计算机实现从一开始的经典迭 代法，包括j a c o b i 迭代法，g a u s s s e i d e l 迭代法，超松弛( s o r ) 迭代法与分块迭代法b j ， b g s ，b s o r 和其相应的对称型迭代法，以及随着研究地深入，近些年提出的快速松 弛( a o r ) 迭代法，交替迭代法，不完全分解法和p e 方法等等，都是以矩阵分裂为前提 来研究迭代矩阵的收敛性，从而实现线性方程组问题的求解，并应用到相应的实际 情况中与前面的经典迭代法相比，后来出现的迭代法具有更好的收敛性，因此具有 更大的实用价值，特别是对比较病态的系数矩阵的方程组更是如此本小节依次介 绍基于矩阵分裂的基本迭代方法，包括单分裂迭代法，两步迭代法，并行多分裂方法 以及简单的预处理思想 单步定常迭代法一般是对系数矩阵进行单次分裂a = m n 而引出的迭代法， 其中m 是非奇异的， z 知= m 一1 n x 七一1 + m 一1 b ，七= 1 ，2 ，( 1 3 ) 式( 1 3 ) 就称为单分裂迭代法其中m - 1 称为迭代矩阵，z o 是迭代初始值前 面所述的经典迭代法就是对m 取不同的矩阵，从而得到具体的迭代算法 v a r g a 1 1 1 】和y o u n g 1 2 7 1 对此进行了详细地论述，他们的著作已成为迭代法方面的 经典著作文【5 8 】对a o r 方法和t o r 方法进行了深入地总结和研究 2 第一章绪论 如果在每步迭代中，再考虑一次分裂，那么就可以得到交替迭代方法，有如下 的迭代式： iz 枞2 = 圻1 1 + 圻1 b ， lx k + l = m f l n 2 z k + l 2 + 岈1 b 交替迭代方法是一种运用广泛且十分有效的求解线性系统的方法基于经典迭代法 构造的对称型迭代法比如对称g a u s s s e i d e l 方法，s s o r 方法都属于交替方法类还 有交替方向隐式迭代技术( a d i ) t 8 9 1 也在数值代数中占有一席之地文0 7 在分析经 典交替迭代法收敛性的同时给出了由此引出的矩阵分裂的比较定理文【1 1 4 进一 步研究了系数矩阵为日矩阵时线性系统的收敛情况随后，文【3 1 】将经典交替方法 推广到非定常的交替迭代法，广义交替迭代法和并行交替迭代法等，并且分别分析 了迭代法的收敛性和单调性 由于迭代法在求解方程组时具有十分明显的优越性，所以很多学者致力于研究 新的迭代技术其中，两步迭代法又称内，夕 迭代法，在文【8 3 】中提出它主要对离散 化的偏微分方程组求解具有一定的优势，考虑如下的分裂： a = m n = f g 一 得到两步迭代法的迭代格式， z 口+ 1 = f 一1 g x 口+ f 一1 n y n 一1 + b ，移= 1 ，2 ，p ， 其中矽是内迭代的次数，f l , 是外迭代的次数如果在每一次外迭代过程中，内迭代次 数p 都是固定的，则上述迭代法就称为定常的两步迭代法如果内迭代数p 随着外迭 代数1 7 , 的变化而变化，即不同的外迭代数相对应的内迭代数是不同的，那么就变成 非定常两步迭代法具体的算法描述将在第三章中给出随后很多文献都进一步 研究了这种方法，文【4 2 】分析了日矩阵系统中的收敛性问题文 2 3 ，5 9 ，7 7 分别给 出了对称正定和h e r m i t i a n 正定情况下，运用不同的方法获得两步迭代法的收敛性 文 1 3 0 研究了不完全l u 分解在两步迭代法中的应用 多分裂技术是由o l e a r y 和w h i t e 踟提出如果给定4 的多分裂，有如下表示， a = m z n z ，i = 1 ，2 ，l ， 那么每一个分裂都可以由各个处理机并行解决， 劈= 坷1 n t z 后+ m i - 1 b ， 3 电子科技大学博士学位论文 然后在主处理机中进行加权平均 其中权矩阵蜀，f = 1 ，2 ，l 是非负对角矩阵，且丝1 易= i 并行多分裂迭代 法自从提出后，就有了快速发展并出现许多的收敛理论【8 2 ，9 9 2 0 随后结合其它 一些迭代方法出现了大量新型的并行多分裂迭代方法，比如，文 3 1 ，4 1 结合并 行同步多分裂模型和交替方向迭代法，提出了两种并行同步交替多分裂迭代方 法而非定常的两步迭代法常常和多分裂技术相结合，变成多分裂两步迭代法 文【4 ，2 2 ，2 7 ，7 1 ，1 1 0 ，1 2 9 对非定常的多分裂两步迭代法做了不同的研究，分别都 得到较好的理论结果文【5 3 】研究了在矩阵块分裂的情况下，此迭代法的收敛性 文【11 7 研究了奇异系统下的多分裂两步迭代法，并获得不错的效果文【9 1 】中，给出 了离散的多分裂波形松弛算法文 4 3 1 考虑在波形松弛迭代法中结合两步迭代法， 得到了当系数矩阵a 是m 矩阵，相对应的分裂是复合m 分裂时定常的两步波形松 弛算法的收敛性迭代法的种类还有很多，其他的比如双分裂迭代法 9 7 ，鸭1 2 1 ，1 2 3 】，外 推迭代法 1 0 6 以及h s s 迭代法1 5 ，7 】等 一般来说，迭代法的收敛性与方程组系数矩阵的性质有着密切的关系，例如非 负矩阵，日矩阵，m 矩阵，h e r m i t i a n 正定矩阵等等在一些实际问题中，也常会遇到 这样的特殊矩阵，因此，对它们相关性质的讨论是十分重要的，也是很有价值的，特 别是矩阵的特征值问题 4 7 4 8 1 捌，以及特殊矩阵类的推广【，1 2 5 】比如系数矩阵是非 奇日矩阵的线性方程组的收敛理论1 4 9 ，7 5 ，7 6 8 2 1 2 6 】同时，迭代方法的收敛速度也是 研究中非常重要和关键的问题，一般来说，迭代矩阵的谱半径越小，其对应的迭代 收敛速度越快1 1 1 1 1 因此，对于相同的线性系统，可以通过比较迭代矩阵谱半径的 大小来判断不同迭代方法的收敛速度，为实际计算的选择提供理论依据v a r g a 在 专著【1 1 1 】中给出了单调矩阵正则分裂的收敛性和比较理论对于! e h e r m i t i a n 线 性系统，o r t c g a 和p l e m m o n s 在文 8 6 】中给出两个著名的收敛性定理，这两个定理在 文 1 2 8 】中得到进一步推广w a n g 和b a i 在【1 1 3 中分析了系数矩阵a 是非h e r m i t i a n 正 定矩阵的情况下迭代法收敛的一个充分条件随后，单调矩阵和h e r m i t i a n 正定矩阵 单分裂的比较理论得到了迅速发展并日臻完善 2 9 , 3 8 ，6 7 ，醴7 8 ，10 5 ，1 眠1 矧文 8 2 】研究了 并行多分裂情况下的比较理论此后，非奇m 矩阵和h e r m i t i a n 正定矩阵多分裂的比 较理论层出不穷1 3 0 ，3 7 ，4 0 ，6 7 ，8 1 , 1 1 2 - 1 1 5 然而在许多问题中，经常遇到系数矩阵为奇异矩阵的情况，那么很多文献中 4 七fy 毋 l m = +七 z 第一章绪论 得到的理论结果将不成立，这样我们就需要利用半收敛性理论来求解线性方程组 文【1 8 】对线性系统半收敛理论进行了细致地阐述和分析随后，在文 2 4 ，7 4 ，1 2 8 中 研究了半定线性系统的收敛性质文 7 3 ，9 0 对奇异系统中迭代法的收敛理论和 比较理论做了进一步地分析文 2 1 ，11 6 】结合两步迭代对奇异矩阵的半收敛性做 了分析但是很多这类分析都是在假设分裂中矩阵m 是非奇异的条件下进行的， 文【6 0 】分析了对称正半定系统中，m 有可能是奇异的情况，并且给出了迭代法收敛 的充分必要条件 在迭代过程中，经常出现迭代矩阵的谱半径虽然小于1 ，但是数值和1 非常接近 的情况，从而迭代过程会非常缓慢，效果不太理想，这时往往采用其它办法，其中一 种方法就是对系数矩阵a 进行预处理。然后对预处理矩阵进行迭代求解对预处理 子的构造往往考虑线性方程组的背景和来源，系数矩阵的特点，预条件部分的计算 量以及预处理后矩阵的特点预条件定常迭代法基于矩阵分裂来构造预条件子，在 此类方法中，由于矩阵分裂已经有了深入的研究，理论支持强，代价小，但是效果要 相对差些，国内外很多学者对此进行了研究，6 6 - 6 8 8 7 ，9 3 一0 9 ，得到很多较好的理论结 果对于预条件非定常迭代法，主要是与k r y l o v 子空间方法相结合，很多学者对相关 问题做了研究，这也成为一个新的热点 1 2 2 鞍点问题的求解技术 鞍点问题是一类特殊的线性方程组，广泛的存在于流体力学，带有限制条件的 二次优化，电磁学，线性弹力学等应用领域中在求解n a v i e r - s t o k e s 方程，o s e e n 方程 及对流扩散方程的过程中，通过混合有限元离散方法和m a c 格式的有限差分离散 方法，都可以引出鞍点形式的方程组由于这类问题的系数矩阵通常是大型稀疏的， 用直接法来求解这样的线性方程组是不现实的，因此研究这类问题的快速迭代算法 非常重要这类方程组最初是由优化问题而来，形式如下： 地：( a b 三三) ( ：) = ( 5 ) = 6 ， ( 1 4 ) 其中a r n 黼，c r m m ，b r 仇n ( 可能m n ) 若a 对称正定且c = 0 ，我们 称( 1 - 4 ) 为经典的鞍点问题，如果c 0 ，则称( 1 - 4 ) 为广义鞍点问题在许多文献中此 类鞍点系统也被称作扩充系统( a u g m e m e ds y s t e m ) 1 1 9 3 6 掀9 4 对于广义鞍点问题 的研究也有很多成果【3 1 2 1 尽管系数矩阵是对称的，但其特征值实部有正有负，并且对角块中一般含有奇 5 电子科技大学博士学位论文 异矩阵，因此鞍点问题往往非常病态但是其应用的广泛性，使得对鞍点问题的快 速求解一直是众多学者研究的热点问题，然而一些经典的迭代算法如g a u s s s e i d e l ， s o r 等方法在研究鞍点问题的时候均失效随着对鞍点问题的关注，新型的方法在 研究中被提出，其中最经典的当属u z a w a 类：型的算法u z a w a 方法首先在文【2 】中被 提出，最初用于解决经济学中二次优化问题，该方法形式简单，易于计算机实现，但 最大的不足就是每一步迭代都需要计算矩阵a 的逆，从而产生繁重的计算量为了 避免直接求逆带来的困难，文【3 6 】提出了非精确和预条件u z a w a 方法 2 5 ，2 8 对预 处理下u z a w a 方法的快速算法作了进一步的推广文 1 9 ，2 0 对u z a w a 力 法的收敛性 进行了细致的分析，给出了收敛速度，同时提出了非线性的u z a w a 方法，并研究了用 快速线性和非线性的u z a w a 方法分别求解稳定化的对称和非对称的鞍点问题之后 文 2 6 ，3 5 ，6 9 ，8 4 对非线性的方法进行了深入地研究 类似于传统的s o r 方法，文】提出求解鞍点问题的s o r 1 i k e 方法，并研究了 其收敛性及最优迭代因子的选取随后【8 】将广义s o r 方法引入至l j g o l u b 4 4 的方法 中，在增加一个参数的情况下提出了一种新型的迭代法，找到了最优因子和最优 收敛速度，并且对s o r 1 i k e 方法的最优因子选取作了进一步的完善这一类方法 在很多情况下其收敛速度快于无预处理的m i n r e s 等子空间迭代方法在此基础 上，文 3 2 ，6 1 ，9 6 ，1 3 2 通过结合新的分裂形式以及不同参数的选取，对s o r 1 i k e 方 法的理论成果进行了补充对于实正定线性系统，在h s s 迭代方法【5 】的基础上， 文 6 ，1 2 ，8 8 ，1 0 4 等对经典鞍点问题应用了预条件的h s s 迭代方法，并且给出了预条 件h s s 迭代方法的最优因子及最优收敛速度文【1 6 】分析了h s s 预处理矩阵的谱性 质文 9 】给出了非精确的h s s 迭代法的理论性质此类方法的缺点是特定的预条件 技术大都只能适用于特定的问题文 1 0 ，1 5 ，4 5 ，9 5 1 研究了对称不定预处理方法的 鞍点问题由于鞍点系统与实际结合较为密切，不断出现的新问题需要寻找新的预 处理方法，所以这类研究得到了迅速发展 另一类求解鞍点问题的方法就是非定常的迭代方法，最常见的有k r y l o v 子空 间方法由于鞍点问题自身结构的特殊性，直接应用k r y l o v 子空间方法求解鞍点 问题，其收敛速度不是很理想甚至不收敛，因此需要对鞍点问题进行预处理，使原 问题转化成具有较好性质的等价线性系统许多方法很大程度地考虑了原实际问 题，大都只能适用于特定的模型，构造有效的新预条件子是非常困难的，国内外许 多学者为此做了大量的工作，提出了很多关于鞍点问题的预条件子，鞍点问题迭 代求解的预处理技术已成为数值求解的热门课题之一文 9 2 ，1 0 1 对s t o k e s 问题和 二阶椭圆问题提出了块对角预条件，文 7 2 ，1 1 8 ，1 1 9 】给出了稳定化的s t o k e s 问题的 6 第一章绪论 块对角预条件技术文 6 3 ，7 9 研究了块对角预处理子的谱性质由于该预处理子 中含有s c h u r 余，就需要计算一个逆矩阵，因此新的预处理技术被不断地发掘出来 文 1 0 0 ，1 0 8 将块对角预处理子推广到广义鞍点问题上，利用扰动理论研究了矩阵 的谱性质文 5 6 】分析了带有惩罚项的鞍点问题的块三角预条件子，文 1 0 3 在更一 般的情况下研究了块三角预条件子，并且通过理论和数值实验的分析，该预处理技 术比块对角预条件子更有效文【5 4 】提出了约束预处理子，该类预处理子已广泛的 应用于各类优化问题中，文 3 3 ，3 4 进一步推广了约束预处理子的适用范围对于鞍 点问题的分析方法还有很多，文 1 4 ，3 5 ，3 9 研究了有限元方法求解n a v i e r - s t o k e s 方 程，文 1 ，6 2 研究了约束最小二乘问题，篇幅所限，这里不再一一介绍 1 3 本文主要研究内容、方法和创新点 本学位论文主要研究大型稀疏线性代数方程组的迭代解法，包括基于迭代法找 到一个正对角矩阵d 使得a d 为严格对角占优矩阵，两步波形松弛迭代法，鞍点问题 的迭代求解，预条件g s 迭代法和奇异矩阵的迭代法研究 论文主要研究方法：线性代数的基本知识；h 矩阵，正定矩阵和非负矩阵等特 殊矩阵理论；特征值理论；矩阵分裂理论；m a n a b 程序设计技术等 论文主要内容和创新点： 1 通过迭代方法，对于m 矩阵a 找到一个正对角矩阵d ，使得a d 是严格对角 占优的这个结果改进了文【5 l 】的算法并且利用算法得到的结果给出了对日一矩阵 的谱半径上界的估计( 第二章) 2 利用两步迭代法，完善了定常的两步波形松弛方法的研究，分析了当系数矩 阵是日矩阵时迭代法的收敛情况，并且拥有特殊矩阵的性质给出新证明方法下的 比较理论，充实了该类迭代法的理论成果( 第三章) 3 结合多分裂方法，系统地分析了非定常的多分裂两步波形松弛方法，考虑在 线性系统中，当系数矩阵分别是m 矩阵，日矩阵和h e r m i t i a n 正定矩阵，以及相对应 的分裂是有效的分裂时，迭代法的收敛理论和比较理论( 第三章) 4 建立了一类具有三个松弛因子的修正广义s s o r 迭代法，对文【4 4 】中的算法 进行了扩展，并对迭代法的收敛性进行了研究分析，得到了使得迭代法收敛的松弛 因子的取值区域( 第四章) 5 通过不同的矩阵分裂，建立了两类广义的s o r 方法，对文【7 0 】进行了推广，选 择不同的松弛因子可以获得不同的收敛速度如果选取特殊的参数，此类方法就变 7 电子科技大学博士学位论文 成s o r 1 i k e 迭代法或者经典的u z a w a 方法同时给出参数的一些具体选取，分析了相 对应的算法，并得到较好的理论结果。( 第四章) 6 研究了一类交替的修正g a u s s s e i d e l 迭代法，并给出它的收敛理论和比较理 论，说明此类修正的预条件子迭代法的收敛速度比经典的s o r 算法的收敛速度要 快同时又研究了多分裂情况下修正g s 迭代法的收敛性( 第五章) 7 对于非对称的奇异线性系统，研究了当分裂矩阵也是奇异情况下的收敛性 ( 第五章) 1 4 本文结构安排 本学位论文共分六章 第一章是绪论，主要概述了本文的研究对象，研究目的，研究背景，研究方法以 及创新点 第二章在已有算法的基础上，提出了改进的寻找对角占优尺度矩阵的迭代方 法对于m 矩阵( 或者日矩阵) a ，找到了一个正对角矩阵d ，使得矩阵a d 是严格对 角占优的，并且利用获得的结果得到了对日矩阵谱半径上界的估计 第三章基于求解微分方程的波形松弛方法，结合两步迭代法，根据定常情况下 已有的一些工作，进一步研究了定常的两步波形松弛方法，充实了当系数矩阵以及 相对应的矩阵分裂满足一定条件下该类迭代法的理论成果同时结合多分裂方法， 系统地分析了非定常的多分裂两步波形松弛迭代方法，考虑了线性系统中，当系数 矩阵分别是m 矩阵，日矩阵$ 1 h e r m i t i a n 正定矩阵，以及相对应的分裂是有效的分 裂时，迭代法的收敛理论和比较理论 第四章基于求解鞍点系统的s o r 1 i k e 迭代法，建立了一类具有三个松弛因子的 修正广义s s o r j 迭代法，并对迭代法的收敛性进行了研究分析，得到了使得迭代法收 敛的松弛因子的取值区域同时，通过不同的矩阵分裂，建立了两类广义的s o r 方 法，通过选择不同的松弛因子获得不同的收敛速度如果取特殊情况下的参数，此类 方法就可以变成s o r 1 i k e 迭代法或者经典的u z a w a 方法 第五章研究了一类交替的修正g a u s s s e i d e l 迭代法，并给出它的收敛理论和比 较理论，说明此类修正的预条件子迭代法的收敛速度要比经典的s o r 算法的收敛速 度快同时又研究多分裂情况下修正g a u s s s e i d e l 迭代法的收敛性其次，对奇异线 性系统做了研究，分析了当分裂矩阵也是奇异情况下迭代法收敛的充分必要条件 第六章对整个工作给出了总结并对以后的工作进行展望。 8 第二章基于迭代法寻找对角占优的尺度矩阵 第二章基于迭代法寻找对角占优的尺度矩阵 2 1 引言 m 矩阵，日矩阵，对角占优矩阵等特殊矩阵由于其结构和性质的特殊性，使得 这些矩阵无论在学术研究上还是在实际应用中，都有着独特的价值，并得到国内 外科学研究人员的广泛关注m 矩阵是由o s u o w s k i 弓 入的，定义为：具有非正非对 角元且有非负逆矩阵的实方阵称为m 矩阵并且称具有非正非对角元的实方阵 为z 矩阵 一般来说，对于任意的m 矩阵，很难找到一个正对角矩阵d 使得a d 是严格对 角占优矩阵，h u a n g 和l i 在文献 5 1 1 q b ，假设矩阵a 是不可约m - 矩阵时，给出了一种 迭代方法来寻找一个正对角矩阵d 使得a d 是严格对角占优的在本章中，研究了一 种改进的迭代方法，花费更少的迭代次数就可以找到这样的矩阵d 这- 4 , 节中首 先介绍文献 5 1 1 中给出的迭代算法 算法2 1 1 t 5 1 】 输入：m 矩阵a 输出：b = a g = a d i a g ( g ) ，以及g = g ( 1 ) g ( 2 ) g ( m ) 1 令a ( o ) = a ，g = ( 1 ，1 ，1 ) t ，g ( o ) = d i a g ( 9 ) ，e = ( 1 ，1 ，1 ) t ，m = 1 ； 2 计算a ( 仇) = a ( m 一1 ) g ( 仇一1 ) = ( o ) ； 3 计算向量z = a ( m ) e ，用丘和万分别代表向量z 中最小和最大的元素， a ( m ) = m ，i n x 七，声( m ) = m a x x 知， 如果6 l ( m ) 0 ，终止；不然，继续步骤4 ； 4 计算夕= ( 历) ， 鳜： 卜舄= j i ：d ， i 1 ，i j o ， 其中如是取到向量z 中最大元素万的k 的取值； 5 令g ( 仇) = d i a g ( 9 ) ，迭代次数增加一次m = m + 1 ，转到步骤2 显然，丘( 仃，口( m ) 分别代表的是第m 次迭代后，矩阵a c m ) 的最小行和与最大行 和，不妨分别设为第z 0 行和第如行在算法2 1 1 的思想中，通过分析每次迭代后的矩 阵a ( 川，计算得到它的最小与最大行和，于是就会对g t 进行重新取值，从而使下一次 o 电子科技大学博士学位论文 迭代后的第i o 行的行和增加，以及第j o 行的行和减少，通过重复的迭代，使得某次迭 代后的最小行和丘 0 。也就得到了一个严格对角占优矩阵 2 2 定义和性质 提出改进的算法之前，首先给出一些需要的定义和性质 定义2 2 1 1 8 】矩阵a = ( a q ) c n 加，如果对于任意的z 机) 都有， c l i i i 兄( a ) = 蚓， ( 2 1 ) 那么矩阵a 就称为是对角占优矩阵，如果对于上面的不等式中，至少有一个严格不 等号成立，则称a 是不可约对角占优矩阵，如果对于不等式中，每个不等号都是严格 成立的，即 蚓 忍( a ) = i 口甜i ， ( 2 2 ) 则称a 是严格对角占优矩阵 定义2 2 2 t 1 8 】矩阵a