（计算数学专业论文）一类线aor迭代算法.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以一求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意 作者签名 日期 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进人 学校图书馆被查阅；有权将学位论文的内容编人有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用 本规定 作者签名 日期 m a s t e r sd e g r e ep a p e r a p r i l ，2 0 0 y = = = = = = = = 一一 、2 = 一 摘要 在本论文中，我们将一类线s o r 算法( s o r l ) 【1 0 】推广到线 a o r 算法f a o r l ) ，这些线a o r 算法及修正的线a o r 算法或 由线s o r 算法通过点松弛或者线松弛得到，或由线a o r 算法通 过标准外推，然后进行一些简单的消去得到接着讨论了这些算 法在矩形网格上的实现问题最后给出了一些数值试验，数值结 果表明选取适当的参数，一些线a o r 算法的性能优于线s o r 算 法及修正的线s o r 算法 关键词：线性方程组；稀疏矩阵；微分格式；线a o r 算法 修正的线a o r 算法 2 ac l a s so f i i n en l e 口t e r sd e g r e ep a p e r a b s t r a c t t h i sp a p e rg e n e r a t e sac l a s so fl i n e - s o ra l g o r i t h m s ( o rf o r b r e v i t ys o r l ) 1 0 】i n t oac l a s so fl i n e - a o ra l g o r i t h m s ( o rf o r b r e v i t ya o r l ) t h e s ea l g o r i t h m sa l ed e r i v e df r o mt h el i n ev e r s i o n s o ft h es t a n d a r da o rm e t h o db ym e a n so fap r e l i m i n a r ye l i m i n a - t i o no rp o i n ta n dl i n er e l a x a t i o nf r o ms o r l t h ei m p l e m e n t a t i o n o ft h o s ea o r la l g o r i t h m si nr e c t a n g u l a rg e o m e t r yi sd i s c u s s e di n d e t a i l f i n a l l y , s o m en u m e r i c a le x a m p l e sa r ep r e s e n t e dt os h o w t h a t o u rm e t h o d sa r ee f f e c t i v e k e yw o r d s ：l i n e a re q u a t i o ns y s t e m s ；s p a r s em a t r i c e s ；d i f - f e r e n c ef o r m u l a s ；l i n e - a o ra l g o r i t h m s ；m o d i f i e dl i n e - a o ra l g o - r i t h m s z h a n gj i n | i m a s t e r sd e g r e ep a p e r a p r l l ，2 0 0 6 c h a p t e r1 i n t r o d u c t i o n c o n s i d e rt h el i n e a rc q u a t i o n s a s = c ( 1 ) w h e r e 曲，c 舻a n dai san o n s i n g u l a rm a t r i x ，t r a d i t i o n a l l y , al a r g ec l a s so f i t e r a t i v em e t h o d sf o rs o l v i n ge q ( 1 ) c a nb cf o r m u l a t e db ym e a n so ft h es p l i t t i n g a = m 一 ( 2 ) w h e r emi sn o n s i n g u l a xa n dt h ea p p r o x i m a t es o l u t i o n 西( 。) i sg e n e r a t e da sf o l l o w s ： m s = + c ，t 20 ( 3 ) o re q u i v a l e n t l y 咖( ”1 ) = ( ) + m 一1 e ，t 0 w h e r et h e s t a r t i n gv e c t o r 西( o ) i sg i v e na n d = m n i st h ei t e r a t i v em a t r i x t h e a b o v ei t e r a t i v em e t h o di sc o n v e r g e n tt ot h eu n i q u es o l u t i o n 击= a 一1 c f o re a c h 曲( o ) i f a n do n l yi f p ( ) 1 i fmi sam o n o t o n em a t r i x ，i e ，m - 1 0f i n e n t r y w i s es e n s e ) ，t h e nt h e s p l i t t i n g ( 2 ) i sd e f i n e da s 【1 1 】 1 ar e g u l a rs p l i t t i n go f a i f n 0 2 an o n n e g a t i v es p l i t t i n go fai fm 一1 n20a n dn m 一1 0 3 aw e a kn o n n e g a t i v es p l i t t i n go fai fe i t h e rm 一1 n 0o rn m 一1 0 c l e a r l y , ar e g u l a rs p l i t t i n gi san o n n e g a t i v es p l i t t i n ga n dan o n n e g a t i v es p l i t t i n gi saw e a kn o n n e g a t i v es p l i t t i n g w h e nai sam o n o t o n em a t r i x ，t h e na l l 3 4ac l a s so f l i n e m a s t e r sd e g r e ep a p e r t h ea b o v es p l i t t i n ga r ec o n v e r g e n ta n dm a n yc o m p a r i s o nt h e o r e m sa r ep r o v e ni n 1 3 u n d e rp r o g r e s s i v e l yw e a k e rb u tn a t u r a lc o n d i t i o n sa sw e l la sh y p o t h a , sw i t h i n c r e a s e dc o m p l e x i t yi nt h e i rv e r i f i c a t i o n t h ef o l l o w i n gt h e o r e m sw i l lb eu s e f u l i no u ra p p l i c a t i o n t h e o r e m1 1 l e ta = m 1 一l = m 2 一2b et w on o n n e g a t i v es p l i t t i n g o f a w h e r e a 。三0 i f 2 2 1 t h e n p ( 肘f 1 1 ) 茎p ( 岈1 n 2 ) 0 ) i fm f l2m e l ，t h e n p ( m f l 1 ) ( 1 w h e r e 屯，i = 1 ，2 ，n i s t h e i t ho r d e rs u b s e q u e n t i a lp r i n c i p a l m i n o r d e t e r m i n a n t 0 f m a t f i xb p r o o f i ( 1 ) a s s u m et h a t b=klu=(耋u耋12莩。!l。：，。 w h e r e 肚( d l d 2厶) ，l = 一c “0 ：。) ，c ，= 一( 。：2 、n ) 8ac l a s so f l i n em a s t e r sd o g r e ep a p e r p t p 2 - p 。i = 。一l ( 1 7 饥1 耽。，肼。) u = ( 8 1dbdj)一(。210p17。，。：-一。)f。2 p l = d l p 2 = d 2 1 2 1 u 1 2 p l p a = d 3 l a 2 u 2 3 p 2 p n 一1 = 以一l i n - 1 , 。- - 2 u 。一2 。一1 协 一2 p n = 如一n , n - - 1 u 。1n p n l m o r e o v e r ，f r o mt h ea b o v ee q u a t i o n s ，w eh a v e p l = d l = t 1 mhd2pl-121u12dld2-121u12 一 p lp l k t 肌= t i t i l ，2 i n ，t h e n p i + 12d l 1 一l i + l l u l i n | p i = 堡! ! 翌! 二! ! ! ! 兰垒! 致 t 2 一 t l u n 1 “ 0 c h a p t e r29 吨+ l d 1 “” z 2 1 d 2 u 2 3 f 3 2d s 让2 一i , i f ： 一l d t d lu 1 2 z 2 1d 2u 2 3 f 3 2d 3 。“ 2 i1 k 一1 t 一2d 。一1 d 1u 1 2 z 2 ld 2u 2 3 f 3 2d 3 l i - - 1 4 岛i l盔 d l 札1 2 f 2 ld 2u 2 3 f 3 2d s d l “1 2 f 2 1 4 2 u 2 3 2 3 2 d 3 r t 正l - 2 i - l 1 i - 1 - 2d 一l i l k l反 d l “1 2 f 2 ld 2 “2 3 f 3 2d 3 。 札t 一2 i l 屯一1 1 2 以一l d 1 “1 2 f 2 ld 2 “2 3 z 3 2如 + 。“ 一1 1 i 群一l噍 ac l a s so f l i n em a s t e r sd e g r e ep a p e r d l “1 2 如id 2 “2 3 f 3 2d 3 u t i + l z l l 也+ l d 1u 1 2 f 2 1 如“2 3 f 3 2d 3 。 “l 一“ z “一ld t ( 2 ) la n d ua f ea s f o l l o w s l = u = o f 自+ 1 1 0 l k + 2 2 z 。一k - 0 0 - “l + 1 0 “2 + 2 u n 一n 0 c h a p t e r2 l | n em e t h o d sl l w h e r e2 k n 1 i t i se a s y t os e e t h a t d l i se q u i v a l e n tt o p 1 = d l p 2 = d 2 l p 1 l p 2 1 p 3 m = 也 p k + 1 = d k + 1 一f k + 1 1 1 l 1 + 1 p l p k + 22d k 十2 一l k + 2 ，2 u 2 ，k + 2 m 1 p 。 p n 一1 = d n l k 1 n k 一1 “ 一k l m 1 p 一一l p n = 如一f 。一k z h k ，。p n k 巨 ac | a s so f l l n em a s t e r sd e g r e ep a p e r a sw ek n o w ，t h es u b s e q u e n t i a lp r i n c i p a lm i n o rd e t e r m i n a n to f m a t r i xbi sn o n z e r o t h e n t k + l t k2 lk + 1 f + 1 1d k + l o d k + l f k + l ，i u l ，k + l 助l 以+ l l k + l ，1 “l 。k + l p l p l 0 p 2 o = d k + l i k + l ，l u l ，k + l p l = p k + l p c h a p t e r2 l i r t em e t h o d s1 3 n o w ，s u p p o s et h a t t k + l t k “一1 = z b + l “i k + i ： d k + l f k + 1 _ 1 l k + 2 ，2 f + 1 i l 也+ 一i 0 d k + l 一“+ ；， u 。，k + t m p ：i = d k + t z + p 札i ，k + i 肼 = p k + ，0 i 0 t h ec o m p a r i s o no fs p e c t r a lr a d i io fi t e r a t i o nm a t r i c e sa r i s i n gi n t h em e t h o d sd e f i n e da b o v ec a nb ei d r d eb ym e a n so ft h ef o l l o w i n gl e m m a l e m m a 2 1 1 0 】l e tt h ep o i n tj a c o b im a t r i x j = k 一1 ( 工+ u ) b ean o n n e g a t i v e m a t r i xs u c ht h a tp ( d ) 1 f u r t h e r ，l e tz g = 蟾1 n ab et h ep o i n tg a u s s - s e i d e l m a t r i xd e f i n e db y ( 7 ) a n d2 g = 磁1 廊b et h el i n eg a n s s - s e i d e lm a t r i xd e f i n e d b y ( 9 ) t h e na l lt h ea b o v em a t r i c e sa r ec o n v e r g e n ta n d 0s p ( 2 g ) p ( g ) sp ( z j ) 1 ( 1 3 ) 1 6ac l a s so f i i n em a s t e r sd e g r e ep a p e r 2 2t h el i n es o r ( s o r l ) a l g o r i t h m s t h ea p p l i c a t i o no ft h eo v e r r e l a x a t i o np r o c e s si nt h el i n eg a u s s _ s e i d e la l g o - r i t h ml e a d st oi n c r e a s i n gt h er a t eo fc o n v e r g e n c ea n dt h i sp r o c e s sc a l lb cr e a l i z e d i nt w ow a y sd i s t i n g u i s h c lh e r ea sp o i n tr e l a x a t i o na n dl i n er e l a x a t i o nd e s c r i b e d b e l o w p o m tr e l a x a t i o n ：u s i n g t h eo v e r r e l a x a t i o nt o ( 1 2 b ) w eo b t a i nt h ef o l l o w i n g e x e c u t i v ee q u a t i o n s ： 叶( 。+ 1 ) = l l p 17 ( 。+ 1 ) + 巩西( 蚪) + l 2 ( 。) + c ( 蚪1 ) = w p 一1 巩咖( 芒+ 1 + 町o + 1 】+ ( 1 一u ) 西( 2 t2 0 ( 1 4 a ) ( 1 4 b ) r e p r e s e n t i n gt h el i n es o ra l g o r i t h m sw i t ht h ep o i n tr e l a x a t i o n ( c a l l e df o rb r e v i t y t h ep s o r la l g o r i t h m ) a n dc h a r a c t e r i z e db yt h ef o l l o w i n gs p l i t t i n gm a t r i c e s ： 碑。= 三吼一u 巩】，取。= 1 d l 。+ ( 1 一u ) ( p l ，) 】 2 ，= 厨岳1 取。= ( ，一u b ：1 巩) 一1 巧1 w l 2 + ( 1 一u ) ( p l 1 ) i ( 1 5 ) w h e r e j 乩= ( i 一l p 一1 ) p ( ，一u p 一1 u ) l i n er e l a x a t i o n ：t h ea p p l i c a t i o no ft h eo v e r r e l a x a t i o n st o ( 1 1 ) p r o v i d e s ： ( ，一p 一1 仉) ( + 1 ) = u p 一1 叩( + 1 + ( 1 一u ) ( ，一p 一1 仉) 妒( 日( 1 6 ) a n dw eo b t a i nt h ef o l l o w i n ge x e c u t i v ee q u a t i o n s ： r ( + 1 ) = l 1 p 一1 卵( 蚪1 ) + 仉曲( 。+ 1 ) + l 2 曲( 。) + c 件1 ) ：p 一1 i v l 移+ 1 + ( u 一1 ) u 1 西( + w r ( + 1 】+ ( 1 一u ) t 0 ( 1 7 a ) ( 1 7 b ) r e p r e s e n t i n gt h el i n es o ra l g o r i t h m sw i t ht h el i n er e l a x a t i o n ( w e l lk n o w na s l s o r la l g o r i t h m ) a n dc h a r a c t e r i z e db yt h ef o l l o w i n gs p l i t t i n gm a t r i c e s ： 凰。：三旧一。吲，厕，：三p 如+ ( 1 一u ) b 】 2 b = 勋五1 瓤。= ( f w b 一1 觇) 一1 p b 一1 a + ( 1 一“) ，】 ( t s ) c h a p t e r2l i n em e t h o d s 1 7 w h e r ebi sd e f i n e db y ( 8 ) i nt h ea b o v em e t h o d ，w h e nt h ec o e f f i c i e n tm a t r i xai s2 - c y c l i cc o n s i s t e n t l y o r d e r e d t h es p e c t r a lr a f i u sp ( z 抽) 1f o ra l l0 u 2 ，a n do - ) o p ，m i n i m a l i z i n gp ( z f 5 ) c a nb cd e t e r m i n e db yf i n d i n gt h ev a l u eo ft h es p e c t r a lr , ”l i u sp ( 2 g ) d e f i n e di n ( 9 ) ，a c c o r d i n gt ot h ef o l l o w i n gf o r m u l a ： ， 2 e2 u = = = = = = ， 1 + 4 1 p ( g ) w h e r ep ( b ) = 0 1 ，i e ， p ( z b ) ：掣! 三! 堕! 2 3t h el i n ea o r ( a o r l ) a l g o r i t h m s t h ea p p l i c a t i o no ft h ea c c e l e r a t i o no v e r r e l a x a t i o np r o c e s si nt h el i n es o r a l g o r i t h ml e a d st oi n c r e a s i n gt h er a t eo fc o n v e r g e n c ea n dw ea s ep o i n tr e l a z a t i o n t ol s o r l a l g o r i t h mw eo b t a i nt h ep o i n tr e l a x a t i o nl i n ea o r m e t h o d ( c a l l e df o r b r e v i t yt h ep l a o r la l g o r i t h m ) u s i n gt h ep o i n ta c c e l e r a t i o no v e r r e l a x a t i o nt o ( 1 7 b ) w eo b t a i nt h ef o l l o w i n g e x e c u t i v ee q u a t i o n s ： 7 7 ( 抖1 ) = l 1 p 一1 ，7 ( 蚌1 + 妒 件1 + 2 。+ cf 1 9 a 1 咖件1 = 等p 一1 f 仉件1 + ( 一y 一1 ) u 咖( ) + 7 叩( 。+ 1 】+ ( 1 一u ) 曲( ” t2o ( 1 9 b ) r e p r e s e n t i n gt h el i n ea o ra l g o r i t h m sw i t ht h ep o i n tr e l a x a t i o n ( c a l l e df o rb r e v i t y t h ep l a o r la l g o r i t h m ) a n dc h a r a c t e r i z e db yt h ef o l l o w i n gs p l i t t i n gm a t r i c e s ： 弛r 言b u 吼 v 知= 三【b 孝一u b + u l 2 w 1 8ac l a u so f i i n e m a s t e r sd e g r e ep a p e r 2 叫= 磕1 霄= 【b 导一u 一1 b 等一w b + u l 2 】 ( 2 0 ) w h e r e b 等= ( ，一l 1 p 一1 ) p ( j w p 一1 玩) w h e nu=1t h ep l a o r la l g o r i t h mi st h cl s o r la l g o r i t h m a n dw h e nu= ，y = 1t h ep l a o r la l g o r i t h mi st h eg s la l g o r i t h m i fw eu s el i n er e l a x a t i o nt op s o r l a l g o r i t h m ，w eo b t a i nt h el i n er e l a x a t i o n p o i n tr e l a x a t i o nl i n ea o rm c t h o d ( c a l l e df o rb r e v i t yt h el p a o r la l g o r i t h m ) u s i n gt h el i n ea c c e l e r a t i o no v e r r e l a x a t i o nt o e x e c u t i v ee q u a t i o n s ： 卵( + 1 ) = 三l p 一1 r ( 件1 ) + 现咖( + 1 ) - bl 2 西( ) + c ( 1 4 b ) w eo b t a i nt h ef o l l o w i n g 妒o + 1 ) = t p 一1 矾妒( + 1 1 + u 尸一1 叩( h 。1 + ( “j 一7 ) p 一1 u l q b ( 。+ ( 1 一u ) 毋( 。) ( 2 1 a ) t 0 ( 2 1 b ) a n dc h a r a c t e r i z e db yt h et o l l o w i n gs p h t t i n gm a t r i c e s ： 1 1 届，2 五峨一“蜴1 ， 如= 三暇一u b + 心】， 2 扣= 廊；1 风，= 【b u 巩 一1 【目一w b + w l 2 】 ( 2 2 ) w h e r e z k = ( i 一厶p - 1 ) p ( f 一1 p 一1 矾) w h e nu = t h el p a o r la l g o r i t h mi st h ep s o r l a l g o r i t h m ，a n dw h e nw=7= 1t h el p a o r l a l g o r i t h mi st h eg s la l g o r i t h m i fw eu s es t a n d a r de x t r a p o l a t i o nt op o i n ts o r la l g o r i t h m w eo b t a i nt h e s t a n d a r dr e l a x a t i o np a o r l m e t h o d ( c a l l e df o rb r e v i t yt h es p a o r la l g o r i t h m ) c h a p t e r2 l i n em e t h o d a t h ee x e c u t i v ee q u a t i o n si s ： 面o + 1 = l 1 p 一1 叩( 件1 + 7 u 2 ( 。+ 1 + ( u 一7 ) 巩+ w l 2 】咖( ”+ w c + ) = p 一1 b u l 毋o + 1 + 面( 。+ 1 + ( u 一，y ) u l ( 。】+ ( 1 u ) ( t 三0 ( 2 3 a ) ( 2 3 b ) a n dc h a r a c t e r i z e db yt h ef o l l o w i n gs p l i t t i n gm a t r i c e s ： 矾2 圭旧一，y 巩 ， 成f2 言 ( 1 一u ) 口+ ( “，一7 ) + w l 2 l ， 2 “= 磊1 0 = i b 一7 魄】一1 ( 1 一u ) b 十( u 一1 ) 巩+ u l 2 ( 2 4 ) w h e nu = ，yt h es p a o r la l g o r i t h mi st h ep s o r la l g o r i t h m ，a n dw h e nu=7= 1t h es p a o r la l g o r i t h mi st h eg s l a l g o r i t h m i fw eu s es t a n d a r de x t r a p o l a t i o nt o l i n es o r la l g o r i t h m w eo b t a i nt h e s t a n d a r dl i n er e l a x a t i o nl a o r lm e t h o d ( c a l l e df o rb r e v i t yt h es l a o r la l g o - r i t h m ) t h ee x e c u t i v ee q u a t i o n si s ： 面水+ 1 ) = l t p 一1 叩( 抖1 + 7 u 2 妒( 。+ 1 + ( ( u 一7 ) 巩+ 。2 1 毋( 砷+ c ( 2 5 a ) 毋( 。+ 1 = p 一1 巩( h 1 + 开( + + ( u 一1 ) u 妒( 。】+ ( 1 一u ) ( t 0 ( 2 5 b ) a n dc h a r a c t e r i z e db yt h ef o l l o w i n gs p l i t t i n gm a t r i c e s ： = ：b 一，巩1 ， 霄品= 去f b + ( “，一7 ) 巩+ w l 2 一u b 】， w 2 卵= 乞1 卵= 【日一1 巩】一1 【( 1 一“，) 日+ ( “一1 ) + u l 2 】 w h e r e b ，= ( ，一l l p - 1 ) p ( ，一，y p _ u ) ( 2 6 ) w h e nu =1 t h es l a o r la l g o r i t h mi st h el s o r la l g o r i t h m ，m i dw h e nu =1= 1t h es l a o r la l g o r i t h mi st h eg s la l g o r i t h m ac l a s so f l i n em a s t e r sd e g r e ep a p e r t h e o r e m2 2 l e tz h = 缸- t n t ，b et h el i n es o r a l g o r i t h mw i t ht h el i n e r e l a x a t i o nm a t r i x ( w e l lk n o w na sl s o r l ) d e f i n e db y ( i s ) a n dz “= 地f 。x , z b et h el s o r la l g o r i t h mw i t hs t a n d a r de x t r a p o l a t i o nm a t r i xd e f i n e db y ( 2 6 ) + i f p ( b ) 1 ，8 “8o u 赢，。“8 “ p ( z “) 0a n d ( z ，y ) 0 a sam o d e lp r o b l e mw es h a l