（计算数学专业论文）广义鞍点问题的块三角预条件子.pdf

广义鞍点问题的块三角预条件子 中文摘要 广义鞍点问题的块三角预条件子 中文摘要 鞍点问题来源于许多实际问题，如优化问题，流体力学，结构分析等，因而其求 解非常重要近年来，经过许多作者的研究，已提出一些比较有效的算法，如迭代法 中有u z a w a 方法，不精确u z a w a 方法，带参数的不精确u z a w a 方法，非线性u z a w a 方法，s o r - l i k e 方法，h s s 方法等，预处理方法中有块对角预处理，块三角预处理， 约束预处理，h s s 预处理，限定的预处理共轭梯度法等近来，g o l u b ，e t c 在 1 9 上 提出s 丁分解，并在 3 5 】中把这种方法应用到鞍点问题上，得到一些结果 本文进一步讨论s r 分解，并把这种分解推广到广义鞍点问题上根据【3 5 中的想 法提出了三种块预条件子，并重点分析了其中两种预条件子应用到广义鞍点问题上所 得到的对称正定阵，得出了其般的性质并重点研究了预处理矩阵条件数的上界最 后给出了两个数值算例，一个是纯粹的代数结构的例子，另一个是流体力学中s t o k e s 方程用q i 一尸。有限元离散出来的线性代数方程组结果表明了我们所提出的两种预 条件子在选择适当的参数下用共轭梯度法求解预处理线性系统具有很快的收敛速度 关键词：广义鞍点问题；s 丁分解；块三角预条件子；对称正定阵 i 作者；曹阳 指导教师；蒋美群( 教授) 广义鞍点问题的块三角预条件子 a b s t r a c t b l o c k t r i a n g u l a rp r e c o n d i t i o n e r sf o rg e n e r a l i z e d s a d d l ep o i n tp r o b l e m s a b s t r a c t s a d d l ep o i n tp r o b l e m sa r i s ei nav a r i e t yo fs c i e n t i f i ca n de n g i n e e r i n ga p p l i c a t i o n s ，i n - c l u d i n go p t i m i z a t i o np r o b l e m ，c o m p u t a t i o n a lf l u i dd y n a m i c s ，c o n s t r u c ta n a l y s i s ，a n ds oo n s oi t i si m p o r t a n tt of i n dt h en u m e r i c a ls o l u t i o n r e c e n t l y , m a n yr e s e a r c h e r sh a v ep o s e d ag r e a tm a n yo fe f f e c t i v ea l g o r i t h m s s u c ha s ，i nt h es i m p l ei t e r a t i v em e t h o d s ，u z a w a - t y p em e t h o d s ，i n e x a c tu z a w am e t h o d s ，o np a r a m e t e r i z e di n e x a c tu z a w am e t h o d s ，n o n l i n e a r u z a w am e t h o d s ，s o r - l i k em e t h o d s ，h s si t e r a t i o nm e t h o d sa n ds oo n ；i nt h ep r e c o n d i t i o n e d m e t h o d s ，b l o c kd i a g o n a lp r e c o n d i t i o n i n g ，b l o c kt r i a n g u l a rp r e c o n d i t i o n i n g ，c o n s t r a i n e dp r e c o n d i t i o n i n g ，h s sp r e c o n d i t i o n i n g ，t h er e s t r i c t i v e l yp r e c o n d i t i o n e dc o n j u g a t eg r a d i e n tm c t h - o d sa n ds oo n g o l u ba n dy u a np r o p o s e dt h estd e c o m p o s i t i o nf o r t h en o n s y m m c t r i cm a t r i x i n 【1 9 t h e n , i n 【3 5 ，w u , e t c a p p l i e dt h es rd e c o m p o s i t i o nt os l o v et h es a d d l ep o i n tp r o b - l e m s i nt h i sp a p e r , w ee x t e n dt h estd e c o m p o s i t i o nt ot h eg e n e r a l i z e ds a d d l ep o i n tp r o b l e m a n dp r e s e n tt h i n eb 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 t h e nw et a k et w oo f t h e ma n da p p l yt h e m t ot h eg e n e r a l i z e ds a d d l ep o i n tp r o b l e m n et w o p r e c o n d i t i o n e ds y s t e m sa r es y m m e t r i ca n d p o s i t i v ed e f i n i t e t h e nw e d e d u c et h eg e n e r a lp r o p e r t i e sa n dt h eu p p e rb o u n do f t h ec o n d i t i o n n u m b e ro ft h et w op r e c o n d i t i o n e ds y s t e m so n eb yo n e f i n a l l y , w ep r o p o s et w on u m e r i c a l e x a m p l e s ，o n ei sap a r t i c u l a rl i n e a rs y s t e m , t h eo t h e ri sal i n e a ra l g e b r as y s t e mb a s e do nt h e st o k e se q u a t i o n ，n l en u m e r i c a lr e s u l t ss h o wt h a tt h et w op r e c o n d i t i o n e r sg i v e ni nt h ep a p e r a r ee f f e c t i v e k e y w o r d s ：g e n e r a l i z e ds a d d l ep o i n tp r o b l e m ；std e c o m p o s i t i o n ；b l o c kt r i a n g u l a r p r e c o n d i t i o n e r ；s y m m e t r i ca n dp o s i t i v ed e f i n i t em a t r i x w r i t t e nb yc a oy a n g s u p e r v i s e db yp r o f j i a n gm e i q u n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明本人承 担本声明的法律责任 研究生签名：迎日期： 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸质论文的内容相一 致，除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容论文的公布( 包括刊登) 授权苏州大学学位办办理 研究生签名：垃日期：至牲 导师签名：蝉日期：三竺出 第一章引言 我们考虑如下2 2 阶块线性系统： a b 乏】 ；】= 二】，。朋材= 抚 c - 。， 其中a 湖对称正定，b r ”期行满秩，c r 一跏对称半正定且聊甩这样的系 统常称为广义鞍点问题的线性系统特别地，若c = 0 时称为鞍点问题形如( 1 0 1 ) 的系统广泛来源于许多实际问题，如带等式约束的二次优化问题，等式约束的最j 、- - 乘问题，非线性规划中的内点法，计算流体力学，二阶椭圆型偏微分方程的混合有限 元求解等关于鞍点问题的来源及其求解有一个系统性的介绍，可参考 7 】本文所考 虑的广义鞍点问题主要来源于流体力学中的s t o k e s 方程用有限元进行离散所得到的 线性代数方程组 对于一般的线性方程组a x = b ，当其系数矩阵彳的阶数比较小时，常用的是被称 为直接法的求解方法但矩阵a 具有大型稀疏结构时，直接法求解就比较困难，而且 这样的做法通常会破坏系数矩阵原本的稀疏结构此时，人们更多的是利用迭代法和 预处理方法进行求解 传统的分裂迭代法如j a c o b i 迭代法，g a u s s s e i d e l 迭代法，s o r 迭代法等以及它 们各自相对应的块迭代法已较为熟知与常见但由于( 1 0 1 ) 中c 为对称半正定阵，这 类迭代方法不能直接推广到( 1 0 1 ) 的求解上因此，经过许多作者的研究，产生了适 用于求解( 1 0 1 ) 的分裂迭代法，如精确u z a w a 方法 7 】，不精确u z a w a 方法【8 ，1 3 ，1 4 ， 1 5 ，2 1 ，2 2 ，2 4 ，带参数的不精确u z a w a 方法 5 】，非线性u z a w a 方法 1 1 】，s o r - l i k e 方法 【1 8 ，2 9 ，h s s 迭代法【l ，1 7 等等预处理方法是目前最为流行的一种方法，其主要思 想是找出个矩阵m 使得膨尽量为彳的逆的个逼近这样的矩阵m 必须是非奇异 的并且一般是相对较容易求逆的当然，这样的矩阵是很难找到的因而，若能找到一 个矩阵m 使得 f 1 彳具有一些很好的性质，如条件数大大减小，对称正定，上m 三 角阵等也是常用的方法，然后再用一些经典的方法进行求解经过很多作者的研究， 针对( 广义) 鞍点问题设计出了许多预处理方法，如块对角预处理方法 2 5 ，3 2 ，3 4 ，块 三角预处理方法【1 2 ，3 1 ，3 5 ，约束预处理方法 1 0 ，1 6 ，2 0 ，h s s 预处理方法 2 ，6 ，2 6 】，限 定的预处理共轭梯度法 3 ，4 】等等另外g o l u b ，e t c 在 1 9 】上提出对于一个非对称且 其顺序主子式均为非零的矩阵彳，存在一个对称正定阵s 及一个上( n 三角阵r ，使得 a = - - s 丁或者彳= t s ，称这种方法为s r 分解然后在 3 5 】中根据鞍点矩阵的特殊性质 把这种方法应用到鞍点问题上本文进一步讨论s 丁分解，并把这种分解推广到广义 鞍点问题的求解上由于s 丁分解的不唯性，本文同样给出了几种与【3 5 中类似的 广义鞍点问题的块三角预条件子第一章引言 分解，从而得出广义鞍点问题的块三角预条件子，并分析了预处理矩阵的性质，如特 征值，条件数等 本文的结构是这样安排的：在介绍完本篇文章要用到的有关定义，引理及常见的 结论后，我们将在第三章给出由s r 分解所导出的广义鞍点问题的预条件子，并分析 了预处理矩阵的性质；第四章给出了两个数值例子，一个是纯粹的数值例子，另一个 是用混合有限元离散流体力学中s t o k e s 方程所得到的线性代数方程组，其结果与现有 的方法进行了比较；最后第五章是对本文主要结果的总结与综合评述 2 第二章预备知识 为了方便理解，本章第一节给出了预处理方法的概念及常见的结论；第二节简单介 绍了常见的矩阵分解并重点阐述了本文所要用到的s t 分解的相关概念及重要结果； 第三节给出了鞍点矩阵的一些重要性质 2 1预处理方法简介 对大型稀疏线性方程组求解时迭代法比较实用，但收敛的速度是迭代法的关键对 于对称性问题用共轭梯度法是最好的方法之一。而共轭梯度法的收敛依赖于条件数， 因而改善条件数是十分重要的工作本文研究预处理技巧达到条件数的改善预处理 方法是把原始线性系统等价的转化为与之具有相同解的线性方程组，使之用某些迭代 法时有较快的收敛速度 对于给定的线性方程组a x = b ，预处理的第一步是要找到一个预条件子m 它是 一个矩阵，可以通过不同的方法来定义，但必须满足一定的要求： 1 m 要求非奇异并且在某种意义下是彳的逆的一个充分逼近或者使得 f 1 彳具有一 些好的性质 2 从实际计算角度来看，选取的预条件子m 必须不太难求m x = b 即 矿1 容易计 算 预条件子的选取可通过矩阵分裂的构造迭代方法得到，也可以作为对迭代法的另 一种解释给定线性方程组a x = b 的系数矩阵4 的一个矩阵分裂 彳= m 一 其中肘为非奇异，则可以构造一个迭代 、 x k + 1 = m - 1 n x k + m - 1 b ，( 2 1 1 ) 记其迭代矩阵为g = 矿1 ，则g 可写成 g = 厂1 n = m - 1 ( 肘一a ) = j m - 1 彳， 另记 f = m - 1 b ， 则迭代( 2 1 1 ) 可看成是求解如下线性系统 q g ) x = ， 3 广义鞍点问题的块三角预条件子第二幸预备知识 由于g = i 一胗1 彳，则上述线性系统可重写为 m - 1 a x = m - 1 b 。 ( 2 1 2 ) 称这种线性系统为预处理线性系统，m 称为预条件子显然，预处理线性系统与原 始线性系统有相同的解对于不同的分裂可得到不同的预条件子，对应于j a e o b i ，g a u s s s e i d e l ，s o p , s s o r 迭代法，其预条件子分别为 m j = d - m g s = d e 。 m s o r = 三( d 一们) ， m s s o r = 毒罚( d t o e ) d - 1 ( d 一 其中皿占，分别为彳的对角部分，上三角，下三角部分，叫为迭代参数 一旦选取了一个预条件子m 除了像( 2 1 2 ) 那样对原始线性系统左边乘以预条件 子 f 1 外，还有其他的一些方法进行预处理我们把它们都归纳如下： 1 左预处理 m - - 1 a x = m - j b 2 右预处理 a m - z u = b x = 纩1 “ 3 分裂预处理 m = 舰螈，垅1 彳蝎1 ”= m i l b ，z = 螈1 4 广义鞍点问题的块三角预条件子第二章预备知识 2 2矩阵分解 预条件子的选择除了可以从矩阵分裂的角度来得到外，还可以通过矩阵分解来选 取本文中矩阵的分裂指加法分解，矩阵的分解指矩阵乘法分解一些常用的矩阵分 解有三角分解，满秩分解，s c h u r 分解，q r 分解，奇异值分解等这里我们介绍一 下针对一类非对称正定阵，它可以分解为一个对称正定阵与个三角阵的乘积并称这 种矩阵分解为s 丁分解这种形式的求解方法在二次优化，最d x - 乘，计算流体等实 际问题中已有广泛应用作为一种系统方法的分解，我们是从这儿入手讨论预条件子 的对s r 的分解文献 1 9 已作了较详细的研究，主要有以下结论： 引理2 1 对任一刀阶非奇异非对称矩阵a ，若其顺序主子矩阵均非奇异则么可 以分解为 a=st 其中s 础砌为对称阵，t 础湖为单位三角阵 引理2 2 对任一刀阶非奇异非对称矩阵彳，若其顺序主子阵均非奇异，则彳可以 分解为 彳= s z 或 彳= s r l 。a = t s 其中s 砌为对称矩阵，t 砌为单位三角阵 引理2 3 对任一个非奇异非对称刀阶矩阵彳，若其顺序主子矩阵均非奇异，则存 在三角阵7 和对称正定阵s ，使得a = s r 引理2 4 对任一个非奇异非对称刀阶矩阵彳，若其顺序主子矩阵均非奇异，则存 在三角阵丁，三及对称正定阵s ，使得t a = s = l l 丁或彳r = s = l l r 5 广义鞍点问题的块三角预条件子 第二章预备知识 2 3鞍点矩阵的一般性质 本节主要介绍有关鞍点矩阵的一些基本性质：可解性条件及特征值，这些性质直 接关系到本文中广义鞍点问题的可解性及预条件子的选择 引理2 5 假设彳为对称正定阵，b 为贸的( 2 ，2 ) 块，c 为对称半正定阵若 k e r c lnk e r l b r l = 0 ，则鞍点矩阵舅为非奇异特别的，若召为满秩，则舅为非奇异 引理2 6 假设爿为对称正定阵，丑满秩阵，c = 0 ，则鞍点矩阵舅为非奇异的充 分必要条件是k e r l a ) nk e r l b ) - 0 以上两个引理保证了本文所给出的广义鞍点问题是可解的下面给出有关( 广义) 鞍点矩阵特征值的性质根据s c h u r 分解易得： 【a 口：三 = 一，：】【三三】【三彳一夕r 】 其中s = 一( c + b a - 1 b r ) 从而根据s i l v e s t e r 定律易得如下性质t 引理2 7 若彳为对称正定阵，召为满秩阵，c 为对称半正定阵，则鞍点矩阵舅 为对称不定阵 更进一步，在【2 7 】和【3 0 】中分别给出了鞍点矩阵和广义鞍点矩阵的特征值范围： 引理2 8 若彳为对称正定阵，占为满秩阵，c = 0 设p l ，鳓分别为彳的最大，最 小特征值，矿l ，o m 分别为占的最大，最小奇异值设矿( 贝) 为舅的谱则 矿( 卵厂ur 其中 广= 【 一扣；+ 4 砰) ，；c a , 一批+ 4 0 - d ， r = ，；似- + 批+ 4 砰) 】 引理2 9 若彳为对称正定阵，b 为满秩阵，c 为对称半正定阵设芦1 ，砌分别 为彳的最大，最小特征值，矿l ，口分别为b 的最大，最小奇异值6 为c 的最大特征 值设畎翻) 为贸的谱则 舐贸) 厂ur 其中 ，= m 一一以；+ 4 砰) ， m l - 6 - 4 0 卸+ 6 ) 2 + 4 0 - l ) ， r = ，；“，+ 批+ 叫) 】 有了上面的准备，我们开始广义鞍点问题的预条件子的讨论 第三章广义鞍点问题的块三角预条件子 3 i由s t 分解构造预条件子 在第二章中我们已经给出有关( 广义) 鞍点矩阵的特征值分布但这种特征值分布 直接用经典迭代法求解线性系统( 1 0 1 ) 时是不收敛的，因而在【6 】中把( 1 0 i ) 等价的 转化为： 书a ：】 ；】= 乏】，。衙z ，= 抚 c 3 ， 显然贡为非对称矩阵，且由第二章中广义鞍点矩阵的性质知其顺序主子阵为非奇异， 因而存在s 丁分解由于线性系统( 3 i 1 ) 仅由线性系统( 1 0 1 ) 左乘 【 得来，其中，为单位阵，则线性系统( 1 0 1 ) 也存在一个上三角阵与对称正定阵的乘积， 即sr 分解对于( 厂i 义) 鞍点矩阵这样一种特殊类型的2 2 块不定矩阵也适用在【3 5 】 中已经给出c = 0 的情形，本文进一步讨论c 为对称半正定的情形 由上面的讨论知对广义鞍点矩阵贸必存在一个三角矩阵t 及对称正定矩阵s ，使 得7 贸= s 不妨设r 及s 分别为如下的2 2 阶块矩阵： 丁= 2 ：二】，s = 要：霎三】， 贝由r 舅= s ，有 乃。篇t = b 乃。b 髦t 2 2 c s 蚓s ， 地， l 乃l 彳+ 乃1 r ll 1 22 2l 、7 即 侄 a = s 1 1 ， 置，? 。 ( 3 1 3 ) 彳+ 乃2 召= s 1 2 ， 。 b r 一死2 c = s 2 2 显然，( 3 1 3 ) 相当于一个有六个未知数而只有四个方程的方程组，因而其解可有各种 不同形式的要求，怎样适当的选择其中任何两个块矩阵从而求得其它四个块矩阵并使 得s 具有些很好的性质是一个值得深入讨论的问题，采用与 3 5 】中相同的取法，则 有如下结论： 7 广义鞍点问题的块三角预条件子第三章广义鞍点问题的块三角预条件子 乃= 【够+ 二一o1 ，耻a 够圳删w t n 声c 】， 并且s l 可以分解为 绯n 0 胆护- h i b l b ， 即s ，合同于a 卢蒯一。矿0 + 卢c 】，因而由s i v e r s t e r 定律知，只要卢 。，则s - 为 对称正定阵 2 在( 3 1 3 ) 中若令乃l = 叫一厶t n = 则有 死= 乞，o1 一= a a 2 _ a ) ( 瑚o t a - i ) b rj ， 对s ：采用钔1 4 ) 类似的分解，可得s 2 合同于i 叫2 。m 彳删三r + ci ，师由 s i l v e r s t e r 徽，当口 击( 厶为彳的最小特征值) 时，s 2 为对称正定阵 3 在( 3 1 3 ) 中若令乃l = a ，= - 口( b a 一1 8 7 ) ，则有 乃= a - i + 删之一删0 咖下。】， 耻甜一b ：幺嘲- l c 】 对s s 采用与c 3 4 ，类似的分解，可得s ，合同于i 甜+ 似删0 一，矿广c 】，因而 由于在下三角阵乃中出现了s c h u r 补的逆( b a 一b r ) ，因而在实际计算过程中是 较难处理的，且与块g a u s s 消去法相比，此三角阵作为预条件子并没有什么优势可言， 另外，所得到的预处理矩阵s3 仅为正定矩阵并不对称因而在接下来主要分析三角 阵乃及乃作为广义鞍点问题( 1 0 1 ) 的块三角预条件子所得的对称正定矩阵的一些性 质 8 广义鞍点问题的块三角预条件子第三章广义鞍点问题的块三角预条件子 3 2预处理矩阵特征值分析 取上节中块三角阵乃作为广义鞍点问题( 1 0 1 ) 的预条件子，则可得如下预处理 线性系统： a b 一w t = k 毒卜触】， m 记线性系统( 3 2 1 ) 的系数矩阵为f ，当夕 0 时，f 有如下性质： 定理3 1 1 f 为对称正定阵 2 设a 为，的特征值，【：】为其对应的特征向量，若v = 。，则有a 为彳的特征值，“ 为其对应的特征向量且”n u l t ( b ) ，即 a 肛u = - a u 3 设w = ：】为，的任一特征向量，则有材。 证明： 1 因a 对称正定，利用上节的( 3 1 4 ) 式可直接得到结论 2 设a 为，的特征值，为其对应的特征向量，则有 【a 召。卢+ n t 1 ) b a 。b r + p c ：】= a 【：】，。i 召够+ 1 r + p ci l ，l 。l1 ，l 等价于 彳u+b(pr+v=2u,bu1 ) b a - i b ，- 1 ，+ 3 c v ：i v ( 3 2 2 ) i + 够+ 7 1 ， = 若v = 0 ，则由( 3 2 2 ) 可得 a 眈u = 。 u ， 广义鞍点问题的块三角预条件子第三章广义鞍点问题的块三角预条件子 3 若”= 0 ，则由( 3 2 2 ) 可得b r ，= 0 根据假设b r 为列满秩，因而1 ，；0 ，此矛盾于 ：】为一特征向量，所以”。 口 下面给出矩阵f 的条件数估计，为此先给出一个引理 引理3 1 3 5 设u 矿1 ，则对v p 0 ，有 2 1 u r v i o u r u + 旷旷 定理3 2 设k 为矩阵的条件数，厶，山分别为a 的最小，最大特征值，厶，a 1 分 别为b a - 1 b r 的最小，最大特征值，磊为c 的最大特征值，则有 娴商1 + 0 拟) ， 其中 p ：业丝出嘎孚砸， 否= 型坐型业业业 证明：设a 为，的特征值，w = 为的耗向量，且i | w l l 乩则有 ，”褂 即 a。卢+wtb1 ) b a 。b r + 卢c 】 ：】= a ：】，【 够+ q r + 肥j 【 ，j【vj 从而w r f w = 1 w r w = a 即 a=u r a u + v r b u + u r b 丁1 ，+ ( p + 1 ) v r b a 一1 b r v + 卢，c v =u r a u + 2 u 7 b r ，+ 够+ 1 ) v r b a 一1 b r l ，+ 3 v r c v ( 3 2 3 ) 由引理3 1 得对v p 0 ，取u = 彳 材，矿= a i b r v 2 1 u r b r l ，is 锄和+ 言v r b a 。1b ，v ， 则由( 3 2 3 ) 得 a s ( 1 + o ) u r 4 ”+ 够+ 1 + 吉) v r b a b r v + 西 ( 1 + o ) i l u r u + 够+ 1 + 吉) 石，v + 觚矿v = ( 1 + 踟l 甜+ 够+ 1 + 扣+ 觚 ，让 ( 3 2 4 ) 广义鞍点问题的块三角预条件子第三章广义鞍点问题的块三角预条件子 同理，取百满足击 百 o ， 则由( 3 2 4 ) 得 a ( 1 + d a l “r 材+ ( 1 + 矿 五l ， = ( 1 + 臼) a 1 ( r ”+ v ，v ) = ( 1 + 0 ) , 1 1 同理，对( 3 2 5 ) 取( 1 一扔厶= 够+ 1 一 ) 厶，则有 护厶+ 【+ 1 ) 五一厶 舀一石= 0 ， 取 矛：尘丝塑巡等型幽! 丛， 一，o - _ - _ _ - _ - _ 1 。 ，_ 易得两1 舀 石i 则有 杖y ) 黜2 + ( , 妇- l i ) o - 2 ， 其中 0 = 02 口 矿l ，“分别为b 证明：设a 为y 的特征值，w = ： 为其对应的特征向量，且i m l = ，则有 y 卧槲 n 2 “， 即 【0,42-一a。(e鲥tbbr。+召cr【vb(eta】= a 【： ，i d 。il1 ，i 由( 3 2 1 4 ) 有w r y w = , 1 w r w = 元即 a = u r ( 口a 2 一a ) u + 2 u r ( o a 一1 ) b r y + a r s b r v + v r c v ( 3 2 15 ) 在引理3 1 中令u = ( 以一1 ) u ，v = b r ，则对v p 0 有 2 i “r ( 鲥一d b r 叫锄7 ( 叫一d 2 材+ v r s s r v 则由( 3 2 1 5 ) 得 五，( a a 2 一爿) + 锄r ( 蒯一d 2 甜+ ( 口+ 言) v r b b r v + v r c v s l 一1 ) 1 1 + 联以1 1 ) 2 肌+ + 吉研+ 五n ( 3 2 1 6 ) 同理可得，取百 ：( o ) ，则由( 3 2 1 5 ) 有 a 以鲥- a ) 甜一酣( 叫一d 2 + 位一专) ，刀矿v + ，西 一1 ) 厶一酞哦一1 ) 2 u r u + 一言) 一 1 ，y ( 3 2 1 7 ) 广义鞍点问题的块三角预条件子 第三章广义鞍点问题的块三角预条件子 当1 ，= 0 时，定理3 3 中已经给出y 的特征值下考虑1 ，0 的情形对( 3 2 1 6 ) 取 。一1 ) a ，+ 吠以，一1 ) 2 = ( 口+ 言讲+ 磊， 则有 ( 以1 1 ) 2 矿+ ( 以l 一1 ) a 1 一口一一x j e - 一= 0 ， 取 则由( 3 2 1 6 ) 得 同理对( 3 2 1 7 ) 取 ( 3 2 18 ) a + 吾) 砰+ 石 ( + ，d = + 昙讲+ 磊 ( 3 2 1 9 ) ( 口厶一1 ) 厶一祆哦一1 ) 2 = 一言) 砖， 则有 ( 口厶一1 ) 2 萨+ 【识一( 口厶一1 ) 糊矛一一= 0 ， 取 蚕= 堕些篓巡舞等亟幽坐盟， 易得舀 ；1 则由( 3 2 1 7 ) 得 a 一言) 确( + ，y ) = ( 口一丢斌， 从而由( 3 2 1 9 ) 和( 3 2 2 1 ) 得 o 一言) 一s a s + 丢) 砰+ 磊， 则 | j ( 】，) 粼2 + 两o , t 两l ， 其中只否分别由( 3 2 1 8 ) 和( 3 2 2 0 ) 所定义 1 4 ( 3 2 2 0 ) ( 3 2 2 1 ) 口 第四章数值实验 本章中我们将用块三角阵兀及乃作为预条件子求得广义鞍点问题( 1 0 1 ) 的条件 数并用共轭梯度法求出其解第一节中我们考虑纯粹的代数结构的例子，第二节中我 们将考虑流体力学中的s t o k e s 方程并用q i 一局有限元方法进行离散，所得到的形式 即为( 1 0 1 ) 4 1数值实验l 本节我们考虑纯粹的代数问题在广义鞍点问题( 1 0 1 ) 中矩阵彳，b ，c 分别定义 如下： 其中m = 2 0 ，疗= 3 0 0 ii + 1 ，i = 工 彳= c 口玎，肪铆= ：二- 一j ，：= ，l ，, l0 ，其他 i1 ，i = 工 1 x 1 0 ， b = ( 6 u ) 肭= 2 ，f = 工1 1 工2 0 ， 10 ，其他 c 嘞k = r 瓮k 坯1 0 图4 1 卢取6 2 时对( 3 2 1 ) 用共轭梯度法求解所得到的收敛曲线 1 5 广义鞍点问题的块三角预条件子 第四章数值实验 先给出用乃作为预条件子所得到的线性系统( 3 2 1 ) ，这时所得到的预处理矩阵的 条件数可见表1 其中卢= 0 表示线性系统( 1 0 1 ) ，相对应的七为其条件数 表1 乃作为预条件子时，的条件数 e 01 0 3 0 6 06 27 08 0 i 七 1 6 5 2 2 e + 0 0 32 4 2 7 7 0 72 4 2 0 0 9 52 4 1 3 3 3 92 4 1 3 11 22 6 9 1 2 7 03 0 7 3 9 0 3 由表1 可看出经过预处理以后所得到的线性系统的条件数相应减少这时由于对应的 系数矩阵为对称正定阵，因而可以用共轭梯度法求解，所得到的迭代次数和误差之间 的曲线见图4 1 由计算可知，当误差限制在l o 一，1 0 _ 8 和1 0 - 1 0 时，用共轭梯度法求解分别只需要 9 0 ，1 0 0 和1 1 5 步，这说明用乃作为预条件子来处理广义鞍点问题( 1 0 1 ) 时计算效果 十分明显，但此时缺点是预处理线性系统( 3 2 1 ) 中出现了s c h u r 补b a - 1 b r 的计算 图4 2 当口= 2 2 5 3 8 时对( 3 2 1 2 ) 用预处理共轭梯度法求解所得到的收敛曲线 下面讨论用乃作为预条件子，所得到的线性系统( 3 2 1 2 ) 相x ：l - 5 = 线性系统( 3 2 1 ) ， 其中只有矩阵与矩阵及矩阵与向量的乘积并不包括s c h u r 补b a 1 b r 的计算当口取 为l + 圭2 2 5 3 8 时其条件数为1 4 3 0 4 e + 5 ，只有线性系统( 1 0 1 ) 的正规方程条件数 2 7 2 9 8 e + 6 的矗另外预处理线性系统( 3 2 1 2 ) 的一个好处在于不需要使用其正规方 程就可以把一个不定线性系统转化为一个对称正定线性系统由于( 3 2 1 2 ) 的条件数 依然比较大，在这种情况下共轭梯度法依然收敛比较慢，因而可以考虑用块对角预处 理共轭梯度法取三种块对角阵如下： m ：f 彳 10 l 0 1 b b r + cl j r 尬= i 【蝎= 鲥了彳胎罗+ c 】 广义鞍点问题的块三角预条件子第四章数值实验 分别用m ，朋，飓作为预条件子对( 3 2 1 2 ) 用预处理共轭梯度法所得到的迭代次数和 误差之间的曲线见图4 2 ( 其中- ，一分别代表m ，m 2 ，m 3 时得到的收敛曲线) 由计算可知，当误差限制在1 0 - 6 时，分别用m ，m s ，m 3 作为预条件子进行预处理 共轭梯度法求解分别只需要2 9 4 ，2 3 4 和1 5 4 步，比乃作为预条件子速度稍微慢了点 作为比较，我们用b a i & l i 在【3 中给出的限定的预处理共轭梯度法( r p c g ) 求解 广义鞍点问题( 1 0 1 ) 为了方便，我们用精确的形式取代 3 】中r p c g 方法的逼近形 式，另外，由于r p c g 方法中迭代的每步需要求解三个系数矩阵为对称正定的线性 方程组( 其中两个线性方程组的系数矩阵相同) ，因而可以把它看成是内迭代，所得到的 迭代次数与误差之间的曲线见图4 3 ( 其中内迭代也算作一次迭代) 此外，为了方便与 文中所给出的块三角预条件子进行比较，当误差限制在10 “时所用的计算时间可见表 2 ( 其中c p u 表示计算所用时间) 图4 3 限定的预处理共轭梯度法( p r c g ) 求解所得到的收敛曲线 表2 误差限制在1o “时三种方法的计算时间 乃 r p c g 丁l蚴m 2m 3 c p u0 7 3 4 00 3 2 8 0 1 6 1 0 01 4 6 9 01 2 1 8 0 由计算可知，当误差限制在1 0 4 时，用p r c g 方法只需要5 2 步，优于文中给出的两 种块三角预条件子，但由于这种方法迭代的每一步还需要求解三次线性方程组，因而 由表2 可以看出，其计算所用时间略多于兀预条件子，但少于乃预条件子，不过乃 预条件子的一个好处在于此时线性系统( 3 2 1 2 ) 不会出现s c h u r 补b a 一1 b 丁的计算这 说明本文所提出的两种块三角预条件子计算效果还是比较明显的 1 7 广义鞍点问题的块三角预条件子第四章数值实验 4 2数值实验2 考虑实空间r 2 中有界区域上的s t o k e s 方程： i y 材+ v p = 正i n k t v = 0 ，伽q 其中q 为实空间r 2 中有界区域，系数，为粘性系数，向量函数“= ( u i , u 2 ) ，为r 2 上 的速度向量，标量值函数p 表示压力，l a p l a c e 算子( ) 表示方程的扩散部分若把 s t o k e s 方程中的”，f 分别用分量形式表示再加上边界条件，则可由下给出： 一y ( 铬+ 争) + 箬= 石，i n d , 一“铬+ 移) + 考= 五，i n k 一等一纽o y = 0 ，i n d , i l l21 4 220 ，x = o , y = 0 ，工= 1 ， i l l21 ，i d 220 ，y 2 1 ，0 工 1 下面我们对s t o k e s 方程用低阶混合有限元( q i r ) 进行离散，所采用的单元为四边 形单元这种方法便于计算机程序的实现，但缺点是不满足l b b 稳定性条件，因而需 要采用一些方法使其稳定化，这里我们采用局部稳定化最后可得到如下的代数方程 组 a - c 】 ：】p = 其中 彳= 【言三】，b = c b - ，岛，材= 之】，= 羔】 当网格划分不同时，所得到的线性系统的维数可见下表： 表3 离散后得到的线性系统( 4 2 1 ) 的维数 五 l 1l 1l l 81 62 43 24 86 4 刀 9 84 5 01 0 5 81 9 2 24 4 1 8 7 9 3 8 m6 22 5 45 7 41 0 2 22 3 0 2 4 0 9 4 ( 4 2 1 ) 我们这里的数值实验选取的是当h = 去时所得到的线性系统( 4 2 1 ) 与数值实验1 一 样，我们先给出用乃作为预条件子所得到的线性系统( 3 2 1 ) ，这时所得到的预处理矩 阵的条件数可见表4 其中户= 0 表示线性系统( 1 0 1 ) ，相对应的议刃为其条件数 表4 r l 作为预条件子时，的条件数 l卢 o 2 0 0 5 0 01 0 0 02 0 0 06 0 0 08 0 0 0 k ( d 1 1 6 3 6 e + 0 2 01 2 2 7 01 1 4 7 91 1 4 7 61 1 4 7 51 4 5 4 71 9 3 9 4 1 8 广义鞍点问题的块三角预条件子第四章数值实验 由表4 可以看出，对s t o k e s 方程用q i r 有限元方法离散所得到的线性系统( 4 2 1 ) 是一个近乎病态的线性系统，这时用乃作为预条件子其条件数大为减小这时由于对 应的系数矩阵为对称正定阵，因而也可以用共轭梯度法求解，所得到的迭代次数和误 差之间的曲线见图4 4 由计算可知，当误差限制在1 0 - - 6 ，1 0 8 和1 0 1 0 时，用共轭梯度 图4 4 声取1 0 0 0 时对( 3 2 1 ) 用共轭梯度法求解所得到的收敛曲线 法求解分别只需要7 3 ，8 4 和1 0 7 步，这说明用乃作为预条件子来处理广义鞍点问题 ( 1 0 1 ) 时计算效果十分明显 同样，我们再来用乃作为预条件子来预处理( 1 0 1 ) ，所得到的线性系统( 3 2 1 2 ) 相对于线性系统( 3 2 1 ) ，其中只有矩阵与矩阵及矩阵与向量的乘积并不包括s c h u r 补 b a - 1 b r 当口取为1 + 士1 0 7 6 4 时其条件数为7 9 6 6 0 e + 5 ，比线性系统( 1 0 1 ) 的条 件数要小很多，更不用说线性系统( 1 0 1 ) 的正规方程的条件数另外预处理线性系统 ( 3 2 1 2 ) 的一个好处在于不需要使用其正规方程就可以把一个不定线性系统转化为一 个对称正定线性系统由于使用死作为预条件子所得到的线性系统( 3 2 1 2 ) 的条件数 比用兀作为预条件子所得到的线性系统( 3 2 11 ) 的条件数要大，在这种情况下共轭梯 度法依然收敛比较慢，因而我们同样可以考虑用块对角预处理共轭梯度法取与上节 中相同的三种块对角阵： 帕= ia 。肋icl ，必= 10 ，肋罗+ cl ，尬= l 鲥2 0 - 彳b 召l c1 分别用m ，尬，瞒作为预条件子对( 3 2 1 2 ) 用预处理共轭梯度法所得到的迭代次数和 误差之间的曲