（计算数学专业论文）预处理hss方法和模糊线性方程组的迭代解法.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以求实、创拧的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果 3 ，本论文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意 作者签名 日期， 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进人 学校图书馆被查阅；有权将学位论文的内容编人有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用 本规定 作者签名。 日期， f a s t e l - sd e g r e ep a l a a p r i l 2 0 d 7 摘要 本论文包括两个主要内容：预处理h s s 方法和模糊线性方程 组的迭代解法 第一章简要介绍了2 0 世纪或更早时期的有关解线性方程组及 模糊线性方程组的经典迭代解法的发展过程 第二章对h s s 方法【4 】应用顶处理技术并在相关的理论分析 的基础上给出了数值结果 最后一章给出了模糊线性方程组的两种迭代方法：s s o r - c g 方法及s e m i - c g 方法并通过数值例子说明了算法的有效性 关键词：非厄尔米特矩阵；分裂；预处理；厄尔米特矩阵；反 厄尔米特矩阵；迭代方法；模糊线性方程组；s s o r - c g 方法； s e m i - c g 方法 a h 毗r a c t2 a b s t r a c t t h ep a p e rc o n t a i n st w om a i nc o n t e n t s o n ei st h ep r e c o n d i t i o n e d h s s m e t h o d ，t h eo t h e r sa r et w oi t e r a t i v em e t h o d s f o rs o l v i n gf u z z y l i n e a rs y s t e m s t h ed e v e l o p m e n to ft h ec l a s s i c a li t e r a t i v em e t h o d sf o rt h es o l u - t i o no fl i n e a rs y s t e m sa n df u z z yl i n e a rs y s t e m si nt h e2 0 t hc e n t u r y o rm o r ee a r l i e ri ss i m p l yi n t r o d u c e di nc h a p t e r1 i nc h a p t e r2 ，w eu s et h ep r e c o n d i t i o n i n gt e c h n i q u eo nh s s m e t h o d ，a n ds o m er e l a t i v et h e o r i e sa r eg i v e n f i n a l l y , w eu s ea n u m e r i c a le x a m p l et oi l l u s t r a t eo u rt h e o r i e s i nc h a p t e r3 ，t w oi t e r a t i v em e t h o d sa r ep r o p o s e dt os o l v ef u z z y l i n e a rs y s t e m s s u c ha ss s o r c gm e t h o da n ds e m i - c gm e t h o d a l g r i t h m sa r ei l l u s t r a t e db ys o l v i n gs o m en u m e r i c a le x a m p l e s k e yw o r d s ：n o n - h e r m i t i a nm a t r i x ；s p l i t t i n g ；p r e c o n d i t i o n - i n g ；h e r m i t i a nm a t r i x ；s k e w - h e r m i t i a nm a t r i x ；i t e r a t i v em e t h o d s ； f u z z ys y s t e mo fl i n e a re q u a t i o n s ；s s o r ，c gm e t h o d ；s e m i - c o n j u g a t e d i r e c t i o nm e t h o d z i m l i a p r l l ，2 0 0 7 c h a p t e r1 t h ei n t r o d u c t i o no ft h ec l a s s i c a li t e r a t i r em e t h - o d sf o rl i n e a rs y s t e m s n u m e r i c a ll i n e a ra l g e b r ai sa l le x c i t i n gf i e l do fr e s e a r c ha n dm u c ho ft h i s r e s e a r c hh a sb e e nt r i g g e r e db yap r o b l e mt h a tc 蛆b ep o s e ds i m p l ya s ：g i v e n a 俨期，b 俨，f i n ds o l u t i o nv e c t o r ( s ) 伊s u c ht h a t 缸蒜b m a n y s c i e n t i f i cp r o b l e m sl e a dt ot h er e q u i r e m e n tt os o l v el i n e a rs y s t e m so fe q u a t i o n s 船p a r to ft h ec o m p u t a t i o n s a l t h o u g hi t e r a t i v em e t h o d sf o rs o l v i n gl i n e a r 毋，g t e m 8f i n dt h e i ro r i g i ：ui nt h e e a r l y1 9 t hc e n t u r y ( w o r kb yg a u s s ) ，t h ef i e l dh a ss e e na ne x p l o s i o no fa c t i v i t y s p u r r e db yd e m a n dd u et oe x t r a o r d i n a r yt e c h n o l o g i c a la d v a n c e si ne n g i n e e r i n g a n ds c i e n c e at h ep a s tf i v ed e c a d e sh a v eb e e np a r t i c u l a r l yr i c hi nn e wd e v e l o p - m e n t s , e n d i n gw i t ht h ea v a i l a b i l i t yo fl a r g et o o l b o xo fs p e c i a l i z e da l g o r i t h m sf o r s o l v i n gt h ev e r yl a r g ep r o b l e m sw h i c ha r i s ei ns c i e n t i f i ca n di n d u s t r i a lc o m p u t a - t i o n a lm o d e l s i t e r a t i v em e t h o d sh a v et r a d i t i o n a l l yb e e nu s e df o rt h es o l u t i o no fl a r g el i n e a r s y s t e m sw i t hd i a g o n a l l yd o m i n a n ts p a r s em a t r i c e s f o rs u c hs y s t e m st h ej a c o b i a n dg a n s 8 s e i d e lm e t h o d sc o u l db eu s e dw i t hs o m es u c c e s s ，n o ts om u c hb e c a u s e o f t h e l i m i t e d a m o u n t o f t h e r e d u c t i o n i n c o m p u t a t i o n a l w o r k b u t m a i n l y b e c a u s e o f t h el i m i t e da m o u n to f m e m o r yt h a ti sr e q u i r e d t h eg a u s s - s e i d e li t e r a t i o nw a s t h ep o i n tf o rt h es 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 d sw h i c hd o m i n a t e dm u c h o ft h el i t e r a t u r eo ni t e r a t i v em e t h o d sf o rab i gp a r to ft h es e c o n dh a l fo ft h el a s t c e n t u r y t h em e t h o dw a sd e v e l o p p e di nt h e1 9 t hc e n t u r y , o h 6 n a l l yb yg a u s si a t h em i d - 1 8 2 0 sa n dt h e nl a t e rb ys i d e li n1 8 7 4 t h ep o i n ts u c c e s s i v eo v e r r e l a x a t i o nt e c h n i q u e ss e e mt oh a v ea p p e a r e di n t h e1 9 3 0 ah o w e v e r ，f o r m a l l yi t st h e o r yw a se s t a b l i s h e da l m o s ts i m u l t a n e o u s l y b yl 矗a n k e la n dy o u n gi nt h e1 9 5 0 s u c c e 蜮v eo v e r r e l a x a t i o nm e t h o d s ，a n d n u m e r o u sv a r i a n t s , b e c a m ee x t r e m e l yp o p u l a ra n dw o r et h em e t h o d so fc h o i c e 3 4 i nc o m p u t e rc o d e sf o rl a r g ep r a c t i c a lp r o b l e m s a l t h o u g ht h e i rp o p u l a r i t yh a s b e e no v e r s h a d o w e dl a t e r ，a r o u n da f t e r1 9 8 0 ，b ym o r ep o w e r f u lt e 砌q i l ，t h e y a r es t i l lu s e di ns o m ea p p l i c a t i o n se i t h e ra st h em a i ni t r a t i v es o l u t i o nm e t h o d o ri nc o m b i n a t i o n 丽t hr 瓒q i tt e c h n i q u e sf e g a ss m o o t h e r sf o rm u l t i g r i do r 够 p r e c o n d i t i o n e r sf o rk r y l o vm e t h o d s ) t h e 目c c e 8 8o ft h es o r m e t h o d sh a sl e dt o ar i c ht h e o r yf o ri t e r a t i v em e t h o d s ；t h i sc o u l db eu s e df r u i t f u l l yf o rt h ea n a l y s i s o fl a t e rm e t h o d sa sw e l l t h ea c c e l e r a t e dg a u s s - s e i d e lm e t h o d sh a v em o t i v a t e di m p o r t a n td e v e l o p - m c n t si nt h et h e o r yo fl i n e a ra l g e b r a i np a r t i c u l a r ，r e l e v a n tp r o p e r t i e sf o rm - m a t r i 墨i n t r o d u c e db yo s t r o w s k i ( 1 9 3 7 ) ，w e r eu n c o v e r e da n dc o n v e r g e n c er e s u l t s f o rs o - c a l l e dr e g u l a rs p l i t t i n g s , i n t r o d u c e db yv a r g a ( 1 9 7 4 ) ，w e r ee s t a b l i 8 h e d ac o r n e r s t o n ei nt h ec o n v e r g e n c et h e o r yw 舶s t e i n - r o s e n b e r gt h e o r e m ( 1 9 4 8 ) w h i c hp r o v e dr e l a t i o n sb e 佃l e e nt h ea s y m p t o t i cr a t e so fc o n v e r g e n c eo ft h es u c c e 8 - s i v eo v e r r e l a x a t i o nm e t h o d s ，i n c l u d i n gt h eg a u s s - s e i d e lm e t h o d ，a n dt h ej a c o b i m e t h o d w jw i l li n t r o d u c et h e mi nd e t a i l s f o rt h es i m p l ec a s ew h e n 竹= ma n dai 8n o n s i n g u l a r 骶c o n e o mw i t ht h e n u m e r i c a ls o l u t i o no fal a r g el i n e a rs y s t e m a x = b ，正俨”，b 俨 o ) ( 1 ) w es p l i t e a i n t o a = m n ，( 2 ) w h e r emi 8n o n s i n g u l a r ，w h i c hi sa l s ou s e da sap r e c o n d i t i o n e r ，u n d e rt h ec o n d i - t i o n s ( 1 ) i ti sc h e a pt oi n v e r t ( 2 ) al i n e a rs y s t e mw i t hc o e f f i c i e n tm a t r i xm i 8 m u c hi n o r ee c o n o m i c a lt os o l v et h a n ( 1 ) b a s e do n ( 2 ) ，( 1 ) c a nb ew r i t t e ni nt h e f i x e d - p o i n tf o r m 。= t z + c ，t ：= m - 1 ，e ：= m 一1 b ，( 3 ) w h i c hy i e l d st h ef o l l o w i n gi t e r a t i v es c h e m ef o rt h es o l u t i o no f ( 1 ) ： 矿+ 1 = t + c ，m = 0 ，1 ，2 ，扩俨( 4 ) as u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o r ( 4 ) t oc o n v e r g e ，t ot h es o l u t i o no f ( 1 ) ，i sp ( t ) i l 孤咿“1 ，2 0 a n dt h e nc o m p u t e 孟( i + 1 ) = 孟罅+ 1 2 + 孑( k + 1 ，) i f - 1 u b - a b 高* 孟夏( k 而+ 订t ) 广- 0 ( h 三0 ) m e a n ：s t h a thi 8h e r m i t i a np o s i t i v e ( s e m i - ) d e f m i t e w ed e n o t et h e u p p e rb o u n do f 口( 口。) f o rt h ep a r a m e t e ru 矿( q + ，) w er e v i e wt h ef o l l o w i n g 姒t t 8w h i c hw e r eg i v e ni nf 2 0 j t h e o r e m3 1 ( c f 扛0 1 ) l e t 日 0 乳t h e r ee x i s t sau n i q u ev a l u eo fu ，s a y 岫，s u c ht h a t 0 p ( m ) hi f 2 121+(1-2fi+4)*21 1 -， s o m er e s u l t sf a rp r e c o n d i t i o n e dh s sm e t h o d j 1 1 w h e r e ，y = m 越( p ( d 一1 l d - 1 u ) ，1 4 ) ， t h e n 。，由、，1百(1旦-2豇+4y)12 p ( ) s _ 1 r 1 + 而1 斋2 p 。 ( 一+ 4 ，y ) 叫2 w en o wo b t a i nt h em a i nr e s u l t so ft h ef i r s tp a r to ft h i sp a p e r t h e o r e m3 2 l e th 卜0 ，h = m n ，w h e r ema n dna r eg i w nb y ( 1 9 ) a n d ( 2 1 ) f o rt ( a ) d e f i n e db y ( 1 8 ) a n d0 u 2 ，w e h a v et h a t 鲳p ( m - 1 n ) d e c r e a s e s , 盯( a + ，) 毒r ；i 】i 1 f 丽d e c r e a s e s p r o o s i n c e f 一1 日= m 一1 ( f n ) = i m 一1 a ( m - 1 h ) = 1 一a ( m 4 n ) s i n c eh 卜0a n dn 三0 ，t h e n0 p ( m 一1 n ) 11 1 7 】 n o t et h a t 0 a ( m 一1 ) sp ( m 一1 ) ， w eh a v e 1 一p ( m 一1 n ) 1 一a ( j l f 一1 ) 1 s o m er e s u l t sf a rp r e c o n d i t i o n e dh s sm e t h o d s1 2 t h u s ，w ec a no b t a i n k ( m 一1 2 h m 一1 2 1 ：x , n , 一( m - i 2 h m - i 2 ) k 咖( m - 1 2 h m - 1 2 ) a ( m o h ) k 咖( m - 1 h ) 1 一a 。h ( m “n ) 1 一九一( m - 1 n ) ， 1 s 1 - p ( m - 0 i ti sc a s yt o 黜t h a tw h e np ( m - 1 n ) d e c r e a s e s ，t h e nt h eu p p e rb o u n do f k ( m 一1 2 h m 一1 2 ) d e c r e a s e s a n dw i t ht h e o r e m2 1a n d2 2 ，w e 伽s e et h a t t h eu p p e rb o u n do f 口( 口，u ) d e c r e a s e s t h e n ，b yt h e o r e m2 1 ，c o r o l l a r y2 2a n dt h e o r e m3 1 ，w eh a v et h ef o u o 咄 r e s u l t s ，i m m e d i a t e l y t h e o r e m3 3 l e t 日卜o a t h e r eo d 础sau n i q u ev a l