（计算数学专业论文）关于z矩阵的修正不完全高斯—塞德尔迭代法谱半径的单调性.pdf

摘要 浙过火学鞭士毕韭论文 摘要 通常解线性方程组有a x = b 两种方法。一种燕宣接解法，需要对系数矩阵名 进行分解，因而一般不能保持a 的稀疏性。而实际应用中，特剐怒偏微分方程的 数值求解时，常常遇到的恰恰就是大型稀疏线性方程组的求解问磁。豳此寻求能 够保持穗疏性的有效解法就成为数值代数中一个非常重要的研究课题。 题翦主要豹方法有弧类：一是充分剥用所绘筑阵彳的特点，采用遥当的主元 豢选驭繁路，镬分鳄豳懿因予尽霹能地嫖持醛琉性；二是迭代法。对于第二秽方 浃，迭代矩阵的蕊取其有决定作用。只舂选取懿迭铽矩阵豹谱半经，j 、予l 才熊保 诞迭代法收敛。在遥代矩阵港半径小子l 韵情况下，傻越，j 、燹| l 收敛速发越快。在 解决某些具体问题中，有时虽然其迭代矩阵的谱半径小于1 ，但麓数值和l 菲常 靠近，则迭代过程非常缓慢，效果不好。这时就需采用其他办法。一种方法就是 对系数矩阵a 进行预处理，然后对预处理矩阵进行分解迭代。本文主要讨论的就 是对于经典商斯一塞德尔迭代法进行预处理过程中参数的选取，即最佳参数的定 位和确定。 a b s t r a c t浙江大学颧士毕韭论文 a b s t r a c t i nt h i s p a 转r , w e c o n s i d e rt h eo p t i m a lp a r a m e t e rv e c t o r c to ft h em o d i f i e d i n c o m p l e t eg a u s s _ s e i d e lm e m o d f m i g s ) w ep r o v et h a tt h es p e c t r a lr a d i u sf u n c t i o n 以o f t h ei t e r a t i v e m a t r i x 瓦o fm i g sw i mp a r a m e t e rv e c t o r 口i ss t r i c t l y m o n o t o n i c d e c r e a s i n g w i t h r e s p e c tt o 口s a t i s f y i n g 0 口ei ft h ec l a s s i c a l g a u s s _ s e i d e lm e 氇o dc o n v e r g e sf o raz _ _ m a 掇x 。s o m ep r o p e r t i e so ft h el e f ta n d r i g h t e i g e n v e c t o r sc o r r e s p o n d i n gt ot h el a r g e s te i g e n v a l u ei nm o d u l u sa r eg i v e n ，t o o ，t h e s e r e s u l t sa t eu s e f u lt of i n da no p t i m a l p a r a m e t e rf o rm i g s s o m ei l l u s t r a t i v ee x a m p l e s a l eg i v e n i i 本文搜震簿号说磷滤 王大学疆圭毕业论文 本文使焉符号说明 a ；z 一矩蓐，s i z e 驻) = n ，对囊元蔻1 b ：n 缎列向量 l ：矩阵a 的严格下三角部分整体取负 u ：矩簿a 鹄严捂上三角帮分整露取负 l 。：毛。! s u 。：u 。= u + ( 三一k ) 掰： n l 维的列向鼹，甜= k ，婵2 ，盘r d + = 扛舻1 a t a t , i 1 a i + 1 1 ， 1 , 0 - a 。- o 表 示建豹_ | 舞有元素帮大予零a 对于淘量搿，声，捃 筘表示掰裔分量瓴 焦。 1 1 1 豁牵籍遂翦鬻聚 囊嚣大学骧毕篮遗文 第一耄翊溪的背景 1 。经典衰簸一塞德象迭代 对于一个大型稀疏n 阶瓶阵a 和一个n 维商量b ，遮代法经常被用来解决线 髓系统a x ：6 。校多迭代激帮楚蒸于a 的粱种分离。褶应予分离a * m n ，其 中袋是l 专髯嬲，霹强萼| 爨麴下逛我 ( 1 1 )m x ( + ) = n x ( + 6 ， 麟者等价的 ”= t x 渤歹， 熟中t = 掰n , f = 膨。6 。掰魏，对予经夔的高新一赛德家方法，分离 a = d 一三一u ，荬中b 楚替鸯彝辫螽阵，一毛黧一珏分掰楚蠢戆严牾下嚣严臻上 三角部分。 2 + 毫骞鹣工撵 我们知道送代矩阵t 的谗半径决定遮代方法是否收敛以及收敛的遴度。为了 加快收敛速庶，种方法怒闻菜矩阵p 对绫性系统出。b 进行预处蠼，使灏问题 转穗舞p a x = 鳓，然嚣辩已经预憝毽过豹系统p a x = 始运薅遥我方法( 1 t ) 。 对于矩藤p a ，露新的分离曩* 删= 盛一贾糨应的迭代怒哦即+ 一l ：歙睛) + 器。 埘予预处理矩黔p 的选取，成该使迭代矩阵的谱半径尽可能的小。 黠予健统豹菇蘩一赛穗尔这找法，g u n a w a r d e n ae 1 1 l 撬癌一个铸萃臻疆理 斑蹲p * j + s ，其中 s = - 0 。 o n 怒矩簿羲除。( 这鸳我裔淹了方霞起凳，镁设窳薄鹜缀被对角称凄豫，帮名静 $ 嗽 一 2 唾0 o 第一章搿题懿骛袋 囊涯大攀醺警旺途文 j c 雩建元撰为1 ) 霹予矩阵矗凳z - - 矩阵瀚溥影，帮，嘞墨镜f # 歹，融经涯舞了奁 浆些条舞下，鼷缝溪高颠餐德尔方蘧竣簸速菠绦予健绫嚣鸯鬟葵德尔方法 1 】。k o h o ne 1 2 对它进行改进，弓i 入参向量群，使鞭处理矩阵p 。，+ & ，其中 s 。= 0 一a l d n 0 一嚣2 3 0 一眠啦4 口”一l 矗h l m o 遮整必是参向擞搿的第i 个分鬣。在这枣| f 情况下，预处理过的矩阵p a 有一个麓 单的分离 p a = 0 一一& ) 移一& + u ) ， 濑越等毽穆歪鹣嵩斯一赛穗承迭代 g 一三一& 冷强# = 秽& + & 秽) 善蝴手矗。 我们称之为修难高斯一赛德尔方法( m g s ) 。 显然，如果口= 口，即向鼙的所有分激都等于1 ，m g s 方法的迭代矩陴和 1 中褥弱。嚣经典靛衰藜一赛穗容方法 g s ) 海藏予攘= 0 懿蘩影。我船已爨黎遘 ( 可参糟 1 ) ，在假设o o i , # + l a “， l ，i * 1 , 2 ，。，撵一1 的憾提下，对予z 矩阵叠， 强g s 收敛时，m g s ( 当疗= 1 孵) 收敛速成快于经典的g s 方法。在 2 中，进一 爹讨论了当揲惫变量鼹m g s 穷法静投鼓毪。已经证靖了潦矗怒不胃魏辩角占饶z 一矩辫嚣尊，对予0 或蔓l ，m g s 方法收敛，静显存在菜秘燮群( 英分擞裙大予1 ) ， 使蕊嚣予! 墨癌球，m g s 方法竣簸。熬嚣，爨藿毒在一个参变藿g ，镶褥其辩痉 的m g s 方法收敛速度快于当髓= p 购情形，这点并不瀵越。也没有攒燃是否存在 个最饿参变墩群。，使得逖代矩阵的谱半径最小。 第一耄勰题戆聱最 溪江大学颈圭拳监论文 3 零文豹工俸 在这里，我们从更一般她角度考虑对分离么= i - k 一“二，其中k 是严格下 三角矩阵，u 。，惫0 。对该分离进行预处理得 p a = ( ，一l 。，一s 。上。) 一移。一s 。+ s 。u 。) ， 由此导出更一般的迭代 ( 1 。3 ) ( j l 。一& 。) 茸嵇q ) = ( 矽。一瓯+ & 玎。) x 壮十玉， 我嚣j 稼之戈修正不竞金毫簸一赛戆容迭代( m i g s ) 。当然，囊曩掰般必须满是 ( 1 i4 ) 酣。d “+ t 口，“，1 ， 以保j a 7 5 i - l 。一& 上。是非奇异的。因此，迭代矩阵有如下形式 以= ( i 一厶& 三。) “( 一& + 咒巩) 。 我们进一步限制口使得l 魑非负的，用s + 表示满足条件的岱的集合，则 s = 匆r ”k 吒。，譬l ，t o ) 。 对于z 一矩阵a 来说，搿d + = 缸毯胄“k 甜u + d 叫 l ，o q 蔓l 是瓦菲负的一个 充分条 牟。在诧条释下，瓦稽瘟予谱睾镣p 敷) 有菲受的右( 左) 特征商豢 3 。 在这纂文章中，我粕将推广2 中已有瓣缝论。我弱将迁爨：( 1 5 ) 当 0 蔓口e 时，如果g s 方法收敛，则m i g s 方法的谱半缀函数p 级) 是严格单调递 减的( m g s 方法可看作当上= 三。的特例) 。将会提及系数矩阵“相应于模最大特 征值的左( 右) 特征向量的一些性质，这些性质有助于参变缀d 的单调性证明。 在接下来豹章节中，第二章主簧证葫上蟊| 莠述静结论( 1 5 ) ；第三牵对改迸后 的算法与原经舆高斯一塞德尔迭代法进行e e 较并给出一些数馕例子；最后一章总 结结论。 篓三皇篓釜茎篓 望鋈杰鳖兰兰! i 墨 第二章理论分析 在本章节，主要垮谖爨本文豹棱心宠理，避过该楚理，我爨褥了簿刭在一定 取值范围内预处理商斯一纂德尔遮代法的最佳参数的选取。 1 ，袋娃参数懿定建 在【5 中，曾提出当口= e 时，预处理矩阵的谱半径比当甜取其 也值时小这一 现象。但是并没有给出严格的证明。接下来，我们将试着在照一般的m i g s 方法 中 正爨这一猿惩。 命题2 1 设避最，l = 1 2 。辟1 ，g ，箩e ，羲o 芦一岱o ， 则以下三条必满足其中之一： ( 1 ) p p l 。 诞嘤：下瑟我键在尼秘娱竣下绘予涯弱。关予这些骰竣戆歪礁注，滋蟹在下一节 证明。 ( 1 ) 假设；3 x a 0 ，艺扎= 以x 。在此假设下 0 = 移。一s 。+ s 。u 。h 一以( ，一三。一& 工。h = 鼬m + p ，l 。一p 。j + s ，鼬。十p 。l m 1 1 玲 ( 2 1 ) * + s 。x u 。+ p 。工。一，) 一( 尸。1 v ) x 。 记j = 一口，则s 口= s d + 咒。所以 了b x = 0 一l m se l m y 如。一sb + s m x = 电一l m s ，l m t 翅。一s ；+ s 翔m s6 如。i 淞 = 0 一k 一岛k ) - 1 瓴( f l 。一& 。) + & 移。一f 玲 = q l m s 口l m 7 1 l p ，q l m sb l 。) + ss 婶。七p 。l 。一i 恤 = p x 碡一l m s 8 l 。p s 6 。斗p ，毛m 一岛x 。 4 第二章理论分析浙江大学硕上毕业论文 一风x + ( p o l 如一k s a l 。) _ s 。( 1 + s o ) - 1 x ( 2 ) 记 n - 2 1 g ，= & “2 e & ) x 胪b s ：, - 2 h 去移一& 小 霰浚：氆= p ，+ 去萤。z = l ，2 ，匕j ，其中热跫拱i g s 方法迭谯矩薛匏谱半裰。 在此假设下， ( 2 。2 ) n - 2 s , ( i + s o ) - 1 茗= & ( - 芦x = 岛。 +去铲=霎万19l p l 觳+ 士g p 。 篇 + 9 2 = = 乞 = r 绺+ = = f 。 或磊瑶 1 万 港野= 2 m ，g 。= s ：2 - 2 聋0 ， 游行= 2 m + 1 ，g 。= s d 酲。( ，一) x 。 ( 3 ) 假设：g l o y t g 0 设y 0 怒的左特征向量 假设：眈_ l ，只) 0 。 因为o l 。一s a l ，) _ 1 的下三角部分怒正的，所以y 7 0 l 。一& 厶，) _ 1 的前n 一1 行元素是正的。5 4 9 ，的前n 一1 个元索为正，可得y r ( 1 一，一& 点。) - 1 9 ， o 。由 p 8 y x = 扩t b x = y 7 h 工+ 魄一1 以一厶厶) 1 9 ，) = 或芦7 x + 毛气一l 7 0 一三。一s # l 。，g ，。 若p 。 1 ，则p p y 7 x 成。 褒主囊翡毯爨跫程孛，我钌在器凳蟪方撵芗鬣设。落裁燕遵哭簧速疆签覆设 成立，该命题即为真。下耐藏们将接着诚明这些假设。注意到这四娥假设怒相互 独立的，所馘可以分剐证明。 2 系数矩膝桐艇。于谱半径的左将征向爨的性质 在第一个假设中，我们假定系数矩阵一相应于谱半衽存在大予0 的左特征向 嚣，在这- - 4 节，我餐将诞嘲它礴实存在。 定理2 1 ：若掰# ，“ q 1 ， 0 ，i 拦l 。，霏一1 ，搿岜冀州，o g 啦9 1 ，且娥+ l d 件| f 0 ，使得疋茹。= 以颤。 诋明：为了记母方便，戳殿不弓f 越混淆的情况下，记t - - - t , , ，x = ，p = 戊。 ( 1 ) 首先证明如0 。糟不然，z 。= o ，鼠可设喾o ，魄+ 1 = = x n = 0 。 i 7 3 x ，= 试，x 2 ，y ，岛* 0 榭，颤+ ：，+ ，罗= 0 。舅谣 他，( i - l - 训= 匕 ) 一= ( 琨复琮磋k 。， 汜姗， 吒母是畿笼) 孤 剃窿擐= 掣褥 援翌主z , 赢l 凫溉站。陋慨盼。池五2 1 1 + 蹋心1 k = j 2 2 ”1 ”“p 自鼗褥 班：，+ 溉，弦，；o 。 i n 终x a 筑l 2 i o ，强1 毓0 ，掰潋皿2 l 髫? = o ，都五2 1 墨= o 。豳予2 l 和盖， 帮楚 受戆，虽壤 露，鬟麓龟南= 嵇，帮= 岛q 三碲+ 毛魂& 壹 o ， 携i 懿矛鼹。因敝故0 。 ( 2 ) 现诞聋 0 e 不妨设晦= 姨 。= 0 。考惑嚣转薅黟 6 第二章理论分析 浙江大学硕十毕业论文 所以 若x l = x 2 = = x i = 0 ，则因为 c ，一l 。一s l 。) 。妙。一& + & u 。b = ， 妙。一+ s 。u o b = p 0 一上。一咒，h ， p ：p 。一s 。+ s u u 。，k = 肛：( ，一l 。一，咒三。k 。 注意到e n 7 s a = 0 ，可由上面的等式推出 矗= 去乙一+ o x ， o l t ” 其中，f 甚卅表示的是不属于上。的元素下标。，m 表示的是属于l 的元素下标。 所以i 0 ，所以彬：= 0 。由此可得 牌 0 = e k t 形1 2 巳= ( 1 - a ) “l o = t 2 p 2 = + 2 + + l ，。 因为舢- ，甜“舢： o ，i g k , k + 2 o ，z d k , k + l o ，所以由0 ) 得吼= 1 ；由( 6 ) 得：0 矛盾。因此该种情况不成立。 若g 。，x ：，。) 0 ，记工= ( 并，x 。，x 。) 7 ，其中 考虑分块 x ，=4 q ，x | 0 ，x h = fx k + l i 2 0 ，x = i i l “ i - i r 吲 三：z f3 i 砭岛- 瑞 一三3 2 三3 3 【 7 0 。 譬+ 他k i f rw 己 & 一 0 一 u 第二章理论分析浙江大学硕士毕业论文 则由t x 一厣得 霞盏糍归- - p ，x + ，- l - i 吲- 1 啊班，弦。0 j工：，i + 五：，皿，+ ( 砬三：。彬，+ 聪，p = j j 畦2 l 盖，+ 菇，+ 3 x m = 0 。 因为3 0 ， o ，1 x 1 0 ，所以三：，x ，= 0 。同( 1 ) 理，得出矛盾。因此 该种情况办不成立。原命题得证。 由蘧，我缃证臻了繁一令缓浚戆覆确洼。在落实了系数矩辫秘痰予谱半疑麴 左特征向量的性质后，我们接着来看其右特征向量的性质，也即第四个假设。 3 系数矩阵相应于谱半径的右特微向量的性质 第嚣个缀设中疆定潜半径懿左黪 蒌囱量若丈予簿予0 ，羹l 箕疆嚣嚣令分爨至 少有一个不为0 。也即下面的定理。 定理2 2 墩“。+ l 口， o , i = l ，n - 1 ，若y o 是p 的左特征向掇，掰如前，则 ( 2 2 1 ) ( y ，y 。) 0 。 证明：设饥十y 。) - - 0 。记m 0 ，y k “= = y 。= o ，1 9 k n - - 2 。又汜 誓= ( y ；，魏y ，= 恢。，y 。y = o 。 由y 7 t = 7 及( 2 1 1 ) ( 2 1 2 ) 得 ( 2 。2 ，2 黟碟戳：= 0 。 因为u l 。一& 三。- i 下三角部分为正，即 ( 2 。2 3 ) 窭一乓一鼓k ， o ，i 歹。 又因为写o ，y k 0 ，所以矽球 0 。所以啊，= 0 ，同定理2 1 的( 2 ) 中矛 盾，证毕。 4 证明中需要的个引理 8 暇嚷 ，。：。，；，。l l l m 攀 + 口 s m 第二章理论分搬滤江大学残生毕韭连文 我镪姨i 孛对念题2 。l 懿渡唆中，第二令缓设中戆等式是菲鬻毒势熬。这 也是在实践中摸索出来的一个关系式。下面我们就来证明这个等式。 引理2 1 设搿d ，x = x ( a ) 是相应于m i g s 方法迭代矩阵的非负特征向量，对于 任意的d r “，记 则 s 。r x ， 只唱s f - 2 i l l + 去pp 。一是) 卜 m 歹 l g i 。p | + g t + 1 ， p 。 蔟孛熊是m i g s 方法迭钱矩蓐螅遴半径。 证明：由定义， n - 2 1 g ，= & s ( i ) 4 x f ：l 厶，陲l ， l z j ：嚣醴 z f 窆_ 芦。一毛一瓦) n - 2 1 ( - 筑芦o + s o ) l 。 x i “0女m o 碣m 隧“ t s 。l m ) + ( ，一( - s o ) z ( - s o ) ( i - l ，( - s o ) n - 2 1 + l k 。、i x = & 。2 i 一 + p k 。 k 。o， ：& 霞m f 鐾( _ & y 8 一k 一& k ) + 五肼_ 。= & 霞“2 l ( _ & y 8 一三。一& k ) + 五肼k 。 #*”t 凌这里，应用了一令隐含懿条传嚣= 0 。 因为。，x ) 是迭代矩阵的一个特 正对，所以 g 一三掰& 三。矗= 移。+ s o u 。b ， p 。 搬它代入上式，褥 蚤一是霹“2 ( 毛，+ j | 。n 盏- 2 1 sk 瓯一是+ 鼓瓯小 9 籀一章避论努辑 濒江大学联士毕韭论文 = s 澎k 2 。卜去挚& 胁s o ) u 。十瓦1n 白 - - 2 t ( _ 跗“) x = 岛联2 1 - 2 一十去。一卜& 尸k + 去一”争s 。y 一& ) ：& 受m f 瓦+ 土p 。一s o ) + ”- 2 l - - 1 & 笋b lp m成 蕊 ：p ，+ 三g + l 。 p 。 证毕。 下溪昃囊下最器一令栽凌还没有解决。只簧涯甓了这令锻没静歪确毪，簧| j | 顾2t 姗虎寺 5 验证第三个缓教戆正确洼 由引理2 1 t ，酽”去铲2 刍m - i 万1 ”古p 。函p ；p 口 1 百g ， p 。 嚣= 2 m ，g ，= & 篾一2 x 0 ， 弹= 2 m + l ，g 。= & 嚣3 p 一& 墨。 只需证明g l 0 且虽# 0 。 因此 注意到存在某标孱叩0 ，使得& 酸= t i e ，。0 又由( 2 1 ) 得 e r x = e ：( l m + 吉c 一上。蝈x 。 p 躐s - 2 x = 渊4 一+ 吉犯一乞小 t 0 羔三墨l 望堡熊踅 觐坚查堂堡圭垩錾造塞 则 c 2 2 ， 菩m s a s ：。( ，& ( 三。+ 吉犯一厶) ) ) x 。 如果在选墩三掰时，把殿采蛉系数矩膝_ 蛉最后行( 除对角元赆) 都l 乍为五。，的 最后一彳亍元素，即犯一三。) = 0 。则( 2 2 ) 式可化为 。 2 s 。p & 三掰砖2 又爱。c 毛+ 吉帆一鼓+ 叉拶) 卜2 。 所以g 。= & o + & ) x 0 。又出( 5 1 ) 得 。 虽萋古魏= 岛萋皓) 4 皈+ 去瓯一篷骑。 当n 2 3 时军惘( 2 3 ) ，当h 4 时利用( 2 4 ) ，可以得出 g l & 三。x 。 因为o s s l m 2 0 ，x 0 ，所以蜀0 。在这里，我们发现第三个假设未能证明对 所有的k ，u 。成立，只怒证明了在某种条件限制下成立。困此，我们得趱了具有 菜些礞嬲的结果。鄂下瓤拘宗璋 定理2 1 设唾霆，江l ，2 ，拜一l ，声d ，著。辚声一g 。，警岱一l o ) ：。 时，以下三条必满足其中之： ( 1 ) 乃 1 。 冬注：可骏缀容易静验谖，当n = 2 辩，定理2 。i 筏立，显然或在窃：l 簿鬟夺。 由上面的定理，可以很盥然的得到如下推论： 推论2 i 缓竣6 i , i + i q 扎， o , i = 1 ，2 ，羚一1 如果尹0 ) 1 ，员| j 第一章理论分析 浙江大学硕士毕业论文 。m i ；n 。p 如) = p 0 ) 。 至此，我们已经证明了m i g s 在p ；乜一上。) = 0 时( 当l 。= l 时，即m g s ) 方 法在参变量0 口8 时，p 0 ) 是单调递减函数。 第三章嚣法分橱 游江大学顼士毕业论文 第三牵算法分析 1 与经典高斯塞德尔迭代法的比较 经典高斯一塞德尔迭代法在锶步迭代过程中都利用最新得到的x 的分量，即 在许髯善时稍露静面己褥到的x ， i ，孺m a t l a b 语言描述莸怒 f o r i = i ：n x ( i ) = ( b ( i 卜l ( i ，1 ：i - 1 ) 4 x o ：i - 1 ) + u ( i ，i + l ：n ) 4 x ( i + l ：n ) ) a ( i ，i ) ； e n d 露攫爨本文联提出黪葵法，先对系数矩黪盖送行疆祭体处瑾，孬霹镄楚瑾羼懿矩 阵进行高瓶一塞德尔迭代。这样的好处魑可以降低迭代矩阵的谱半裰，从两减少 迭代步数以到达减少计算量的目的。 下獯我 f 】来看个蒸俸瓣铡子。 例取一= llo 011 一三o1 矮怒篷解。嚣用m i g s 法，取 l 。= ，b = 1 ，1 ，1 】。用高斯一寨德尔迭代法在迭代6 9 步 ooo ooo 一三oo ， ，o 一1 ，u 。= 1 00 l0 0 时，只薅迭代3 5 步，诗算爨大大减少。 2 几个数德例子 飘第二章豹证疆中我稍褥知，程满足一定条件下，系数矩阵彳在经过预处理后 所得的迭代矩阵的谱半径随篱参量窿呈单调递减。这一小节，我们采举几个具体 例子。以加深对这一结果的理解。 铡i 取，j 、节移j 子中酌矩阵，翔柒按照经典高斯一塞德尔遥代法，其迭 r q | 甜 、t；：i， o q 篷兰童篷鎏坌堑 鳖鋈叁耋塑主矍望望耋 阳一10 、 代矩阵丁2 ：一。0 。5 - 1 j 相应的谱半径“神= o 。7 0 7 1 。若对系数矩阵一不完 全分离势进行预蘩l 串，不媲设奠= j 一毛一，其孛三。，吃与1 中铡提嗣。 著毅c g = # ，剩p ( l ) = 0 5 ；蓑取拦。圭g ，剽尹圆) = 0 5 8 7 7 ； ，哪 箸取g = 羚2 ，0 + 茸】，翔p ( 瓦) = 0 6 3 6 9 ；若取掰= 【o 4 ，0 2 矗爱| j p ( l ) = 0 6 3 6 9 ； 若敬a = 【0 3 ，0 。3 】4 ，爨l 矿瓦) = 0 6 3 8 6 ； 装取搿= 【o 。1 ，0 5 】 ，n p ( t o ) 一0 6 3 1 4 ； 蒋取饼= 【0 5 ，0 ，l 】，则厦t o ) = 0 6 3 1 4 ； 游取a 引o 1 ，0 9 1 ，n p ( l ) 一0 5 3 8 6 一= lo 2 0 1 一o 4 0 2 一o 210 3一o 。lo ，6 一o 3 0 21一o 1 0 6 0 ，l 一0 1 一o ，ll一0 ，o l 一0 2 0 3 0 。4 0 31 薄弱经典毫袋一塞德零迭 弋，爨p = 0 9 6 t 1 ；不妨取群= g ，a = 1 一l 。一乇。 蓉取卅= 若取厶，* o o 2o o 3 o ，1 o ，2 0 o 。2 o 3 0 0 2 o 2o o 10 10 o 30 。40 30 g 0 - 2o 000 0 30 40 30 ，则p * o 9 5 0 5 ； ，则p * o 9 5 7 5 ； t 4 臻三章算法分辑潺 王大学鹾士毕监论文 萋取三。= 着取l 。= 蓿取三。= 游取氐= 装取三。= o 。0 。0 00l ，裂p 。0 。9 6 6 6 ；o 3l ，刘= 。5 oooof 00 30 400 j 0 1 00 | 0 00 l ，则p = 0 9 7 4 6 ； o o00i 、0 00 40 o j 0 1 0 20 l 0 30 20 l ，则p = 0 9 6 3 5 o 。lo 。lo 1gl 0 20 30 0 3 o j 0 、 o 2ol 00 20 | ，女j t p = 0 9 7 2 8 ； o 1o 1 o 10l 0 200 0 0 o 1 00 f 000 l ，贱尹= 0 9 7 6 8 。 o 1o 1o 10i 00000 例3 我们取阶数较大的矩阵。为了书写方便，我们采用m a t l a b 中的记号。 矩阵的生成逶稷如下； a 一一r a n d ( 5 0 ) k a a d i a g ( d i a g ( a ) ) + e y e ( 5 m l m ；z e r o s ( 5 0 ) f o r i = l ：l l 。l t 2 - - d i a g ( d i a g ( a ，- i ) ，- i ) l m = l m + t e n d 1 5 第三章算法分析浙江大学硕士毕业论文 即一k 依次取次下对角霜，次下对角元加上再下蠢- - n 对角元。我们随枫取 四次a ( k = 2 0 ，3 0 ，4 0 ，5 0 ) ，并把相应的绪果绘成图，如下： ( 1 ) k 2 0 ( 2 ) k = 3 0 ( 3 ) k = 4 0 14 一 l 。3 5 i 13 i ， |，。 ” 7 7 | 12 一一打一 俘籀嚣 褥鹅啦4 5船 o ”卜言一靠右嗜打言。誊 1 6 第三章冀接势辑囊嚣大学疆圭筝照谂文 螭0 l j o4 - j l a 辅 ； n 3 h 。 r - 一 05坩堪 一一一，一l 措蒋 椭龉鞴 扶瞬象中我们可以褥出满足定瑷2 1 。 整二兰墼墨鉴矍璧 堑垩盔兰堕圭璺! ! ! ! 苎 第罄章总结 在第二耄中，我们证明了本文的主要结论，即 定理2 1 设掰，蔓届，i = 1 , 2 ，n 一1 ，口，d 。，菪o 一口0 ，当e r ( l - l 。) = 0 时，以下三条必满足茕中之一： ( 1 ) p 口 l 。 从篇三章的例子中，我们也可以看出确实符合该定理。假是我们只讨论了当 穰。屈的情形，如果a 中某些分嫩大于声中的分量，而其余的则小于等于卢中 对应的分量，那会有什么结果昵? 勇耱，当瓦不瀚辩( 注：一照三m 确定，瑟凿定，搿黻只需讨论一个都 霹) ，题谱半经有倪影噙? 我们从第三章的例子中我们可以发现一些脊趣的现象。 佣如扶例1 中可姐看到当参量盯的各个分鼙之间蓑得越太，则谱半径越小。 扶第三搴豹铡2 孛我翻霉激看爨，当三。中存京游元素篷较大鹣话，谱半径程对 较小。铡3 中我们从曩象霹以壹缀憨看型兰三。取黪黠焦线越多，鬟g 迭代簸簿静 谗半径越小。 上颂我们所看到的现象除第三个已经有定理保证以外，萁余的都未曾证实。 蠢待于今轰继续深入褥究。 i 8 叁耋茎墼 塑姿态堂堡圭璺些笙苎 参考文献 【l 】a ，d 。g u n a w a r d e n a , s 。k j a i u , l s n y d e r , m o d i f i e d i t e r a t i v em e t h o d sf o rc o n s i s t e n t l i n e a rs y s t e m ，l i n e a r a l g e b r aa p p l 1 5 4 1 5 6 ，p p 1 2 3 * 1 4 3 ，1 9 9 1 2 】t k o h n o ，hk o t a k e m o r i ，h n i k i ，m u s u i ，i m p r o v i n gm e t h o d m o d i f i e di t e r a t i v e m e t h o d sf o r z - m a l r i c e s ，l i n e a r a l g e b r aa p p l 2 6 7 ，p p 1 1 3 1 2 3 ，1 9 9 7 【3 】a ，b e r m a n ，r j 。p l e m _ m o n s , n o r m e g a t i v em a t r i c e s i nm a t h e m a t i c a ls c i e n c e s ， s i a m ，p h i l a d e l p h i a ，p a ，1 9 9 4 【4 w l i ，ws u n ，m o d i f i e dg a u s s - s e i d e lt y p em e t h o d sa n dj a c o b it y p em e t h o d sf o r z - m a t r i c e s ，l i n e a ra l g e b r aa p p l 3 1 7 ，p p 2 2 7 2 4 0 ，2 0 0 0 5 1k r j a m e s ，c o n v e r g e n c eo fm a t r i xi t e r a t i o n ss u b j e c tt od i a g o n a ld o m i n a n c e ， s i a m j n u m e r a n a l 1 0 ，p p 4 7 8 4 8 4 ，1 9 7 3 6 】k r j a m e sa n dw r i h a ，c o n v e r g e n c ee f i t e d a 岛rs u c c e s s i v eo v e r r e l a x a t i o n ， s i a m j n u m e r a n a l 。1 2 ( 2 ) , p p t 3 7 1 4 3 , a p t , 1 9 7 5 【7 】m u s u i ，h n i k i ，a n dt k o h n o ，a d a p t i v eg a n s s _ s e i d e lm e t h o d f o rl i n e a rs y s t e m s ， i n t e m a t l j c o m p u t m a t h 5 1 ，p p 1 1 9 1 2 5 ，1 9 9 4 瀚s 。v a r g a , m a t r i xl t e r a t i v ea n a l y s i s ，p r e m i c e - h a l i , e n g e l w o o dc l i f f s 零j ，1 9 6 2 【9 】a b e r m a na n dr j p l e m m o n s ，n o n n e g a t i v em a t r i c e si nt h em a t h e m a t i c a l s c i e n c e ，a c a d e m i c ，1 9 7 9 f lo 】j e m i l a s z e w i c z , i m p r o v i n gj a c o b ia n dg a u s s s e i d e li t e r a t i o n s ，l i n e a ra l g e b r a a p p l 9 3 , p p 1 6 1 1 7 0 ，1 9 8 7 【11 】m e m o k a r i - b o l h a s s a na n dt n t r i c k , an e wi t e r a t i v ea l g o r i t h mf o rt h es o l u t i o n s o f l a r g es c a l es y s t e m s , p r e s e n t e da t2 8 如m i d w e s ts y m p o s i u mo nc i r c u i t sa n ds y s t e m s l o u i s v i l l e ，k y 1 9 2 0a u g 19 8 5 1 2 】m e m o k a r ib o l h a s s a n ，d s m a r t ，a n dt n t r i c k , an e wr o b u s tr e l a x a t i o n t e c h n i q u ef o rv l s i c i r c u i ts i m u l a t i o n , p r e p r i n t 13 】h s c h n e i d e r , t h e o r e m so l lm s p l i t t i n go f8s i n g u l a rm _ m a t r i x 。l i n e a r a l g e b r a a p p l 5 8 ，p p 4 0 4 2 4 ，1 9 8 4 【l 碡j w l ia n dz y y o u ，t h em u l t ip a r a m e t e r so v e r r e l a x a t i o n m e t h o d , 妻壹塞鍪 。 ，望鋈鲞燮蹩主兰! ! i ! 圣 l c o m p u t m a t h ，1 6 ( 4 ) , p p 2 3 1 - 2 3 8 ，1 9 9 8 1 5 1 z i ，w 0 z n i c k i ，n o n n e g a t i v es p l i t t i n g t h e o r y ,j a p a n l l n d u s t ，a p p t m a t h 。，l l , p p 2 8 9 - 3 4 2 ，1 9 9 4 【1 6 】r 。sv a r g a , m a t r i xi t e m t i v e a n a l y s i s , p r e n t i c e h a l l