（计算机软件与理论专业论文）大稀疏鞍点线性系统的迭代解法.pdf

东北大学博士学位论文 大稀疏鞍点线性系统的迭代解法 摘要 鞍点线性系统是一类对称不定的线性系统，它来源于鞍点型偏微分方程问题、 最优化问题、最小二乘问题等研究领域实际应用中导出的这类系统通常都是大规 模的，并且系数矩阵具有稀疏性，因此应采用迭代法进行求解然而，鞍点线性系统本 身特殊的结构特点使得一些著名的算法，诸如逐次超松弛迭代法( s o r ) 或共轭梯度 法( c g ) 均失去效力因此寻求解决大稀疏鞍点线性系统的有效的迭代解法具有重要 的现实意义 目前为人们所熟知的u z a w a 算法和m i n r e s 算法是两类求解鞍点线性系统的 有效方法u z a w a 算法格式简单，但收敛速度较慢m i n r e s 算法计算效率高，但计算 格式比较复杂寻求具有更简单的计算格式或者更快收敛速度的迭代算法，成为热门 的研究课题 经典的s o r 算法同样具有格式简单、存储量小的特点，因而早为人们所关注 近年来有学者开始研究广义化的s o r 算法来求解鞍点线性系统李长军等学者于 1 9 9 8 年首次提出了一种广义化的s o r 算法：g s o r 算法g o l u b 等学者于2 0 0 1 年提 出了s o r - l i k e 算法这两种算法本质相同，因此我们将其统称为广义化s o r 方法这 类算法具有同u z a w a 算法一样简单的计算格式，并带有一个预优矩阵 本文首先对s o r - l i k e 算法重新进行了深入的研究，采用比较初等的方法详细地 刻划了s o r - l i k e 算法迭代矩阵谱半径的基本特征；给出了s o r - l i k e 算法最优迭代参 数以及迭代矩阵谱半径的显式表达式；进一步证明了，通过选取合适的预优矩阵，可 以使s o r - l i k e 算法的迭代矩阵只含有实特征值，从而可以采用c h e b y s h e v 多项式加 速这一结果是令人振奋的，丰富了d m y o u n g 的超松弛理论；同时我们还更正了 g o l u b 在2 0 0 1 年关于s o r - l i k e 算法的收敛性分析中出现的错误 基于对s o r - l i k e 算法的理论分析，我们深入研究采用c h e b y s h e v 多项式对s o r - l i k e 算法进行加速，从而给出了g s o r - s i 算法理论分析和数值计算表明，这一算法 具有和s o r - l i k e 算法相近的计算开销，却拥有比s o r - l i k e 算法快得多的收敛速度 针对鞍点线性系统的特有的结构特点，我们提出两种含有两个迭代参数的广义 化s o r 算法，即g a o r 算法和t p g s o r 算法，给出了t p g s o r 算法的最优参数的 显式表达式以及相应的最优迭代矩阵谱半径的显式表达式t p g s o r 算法的计算格 i i 东北大学博士学位论文摘要 式同s o r - l i k e 算法一样简单，但理论分析和实验结果均表明它的收敛速度却大大提 高了 我们研究将预优共轭梯度算法口c g ) 应用于对鞍点线性系统的求解，并在理论上 直接证明了：p c g 算法具有比u z a w a 算法、s o r - l i k e 算法以及g s o r - s i 算法更快 的收敛速度数值计算结果也进一步证明了理论分析的正确性 对矩阵的特征值估计以及预优矩阵的选取在实际应用中具有重要的意义本文 讨论了这一问题，并对一类广为使用的预优矩阵给出了合理的解释 本文将所有论及的数值方法应用于数值求解定常s t o k e s 方程首先我们采用两 种混合有限元格式对定常s t o k e s 方程进行离散，并编程导出了相应的鞍点线性系 统，即由程序自动生成线性方程组的系数矩阵和右端项然后应用s o r - l i k e 算法、 g s o r - s i 算法、t p g s o r 算法、p c g 算法以及著名的m i n r e s 算法和u z a w a 算法 ( 或预优u z a w a 算法) 分别对所生成的线性方程组进行迭代求解数值计算结果完全 印证了本文的理论分析结论p c g 算法的收敛速度在6 种算法中最快；t p g s o r 算 法和g s o r - s i 算法的敛速接近于p c g 算法，而t p g s o r 算法和g s o r - s i 算法的优 势在于计算格式简单，存储量小，更适合并行运算 最后我们将所研究的方法应用于医学c t 图像重建，提出了基于加权最小2 一范 数准则的c t 代数重建模型在这一模型中，通过对加权参数的调熬可以控制对重建 图象的平滑消噪水平这个模型最终导出的方程与鞍点线性系统具有同样的格式将 p c g 算法应用于这一模型，导出了p c g 代数重建算法数值仿真结果表明，p c g 代 数重建算法较滤波反投影方法有更好的消噪能力 关键词鞍点线性系统，s o r 算法，广义s o r 算法，s o r - l i k e 算法，两参数广义s o r 算法，预优共轭梯度算法，s t o k e s 方程，c t 代数重建，加权最小2 范数准则， 共轭梯度重建算法 1 1 1 东北大学博士学位论文 a b s t r a c t i t e r a t i v em e t h o d sf o rl a r g es p a r s esa d d l e p o i n t l i n e a rs y s t e m s a b s t r a c t s a d d l ep o i n tl i n e a rs y s t e mi sas y m m e t r i ca n di n d e f i n i t el i n e a rs y s t e mo fe q u a t i o n s i t i sa l s ok n o w na sa u g m e n t e ds y s t e m i ta r i s e sf r o mm a n ys c i e n t i f i cr e s e a r c ha n de n g i n e e r i n g c o m p u t a t i o n ss u c ha sn u m e r i c a ls o l u t i o n so f p 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 ，t h eo p t i m i z a t i o n p r o b l e m sa n dl e a s ts q u a r ep r o b l e m s i np r a c t i c a la p p l i c a t i o n s ，t h i ss y s t e mo f t e ni sl a r g ea n d s p a r s e , t h u si ti ss u i t a b l et ob es o l v e db yi t e r a t i v em e t h o d s h o w e v e r ，t h es p e c i a ls l r u c t a r e o f t h i ss y s t e mm a k e ss o m ew e l l - k n o w na l g o r i t h m s ，f o ri 玎剜a n c e ，s u c c e s s i v eo v e r - r e l a x a t i o n ( s o r ) m e t h o do rc o n j u g a t eg r a d i e n t ( c g ) m e t h o di n v a l i d t h e r e f o r e ，i ti sh i g h l yd e s i r a b l e t od e v e l o pe f f e c t i v ei 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 es p a r s es a d d l ep o ml i n e a rs y s t e m u z a w am e t h o da n dm i n k e sm e t h o da r et w ow e l l - k n o w na l g o r i t h m sf o rs o l v i n gt h e s a d d l ep o i n tl i n e a rs y s t e m s u z a w am e t h o dh a sas i m p l ef o r m a tb u tal o wr a t eo f c o n v e r g e n c e ，w h i l em i n r e s m e t h o di sh i g h l ye f f e c t i v e ，b u th a sac o m p l e xf o r m a t t of i n d a na l g o r i t h mw h i c hh a sas i m p l e rf o r m a ta n dh i g h e re f f i c i e n c yi sa l lo p e np r o b l e m t h ec l a s s i c a ls o rm e t h o di ss i m p l ei nt h e o r y , h a sal i t t l er e q u i r e m e n tf o rs t o r a g e ，a n d i se a s i e rt oi m p l e m e n t ，h e n c ei ti sw e l c o m e db ys c i e n t i f i cr e s e a r c h e r sa n dc o m p u t a t i o n a l e n g i n e e r s u n f o r t u n a t e l y , t h es o rm e t h o dc a nn o tb ea p p l i e df o rs o l v i n gt h es a d d l ep o 缸 l i n e a rs y s t e mb e c a u s eo ft h es i n g u l a r i t yo ft h ed i a g o n a lp a r to ft h ec o e f f i c i e n tm a t r i x r e c e n t l yt h eg e n e r a l i z a t i o no fs o rm e t h o dh a sb e e ns t u d i e df o rs o l v i n gt h es a d d l ep o i n t l i n e a rs y s t e m l i ，l ia n de v a n sp r o p o s e da g e n e r a l i z e ds o r ( g s o r ) m e t h o d i n1 9 9 8f o r s o l v i n gt h ea u g m e n t e ds y s t e md e r i v e df r o mt h el e a s ts q u a r e sp r o b l e m t h e ni n2 0 0 0 ，l ia n d e v a n sg a v eam o r eg e n e r a lg s o rm e t h o df o rs o l v i n gt h ea u g m e n t e ds y s t e m i n2 0 0 1 ， g o l u b ，w ua n dy u a np r o p o s e das o r - l i k em e t h o d ，w h i c hi sas p e c i a le a s eo ft h eg s o r m e t h o dg i v e nb yl ia n de v a n si n2 0 0 0 t h e r e f o r e ，w ec a l lb o t ht h eg s o rm e t h o do fl i a n de v a n s ，a n dt h es o r - l i k em e t h o do f g o l u be ta lg e n e r a l i z e ds o r m e t h o d s g e n e r a l i z e d s o rm e t h o dh a sa s i m p l ef o r m a ta sw e l l ；m o r e o v e r , i th a sap r e c o n d i t i o n i n gm a t r i x i nt h i st h e s i s ，f i r s t l y ，t h ec o n v e r g e n c ea n a l y s i so f t h es o r - l i k em e t h o di sr e c o n s i d e r e d b yu s i n ga ne l e m e n t a r ym e t h o d , t h es p e c t r a li ”d d i l l so ft h ei t e r a t i o n m a t r i xi s f u i l y i v 东北大学博士学位论文a b s t r a c t c h a r a c t e r i z e d ；h e n c et h ee x p l i c i tf o r m u l a ef o rt h eo p t i r n u mp a r a m e m ra n dt h ea s s o c i a t e d o p t i m u ms p e c t r a lr a d i u sa r eg i v e n ；f n r t h e r n l o r e ，i ti ss h o w nt h a tb yap r o p e rc h o i c eo ft h e p r e c o n d i t i o n i n gm a t r i x , t h eo p t i m u mi t e r a t i o nm a t r i xo ft h es o r - l i k em e t h o dh a sn o c o m p l e xe g e n v a l u e s ，t h u si t c a l lb ea c c e l e r a t e db yc h e b y s h e v ep o l y n o m i a l t 1 1 i si sa s u r p r i s i n ga n de x c i t i n gr e s u l t ，w h i c he n r i c h e st h es o r t h e o r i e so fd m y o u n g b e s i d e s ， s o m ee r r o r si nt h ec o n v e r g e n c ea n a l y s i sg i v e nb yg o l u be ta 1 a r ec o r r e c t e d s e c o n d l y , b a s e do nt h er e s u l to ft h ec o n v e r g e n c ea n a l y s i so ft h es o r l i k em e t h o d ， c h e b y s h e vp o l y n o m i a la c c e l e r a t i o no f t h es o r - l i k em e t h o di st h e ns t u d i e da n dag s o r - s i m e t h o di sp r o p o s e df o rs o l v i n gt h ea u g m e n t e ds y s t e m t h e o r e t i c a la n dn u m e r i c a lr e s u l t s h a v es h o w nt h a tt h eg s o r - s im e t h o dh a sam u c hf a s t e rr a t eo f c o n v e r g e n c e t h i r d l y ，t w om o r ev e r s i o n so ft h eg s o rm e t h o dh a v eb e e nd e v e l o p e df o rt h e a u g m e n t e ds y s t e m ；e a c ho f t h e mh a st w op a r a m e t e r sa n do n ep r e c o n d i t i o n i n gm a t r i x 硼1 e t w on e wm e t h o d sa l ec a l l e dt h eg a o rm e t h o da n dt p g s o rm e t h o dr e s p e c t i v e l y t h e e x p l i c i te x p r e s s i o n so ft h eo p t i m a lc h o i c e sf o rt h et w op a r a m e t e r sa n dc o r r e s p o n d i n g s p e c l r a lr a d i u so f t h ei t e r a t i o nm a t r i xo f t p g s o rm e t h o da r eg i v e n t p g s o rm e t h o dh a s as i m p l es t r u c t u r ea sw e l l ，b u ti t sc o n v e r g e n c er a t ei sm u c hf a s t e rt h a nt h a to fs o r - l i k e m e t h o d f o u r t h l y , t h ep 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 e t h o do c g ) i sc o n s i d e r e df o r s o l v i n gt h es a d d l ep o 缸l i n e a ls y s t e m w et h e o r e t i c a l l yp r o v et h a tt h ec o n v e r g e n c er a t eo f p c gm e t h o di sf a s t e r ( a tl e a s tn o ts l o w e r ) t h a nt h a to fu z a w am e t h o d ，s o r - l i k em e t h o d a n dg s o r - s im e t h o dr e s p e c t i v e l y ，w h i c hi sa l s oc o n f i r m e db yn u m e r i c a lc o m p u t a t i o n s f i f l h i y , t h ec h o i c eo ft h ep r e c o n d i t i o n i n gm a t r i xi sc o n s i d e r e d t h eu p p e ra n dl o w e r b o u n d sf o rat y p eo fm a t r i c e sa r eg i v e n ，w h i c hl e a dt oa ne s t i m a t i o nt ot h ec o n d i t i o n n u m b e ro ft h et y p eo fm a t r i c e s t m sr e s u l t e x p l a i n sw h yt h ec h o i c eo fak i n d o f p r e c o n d i t i o n i n gm a t r i xb yg o l u ba ta 1 ( 2 0 0 1 ) a n dl ie ta l ( 2 0 0 3 ) f o rt h es o r - l i k em e t h o d w o r k sf i n e s i x t h l y ，a l lm e t h o d ss t u d i e di nt h i st h e s i sa r ea p p l i e df o rs o l v i n gt h es t a t i o n a r ys t o k e s e q u a t i o n 1 1 1 ee q u a t i o nw a sd i s c r e t e db yt w ot y p e so fm i x e df i n i t ee l e m e n tm e t h o d s r e s u l t i n gi na l la u g m e n t e ds y s t e mo fe q u a t i o n s ap r o g r a mw a sw r i t t e nf o ra u t o m a t i c a l l y g e n e r a t i n gt h ec o e f f i c i e n tm a t r i xa n dr i g h th a n ds i d eo f t h el i n e a rs y s t e m t h e nt h es o r - 1 i k em e t h o d , g s o r s im e t h o d , t p g s o rm e t h o d ，p c gm e t h o d ，m 肿t e sa n du z a w a m e t h o d ( o rp r e c o n d i t i o n e du z a w am e t h o d ) a r ea l la p p l i e dt ot h eg e n e r a t e ds a d d l ep o 缸 l i n e a rs y s t e m t 1 l en u m e r i c a lc o m p a r i s o n sh a v ec o n f i r m e dt h ec o l t e c t n e s so f t h et h e o r e t i c a l 。v 东北大学博士学位论文 a b s t r a c t a n a l y s i so ft h i sp a p e r t h en u m e r i c a lr e s u l t sd e m o n s t r a t ep c gm e t h o dh a st h ef a s t e s t c o n v e r g e n c er a t ea m o n ga l lm e t h o d sc o n s i d e r e d ，a n dt h ec o n v e r g e n c er a t e so fg s o r s i m e t h o da n d i p g s o rm e t h o da r ec l o s e dt ot h a to fp c gm e t h o d n o r et h a tg s o r - s i m e t h o da n dt p g s o rm e t h o d sa r em o r es u i t a b l et op a r a l l e lc o m p u t a t i o n f i r m l y ，a na p p l i c a t i o ni nc ti m a g er e c o n s t r u c t i o ni sc o n s i d e r e d ac ta l g e b r a i c r e c o n s t r u c t i o nm o d e lb a s e do nt h ew e i g h t e dl e a s t2 - n o r mc r i t e r i o ni sp r o p o s e d i nt h i s m o d e l ，t h es m o o t h i n gl e v e lo fr e c o n s t r u c t i o nc a r lb ec o n t r o l l e db ya d j u s t i n gaw e i g h t i n g p a r a m e t e r t h ep r o p o s e dm o d e lr e s u l t e di na na u g m e n t e ds y s t e mo fe q u a t i o n s t h ep c g m e t h o di sc o n s i d e r e df o rs o l v i n gt h el i n e a rs y s t e m s i m u l a t i o nr e s u l t sh a v es h o w nt h ep c g m e t h o di sb e t t e rt h a nt h eb a c kp r o j e c t i o nm e t h o di nt e r m so f e l i m i n a t i n gn o i s ee f f e c t k e yw o r d s s a d d l ep o i n tl i n e a rs y s t e m ，s u c c e s s i v eo v e r - r e l a x a t i o nm e t h o d ，g e n e r a l i z e d s o rm e m o s o r - l i k em e 也o d ，t w o - p a r a m e t e rg e n e r a l i z e ds o r m e t l l o d ， p 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 e t h o d ，s t o k e se q u a t i o n ，c ta l g e b r a i c r e c o n s t r u c t i o n ，w e i g h t e dl e a s t2 - n o r mc r i t e r i o n ，p r e c o n d i t i o n e dc o n j u g a t e g r a d i e n tr e c o n s t r u c t i o n v i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：季萄 日期- 谳寄罾月q 鼍 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 学位论文作者签名： 日期： 另外，如作者和导师不同意网上交流，请在下方签名；否则视为 同意。 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学博士学位论文 第一章引言 第一章引言 1 1 背景 科学计算通常会导出大规模的线性系统： a x = b 能否快速准确地得到线性系统的解，是实际工作中面临的重要问题 对于这些大规模的线性系统，即使在理论上可以判断出其解是惟一存在的，实际 应用中也会面临着种种的困难假设方程组的系数矩阵是n xn 阶的，则用c r a m e r 法 则求解方程组所用的计算量大约是铆2 1 ) 州，当玎= 2 0 时，约需要9 7 1 0 2 0 次乘法， 如果用每秒百万次的计算机来计算，需要三千万年的时间即使采用g a u s s 消去法等 直接方法，其计算量也大致在o ( n 3 ) ，当n 很大时，也需要不小的计算开销因此后来 人们提出了采用迭代法来解决这一问题迭代法每次迭代的计算量大致为o ( n 2 ) ，好 的迭代法可以在很少的迭代步内得到高精度的解，相比较而言确实加快了求解的速 度迭代法的另一个特点是可以充分利用和保持系数矩阵的稀疏性，这样就有可能节 省内存开销因此可以说，采用迭代法解决上述问题，在时间上和空间上都占有某些 优势 系数矩阵具有稀疏性的大规模的线性系统简称为大稀疏线性系统采用迭代法 来求解大稀疏线性系统已经得到了专家们的广泛的共识 任何一种方法都不是万能的不同的迭代解法适用于不同的线性系统某些具有 特殊结构的线性系统很难应用常规的迭代算法来进行求解，而这些系统往往具有很 广泛的应用背景因此，为这些特殊的大稀疏线性系统找到“量身定做”的迭代解法， 成为重要的研究课题 1 1 1 鞍点线性系统的来源 本文将主要考虑如下的线性系统 b 盒踟0 书 t ， l 如jl q ”“ 其中a r 为对称正定矩阵，b r 为列满秩矩阵，向量x ，b r ”，y ，q r “， m 弗易知系统( 1 1 ) 存在惟一解 东北大学博士学位论文第一章引言 线性系统( 1 1 ) 称作鞍点线性系统( s a d d l ep o i n tl i n e a rs y s t e m ) ，也称作扩充系统 ( a u g m e n t e ds y s t e m ) 卜5 1 或者k k t 系统吲，它的应用来源很广，譬如： 1 鞍点型偏微分方程问题这类问题主要来源于流体力学问题导出的数学模型， 如著名的s t o k e s 问题卜”。2 ”本文将在第六章中对s t o k e s 问题做具体论述 2 最优化问题文献 2 9 】指出，寻求二次泛函 j ( v ) = 9 ( a v ，v ) 一( b ，v ) 关于集合 u = v r ”：b 7 v = q 的相对极值( 其中a ，b ，b ，q 的定义同( 1 1 ) ) 的问题可以转化为方程组( 1 1 ) 3 最小二乘问题文献 3 0 ，p p 2 1 0 2 11 指出，对于方程组 b y = b 其中矩阵b 的定义同( 1 1 ) ，它的最小二乘解是正规化方程组 b b y = b 1 b 的解而这个正规化方程组也可以写成等价形式 堋书 从而与系统( 1 1 ) 有相似的结构文献 3 1 1 也有相关的结论 鞍点线性系统也出现于许多其他研究领域中，不再一一赘述总之，其应用背景 是相当广泛的 1 1 2 鞍点线性系统的特点 鞍点线性系统( 1 1 ) 具有几个鲜明的特点首先，它的系数矩阵是对称不定的事 实上，考察矩阵 w = ( 参b 易见矩阵w 是对称的，另外成立 w = 躲一b h ) ( ab 这说明矩阵w 既有正的特征值也有负的特征值 矩阵w 的另一个特点是对角块中有奇异矩阵( 具体地说，是零矩阵) 综上所述，鞍点线性系统( 1 ，1 ) 是对称不定的、系数矩阵对角块中含有奇异矩阵 的线性系统 东北大学博士学位论文第一章引言 以上所述的系统( 1 1 ) 所国有的特点使一些著名的迭代解法，如s o r 算法以及 p c g 算法难以直接应用h 3 2 。3 ”，原因在于： 1 p c g 算法只对对称正定的系统有效，而系统( 1 1 ) 的系数矩阵w 是对称不定的 2 s o r 算法要求系数矩阵的对角块矩阵是非奇异的，而矩阵w 不满足此条件 正是由于大稀疏鞍点线性系统具有如此广泛的应用来源和重要的应用价值，而 常规的迭代解法难以适用于对此系统的求解，因此寻求适宜的求解大稀疏鞍点线性 系统的迭代解法这一课题才受到了众多学者的关注对这一课题的详尽论述，可参见 文献 1 - 4 ，3 2 - 4 5 】 1 2 研究现状 目前，人们已经得到了几种比较成熟的求解系统( 1 1 ) 的算法，其中包括古典的 u z a w a 算法【4 1 以及近年来比较热门的非精确u z a w a 算法臣3 1 和m i n r e s 算法【4 5 】本 文所主要讨论的广义化s o r 方法和p c g 算法也是非常具有竞争力的算法 1 2 1 两种已知的算法 较早为人们所熟知的求解系统( 1 1 ) 的经典算法是u z a w a 算法u z a w a 算法格式 简单，需要的存储空间小，易于并行化处理，是一类较早出现的比较成功的定常迭代 算法，其具体计算格式可参见文献【4 】或本文的第五章 1 9 9 8 年b f i s c h e r 等学者提出了m i n r e s ( m i n i l n u n 2 r e s i d u a l ) 算法这一算法适 用于对称非正定线性系统的求解与u z a w a 算法相比，m t n r e s 算法的收敛速度较 快，但它的计算格式比较复杂，具体参见文献 4 5 ，4 6 这两类算法目前仍然为许多专家们所关注，对它们的进一步讨论( 如非精确 u z a w a 算法和预优m i n r e s 算法) 也是当前的研究方向之一同时，学者们也相继开 发出新的算法人们期望新算法具有比u z a w a 算法更快的计算效率，或者具有比 m i n r e s 算法更简单的计算格式或更少的存储空间 1 2 2 广义s o r 方法 在迭代法的历史中，d m y o u n g 于2 0 世纪7 0 年代提出的s o r 算法( s u c c e s s i v e o v e r - r e l a x a t i o n ) t 卅曾经以其优雅简洁的格式而风靡一时，是一类经典的迭代算法 遗憾的是，由于1 1 - 2 节中所提及的原因，经典的s o r 算法不适用于求解鞍点线性系 统系统( 1 1 ) 查! ! 查兰堡主兰竺垒圣堑二羔! ! 三 对经典理论的继承和发扬是永无止境的近年来，一些学者开始讨论用广义化的 s o r 方法来解系统( 1 1 ) ，并取得了新的进展李长军等学者m 。4 1 于1 9 9 8 年最早提出 了广义s o r 算法，简称g s o r ( g e n e r a l i z e ds o r ) 舅t 法 文献【3 2 ，3 3 】讨论了当a = i ( 单位矩阵) 时的情形，采用的分裂格式为： ( ；烈o h 言再 z ， 导出迭代算法： ( q 言? 1 ：) ；：) = ( 苫- p b y 八y x o 。，+ ( ： ，c 七= ，2 ，c - s ， 其中p 为迭代参数，而p 为预优矩阵 文献 3 3 给出了g s o r 算法的收敛性分析以及参数p 的选取方法 文献 3 4 1 采用了更一般的分裂格式： ( 0 b = ( a b + ? 1d 0 2 一( 。0 1 一d 芋 ， c 4 ， l b jl 1 2j 2j p + 吖 从而又给出种更广义的s o r 类算法： ( a 1 参艘) = ( 0 1 0 苌刖心阶啦，n s ，l i ；7 i 2j l y t + l j = li 2 j l y j + l q j ( 七。= 1 ，2 ，+ t 1 5 其中d 。，d ，为预优矩阵，许多迭代算法如u z a w a 算法都可以看作是( 1 5 ) 的特例 2 0 0 1 年，g o l u b 等学者在文献 3 5 】中采用了一个更接近于经典s o r 算法的分裂： ，ab 、 ll = d l u ，( 1 6 ) ib t 0j 一一。一 、“o 其慨( a 护= ( 一 ： ，u = ( 0 苫) 舢预优矩降 进而也给出一类广义的s o r 类算法： c 。一扎悦 = 【( 1 一叻。+ 洲剖+ 心舻啦，吐乃 称作s o r - l i k e 算法需要说明的是，若取 d j ：竺a ，d 2 ：土q ， 则g s o r 算法( 1 5 ) 变为s o r - l i k e 算法( 1 7 ) ，因此本文将在以后的讨论中将s o r - l i k e 算法和g s o r 算法统称为广义s o r 方法另外需指出的是，文献 3 5 】的推导中存在 错误需要进行修正本文将在第二章中做详细论述 东北大学博士学位论文第一章引言 1 2 3p c g 算法 对于对称正定( s p d ) 的线性系统，目前最被看好的一类算法是共轭梯度算法，简 称c g ( c o n j u g a t eg r a d i e n t ) 算法它首先由m i lh e s t e n s 和e s t i e f e l 于1 9 5 2 年提出 4 8 j ，后来发展成为一类比较成熟的迭代解法实际应用中通常需要对系数矩阵进行 预优处理，这就导出了预优共轭梯度法，简称p c g ( p 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 t ) 算法详细的论述可参见文献f 4 ，3 0 p c g 算法具有很多良好的性质，主要有： 1 无需选取迭代参数 2 ，理论上有限步之内就可以得到精确解，实际计算中的收敛速度也往往很快 在1 1 2 节中已经提到系统( 1 1 ) 的系数矩阵是非正定的，因此也不能直接应用 p c g 算法进行求解不过，由系统( 1 1 ) 可以推得 ( b 1 a b ) y = b 1 a b q ，( 1 8 a ) x = a 。( b b y ) ，( 1 8 6 ) 其中矩阵b 1 a 。b 是对称正定的，因此可以采用p c g 算法先对方程组( 1 。8 a ) 求y ，再 代入方程组( 1 8 b ) 求x 而得到方程组的解有些文献中称此算法为块p c g 算法，本文 仍称作p c o 算法，并将在第五章中做详细的论述 1 3 本文所研究的主要内容及结构 本文首先在下章( 第二章) 对s o r - l i k e 算法重新进行了深入的研究，采用比较 初等的方法详细地刻划了s o r - l i k e 算法迭代矩阵谱半径的基本特征；给出了s o r - l i k e 算法最优迭代参数以及迭代矩阵谱半径的显式表达式；进一步证明了，通过选取 合适的预优矩阵，可以使s o r - l i k e 算法的迭代矩阵只含有实特征值，从而可以采用 c h e b y s h e v 多项式加速这一结果丰富了d m y o u n g 的超松弛理论；同时还更正了 g o l u b 在2 0 0 1 年关于s o r 1 i k e 算法的收敛性分析中出现的错误 在第三章，基于对s o r - l i k e 算法的理论分析，我们深入研究采用c h e b y s h e v 多项 式对s o r - l i k e 算法进行加速，从而给出了g s o r - s i 算法理论分析和数值计算表明， 这算法具有和s o r - l i k e 算法相近的计算开销，却拥有比s o r - l i k e 算法快得多的收 敛速度 在第四章，针对鞍点线性系统的特有的结构特点，我们提出两种含有两个迭代参 数的广义化s o r 方法，即g a o r 算法和t p g s o r 算法给出了t p g s o r 算法的最 优参数的显式表达式以及相应的最优迭代矩阵谱半径的显式表达式t p g s o r 算法 的计算格式同s o r - l i k e 算法一样简单，但理论分析和数值计算结果均表明它的收敛 速度却大大提高了 东北大学博士学位论文第一章引言 在第五章，我们研究将预优共轭梯度算法口c g ) 应用于对鞍点线性系统的求解， 并在理论上直接证明了：p c g 算法具有比u z a w a 算法、s o r - l i k e 算法以及g s o r - s i 算法更快的收敛速度数值计算结果也进一步证明了理论分析的正确性 对矩阵的特征值估计以及预优矩阵的选取在实际应用中具有重要的意义本文 在第五章讨论了这一问题，并对一类广为使用的预优矩阵的合理性给出了解释 本文在第六章将所有前面论及的数值方法应用于数值求解定常s t o k e s 方程首 先我们采用两种混合有限元格式对定常s t o k e s 方程进行离散，并编程导出了相应的 鞍点线性系统，即由程序自动生成