（计算数学专业论文）psd迭代法的收敛性分析及误差估计.pdf

p s d 迭代法的收敛性分析及误差估计 林喜梅 摘要大型线性方程组的求解是大规模科学与工程计算的核心，许多作者 都对此作了研究( 见【1 8 - 2 9 1 ) 。随着计算机的飞速发展，需求解的问题的规模越来 越大，迭代法已取代直接解法成为求解大型线性方程组的最重要的一类方法一 般情况下，线性方程组的迭代解法不能通过有限次的算术运算求得方程组的精确 解，而是逐步逼近它，即使每个计算步骤都用精确的算术运算，迭代解法也只能得 到近似解因此，凡是迭代解法都有收敛性与误差估计的问题，本文主要讨论预条 件同时置换( p s d ) 迭代解法的收敛性与误差估计 对于p s d 迭代法收敛性问题已有许多工作者对它进行了研究( 见【l 】_ 【1 3 ) ，而 本文在第二章中一方面指出d j e v a n s 和n m m i s s i r l i s 在文献 1 】中定理3 3 的 不准确，同时给出了当线性方程组a x = b 的系数矩阵a 为对称正定阵时，p s d 迭代法收敛的个充分条件与之比较，并且在2 3 中用实例说明了对于一部分矩 阵而言本文得到的充分条件广于【1 】中定理3 3 的充分条件；另一方面，按照文献 f 1 4 的方法，我们从p s d 迭代法的特征值a 与其j a c o b i 迭代矩阵b 的特征值p 的关系式： ( a 一1 + r ) 2 = f p 2 【u ( 2 一u ) ( 一1 ) + r 】 出发，在不同条件下对p s d 迭代法的收敛性和最优参数以及最优谱半径进行了完 整的分析：( 1 ) 在系数矩阵以为( 1 ，1 ) 相容次序矩阵且对角元全不为零，其j a c o b i 迭代矩阵b 的特征值全为实数的条件下，给出了p s d 迭代法收敛的充分必要条 件，此结果与 9 】中的定理1 等价，此时最优参数及最优谱半径由 8 】得： 2 - 2 “o p t 5 1 ，t o p l 2 e 可，p o r e 2 秭i ； ( 2 ) 第三章表3 3 中给出了，当系数矩阵a 为( 1 ，1 ) 相容次序矩阵且对角元全不为 零，其j a c o b i 迭代矩阵b 的特征值全为纯虚数或零时的p s d 迭代法的收敛范围 和最优参数，并且我们可以得到当0 西 垡机i 啊忑时， 2 21 + f + 们哥 “o p fi t 可雨i 或万磊豇了写t o p 产百五丽了丽i 甭 垡扳琢 ”。一、r 干萨( 1 十、t ：雨) p s d 迭代法是s s o r 方法的最佳外插迭代；除此之外，p s d 迭代法的收敛速度 和s s o r 方法的收敛速度一致 随着系数矩阵a 的阶数的增大，线性方程组a x = b 的精确解很难直接解出， 因此我们有必要去获取其误差估计来判断每一步迭代的好坏本文的第四章在线 性方程的系数矩阵a 为对称正定( 1 ，1 ) 相容次序矩阵的条件下，得到了一个依赖于 向量内积的p s d 迭代法的误差估计，并用实例说明了此误差估计的有效性与实用 性 关键词：p s d 迭代法对称正定阵收敛性最优参数最优谱半径 a n a l y s i so fc o n v e r g e n c eo fa n de r r o rb o u n df o rp s d i t e r a t i v em e t h o d l i nx i m e i a b s t r a c t ：h o wt os o l v et h el a r g el i n e a re q u a t i o n si st h ec o r eo ft h el a r g e - s c a l e s c i e n c ea n de n g i n e e r i n gp r o j e c tc o m p u t a t i o n m a n ya u t h o r sh a v es t u d i e di t ( s e e ：s 一 2 9 】) ， w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e r ，t h es c a l eo ft h ep r o b l e mb e c o m e sl a r g e ra n d l a r g e r d i r e c tm e t h o dh a sb e e ns u b s t i t u t e db yi t e r a t i v em e t h o da n di t e r a t i v em e t h o dh a s b e c o m eo n ek i n do ft h ei m p o r t a n tm e t h o d sf o rs o l v i n gl a r g el i n e re q u a t i o n s u s u a l l y , w e c a n o tg e tt h ee x a c ts o l u t i o no fl i n e a re q u a t i o n sb yw a yo ff i n i t ea r i t h m e t i c so p e r a t i o n s b yi t e r a t i v em e t h o db u tc a ng r a d u a l l ya p p r o a c hi t a l t h o u g he v e r yt i m et h ea r i t h m e t i c o p e r a t i o ni sa c c u r a t e ，w eo n l yg e tt h ea p p r o x i m a t es o l u t i o nb yi t e r a t i v em e t h o d s o ， i t e r a t i v em e t h o dc o d c e y i 】st h ep r o b l e mo fc o n v e r g e n c ea n de r r o rb o u n d t h et h e s i sd e a l sm a i n l yw i t ht h ec o n v e r g e n c ea n de r r o rb o u n do ft h ep r e c o n d i t i o n e d s i m u l t a n e o u sd i s p l a c e m e n tm e t h o d ( p s dm e t h o d ) m a n ya u t h o r sh a v er e s e a r c h e dt h e c o n v e r g e n c eo fp s dm e t h o d ( s e e 1 - 【l3 】) o nt h eo t h e rh a n d ，i nc h a p t e r2 ，w ep o i n t o u tt h ee r r o ro ft h e o r e m3 3w h i c hw r i t t e nb yd j e v a n sa n dn m m i s s i r l i si na r t i c l e ” a tt h es a n l et i m e ，as u f f i c i e n tc o n d i t i o nf o rc o n v e r g e n c eo ft h ep s dm e t h o di sg i v e nt o b ec o m p a r e dw h e nt h ec o e f f i c i e n tm a t r i xao ft h el i n e a rs y s t e ma x = bi sas y m m e t r i c ， p o s i t i v e l yd e f e c t i v em a t r i x i n 3 2 ，5 1 1e x a m p l ei sg i v e nt os t a t et h a tt h er a n g eo fo u r s u f f i c i e n tc o n d i t i o ni sw i d e rt h a nt h e o r e m3 3o fa r t i c l e 1 】o nt h eo t h e rh a n d ，f o l l o w i n g a na n a l o g o u sa p p r o a c ho f 【1 4 a n ds t a r t i n gt h ef u n c t i o n a lr e l a t i o n s h i p ( 一1 + t ) 2 = r 2 p ( 2 一u ) ( a 一1 ) + r 】 w eh a v eap e r f e c ta n a l y s i sf o rt h ep s dm e t h o dt oc o n v e r g ea n do p t i m u mv a l v e sf o rt h e i n v o l v e dp a r a m e t e r su n d e rd i f f e r e n tc o n d i t i o n s ( 1 ) u n d e rt h ea s s u m p t i o n st h a tai s8 c o n s i s t e n to r d e r e dm a t r i xw i t hn o n v a n i s h i n gd i a g o n a le l e m e n t sa n dt h ee i g e n v a l u e so f t h ed a c o b im a t r i xo faa r er e a l ，w eg e tn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rt h ep s d m e t h o dt oc o n v e r g e n c e t h er e s u l ti se q u a lt ot h e o r e mlo fa r t i c l e 9 u n d e rt h es a m e c o n d i t i o n ，w ec a ns e et h eo p t i m a lp a r a m e t e ra n do fc o r r e s p o n d i n gs p e c t r a lr a d i u so ft h e p s dm e t h o di n 8 ： 嘶叫惭= 击脚= 岳； i i i ( 2 ) w h e na i sac o n s i s t e n to r d e r e dm a t r i xw i t hn o n v a n i s h n gd i a g o n a le l e m e n t sa n dt h e e i g e n v a l u e so f t h e j a c o b i m a t r i x o f aa r e i m a g i n a r y o rz e r o ，w eg e t n e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sf o rt h ep s dm e t h o dt oc o n v e r g e n c e i nc h a p t e r3 t h eo p t i m a lp a r a m e t e ra n d o fc o r r e s p o n d i n gs p e c t r a lr a d i u so ft h ep s dm e t h o da r eg i v e nb yt a b l e3 3 m o r e o v e r u n d e rt h ea s s u m p t i o n0 西 立耳罾， w a p t 2石+ 1 + 22 r 孺+ 1 一面 1 + 垡2 + v q + 西2 唧户面面丽石丽； 垡归一毋 9 唧2 丽i 丽i 丽 p s dm e t h o di st h eo p t i m a le x t r a p o l a t i o no ft h es s o rm e t h o d 、o t h e r w i s ei t sc o n v e r - g e n c er a t ei st h es a 3 n et ot h es s o rm e t h o d o nt h ei n c r e a s i n go ft h er a n ko fa ，i ti sd i f f i c u l tt og e tt h ee x a c ts o l u t i o no fl i n e a r e q u a t i o na x = bd i r e c t l y s o ，w et h i n ki ti sn e c e s s a r yt oo b t a i nt h ee r r o rb o u n dt oj u d g e p e ri t e r a t i o n i nc h a p t e r4 ，u n d e rt h ea s s u m p t i o n so ft h ec o e f f i c i e n tm a t r i xao ft h e l i n e a rs y s t e mi sas y m m e t r i cp o s i t i v e l yd e f e c t i v ea n dc o n s i s t e n t l yo r d e r e dm a t r i x ，w eg e t ae r r o rb o u n df o rt h ep s di t e r a t i v em e t h o da n dt h ee r r o rb o u n di sd e p e n d e n to nt h e i n n e rp r o d u c to fv e c t o r a ne x a m p l ei sg i v e nf o ri u u s t r a t et h ee f f e c ta n dp r a c t i c a b i l i t y o ft h ee r r o rb o u n d k e y w o r d s ：p s di t e r a t i v em e t h o d ，s y m m e t r i cp o s i t i v e l yd e f e c t i v em a t r i x ，c o i l - v e r g e n e e ，o p t i m a ip a r a m e t e r ，o p t i m a ls p e c t r m 学位论文独创性声明 y 9 0 0 5 8 3 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 作者签名：垫童垫日期：迎玺蝎 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版。 作者签名：盏圭翅 日期砌6 晕协目 日期：丝兰! 至! 纠 第一章引言 在实际应愿巾，特别是馈微分方程匏数篷求惩时，鬻卷遇裂豹埝恰就是大型 稀疏线性方程组的求解问题因此寻求能够保持稀疏性的有效解法就成为数值代 数中一个 常重要的研究深题，隧藏发鼹起来的一类重要的方法便是迭代法 这里，我们将讨论的是单步耀常线性迭代法； + 1 = g 盎+ c ，k = 0 ，1 ，2 ，。 其中g r n n 为选代矩阵，。( o ) 为初值。 我们知道，除了每步迭代所需的计算开销任何一种遥代法翡有效性都取决于 意的收敛速度，因此许多工作者千辛万酱地去寻求各种加快迭代法收敛速度的技 术，其中一种行之有效的方法是掰条件怒阵q 采构造一种新的遥代格式通过这 种技术，许多古典的迭代法比如：a s , s d 月的收敛性得到了很大的提高【1 5 】，于是 人们想蔻否可以澈过这种技术我一种送彳弋格式来敬造对称翡s o r ( s s o r ) 收敛毪 呢? 终予在1 9 8 0 每，d j e v a n s 和n m m i s s i r l i s 提出了求解大型线性方程组的预 条件霹爵麓换迭健法弹p s d 迭俊法瓣。 求解线性方程组 a x 一屯 1 1 ) 其中a 苣r n ”非奇异阵髓对角元日 零，$ ，b 钟芦未知，b 已知。 不失一般往，我们假设 a = i 一五一矿，( 1 2 ) 其中，l ，一u 分剐为a 的严格下和上三角矩阵，相应的j a c o b i 迭代矩阵 b = l + u ( 1 3 ) 耪q 是非奇异阵且q “易计算，于是( 1 1 ) 可以变成 q a x q - 1 b( 1 4 ) 令 q 一一w l ) ( i w u )( 1 5 ) 与( 1 2 ) ，( 1 5 ) 所对应的p s d 迭代法f l j 的迭代格_ 式为： 嚣2 + 1 = s 口搿是+ ( j 一甜f ) 一1 ( j 一皤) 1 r 6( 1 6 ) 1 对应的迭代矩阵为 s 。= m 一1 n = ( j _ u u ) 一1 ( ，一w l ) 一1 ( 1 一丁) j + 盯一u ) ( l + 矿) + u 2 l u 】 其中r ，u 为实数且r 0 ，这里， m = ；( j u l ) ( j u u ) 随着r 和u 的取值不同，就可以得到不同的迭代方法，如下表所示 表l r 矩阵肘方法 01j j n c d b i 0 言j j d 且 u ( 2 一u ) 珂壬：可( j u 工) ( j u u ) s s o r uu 占( j w l ) ( i w u ) e m a 1 ( i w l ) ( i w u ) p 】 本文主要考虑当线性方程组a x = b 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵且其 j a c o b i 迭代矩阵的特征值在不同的条件下的p s d 迭代法的收敛性问题以及最优 参数的选取；本文另一个结果是在系数矩阵且为对称正定( 1 , 1 ) 相容次序矩阵，并 且其p s d 迭代法收敛的情况下，对p s d 迭代法的误差进行了分析 2 第二章j a c o b i 特征值为实数时p s d 迭代法的收敛性 在本章中，我们主要是在线性方程组的系数矩阵a 为( 1 ，1 ) 相容次序矩阵及a 的j a c o b i 迭代矩阵的特征值脚均为实数且嵋 1 的条件下，得到了p s d 迭代法 收敛的一个充分必要性定理，并由此得到了一个易于判别p s d 迭代法是否收敛的 收敛性定理，与此同时，我们也得到了表1 中各迭代法收敛的充分必要性条件 2 1 预备知识 d j e v a n s 和n m m i s s i r l i s 在文献【1 】中提出了p s d 迭代法的同时，还对当系 数矩阵且为实对称正定阵时，p s d 迭代法的收敛性进行了讨论，并得到了p s d 迭代法收敛的一个充分必要性条件，即： 0 u 2 ，0 丁 2 w ( 2 一u ) 2 我们将举例指出此条件并不准确，只是一个充分条件，必要性不成立同时我们也 给出一个充分条件与之比较当系数矩阵a 为相容次序矩阵且h 阵时，文献 2 】和 3 也对p s d 迭代法的收敛性进行了讨论本章中，我们将在a 为( 1 , 1 ) 相容次序 矩阵及a 的j a c o b i 迭代矩阵的特征值脚均为实数且碍 0 ，则其j a c o b i 的特征值 胁，i = 1 ，2 ，n 是实数，若记p 1 = m i n m ，卢。= m a x # f ，则下述关系有且仅有一个 lt 成立： ( a ) 肛l = p 。= 0 ( b ) p 1 0 p 。 霉l 璎2 农零l 溪1 瓣条移下，搿揪= 融一。鹭最投墨a 秀慰惫矩蓐。 不失一簸性，当a 势黠称爱定箨瓣，我 l 纹考虑舻l o 鳓鹣蘩凝。 霉l 璎3 【1 键若线羧方羧缀豹系数缀箨建涛( 1 , 1 ) 穰銮凝穿矩簿瓣筵p s d 迭代 瓷辫。懿聿擎往稳天与j a c o b 遥f 戆阵b = 五+ 秽懿特鬣毽舻鸯辩下关系： a i 十f ) 2 = 帮2 扫( 2 一掰；( a 1 ) 碉2 1 ) 霉l 瑾罐滓1 菪热了筠秀实数，二敬方程妒一雕+ 7 = 0 鹬两根努剿为a l ，沁弼 阪i 1i l ，2 静充分必簧条件楚： 翻 1 ，疆1 + 7 ， 薯 理磊嘲菪线栏方程缀l 1 ) 秘系数怒终五巍疆，1 ) 狸察次序艇黪豆对燕嚣全 不为零，其j a c o b i 迭代矩阵b 的姆皴瞧芦l ，加均为实数，且罅l p 啦j ， 赠p s d 送健法牧皴静充分妊隳条转斑； 0 f 瓯， 。势髓娥瓯= ，蠹 堡螋笔孚圊 定瑾l 删若a 怒实霹黪鞋定簿，捌p s s 迭代法收敛豹充分菸要条释怒 0 甜 2 ，o 丁 ；时， 耻( 洲= 警她a 拼 - 可见当u = ，r = 1 时p s d 迭代法仍然是收敛的 定理l 若a 是实对称正定阵，当0 r 2 ，呈二龇2 j l l u 呈二学时， 研州= ( j u u ) 一1 ( j 一上，工) 一1 ( 1 一t ) i + ( 丁一c ，) ( 工+ u ) + 0 3 2 工明 m = ；( i - - c d l ) ( ，一u c y ) ，= ； ( z - t ) r + ( t - - t o ) ( 工+ 矿) + j l u m v + = ；【( 2 一t ) j + ( t 一2 u ) ( 工+ 矿) + 2 l u ；【( 2 一r ) j + 一一2 u ) 陋+ u ) 】正定： m t + 正定 r ，2 一( 1 一p 。) r 百9 斧 时，m t + 正定 ( 2 ) 当2 w r 0 时我们考虑( 2 w r ) 肛l 2 一r 即当u ，r 满足下列条件 掣 u 百t2 m 2 时，m 7 + n 正定 总之：当0 t 2 ，生垃2 # i 兰二甓竽时，m t + 正定根据文献【1 6 】当 a 为对称正定阵时，m t + 正定甘p ( s 。) 1 ，定理证毕i 上面的收敛性定理依赖于j a c o b i 迭代矩阵的特征值，我们将在本章的第三节 的数值例子中指出在某些情况下，定理1 所示的收敛区间将广于定理1 ，得到的收 敛区间。 下面我们将在线性方程组a x = b 的系数矩阵a 为( 1 ，1 ) 相容次序矩阵，j a c o b i 迭代矩阵的特征值脚全为实数，且芦 1 的条件下来讨论p s d 迭代法的收敛 性 定理2 若方程组( 1 1 ) 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵且对角元全不为 零，其j a c o b i 迭代矩阵日的特征值p 1 ，p 2 ，均为实数，且p i ( v j ) ，记 坐2 呼n 川，卢2 m 胁i 则p s d 迭代法收敛的充分必要条件为： 。 r 2 ，1 一n u l + n ，其中? = v 7 二羔! 二蔓兰l 专；掣 证明由引理3 知，舅。的特征值a 与j a c o b i 迭代矩阵b 的特征值弘满足下 列关系式： ( a 一1 + r ) 2 = r u 2 p ( 2 一u ) ( a 一1 ) + r 】 通过整理得： 2 一 2 ( 1 一下) + u ( 2 一u ) 下上2 1 + ( f 一1 ) 2 + u ( 2 一u ) 一r 】下肛2 = 0 根据引理4 ，p ( s ，- 。) 1 等价于求解下列方程组： r k r 一”2 + p 。一u 一r l r p 2 i 1( 2 2 ) l1 2 ( 1 一r ) + u ( 2 一) r p 2 i l + ( 一1 ) 2 十p ( 2 一w ) 一r r u 2 6 下面令0 3 ( 2 一u ) = 0 ，则( 2 2 ) 变为 一1 ) 2 + 徊一r ) 叫2 i 1 ， ( 2 3 ) 1 一下) + 日t 肛2 i 1 + ( r 一1 ) 2 + ( 0 一下) 7 - p 2 此时与【1 4 】中的a o r 方法收敛的充要条件一致，这里只须把7 - 当u ，相应的0 当 作，y ，于是由1 1 4 得到：i 1 ( v ( i ) ) ，并且有： ( 1 ) 当丝0 时，r 与0 的取值范围如下表； 表2 i t1 8 ( 而，o ) ( 卢( p 2 ) ，a ( 口2 ) ) ( 0 ，2 ) ( a ( 豇2 ) ，z ( 0 2 ) ) 2 ，研2 ) ( n ( 肛2 ) ，卢( 矿) ) 喜萎中： n ( z ) 兰彳1 - i 互1 丁2 z 一 丁2 + 2 r 一2 ) ，卢( z ) 兰；( r z 一下+ 2 ) 声= p 2 下面根据表2 来确定u 的范围 ( i ) 由表2 知：当一2 v s 一些 r 0 时，p ( 矿) 0 3 ( 2 一c ) ) o ( 口2 ) ，即 r iu 。一2 u + 号芦 o ( 2 5 ) 由与( 2 4 ) 相对应的关于u 的方程的判别式 a 1垡二! 三! ! 二剑 o “2 、。 知( 2 4 ) 与( 2 5 ) 组成的不等式组无解 7 ( i i ) 由最2 知：当0 t 2 时，有a ( ) u ( 2 一u ) o ( 2 6 ) 【u z 一+ 12 - 2 舻r 2 + 2 r - 2 。( 2 - 7 ) 由与( 2 - 6 ) 相对应的关于u 的方程的判别式 。：! 眭! 掣! 二拗 o 得c ) ( 一，+ o 。) ；由与( 2 7 ) 相对应的关于u 的方程的判别式 。：坐：! ! 二里! ! 芸壁! 型! 二：虬。 得1 一。 l + a 其中，a = 、i 事币= i f i 面f 五沔丽所以，解( 2 6 ) 和( 2 7 ) 组成的不等式组得到最后结果为：当0 r 2 时， - 一a u + a ，其中a = 圭二：垡二二至：；去掣 ( i i i ) 由表2 知；当2sr 2 1 一生时，o ( 口2 ) w ( 2 一c ，) 。( 2 8 ) l 冉弘+ 垃鼍笋型 0 解此不等式得：f 研2 又因为 2 茎r f ：i 2 妒，所以下面考虑它们的交集，然而1 一口2 1 一矿 面：互2 妒可见此交集为空集因此，3s 0 所以，由( 2 8 ) 及( 2 t 9 ) 组成的不等式组也无解 总之，通过( i ) ，( i i ) ，( i i i ) 分析可知：当芦0 时，r 和u 的范围分别为定理所 述 8 ( 2 ) 当些= 0 时，在p 1 ，p 2 ，p 。中，我们分两种情况来考虑： ( i ) m = 0 ，1 i s m ，此时由( 2 2 ) 得到p ( 昌，。) 1 0 r 2 ( i i ) 地0 ，m i 茎n ，可按照( 1 ) 来分析 综上所述，定理证毕_ 推论若方程组( 1 1 ) 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵且对角元全不为 零，其j a c o b i 迭代矩阵日的特征根弘1 ，p 2 ，脚均为实数且p 2 f i ( v j ) ，记p = r a i ni p i i ，口= 9 xi p t l 贝0 ： ( i ) p j 迭代法收敛( 即p ( 岛。) 1 ) 的充要条件是： 1 一秽 u 1 + 毋 其中，毋= 、5 ( 1 + 肛2 ) 皿( 若万= 0 ，则一o o u + o 。) ( i i ) s s o r 迭代法收敛( 即p ( & ( 2 一。) ，。) 1 ) 的充要条件是：0 u 2 ( i i i ) j o r 迭代法收敛( 即p ( ，0 ) 1 ) 的充要条件是：0 u 2 0 + _ ) 由定理2 与引理5 作比较得： 定理3 若方程组( 1 1 ) 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵且对角元全不 为零，其j a c o b i 迭代矩阵b 的特征根p 1 ，肛2 ，p 。均为实数且肛 l ( v j ) ，记 卢= m i ni 以 ，卢= m a , x 批j 则由定理2 得到的p s d 迭代法收敛的充分必要条件与引 理5 得到的充要条件等价 证明由定理2 知p s d 迭代法收敛的充分必要条件为： 0 下 2 ，l o u 1 + n ( 2 1 0 ) 其中a = 以币j 百瓦丽j 万面西丽 把n = 、i i 百二孑污忑而石二万可西丽代入( 2 1 0 ) 的1 一n 0 ( 2 1 2 ) ( 1 一- 2 ) t 2 + ( 4 芦2 u 一4 2 _ 2 u 2 ) r + 4 0 9 即 或 ， o 1 一“ 所以， 岍 型型竖笔岽塑型，。r 即为引理5 的结果i 特别地，我们需指出在定理2 的条件下，所对应的p s d 迭代法的最优参数及 最优谱半径【8 】为： u 删乩唧t = 寿忡= 蓦 因此，在系数矩阵a 为( 1 , 1 ) 相容次序矩阵且对角元不全为零，其j a c o b i 迭代矩阵 的特征值蜥全为实数且f 脚i 1 的条件下，我们得到了较完整的p s d 迭代法收 敛的充分必要条件以及最优参数的选取 2 3 数值例子 例1 设线性方程组a x = b 的系数矩阵 a l 0 2 010 1 2 0 1 1 0 易知a 为对称正定阵，其j a c o 坼迭代矩阵的特征值分别为 肛。= 一；，卢z = o ，p 。= 互1肛1 = 一互，卢2 = u ，p 3 = 互 因此，定理1 所示的r ，u 的范围为 0 u 2 ，0 丁 2 0 d ( 2 一u ) 2 ( 2 1 3 ) 定理i 所示的r ，u 的范围为 0 - r 2 , 虿3 t - 2 w 2 一； ( 2 “) 易知，由( 2 1 4 ) 所围的收敛区域面积大于( 2 1 3 ) 所围的收敛区域面积，u p ；e 此侵j 中，定理1 所示的p s d 迭代法的收敛范围优于定理1 所示的p s d 迭代法的收敛 范围 例2 设线性方程组a z = b 的系数矩阵 a = 1 1 2 00 1 2 1 1 2 0 0 1 2 1 1 2 001 2 1 此时a 为( 1 ，1 ) 相容次序矩阵，其j a c o b i 迭代矩阵的特征值分别为 旷一学脚：学棚：一学舢= 堂8肛1 2 一v 丁，p 2 2v 丁，p 3 2 1 丁p 4 2v 因此矿= 学，- 2 = 学，所以，p s d 迭代法收敛的充要条件为 0 下 2 ，1 一妒 u 14 - 庐 此处妒= 俨旱萨 当l u 取不同值时，我们得到下表 表3 u p 1 4 3o 40 8 8 6 4 9 1 4 1 7 7 1 4 3l 0 5 0 5 9 4 7 1 5 0 9 1 4 31 40 6 4 4 0 8 4 6 9 8 6 1 4 50 50 7 8 0 1 7 4 4 1 6 7 1 4 50 90 5 0 3 9 7 1 9 4 3 2 1 4 5 1 0 4 9 9 0 3 7 3 2 0 8 1 4 51 30 5 7 5 2 4 3 6 3 3 0 1 4 7o 40 9 3 9 2 6 0 4 0 8 0 l _ 4 70 8 0 5 2 7 6 5 1 5 3 0 3 1 4 7 1 0 4 9 2 1 2 7 4 9 0 8 1 _ 4 71 2 0 5 2 7 6 5 1 5 3 0 3 1 4 80 50 8 1 7 0 0 5 6 1 2 1 1 4 80 90 4 9 4 7 2 3 4 4 3 8 1 - 4 8 1 0 4 8 8 6 7 2 5 7 5 7 1 4 81 1 0 4 9 4 7 2 3 4 4 3 8 1 - 4 81 50 8 1 7 0 0 5 6 1 2 1 1 4 9o 40 9 6 5 6 4 4 9 0 3 6 1 - 4 91 0 4 9 0 0 0 0 0 0 0 0 1 4 91 40 7 1 3 0 6 7 2 7 3 5 l _ 5 00 5 0 8 4 1 5 5 9 7 4 1 4 1 5 010 5 0 0 0 0 0 0 0 0 0 1 5 01 30 6 2 9 5 6 2 3 7 8 7 1 6 01 0 6 0 0 0 0 0 0 0 0 0 1 9 010 9 0 0 0 0 0 0 0 0 0 从上表中我们很容易看到，当r 的值越靠近1 4 8 ，u 的值越靠近1 时，对应的谱 半径越靠近0 4 8 8 6 7 2 5 7 5 7 ，特别地，取文献【8 】中的) t = 1 ，嘞f 2 专竽1 - 4 8 6 4 时，得到p o p = 坠学0 4 8 6 4 1 2 第三章j a c o b i 特征值为纯虚数或零时p s d 迭代法的收敛性 在本章中，我们将在线性方程组a x = b 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵 及a 的j a c o b i 迭代矩阵的特征值均为零或纯虚数的条件下，来讨论p s d 迭代法 的收敛性及最优参数的选取 3 1 一些引理及预备知识 引理1 【。l 设方程组( 1 1 ) 的系数矩阵a 为( 1 ，1 ) 相容次序矩阵，则其s s o r 迭 代矩阵的特征值蜥与j a c o b i 迭代矩阵b 的特征值蜥有如下关系： 【一( 1 一u ) 2 】2 = ( 2 一，) 2 u 2 蜥2 ，j = 1 ，2 ，n 引理2 【17 1 若t 为n 阶迭代矩阵，其特征值巧的实部为q ，虚部为，即 = x j + i y j ，j = 1 ，2 ，n ，又设g = ( 1 一卢) j + 卢t 为t 外插迭代矩阵，卢为实参 数，则存在卢使g 收敛的充要条件为 i ( v j ) 引理3 在引理2 的条件下，若x j i ( v j ) ，则g 收敛的充要条件为： 0 卢 l ( v j ) 则g 收敛的充要条件为t ? 2 ( 1 巧) ( 1 一勺) 2 + 谚 ) 卢 0 求解大型稀疏线性方程组 a x = b ( 3 1 ) 对应的p s d 迭代法的迭代矩阵 s 下w = 工一丁( f u 【，) 一1 ( 工一u l ) 一1 d 一1 a 其中l = d _ 1 a ，u = d - 1 g ，f ，【) 为迭代参数且r 0 对应的s s o r 迭代法的迭代矩阵 灿= ( j w l ) ( 1 一u 矿) 】一1 【( 1 一w ) i + u 捌【( 1 一u ) j + u u 】 1 3 不难推出，p s d 迭代法的迭代矩阵和s s o r 迭代法的迭代矩阵有如下关系： 母，u = 卢帆一+ ( 1 8 ) i 其中卢= 南，于是p s d 迭代法的迭代矩阵s ，u 的特征值 与s s o r 迭代法的 迭代矩阵的特征值 对应有： a = 卢u + ( 1 一卢)( 3 2 ) 在本章中，除非特别声明，否则总假定线性方程组( 3 1 ) 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵，其j a c o b i 矩阵的特征值脚均为纯虚数或零：协i = ，o t = 乎q ，西5 甲q ，。2 呼“ 0 j l q o ) ，j = 1 ，2 ，“ 3 2 主要定理及证明 定理1 若方程组( 3 1 ) 的系数矩阵a 为( 1 , 1 ) 相容次序矩阵且对角元全不零， 其j a c o b i 迭代矩阵的特征值均为纯虚数或零，当且仅当r ，u 满足下列条件时，p s d 迭代法收敛 ( a ) o t 0 ( i 万雹s u s 石蓑乇，o 订 溉u 1 ( i i 丽辛嘉石j 茎u 磊万南 或雨再等面“万霸嘶2 ，0 一削m i n 。w ( 2 - ( i i i 徊二而笔丽瓤茎二万杀，嬲u 3 ) r o ( i v ) 若西a2 瓜a 2 22 百万覆； 面 “s f 7 弄蒜 或f 万斋丽墨u 雨再- 而2 法i n o h , x u ；2 ) r o ( b ) c t = 西= 0 ，0 r 2 ，c ，任取 ( c ) c 壁= o 且o 西，l u 的取值范围为( 口) 中的( i ) 和( i i ) 1 4 其中：型型虹辱乒圃，u ；2 ) ：掣铲， 拶) ：堡坐型蔓土压孽雾翌至婴，r 和如分别是根号下为非负和负的下标 j 的集合 证明由s s o r 迭代矩阵的特征值q 与其j a c o b i 的特征值脚满足引理i 的 关系式以及心为零或纯虚数得： 【q 一( 1 一u ) 2 2 = 一( 2 一) 2c 1 2 司，j = l ，2 ，一，n ( 3 3 ) 令( 3 3 ) 中的u ( 2 一u ) = 0 ，于是有 田+ p 2 司一2 ( 1 一口) 】+ ( 1 一日) 2 = 0 ( 3 4 ) 令( 3 4 ) 中的q = q + 锄于是有 ，司一谚+ p 2 鸳一2 ( i 一日) b + ( 1 一日) 2 = o ( 3 5 ) i2 z j y j + p 2 畸一2 ( 1 一口) 】盼= 0 ( 3 6 ) 由( 3 6 ) 得协：0 或q = 2 0 - 0 2 ) - o , 下面分两种情况来讨论 ( i ) 蜥= 0 此时由( 3 5 ) 知 司+ p 2 田一2 ( 1 一日) 唧+ ( 1 一日) 2 = 0 ( 3 7 ) 因为巧全是实数，所以( 3 7 ) 的判别式0 4 4 4 ( 1 一o ) 0 2 碍0 ，并记地= j 1 0 4 碍一 4 ( 1 一日) 口2 嵋o ) ( a ) 壁0 当0 = 0 时，由( 2 ，1 ) 知0 r i 冬；当0 0 时由0 4 a j 一4 ( 1 一o ) 0 2 丐2 0 得到 0 百卉霜或0 茎而暑酉此时由( 3 7 ) 得： 1 = 【2 ( 1 一p ) 一口2 叶2 一痧虿i f 丽葡2 = 【2 ( 1 一p ) 一目2 ，2 + 0 4 - 4 ( 1 - 0 ) 0 2 哼1 2 根据引理2 p ( 鼻，。) 1 甘毋 1 1 5 又因为弓1 0 ，所以当口三赤或口志时p ( 鼻，) 1 营乎 1 即： o a j 0 2 a ；- 4 ( 1 - o ) 0 ，日4 碍一4 ( 1 一口) 口2 2 一【2 ( 1 一口) - 0 2 弓】) 2 由( 3 9 ) 和( 3 ，1 0 ) 知：当p 再击再或日丽彘时恒有拶 1 根据引理3 和r = 阳于是有 ( i ) 酆志时，。 一刖m a 。n 。 ( 3 9 ) ( 3 1 0 ) ( i i 脚赤毛帅j e n 。a 坐啦墨型 ， 0 ) ( i i ) 当8 了艿焉麦j 时，m “ i r 己虿二二2 r 0 ) ( b ) 立= 石= 0 ，此时j a c o b i 的特征值全为零，由( 2 1 ) 得p ( 晶。) 1 0 r 2 ( c ) 垒= 0 ，且垡西，此时对于j a c o b i 的特征值卢l ，弘2 ，卢。可设 ( i c ) 胁= 0 ，1si m 此时可按( 1 ) 中的( b ) 来分析； ( i i c ) m 0 ，m n 此时可按( 1 ) 中的( a ) 来分析 ( 2 ) q = 2 ( 1 一日) 一日2 a ； 2 记i n = j 1 0 4 碍一4 ( 1 一p ) 口2 畸 0