（应用数学专业论文）大型线性方程组迭代算法的误差分析研究.pdf

电子科技大学硕士学位论文 大型线性方程缝迭健算法的误差分析臻究 摘要 本文簌方程缀a x = b 麴系数矩黪a 其蠢据容铁痔及瓣称藏定麴祭孛 下， 利用 如= x x 。，蕊兰x 算纠，耧蠡“竺x 榭盖量 的范数及内积得捌了选代法姻误差向量以一x 的范数豹上界，其中x 为 方程组a x 。b 的精确解，j 。一、x 。、j 州为方程组a x 一6 的选代向澄。 第2 攀嫒究了m a o r 然提法豹误蒺雾，舜在魏基璐上建鼗7 一类 m a o r 选代法的停机准则。 | | 峨帕基方洲t 一1 ) 一1 ) 川蚺( ，一蛾) i 所) 2 i j 刚： - 2 ( 0 1 - 1 x t 0 2 - t ) 溉，最+ 1 ) + 2 1 c 0 1 ( ，一棚2 ) l 衍最2 瓯+ l + i t 民+ l 旺 第3 章瓣s a o r 逡代法豹误麓进程了研究，褥到了翔下静鳝浆，荠结 合实际算例讨论丁一类s a o r 迭代法的终止条件。 l j 颤l i ；砉 f ( 1 一t o ) 2 + i a ) ( r c o ) l a 3 4 i 础； - 2 【( 1 一出) 4 + 掰2 ( ，一国) 2 a t 蛾，艮i ) + 4 ( 1 一膨) 2 l a g z - 搿) l 彳l | 文| 2 | l 蕊“。l lz + 蘸+ l l | ；， 缮4 章研究了t o r 迭代法的谡差上爨，得到了如下的估计，搏结台嶷 际算例研究了s a o r 迭代法的终止条件。 隅l f ；s 寿 f ( 1 一i 1 国峒) 2 + l4 1 - p ( a + p ) t 芦确砌i 2 1 - 了1 似+ d 2 ( 暖，瓯“) + 专l 以+ 声) l 衍瓯) i 。反。l j2 + 1 1 s t h l i ；) 关键词：线性方程组，迭代法，误麓界。 n 生量型塾娄鲎堡圭鲎垡鎏壅 t h ee r r o ra n a l y s i so fi t e r a t i v ea l g o r i t h m s f o rl a r g el i n e a rs y s t e m s a b s t r a c t s u p p o s ea x 一6i s as y s t e mo fl i n e a re q u a t i o n sw h e r et h em a t r i xai s s y m m e t r i cp o s i t i v ed e f i n i t ea n dc o n s i s t e n t l yo r d e r e d ，w h i c hi so b t a i n e df r o m af i n i t ed i f f e r e n c ea p p r o x i m a t i o nt oa ne l l i p t i cb o u n d a r yv a l u ep r o b l e m t h i s p a p e rd e r i v e st h eb o u n d sf o rt h en o r m o ft h ee r r o r s * x 工o ft h ei t e r a t i v e m e t h o d si nt e r m so f t h en o r m so f 壤黼苫善“，= 善m 。x w h e r e 聋i s t h e e x a c ts c i a t i c no fa x 拳6a n d 并。_ 1 ，x 量，x i + j i st h ei t e r a t i o nv e c t o r s ，a n dt h e i r i n n e rp r o d u c t i nc h a p t e r2 ，w ea n a l y z et h ee r r o rb o u n do ft h em a o rm e t h o d ，a n do n t h eb a s i sw e g i v es t o p p i n gc r i t e r i ao f t h ei t e r a t i v em e t h o d i 靠 i 蕊砉 ( 1 ( l l 一1 ) i + l 灿仃一吨) f 衍) 2 i f 玩f f ； 2 ( f 0 i - 1 x 0 , 2 - 1 ) 靠，疋+ i ) + 2 l l ( r - m 2 ) t 衍甄l l2 f l 屯l 2 + l l 砖+ 1 i f i ) i nc h a p t e r3 ，t h ee r r o rb o u n do ft h es a o rm e t h o di sd e r i v e da n du s e da s g i v es t o p p i n gc r i t e r i ao ft h ei t e r a t i v em e t h o d i i 颤i i i 古 【( 1 一m ) 。+ i o 一国) i r l i 瓯| f ： 一2 【( 1 一曲) 4 + 掰2 ( ，一甜) 2 】( 瓯，+ 1 ) - 4 器一掰) 2 l m r 一囝| 岔 l 菇 l2 | 壤。l l2 + | 最+ l | | ； i nc h a p t e r4 ，w eg e tt h ee r r o rb o u n do ft h et o rm e t h o d ，a n du s ei ta st h e s t o p p i n gc r i t e r i ao ft h ei t e r a t i v em e t h o d ；咏 l ；两i l l l 一百i ( 盘+ 芦妒+ l 扣g + 彩 芦艄l 础i - 2 i - j 1 妇+ ) r 最，以+ ，) 十主l 厦口十) f 翔氓2 i i 瓦h 2 十以+ l f f ； k e yw e r d s ：l i n e a rs y s t e m s ，i t e r a t i v em e t h o d ，e r r o rb o u n d 1 l l 电子科技大学硕士学位论文 独创性声明 本人声明所星交的学位论文是在导卿指导下进行的研究工作及取锝的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不 毽耩其德入已经发表或撰写避麴碜 究或聚，选举包含为获褥电子辩技大学 或其他教肖机构的学像或证书而使用过的材料。与我同工作的间志对研 究所傲的攒献均已在论文中作了明确的说明并袭示谢意。 签名：日期：年月臼 关于论文使用授权的说酮 本学位论文的作者完全了解电予科技大学有关保留、使用学俄论文的 规寇。有救傈留并向国家有关部门藏辊梅送交论文的复印伴和磁盘，兔许 论文被查阅和媸阅。本人授投电子辩技大学可以将学位论文的全端或郝分 内容编入谢关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。 签名；导师签名； 囊麴：颦弼疆 电子科技大学硕士学位论文 符号说骥 c ”盯维复向量的全体 最“” 靠除安矩蓐夔垒体 a 7 矩阵的转置 聋，” 离量麓内积 ”虬 摸2 藏数 反爿) 矩阵a 的谱半径 d i a g ( a )囊踅辫a 懿慰蕉廷构藏靛慰角矩簿 v 毯子搴 技走学硬圭学位论文 第1 章引言 1 。1 选题背豢 蘧萋攀毒攀搜拳夔飞速发疑，矩终诗算貔瑷谂秘方法与方程缀豹求解已 经成兔器萃辱技领域处理数学阏题静不可或缺的强大工具，它是计棼数学的 一个重蒙分支，同时它在系统工程稳定性理论簿相关学科，特别熄在计算 机科学中也得到了广泛的威用。 众所周期，许多实际闯磁最嚣常常归结为解一个或一些大型黼蔬矩阵 熬线性方裁缝戆求解阏瑟，线瞧方疆缝豹求薅竣为诗霎鼗学孛数镶筏数磅 究的核心之一。 如在解拉普拉斯边值问题时，用差分格式离散化后会产生一悠大型的 稀疏矩陴的线性方程组，而对这种方程组一般浆用迭代法求解。特别是随 着计算枫技术靛进步，对逡代法豹研究受到了因内外许多科研人鼹的重 露，褒褥? 缀多磅究成采。入襞j c 重迭式法熬磷究丰富察发矮了数傻健数理 论和方法，同时也为矩阵瑗论的应用开辟了广阔豹前景。因j 毙辩迭代法的 研究就成为数值代数中一个非常重要的研究课蹶。 线性方程组的迭代解法国童接法不同，不熊通过有限次的算术运算求 褥方程组麴精确艇，两是逐步遥近它，即使每一步都用精确的冀术运算， 迭筏法毽必戆缮裂近辍鳃。黧藏，冗是迭筏法帮蠢狡敛毪与误麓穗诗熬翅 题。对予一个给定蛇方程缀，某些迭代法收敛的很快，而有些迭代法可能 不收敛，或收敛得很慢，以聪于无实用价值。j a c o b i 迭代法是最旗本的迭 代法，因为具有内在的并行性在犬规模科学妈工程计算的并行数假算法中 发挥翥鬟簧豹作用。两在实鼯计算对，g a u s s s e i d e l 迭我法豹迭代格式比 j a c o b i 逡代法豹迭代格式紧凑，并显哭需要一套存放迭载商量豹鼙嚣。薅 于用五点麓分格式艇调和方程边值问题时所导出的方程组，当方程组的阶 数较高时j a o o b i 迭代法和g a u s s - s e i d e l 迭代法的收敛速度变得很慢。因此 人们发展了对某些特殊的矩阵收敛速度比j a c o b i 迭代法和g a u s s + s e i d e l 迭 找法抉褥雾戆超捡魏迭代法( s o r 迭我法) 。基予s o r 方法，a + h a d j i d i m o s 撵密了一耱灏懿迭代方法一a o r 方法，童予嚣个参数眈一个参数有曼大 电子科技太学预士举位论文 瓣选铎余蟪，霞箍霹豁臻望a o r 方法范辍上葵窀方法骞雯捷静收敛逮魔。 文献 6 1 提出了包含四个参数的u s a o r 迭代法，当网个参数取适当的值 时，u s a o r 迭代法分剐转化为上谣各种方法外，还w 转化为j o r ，s s o r ， s a o r ，u s s o r 等方法。 伴随着迭代法的研究，人们对误差估计进行了深入的研究。t h e o d o r er h a t c h e r 予1 9 8 2 年在l i n a l g a p p l f 美】发表了辩s o r 迭彳弋法的误差 界钧研究工作；m + m a d a l e n a ，m e s t e l at r i g o ，毒nm m a d a l e n as a n t o s 予 1 9 9 6 年在 l i n a i g a p p l 【美】发表了荚于s s o r 方法和u s s o r 方法的 误蓑巽缝慕；yz ，s o n g 手1 9 9 9 年在转| t n u m 。m a t h ，| 瑞典】发表了关 于a o r 方法的误差分析结果。 1 。2 迭代法概遴 邀代法一般可表述为： = 张 椎o ，椎o ) k = ，l + 1 ，。，( 1 ，2 。1 ) 其中魄称作迭代算予，粕，幽一l 为迭代初值，通常称迭代法( 1 2 1 ) 为，步 迭彳弋法；，= 1 时，亦称为单步迭代法。如果遮代葬子纯向后无关，即 镪= 妒，测藜迭代法( 1 2 。1 ) 为定零迭拽；否则称之鸯苓定豢迭找。 下面讨论单步定常迭代法： 瓠= g x k l 十c ，素= l ，2 ，( 1 2 2 ) 其中g 乍r ”称为迭代矩阵，称为初值。 定义1 2 1 如果存在 r ”，使得对任慧的初值x o r ”，由迭代法f 1 2 2 ) 产生黪滓裂 喙 鹣蒸收敛裂瓠t 帮 您投。文， 则称迭代法 1 2 。2 ) 是收敛豹；否则称之为发散豹。 如果迭代法( 1 2 2 ) 是收敛的，则必有 冀。= g x , + 幺 现记 h k 。x t 一瓠， 电子科技大学硕士学位论文 则易证 = g 甜。 由此可知，迭代法( 1 2 2 ) 收敛的充分必要条件是 l i r a g 女：0 定理1 2 1 1 1 6 】迭代法( 1 2 2 ) 收敛的充分必要条件是 p ( g ) l 定理1 2 2 1 1 6 设”| | 是由向量范数诱导出的算子范数。如果| | g | | 1 ， 则迭代法( 1 2 2 ) 收敛，且有 慨刮小器| i x 0 - - x 忆 l 一u 和 f l x k - x , 忆 器8 x k - - x k _ i 忆( 1 2 3 ) 对一切的自然数k 成立。 从( 1 2 3 ) 可以看出t 只要0 g l 不是很接近l ，当相邻两次迭代向量札 与x 很接近时，则与矗也很接近。因此，常用量i ix k x n0 是否已经 适当小来判断迭代是否应当终止。但是，如果i i g l i 很接近l ，即使 | | 坼一工| i 已很小，也不能断定| l x k 一工。| i 很小。 设已给定线性方程组 4 x = b ， 其中a r 和b r ”已知，算e r ”未知。现在我们讨论如何构造迭代法 ( 1 2 2 ) 来求线性方程组a x = b 的解。 首先，我们自然希望构造出来的迭代法如果收敛，其极限就是方程组的 解。这就需要其迭代矩阵g 和常向量c 满足 鲫爿一g 和q b = c( 1 2 4 ) 其中q e r 是某一非奇矩阵。如果( 1 2 4 ) 成立，则称迭代法与方程组是 相容的。 电子科技太学硕士学垃论文 糕在缓定蠢蠢露下分裂： a = m - n ， 其中m 为非奇矩阵。令g = m n ，c = m b ，则由此产生的迭代法是相容 数。 基于这种思想，对a 进行不同的分裂，就可以构造出各种各样的相容 静这代法。 设矩阵4 为 则 令 l ， j a c o b i 迭代法 冀中 迭代矩阵为： a = q 1a 1 2 撑2 la 2 2 a ”1a 2 d = d i a g ( a n 。d 1 2 2 ，口m ) ， c l = = 00e 口2 1 0c 口辩la , a o 0 口1 2 a l h 0 0 a 2 h 000 l = d 一1 瓯，u = d 一1 c v a = d - c 一c t , = d 一4 ( ，一l 一矿) a = m s 一心， m j = d ，n j = c l + c u ， 4 ； 壤予辩技丈擎硕士学使谂义 j = m j l n j = 矿t ( c l + c u ) = 三+ u = 1 一d 一1 a ( 1 2 5 ) 迭代格式为： 观= ( c c v ) x m l + 垂，m = 1 , 2 ，( 1 。2 ，6 ) 设粕憩一个任意豹枥鲶迭代商量，然嚣囊公式( 1 2 终蠢翔鬟痔弼 ，x 2 ，这种迭代法称为j a c o b i 迭代法，或简称为j 方法，矩阵( 1 2 5 ) 称 为对应予矩阵卅的j a c o b i 逖代矩阵。 定璞1 2 3 1 1 7 】设矩阵a 髭具有正对角元的对称矩阵，则j a c o b i 迭代 法收敛黪充分鍪要条箨是a 秘2 d a 都是正跫缀薄( 这嚣个矩蹲豹差鬟投 是菲辩建愆豹符号不圈) 。 2 g a u s s s v i d e i 迭代法： 对于j a c o b i 迭代法，( 1 2 ，6 ) 的分量形式是 = 嚣屯+ 岛l = l 2 ，引 1 2 。7 ) j 2 j j 辐 事实上，猩计算之前并：，x ：，i - 1 已经计算好了，但是，谯j 方法 中计算仍旧用艺一，并。2 小，1 - d 1 ，如果改阁艺代替一。o 一，2 。拧) 则( 1 2 。7 ) 妓使成为 = 毛磁嘞q + 岛g = l ，2 ，蟛 ( 1 2 8 ) i 奄i i 鹤 这种格式的迭代法称为方稷缀的g a u s s s e i d e l 避代法，简称g j 方法。( 1 2 8 ) 式的矩阵形式是 焉。= ( ，一) 叫( 矗料_ + ( ，一三) 一1 b( 1 2 ，9 ) 英孛矩黪一五) _ l f 称兔对寂于楚箨蠢豹g a u s s 。s 尊i d e l 迭筏矩瘁。 3 翘松弛迭代法 a 分裂为： a = m m n 。， 其孛 虬= 去d c l ，虬= 气孑d + 岛， 电子科技大擘硕士学位论文 掰蔻津零实数，称俸橙翘因予。 迭代矩阵为： = 虻。= ( j - c o l ) 。( 埘v + ( 1 + ) ，) ， 当掰= 1 慰，s o r 迭找法裁是g a u s s s e i d e l 迭我法。嚣此适当选取 参数m 可望s o r 迭代法比g a u s s s e i d e l 迭代法具有更快的收敛速度。 4 对称超松弛迭代法 4 分裂为： a = m s n3 ， 其中噱2 而面1 d - 国( c i , + 白) + a 2 c l d - i c y 2 面1 丽( d - e a t ? ) 础d ”蝙) t 虬2 寂圭面“1 _ 妫2 d 一酬卜纠( q + 白) + a 2 c l d - n 白j 甄2 蕊面1 黔m ) d 一蛾】d - i ( 1 一掰渺一蜗】f 迭技矩薄为； r o = m ：l n | = u m l m 其中 u 。= ( 1 一s u ) 。( 如l + ( 1 + 国y ) 五。为s o r 选代法的迭代矩阵。 国魏霹怒，s s o r 遮我法实质土藏是褥q 帮岛等弱爱铸造续她毽用 两次s o r 迭代法。这样做的好处是： ( 1 ) 可充分利带内外存交换晴褥列的信息，减少肉矫存交换的次数， 提薅计算效率。 ( 2 ) 在某些特殊问题中s o r 迭代法不收敛，但仍然可构造出收敛的 s s o r 迭午法。 ( 3 ) s o r 迭代法的渐进收敛速度对作松弛因子掰的选择一般来说非常 敏媾，而s s o r 迭代法却不敏感。 6 电子科技大学硕士学位论文 1 3 本文主要工作 本文对一些著名迭代法的误差估计进行了更加深入的研究。 第2 章对m a o r 迭代法的误差界进行了研究； 第3 章对s a o r 迭代法的误差界进行了研究： 第4 章对t o r 迭代法的误差界进行了研究。 本文对于这些著名迭代法的误差进行了分析研究，分别获得了它们的 误差估计上界，实际上还可由所得结果得到关于这些方法进行实际计算的 停机准则。 所进行的研究是文献中未曾研究过的工作，而且受到了国际著名刊物 c o m p u t e r s & m a t h e m a t i c sw i t ha p p l i c a t i o n s ( s c i 和e i 收录刊物) 的编 委、国际著名计算数学家p r o f e u g e n el w a c h s p r c s s 的评价：“t h ee l r o r b o u n d d e v e l o p e dh e r ep r o v i d e sav a l u a b l es t o p p i n gc r i t e r i o n 说明l 本硕士论文的工作之一，已被c o m p u t e r s m a t h w i t h a p p l i c a t i o n s ) 正式录用并已签版权转让书。 7 电子科技大学硕士学位 第2 章m a o r 迭代法豹误差器 2 1 戮言 我们考虑用修正超松弛法( m a o r ) 求解线性方程缎a x = b ，其中d = ( ) 为n 阶非奇方阵。如果矩阵a 的对角元索非零，将矩阵a 分裂成 名。d - c e c # 。毯f 一三一趵， 其中l = d c 。，胪d c ，d = d i a g ( a ) ，c z 和c u 分别为严格下三角和严 格上三角矩阵。义【l 】奁a 其有相密秩序下定义修正超松弛法( m a o r ) 如下 j 。+ 1 搿三o , f x + ，声， j ；0 ，l ，2 ， 这受昭= d i a g ( o 口j i l ，0 0 2 1 2 ) ，l ，娩0 ，f = d i a g ( y 1 1 l ，如f 2 ) ，修正麓橙懿法 的迭代阵k ，为 三n f2 ( t d 一厂c ) 。【( ，一n ) d + ( 腔一厂) q + 腑c u 】 一i 一，五) 4 【? 一兹十露一r ) c l + 露c u 】， = ( d f q 一赡6 = ( ，一f l ) 。1 d 。力6 赫证上瑟定义盼髂薤麓松弛法审参数“不楚独立豹，霞诧修磁超松弛 法的迭代黪可以记为k 。，即鸯 芦= k ，哪，苫十廖峨一。， 七= 0 ，l ，2 ， 5 k m 。g r l ) 。一露+ ( c 0 2 - y 强+ 蛾蠲t 畋。一2 【，一y l ) “d “伤。 当参数，和( 0 2 相等时m a o r 迭代法变为m s o r 迭代法【觅文5 ，第8 章】， 这对m s o r 迭代簿记戈k 。， k u 2 l ) “【，一口+ 脚l 明a 记j a c o b i 迭代阵雪一三+ u ，x 为线经方程缀a x = b 的精确解， 毛z 冀- 工。，疋苫j 。 于是有 岛+ l 。k 。，颤，热2 k 。，磙， 矗。( ? 。k 。) 。1k 。，以。 当a 其有相容秩序及对称磁定时，矩降a 有鞠下结牵哿 8 电子科技大学硕士学位 二钾 相应地j a c o b i 迭代阵b 等于 ；讣 我们记j a c o b i 迭代阵b 的特征值为“，i = 1 ，n 。如果“都是实数， 则记 擘2 m l 。i 。n m ，2 m k 。a x “ ， 显然，如果a 是正定矩阵，则有麒都是实数并且 0 。 引理2 , 1 1 ( 【l 】) 如果a 为一h e r m i t e 正定矩阵，那么m a o r 迭代法当 参数满足如下条件时收敛， o 珊l 0 ) 2 y 2 ，m 2 2 ， 或 0 o j 2 0 7 1 2 , 邪，导。 引理2 1 2 ( 【2 】) 分别记m a o r 迭代阵k 。，和j a c o b i 迭代阵b 的特征 值为 旯) 和 肼，则有 ( a + 国l - 1 ) ( ，+ 脚2 - 1 ) = 9 0 1 ( c 0 2 一，+ 刃) 2 ，即 a 2 - ( 2 国l - 国2 + ，锄i 2 ) a + ( l - 1 ) ( 2 - 1 ) + 国l ( y - o j 2 ) z 2 = 0 。 2 2m a o r 迭代阵k 如，的特征值和特征向量 从这一节到结束，我们都假设a 具有相容秩序且对称正定并有m a o r 迭代法收敛。不失一般性，进一步假设s 是秩为m = n 2 的非奇矩阵。由 文【1 】可知，j a c o b i 矩阵b 的特征值满足 - 1 l 一2s 一a 聃 0 褥 口2 易( ( 奶一1 ) ( 吐一1 ) + c o i 掰口一吡) ) 2 4 2 ( l 一1 ) ( 奶一1 ) 搦 - 2 t 弘j 一国i ) b j c j 蔓( 1 ( l 1 ) ( 2 1 ) 1 + i 脚l 露 ，一街2 ) 1 ) 2 a i _ 2 ( q 1 ) ( 吼1 ) 毋十2 | q 群驴一) f i 易| + q 。( 2 3 3 ) 1 6 电子科技大学硕士学位 注意到 b j l 2 l 瓴，k 。，c j ) l - 1 | 白j k 。局忆 由c a u e h y - s c h w a r z 不等式知， i 易i 屿i t ：i i k 。训： 户i- l m 1mi ( 4 ) j ( q ) j j f f i lj l 。l i 瓯忆i 】坑。l | ：( 2 3 4 ) m ( 2 3 3 ) 和( 2 3 4 ) 得 口2 慨峨= 口2 弓 j - i - - - 1 ( a 。一1 ) ( 一1 ) h q 衍( y 一吐) i 】2 a j j - i - 2 ( 叻一1 ) ( ：一1 ) b j - + 2 1c o 。力( r - a , 2 ) l i 岛i + q j - ij - i ( i ( c o l 一1 ) ( 2 1 ) i + i i 衍( r - ( 0 2 ) 1 ) 2 | | 巩| i ； 2 ( m ，- 1 ) ( c 0 2 一1 ) 概，以+ ，) + 2 1 q ( 7 - c o ：) 彳i | 喀| | ：| | 以+ 。l | ：+ 瓯+ ，旧) ， 口 注1 3 1 当叻= 吐= 国，7 t = ，2 = y 时，就得到a o r 的误差界 i i s , , l l ；- - - ：- r ( a , 一1 ) 2 + 叫，一曲l 詹) 2 | | 瓯肥- 2 ( 脚一1 ) 2 依，瓯+ - ) + 2 1 吖，- a , ) l 衍i | 暖i i2 瓯。i | 2 + | i 疋。瞄 ， ( 该结论为y s o n g 于1 9 9 9 年发表于b i t , 3 9 ( 1 9 9 9 ) 2 。3 7 3 3 8 3 的结果，( 见 【4 】) ) 。 注1 3 2 当c o l = 国2 = ，l = ，2 时，由( 2 3 1 ) 得s o r 的误差界， 1 7 电子科技太学硕士学位 岛f f i 墨砉 ( 一1 ) 4 f l 哦f f i m 2 ( 国一1 ) 2 瓴，瓯+ 。) 圳以。i | ；) ( t r h a t c h e r l 9 8 2 年的成聚) 。 2 4 算例 律为定理1 3 2 酶藏瘫，考虑l a p l a c e 方程 窘窘钝( 堋芒2 材| 黼= f ( x ，n 强力芒勰， 这里区域q 是l 2 豹长方形，鼬是其边界。爰建步长势喜瓣长方澎弼掇， 内繁点豹编号次序如墅1 所承，这对期五点差分格式所产生豹线瞧方程缒 是a x = b ，其中 彳= 脍咎材 护【4 ，4 ，4 ，4 ，0 ，0 ，0 ，4 ，4 ，0 ，0 ，0 ，4 ，4 ，4 ，4 ，4 ，4 ，4 ，4 ，4 ，0 ，0 ，0 ，0 ，0 ，0 ，4 ， 4 ，4 ，4 ，4 i t , 饥= 圾= 4 1 ，“月= 【，甜。，村“】7 ，“。= 【“。甜。，。】，为1 6 阶单位矩 阵。 这辩矩阵a 其有稽容秩滓并蠢辩称藏定，矩阵b 的谱警径 飙= 8 ，7 4 3 5 4 8 0 7 5 8 0 4 2 8 1 e 1 选用不简的参数用s a o r 迭代求解方程组，表一为用定理2 3 2 给出 熬误差赛效劳与实琢误差| | 龟| | 2 秘魄避行了魄较，这爨 电子科技大学硕士学位 铲姑油w a c h s p r e s 渤皴粥 。1 | 以0 表1 峨2 y七 妒女l l 占。1 1 ： 咋 l5l6l83 296 6 1 4 1 8 5 1 4 2 2 6 4 7 2 e - 0 0 41 9 7 2 2 2 3 2 5 0 6 7 7 1 7 6 e 0 0 49 3 8 0 8 1 1 4 0 9 1 9 0 0 3 5 e - 0 0 3 0 91 11 99 91 6 2 1 7 2 8 0 8 0 2 5 7 4 4 7 e 0 1 21 0 8 7 7 2 0 7 1 1 7 0 1 1 4 3 e 0 1 213 4 5 3 0 2 3 8 4 3 7 0 3 2 4 e 0 1 3 13l41 55 67 4 5 5 6 3 1 4 7 5 0 7 7 4 9 4 e 0 1 573 3 7 5 5 7 9 5 7 6 1 3 2 8 5 e - 0 1 556 6 9 7 5 1 4 8 3 7 7 3 8 9 0 e - 0 1 5 07080 92 1 91 1 3 6 3 3 1 7 1 6 2 6 5 2 2 4 e - 0 1 44 ，5 9 3 6 9 4 5 0 6 0 2 2 5 8 4 e 0 1 5 l0l3161 42 8 6 6 1 5 6 7 6 6 0 3 6 2 2 l e - 0 0 31 4 3 9 2 7 9 7 0 1 6 4 3 8 8 3 e - 0 0 3l4 1 6 9 2 7 0 6 7 1 0 7 9 2 3 e 0 0 2 09l0 81 79 56 4 1 5 3 3 1 0 3 0 2 9 0 8 2 l e - 0 1 53 2 3 3 0 1 8 2 4 8 3 5 2 2 1 2 e - 0 1 50 0 o8l0162 84 2 1 5 2 6 7 7 9 8 0 2 8 0 2 7 e - 0 0 52 1 2 3 0 1 9 8 7 0 8 4 8 3 2 7 c - 0 0 522 3 3 0 4 1 8 3 9 3 2 2 3 0 2 e - 0 0 4 07lol21 7 28 9 9 3 3 2 4 8 6 2 6 9 9 9 8 9 e - 0 1 53 9 2 2 0 8 9 7 0 4 7 1 2 2 3 8 0 0 1 5 喜# 中妒。互：1 ( 1 ( 。一1 ) ( 2 一1 ) 1 + 1 0 ) , ( r - 0 ) 2 ) 1 ? ) 2 i i 以| | ； 口 2 ( q - 1 x 0 ) 2 - 1 ) 做，瓯+ ，) + 2 1 q ( ，一：) 1 , ? l l 以i | ：i i 瓯。i i ：+ i l 以。畦) i 。 对于给定的精度要求，表2 为分别用仇，e 。，ijql i 作为停机准则产生的 迭代次数。 表2 1 0 1 0 - 41 0 x1 0 - 61 0 l o 一8 l0 9 2 y )段。)。)t p )k ( t ) 。)t p )k ( f )t 。) 1 51 61 84 03 43 6 5 44 95 16 96 76 5 o 91 11 94 43 33 7 5 85 25 57 26 66 9 1 31 41 51 71 61 62 32 22 l3 02 82 7 o 7o 80 97 57 47 41 0 31 0 21 0 21 3 11 3 01 3 0 1 01 31 62 01 91 82 32 32 23 23 13 1 o 91 0 81 73 02 92 84 23 83 75 24 65 0 0 81 01 62 6 2 52 43 73 53 54 74 04 4 o 71 o1 26 05 85 8 8 28 08 01 0 31 0 21 0 2 其中七( k ( 小，) 分别代表用吼，e 。，l iq i i 作为停机准则产生的迭代次 数。 注2 4 j 因为 i 最i i ：是精确误差，故气。) 应不小于k ) 才能满足给定的 精度要求。表2 说明用e 。作为停机准则是不可靠的。 1 9 电子科技大学硕士学位论文 第3 章s a o r 迭代法的误差界 3 1 引言 s a o r 迭代法的迭代格式为 善= s 。x 十9 6 ， 七= 0 ，1 ，2 ， 其中 q = 缈( j 一，u ) 1 【( 2 一) j + ( 一r ) ( l + u ) 】( ，一皿) ， s y 口2 u 一7 l r 。= ( j 一应) 卅【( 1 一) j + ( c o 一，) 工+ 甜己，】， q 。= ( ，一) 。【( 1 一国) ，+ 沏一，炒+ c o l 】， ，国为实数 当参数，等于时，s a o r 迭代法变为s s o r 迭代法【见4 】 引理3 1 1 ( 6 】) 如果矩阵4 具有相容秩序且对角元非零，并有a 的 j a c o b i 迭代阵的特征值都为实数且 l ，则当参数 国满足下列条件时 s a o r 迭代法收敛， o ，s 2 ，o 0 时，设 其中属= 2 0 一+ 缈掰) 口= a r y u i 一瓜 2 ( 1 一+ n 耐) k 2 q 必，) ， i = 1 ，i n ， 4 ；去，户1 ，m 。 当矩阵a 对称正定且具有相容秩序时， s 。= ( 。一曲2 7 + 。c o 。( 。y 一+ 。t o ：- 一3 0 ，s y ，s + 吖2 s 7 s ( 3 2 1 ) ( 3 2 2 ) 出( 1 一埘) ( 2 - r ) s 7 + m 2 ，( 2 - r ) s 7 船1 ( 1 一m ) 2 + o j ( m + r 一国r ) s s 7j 。 引理2 2 1 ( 1 ) ；当r s 0 时，s 。u s = 乃，s 。= 瓦巧， ( 2 ) ：当r j 20 时，墨，u ，= 2 j ，s r 。= l s f s + 月，u ， 其中订厂l ，( 1 - o j + o r u ；) 2 ( 2 - y ) 。 证明略。 3 3 误差界 引理3 3 1 a j ，岛，c j ，和e s 定义如上并记d s = ( 1 - a , s ) ( 1 一动，则 e i d = 龋2 a j 2 丸j 瓦b j 千c i 。 证明1 当r o 时， 2 l 聊珂 驴 钟爿 = u 妒群爿 = u 皇王壁垫奎兰堡主兰堡笙主 于是有 a j = 0j u j + b i v i ，nj u s + b j = 巧2 l t j 2 j t 勺2 ( 1 + 虿2 ) + 2 a j b ， b 尸a i u s + b j v j ，a 3 p l 岫研、 1 - + 刚j 。口；加+ 酊) + 巧石( 1 + 虿2 m 蹦乃+ _ ) 篙 c | = a p i 妯习i 。n a 私i 轴对、 = a ，2 勺2 ( 1 + 口；) + 巧石2 ( 1 + 虿2 ) + 2 a j b j 以石t ：；， e j 2 | | 2 i f = _ j j 尹1 i 而口，2 勺2 ( 1 + 口；) ( 1 - 石) 2 + 巧石2 ( 1 + i 2 ) ( 1 = t j ) 2 + 2 a b j 2 j ( 1 乃) ( 1 。以) 目叫2 一“j 2 ”2 - r “j 2 ) ( 1 石) 2 + 砖石2 ( 1 + 虿2 ) ( 1 - ) 2 忸屯以石( 1 _ 似_ ) 若 _ 一叶2l - t u j 2 儿1 2 ( 1 石) 2 】+ 够( 1 + i 2 ) 【石2 ( 1 一l j ) 2 】 等等 章忱 i 心 i 呵 帕 ” 鸵 万 电乎辩技丈学硕士学位论文 + 巧2l - t q 2 八2 j _ 2 2 乃石+ 弼) + 鹭( 1 + 虿2 ) ( 霉i 2 2 石2 乃+ 万2 ) 一乃石2 a ，2 勺现+ q 2 当心2 0 时， a j 2 ( 1 + 所) + 衅毋+ d ，b j b j 等冬| u j 七b y i ，( a j x j + b , n j ) u i 专b | 五罗 。( 巧2 t + q q h ) ( 1 + 所) + - - j 2 主 j 一弗j + 去( 2 q 6 ，t + 霹勺) q 2i | ( a j + 屯) + b s 以巧峨 岩t a j 氕j + b i 孔0 t 、+ 弘：、斗b 2 2 j 凸2 j r o n j a i 寺b 一3 b j 九j 易。瞻( 勺冬+ 屯q ) ( 1 一冬) + 冬巧t 1 西三可哆+ 圭等匕髓 毗以坳州卜t ) + b j n j , z j 2 赫 + 爵纠嗽慨) ( 1 矧慨童】浩 霞为当鬈一0 对，乃。毛予楚岛= ( 1 一以) 2 ，因茈 日珥2 【( 口j 乃+ i 一从l * t ) + 以t 】2 ( 1 + 群) 十彰2 2 ( 1 一五，4 + 【( 吩一+ q ”从1 一乃) + 屯一t 】b j 以( 1 一一) 。骂a i 一2 磅b + c i 。 定理3 3 。2 设矩阵a 对称正定且其霄稽容秩序备，剃当 0 - y 2 ，o r o l + j 4 l 一，- ，井风扎甜不同时等于2 时，s a o r 迭代法的误差 向量满足 电子科拄大学硕士学位论文 | | s 。 | ； 【( 1 一) 2 + l 国( ，国) i ；】4 | | 瓯ij ； - 2 ( 1 - c o ) 4 + 国2 ( r - c o ) 2 卢? 】慨，瓯+ 1 ) + 4 ( 1 - o j ) 2ic o ( y - c o ) i 期8 , 1 12 i i 以+ j i l2 + i i 以+ l 屺( 3 3 1 ) 其中口= 2 【- r ) 2 ( 1 一彳) 2 + ( 2 一r ) ( r 一2 ( - o + 2 x i 一? ) 】，y ，国为松弛因子， 。是j o c o b i 迭代阵的最大特征值。 证明由引理3 1 2 易证t 石= 【( 1 一脚) 2 + 彩( ，一国) 所】2 ，于是 易巧2 【( 1 一) 2 + c o ( y 一) ；】4a j - 2 1 0 一口) 2 + o j ( y 一埘) ；】2q + c j ， q 。( 1 - a 从1 一动；2 【( 国一，) 2 ( 1 一) 2 + ( 2 - r ) ( r - 2 a t + 2 ) ( 1 - 巧) 】。 当o ，s 2 ，0 o ，因此 d ，q 当且仅当鸬一o 。所以有0 口d ，( i _ l ，- ，2 ，m ) ，于是 e j 砉 【( 1 一) 2 + ( ，一脚) 彳】4 月， 1 = 1 i - 2 0 一o j ) 2 + o j o , 一m ) 衍】2 目+ c ，) ( 3 3 ，2 ) 又因b j = 坫j ，s r 。 l 易| - i 传，s 。髟) i l l 白j i ：l l s ，。旬l i ：， 由c a u c h y s c h w a r z 不等式得。 i 岛i 崦s ，刎。 卅!埘! ( 一，) 2 ( c ) 2 ，- 】户1 2 l 疋l i2 i i 瓯+ ，忆( 3 3 3 ) 于是由( 3 3 2 ) 和( 3 3 3 ) 得 兰e ，丢 ( 1 一国) 2 + e o ( r 一国) 衍】4 兰爿， ，= 1 。 o t ，_ 1 。 2 4 墩子辩技大学硕士学位论文 - 2 【( 1 一m ) 2 + 甜( ，一m ) 彳】2 毋+ z c j ) j ；1p i 蔓( 【( 1 一c o ) 2 + | o ( r - c o ) t ? 跏磊雌 8 。 - 2 ( 1 - c o ) 4 + 掰2 ( r - o j ) 2 露】限，蠡+ 1 ) + 4 ( 1 一c o ) 2 w ( r 一脚) ? i | 瓯| 2 i l 瓯+ l i i2 + i i 以+ ，l ； 口 评论：当甜= ，对，就得到迭代法s s o r 的谡麓界 | | 繇躬s 砉嚣。一1 ) 2 | l 颤瞄2 ( o ) - - 妒瓴，袭“) + l 2 ， ( 此为m m a d a l e n am a r t i