（计算数学专业论文）一类非对称矩阵半迭代法的研究.pdf

一类非对称矩阵半迭代法的研究 曹晓春 摘要大型线性方程组的求解是大规模科学与工程计算的核心随着生产实 践的发展，迭代法已取代直接解法成为求解大型线性方程组的最重要的一类方法 半迭代法是迭代法的一种，与一般迭代法相比，半迭代法不仅可以提高线性方程组 的收敛速度，而且可以使一些对原方程发散的迭代法收敛自v 堍a1 9 5 7 年提出 半迭代法以来，许多学者都对此作了研究( 见 1 】- 【1 6 】) 本文主要是讨论一类非对称 矩阵半迭代法收敛性的问题 y o u n g 在文献【17 】中，给出了线性方程组a z = 6 的迭代矩阵为对称阵( 此时 迭代矩阵特征值为实数) 时，半迭代法的收敛性在本文第二章，按照y o u n g 的方 法，利用c h e b y s h e v 多项式及其基本性质，讨论了线性方程组a z = 6 的迭代矩阵 为反对称阵( 此时迭代矩阵特征值为纯虚数或零) 时，半迭代法的收敛性，从而扩大 了【l7 】中半迭代法的适用范围，并且在2 3 中，用实例说明了对某些矩阵而言，我 们得到的结果要广于【17 1 e i e 珊a n n 和v a r g a 在文献【1 8 】中，讨论了线性方程组血= 6 系数矩阵的 j a c o b i 矩阵b 是弱循环指数为2 的相容次序矩阵，在b 2 的特征值为非负实数， 满足 盯( b 2 ) c 【o ，卢2 】p ：= p ( b ) 1 的条件下，把半迭代法应用于s o r 方法在本文第三章，我们利用f 1 8 】中相似的 方法，在j a c o b i 矩阵b 是弱循环指数为2 的相容次序矩阵的前提下，从s s o r 迭 代法的特征值a 与其j 舵o b i 迭代矩阵b 的特征值p 的关系式 协一( 1 一u ) 2 】2 = a ( 2 一u ) 2 u 2 p 2 出发，当矩阵b 2 的特征值满足 仃( b 2 ) c 【o ，卢2 】o 卢：= p ( b ) 1 ( 就是所谓的非负情形) 时，研究半迭代s s o r 方法定理3 3 1 得到结论；应用于 半迭代的s s o r 方法加速了取得最优参数u = 的s s o r 方法此外，有一个有 意义的结论【见定理3 4 1 】，若知道盯( 口2 ) 谱半径有形式 盯( b 2 ) c 【o ，7 2 】u 卢2 )o 7 ：= m a x l p i ：p 盯( b ) ，i p i 卢) ， 使用一个次优松弛因子 ，则可以得到一个更小的渐近收敛因子这是用半 迭代法加速s s o r 方法时，得到的另个较好的结果 在j a c o b i 矩阵b 是弱循环指数为2 的相容次序矩阵的前提下，当 盯( b 2 ) c 【一口2 ，o 】o 口：= p ( b ) ( 就是所谓的非正情形) 时，第四章研究了半迭代s s o r 方法，得到与第三章一致的 结论 关键词：半迭代法； c h e b y s h e v 多项式；s s o r 迭代法； 相容次序矩阵； 渐近收敛因子 i i s t u d yo ft h es e m i - i t e r a t i v em e t h o df o r ac l a s so fn o n s y m m e t r i cma i r r i x c a ox i a 秘c h u n a b s t r a c th o wt os o l v et h el a r g el i i l e a re q u a t i o 船i 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 百n e e r i n gp r o j e c tc o m p u t a t i o n w i t ht h ed e v e l o p m e n to ft h ep r a c t i c e ，d i f e “m 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 d h a sb e c o m eo n ek i n do f t h ei m p o i t a m tm e t h o d sf o rs o l 、，i n gl a r g el i n e a re q u a t i o n s s e m i i t e r a t i o ni so n eo ft h ei t e r a t i v em e t h o d s c o m p a r e dw i t ht h eu s u a lm e t h o d s ，s e m i i t e r a t i v em e t h o dn o to n l yc a ni m p r o v et h ec o n v e r g e n c er a t eo ft h el i n e a re q u 舢 t i o n s b u ta l s oc o n v e r g ef 研t h eo r i g i n a le q u a t i o 璐w h i c hm a yb ed i v e r g e n c e n o m 1 9 5 7 ，t h et e 眦。s e m i i t e r a t i v em e t h o d 8 ”w 硒6 r s tu s e db yv a r g a ，m a n ya u t h o r s h a v e8 t u d i e di t ( s e e 【l 】- 1 6 1 ) i nt h i sp a p e r ，w ed i s s c u 辎m a i n l yw i t ht h ec o n v e r g e n c eo f t h e 鼬m i ，i t e r a t i v em e t h o df o rac l a 器o fn o n s y m m e t r i cm a t 血 i 【1 7 】，o h ec 0 v e r g e n c eo ft h es e m o i t e r a t - v em e t h o df o ro h el i n e a re q u a t 如璐 a z = 厶w 嬲锄a l y z e du n d e rt h ea 辎u m p t i o n st h a tt h ei t e r a t i v em a t r i ) 【i ss y m m e t r i c m a t r i x ( i t se i g e n v a l u 睇a 聃r e a l s ) i nc h a p t e r2 ，f o l l o w i n gt h e s i m i l a rm e t h o da n d 璐i n g c h e b y s h e vp o l y n o m i a la n di t sp r o p e l t i e s ，w es t u d yt h ec o n v 盯g e n c eo ft h es 哪i i t e r a t i v em e t h o df o rt h el i n e a re q u a t i o 璐w h e nt h ei t e r a t i v em a t r 波i sa n t i s y m m e t r i c m a t r i x ( i t se i g e n v a l u 嚣a r ei m a 百n a t y o rz e r o ) t h u s ，w e 睬t e n dt h eu s u a lc o n v e r g e n c e c o n d i t i o nt oan e ws i t u a t i o n i n 2 3 ，e x 锄p l 傍a 陀舀v e nf o ri l l u s t r a t et h ee f r e c ta n d p f a e t i c a b i l i t yo fo u rn e wr 船u l t s i n 【1 8 】，t h ea p p i i c a t i o o f o p t i m a ls e m i i t e r a t i o nt ot h e s t a n d a r ds u c c e s s i v ea v e r r e l a x a t 硒n ( s o r ) i t e r a t i v em e t h o d ，w i t ha n yr e 柏r e l a x a t i o nf 抽t o ru ，w 撼a n a l y z e d u n d e rt h ea 鹃u m p t i o n st h a tt h ea s s o c i a t e dj a c o b im a t r i 】【bi sc o n s i s t e n t l yo r d e r e d a n dw e a k l yc y c l i co fi n d e x2 柚dt h a tt h es p e c t r i l m ，盯( b 2 ) ，o fb 2 s a t i s 矗够 盯( b 2 ) c 【o ，卢2 】w i t ho 卢：= p ( 口) 1 i nc h a p t e r3 ，w ee x t e n dt h er e s u l t s 【1 8 】，u s i n ga n a l o g o u sa s s u m p t j o n sa n dt e 出 n i q u e s ，s t a r t i n gt h ef u n c t i o n a lr e i a t i o 璐h i p 协一( 1 一“，) 2 】2 = a ( 2 一u ) 2 u 2 矿 t oa n a l y z et h ea p p i i c a t i o no fs s o ri t e r a t i 、 em e t h o du n d e rt h ea s s i m p t i o n st h a tt h e 舾s o c i a t e dj a c o b im a t r i xbi sc o n s i s t e n t l yo r d e r e da n dw e a k l yc y c l i ci i n d e x2a n d i i i t h a tt h es p e c t r u m ，盯( 上产) ，o f 置2 s a t i 右鹄 盯( b 2 ) c 【o ，卢2 】w i t ho 卢：；p ( b ) 1 f t h i si st h es 0 - c a l l e d 。n o n n e g a t i v ec a s e ”) s s o r - s im e t h o di ss t u d i e d i ti ss h o w n i nt h e o r e m3 3 1t h a tt h e r ei ss e m i i t e r a t i v em e t h o da p p l i e dt ot h es s o rm e t h o d w i t ho p t i m a lr e l a x a t i o np a r a m e t e ru = b m o r e o v e r ，w eo b t a i na ni n t e r e s t e dr e s u l t 【s e et h e o r e m3 4 1 】：as m a l l e ra s y m p t o t i cc o n v e r g e n c ef 抽t o r c a nb ea c h i e v e db yu s i n g as e m i i t e r a t i v em e t h o dt o g e t h e f 、】l r i t has u b o p t i m a lr e l a ) 【a t i o nf a c t o r ( 屿) w h e n m o r ep r o f o u n di n f o m a t i o no n 盯( b 2 ) ，o ft h ef o m 盯( b 2 ) c 【o ，一y 2 】u 卢2 ) w i t ho ，y ：= m a x l p i ：p 一( b ) ，i p i 卢) i sa th a n d u n d e rt h e 勰s u m p t i o n st h a tt h ea s s o c i a t e dj a c o b im a t r i xbi sc o s i s t e n t l y o r d e r e da n dw e a k l yc y c l i ci ni n d e x2a n dt h a tt h e 印e c t r u m ，( b 2 ) ，o fb 2 s a t i l i e s 盯( b 2 ) c 【一n 2 ，o 】 w i t ho 8 ：= p ( b ) ( t h i si st h es o c a l l e d。n o n p o s i t i v ec a s e ) i nc h a p t e r4 ，t h e 靶m i i t e r a t i v es s o r m e t h o di ss t u d i e da n dt h er 鄂u l ti st h es a m ea st h e o r e m3 3 1 k e yw o r d s ：s e 如0 i t e r a t o v ei n e t h o d ；c h e b y s h e vp o l y n o m i a l ；s s o r i t e r a t i v e m e t h o d ；c o n s i s t e n t l yo r d e r e dm a t r i x ；a s y m p t o t i cc o n v e r g e n c ef h c t o r i v 主要符号表 复数域 实数域 自然数 n n 阶实矩阵的全体 矩阵a 的逆 n 维向量 误差向量 向量z 的转置 求和符号 矩阵a 的谱半径 矩阵a 的谱 m 次c h e y b y s h e v 多项式 次数不超过m 的复多项式的集合 取最大值 取最小值 上确界 下确界 求极限 向量( 矩阵) 的无穷范数 非奇异的对角块矩阵 严格下三角矩阵 严格上三角矩阵 覆盖域 渐近收敛因子 原点为圆心，半径为l 的圆周 g r耋=一啡，删删驯一盎 唧时二垦。毛坩c：哪 西 u o 共形映射 最优松弛因子 次优松弛因子 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果尽我所知，除文中已经注明引用的内容外，论文中不 包含其他个人已经发表或撰写过的研究成果，也不包含为获得陕西师范 大学或其他教育机构的学位或证书而使用过的材料对本文的研究做出 重要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：翌吼盘日期：趔生竺旦 学位论文使用授权声明 本人同意在校攻读学位期间论文工作的知识产权单位属陕西师范大 学本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍 为陕西师范大学。学校有权保留学位论文并向国家主管部门或其他指定 机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少 量复制并允许论文进入学校图书馆，院系资料室被查阅；有权将学位论 文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编 出版 作者签名：重堕盘日期：趔筮竺旦 第一章绪论 1 1半迭代法的发展背景 大型线性方程组的求解是大规模科学与工程计算的核心随着计算机存贮的 日益增大和计算速度的迅速提高，使得求解线性方程组的直接法如高斯消去法等在 计算机上可以用来解决大规模线性方程组，并且由于处理稀疏矩阵存贮和计算技术 的飞速发展，加之直接方法理论的日臻完善，都进一步断定了直接方法的巨大实用 价值和可靠性 但是对许多数学问题，不能通过解析方法或有限次的算术运算求得其精确解， 只能通过对解的一次次估计，逐步求得其精确解，这类方法称为迭代法迭代法具 有程序设计简单，适于自动计算，还可以充分利用系数矩阵的稀疏性减少存贮，加 之一个好的迭代法常可用较直接法更少的计算量而得到满意的解因此，迭代法亦 是求解线性方程组，尤其是求解具有大型稀疏系数矩阵的线性方程组的重要方法之 一 设a j 护“为非奇异矩阵，6 舻，则线性方程组 l z = 6 有唯一解z = a 一1 6 现将矩阵a 分裂为矩阵m 与的差； a = m n 其中m 为非奇异矩阵，于是方程( 1 1 1 ) 可以表为 m z = n z + b 即 z = m 一1 z + m 一1 6 若记 g = m 一1 n f = m h 则方程( 1 1 1 ) 可以写为等价形式： z = g z + ( 1 1 4 ) d 动 砷 1 1 1 0 0 0 据此，便可以写出单步定常线性迭代格式： z ( + 1 ) = g z ( ) + ，( = o ，l ) ( 1 1 5 ) 其中称矩阵g 为迭代矩阵，之所以称其为单步是指计算茹( 1 ) 时仅用到z ( 舢定常 是指g 和，均与七无关，线性是指g z + ，为z 的线性映射 对于任意给定的迭代初值z ( m ，则由( 1 1 5 ) 式便可以生成一向量序列 z ( ) ， 我们的目的是求方程组( 1 1 1 ) 的解，因此我们希望 l i mz ( ) = z 膏 为此，引入下述定义t 定义1 1 1 【圳若存在矿舒，使得对任意的近似向量一彤，由迭代格式 ( 1 1 5 ) 产生的序列 ( ) ) 都收敛到矿( 七一o o ) ，即 l i m $ ( t ) = z + 女叶 则称迭代格式( 1 1 5 ) 是收敛的，否则称之为发散的 由此看来，用迭代法解线性方程组( 1 1 1 ) ，需解决如下三个问题： ( 1 ) 迭代格式的构造； ( 2 ) 迭代格式的判敛； ( 3 ) 迭代格式的收敛速度估计 当( 1 1 2 ) 式中的分裂彤，取不同矩阵时，可以得到不同的迭代格式不失 一般性，我们对( 1 1 1 ) 式的系数矩阵a 分解为 a = i l 。一it 其中，一厶一u 分别为a 的严格下和上三角矩阵下面通过表格，列举几种常见的 迭代格式 表1 m g方法 ， 工+ uj a c o b i l 2 0 j ，一工 ( j 一工) 一1 u g s 1 2 0 j 一u 正， ( j u l ) 一1 【( 1 一u ) ，+ u u 】 s o r l 2 l j j r 玉 ( ，一r 三) 一1 【( 1 一( ，) j r + ( u r ) + 。移1 a o r l 2 2 j 【j u l ) 【一u u 【( ，一u 工) ( j r u u ) 】一1 【( 1 一u ) j + u 纠【( 1 一u ) j r + u u l s s o r 【2 3 】 u f 2 一u ) 2 上表是我们最常见的几种定常线性迭代格式，有关它们迭代速度的比较详见 2 4 】对于给定的一个线性定常迭代方法，我们经常能找到一个。相关”的非定常 方法使原迭代格式收敛的更快一些，这个。相关”的方法就是我们所知道的半迭代 法( s e m i i t e r a t i v em e t h o d ，简记s i ) ，或c h e b y s h e v 半迭代法或称c h e b y s h e v 加速 方法半迭代法是一种特殊的迭代法，它不能孤立地，单独地使用，它是基于现有 的j a c o b i ，g a u 睁s e i d e l ，s o r ，s s o r ，a o r 等等其它迭代方法的，若半迭代法应用于 j a c o b i 迭代，就记为j - s i ，依次类似地记为g s - s i ，s o r - s i 等等数值实验表明，使 用半迭代法不仅可以提高收敛速度，而且可以使某些对原迭代法发散的迭代格式收 敛可参考【2 4 】 1 2半迭代法的思想和结构 半迭代法是解线性方程组的一个常用且有效的方法，半迭代法的基本思想是求 和下面我们介绍半迭代法的结构，在介绍半迭代法的过程中体会它的求和思想 由( 1 1 5 ) 式的迭代格式 z ( 詹+ 1 ) = g 。( 七) + ，( 七= o ，1 ，) ， 算出若干次迭代值z ( 们，z ( ，后，若 z ( 砷+ 矿， ( 1 2 1 ) 则 萎一矿 ( 1 2 2 ) 而当( 1 2 1 ) 式不收敛时，( 1 2 2 ) 式仍可能收敛更一般地求和方法是，设有一组 常数 a ，口1 0 ，乜1 l ，n ，口2 1 ，0 2 2 ， 满足 y = o 。t z ， ( 1 2 3 ) 则当o 。= ；晶时，y ( m ) 就是( 1 2 2 ) 式，故( 1 2 3 ) 式是( 1 2 2 ) 式的推广当 我们用特定方法【2 5 ，p 1 4 5 】选好参数n 。女，再结合已知道的z ( m ，一”，可按( 1 2 3 ) 式得出y ( ，y ( ，逐步求得方程的精确解 这就是半迭代法的基本思想和结构，有关求y ( ，y ( 2 ) ，还有更简单的方法， 在【2 5 ，p 1 4 6 - 1 4 7 】中给出了一个三项递推关系式， 一k 。警捺伊， 卢一口j m 1 l 引 3 一描一) + 惫器 q z q 其中7 k ( g ) 为自变量z 的m 次c h e b y s h e v 多项式，迭代矩阵g 的特征值满足 o = p 1 卢2 = 卢 1 ，口卢 这样有了z ( m ，z ( ，就有y ( m ，y ( ， y ( o ) ：。( 0 ) y ( 1 ) = 0 1 l z ( 1 ) + 0 1 0 z ( o ) 可按( 1 2 4 ) 式求出y ( 孙，y ( 甜，而不必通过z ( 2 ) ，z ( ，和0 2 2 ，口2 l ，0 2 0 ，等来 算 则因 当迭代矩阵g 的特征值都大于1 时，即 为他的下降函数，故 1 口= p l 舰= 卢，o 卢 砒) = 等芋 只( 胁) p l ( 。) = 石车孑马 1 ， 因此可用只( g ) 代替g 来进行半迭代 当地中有些大于1 ，有些小于1 ，可取 g 1 = g ( 2 j g ) 则g 1 的特征值为 雎( 2 一胁) l ， 故可用g l 代替g 作为基本迭代矩阵，在此基础上进行c h e b y s h e v 半迭代 以上是迭代矩阵g 的特征值均为实数时，半迭代法的基本情况，可详见【2 5 ，p 1 4 2 1 5 2 】 我们需要强调的是胡家赣【2 5 】文中使用半迭代法的前提是( 1 1 5 ) 式中迭代矩 阵的特征值均为实数，若特征值不为实数或不全为实数，则【2 5 】中的结论是不适用 的 4 1 3半迭代法的研究现状 1 9 5 7 年，从v a r g a 第一次使用。半迭代法”这个名称以来，引起了学术界的 广泛重视和关注，获得了迅速发展，至今已形成较为完整的理论体系尤其是它不 仅使已收敛的迭代法加速收敛，而且也能使对原方程组发散的迭代法收敛，这一特 殊的特点，与其他普通迭代法相比，备受学者和计算机程序设计人员的青睐 1 9 6 0 年，f r a n k 【2 6 】研究用半迭代法加速j a c o b i 迭代法，即j s i ，假设的前 提是( 1 1 5 ) 式中的迭代矩阵g 有实特征值，且小于1 数值实验表明，用半迭代 法大大提高了收敛速度，尤其是当系数矩阵a 是相容次序矩阵时，其收敛速度可 与s o r 方法u 取最优参数时的收敛速度相媲美1 9 5 9 年，s h e l d o n 【2 4 】，曾研究 g s _ s i 的收敛性，。对系数矩阵a 分为不同的情况讨论；当系数矩阵a 为正定矩阵 时，有g s 方法收敛如果要用半迭代法加速g s 方法，必须要求其迭代矩阵的特 征值为实数；当系数矩阵a 为s t i e l t j 部矩阵时，一般情况下，虽然g s 迭代法要 比j a c o b i 迭代法收敛的快，但是由于此时迭代矩阵g 可能有复特征值，【2 5 1 中的 结论不适用，所以无法保证g s - s i 方法比j s i 方法收敛的快；当系数矩阵a 为相 容次序正定阵时，如果用谱半径刻画收敛速度，g s s i 方法收敛速度几乎与s o r 方法一样快，是j s i 方法的2 倍s o r - s i 最早是由毗【2 7 】提出来的，得到的结 论是不能提高u 取最优参数时的s o r 方法的收敛速度 第一次系统地研究半迭代法及把其应用于矩阵问题的迭代解，是1 9 8 3 年的n i e t h a m m e r 和v 孤g a 【2 8 ，他们把半迭代法和可求和理论紧密联系起来之后关于这一 主题的文章如1 9 8 5 年的e i e 珊a l l n ，n i e t h a m m e r 和v a r g a l 2 9 】；1 9 8 6 年的g u t k n e c h t ， n i e t h a m m e r 和g a 【1 1 1 ；1 9 8 6 年的e 沁r m a n n ，n i e t h a m m e r 和v a r g a 【3 0 】，则重点把 半迭代法和共形映射理论联系起来1 9 9 3 年e i e 瑚锄n 和、k g a 在f 4 】【1 8 】中用共 形映射理论与复逼近理论更加细致，深刻地刻画了s o r - s i 的收敛性 现在，可以看到，我们正利用多种领域的工具，如复函数理论，复数逼近理论 及尖端的软件包来研究矩阵方程 1 4本文的主要研究工作 本文进一步讨论了一类非对称矩阵半迭代法的收敛性问题，主要有三方面的 工作： 第一，按照y o u n g 在f 17 】中研究线性方程组a z = ，半迭代法的收敛性方 法，利用c h e b y s h e v 多项式及其基本性质，讨论了线性方程组a z = ，的迭代矩阵 为反对称阵时，半迭代法的收敛性，从而扩大了半迭代法的适用范围 5 第二，当线性方程组a z = 6 的j a c o b i 迭代矩阵b 是弱循环指数为2 的相 容次序矩阵，在矩阵b 2 的特征值p 2 均为非负实数且旷 1 ，若r ( z ) = ；器 ( 矗( z ) 是由( 2 1 9 ) 式给出的次数为n 的c h e b y s h e v 多项式) ，则r ( z ) = 1 ，且 罱翁i r ( z ) i2 南 引理2 1 3 【3 2 】对称矩阵的特征值皆为实数，反对称矩阵的特征值是纯虚数或 零 引理2 1 4 【衢1 线性方程组a z = ，的迭代方程z ( 外1 ) = g z ( 田+ 七，s = o ，1 ，2 ， 迭代矩阵g 是对称矩阵，其特征值满足口= p 1 脚如= 卢 1 ，故当m _ o o 时， ( z ) 斗0 。，瓦妨_ 0 因之，罂硒p m ( p ) - o ，从而有 眉翁l q m ( i 肛) i j o ， 更有 m i ( 蚴j - o 另一方面，由2 1 和c h e b y s h e v 多项式的性质知；t k ( z ) 1 ，因此有 峄p m ( 腑岛( p ) = 志 1 ， 故 p ( q m ) = m l q m ( i 胁) lsm p m ( 1 地) 1 ， 从而半迭代法收敛 i i ) 考虑g 的特征值的虚部为负数的情形，对称地设 一1 一卢= 一肛七一p l = 一o o( o 卢) ，( 2 2 2 ) 可参照i ) 的证明，得到半迭代法收敛的结论由i ) ，i i ) 可知，当g 的特征值为纯虚 数，且有偶数个，在( 2 2 1 ) 式和( 2 2 2 ) 式的条件下半迭代法是收敛的 ( 2 ) 同理可讨论当g 的特征值有奇数个时，即有一个。为单特征根，在( 2 2 1 ) 式和( 2 2 2 ) 式的条件下半迭代法是收敛的 ( 3 ) 若口= 卢，即迭代矩阵的特征值均为零，此时收敛性是最好的i 定理2 2 2 在定理2 2 1 的条件下，若特征值的虚部在f - 1 ，1 】上，则半迭代法 收敛 4 证明与定理2 2 1 相同，略去在定理2 2 2 的条件下，原迭代格式是发散的， 使用半迭代法可使其收敛 2 3数值例子 例2 3 1 对于线性方程组a z = ，其中，= ( ；，；，l ，1 ) t ，系数矩阵a 为 坩2 矧) 其中 1 七= ( ：，；，1 ，1 ) r ， 州2 矧) 1 1 迭代矩阵g 的特征值为a 1 ，2 = o ， a 3 ，4 = 士 取初值z ( o ) = ( 1 ，o ，o ，o ) t ，进行j a c o b i 迭代， z ( 1 ) = ( ；，1 ，1 ，1 ) t ，i j e ( 1 ) o = j j z ( 1 ) 一z i i = o 5 0 0 0 ； z 2 ) - ( 1 ，缸1 ) t ，眇l l = 栌) 一矿o = o 2 5 0 0 ； 卫( 3 ) = ( ；，1 ，1 ，1 ) t ，j l e ( 3 l j = j j z ( 3 ) 一z j j = o 1 2 5 0 对迭代格式进行半迭代法迭代，取v ( o ) = z ( 0 1 ， y ( 1 ，= ；z 扣，+ ；z 。，= ( 萼，；，；，；) ，i i 叩n = l i y c - ，一z ：o a a a a ； y ( 2 ) = 去z c + 刍，+ 要z c 2 ，= ( 蔷，篙，墓，嚣) 川俨= i l y c 。，一引i ：。t a s a ； 泸) = 扣，+ 抄，+ 挚，= ( 釜，警，箸，跏垆) i | ：i 咿侧- o m ， 倒2 3 2 对于线性方程组a z = ，其中，= ( o ，2 ，1 ) r ，系数矩阵a 为 a = ；) 方程组的精确解为矿= ( 1 ，1 ，1 ) r ， 方程组a z = ，的j a c o k 迭代格式为z ( 卧1 ) = g z ( 。) + 七0 = o ，1 ，2 ) ， 其中 七= ( o ，2 ，1 ) t ， g = ；) 显然迭代矩阵g 的特征值为a l = 0 ，a 2 3 = 士i 取初值z ( o ) = ( 1 ，o ，o ) r ，进行j a c o b i 迭代，得 g 1 = ( o ，l ，1 ) t ，2 ( 2 ) = ( 1 ，2 ，1 ) r ，z ( 3 ) = ( 2 ，l ，1 ) 丁，。 舱( 1 = 忙2 l i = 心3 i i 一= 1 ，即i f m o ，亦即z ( 掌矿 对迭代格式进行半迭代法迭代，取y ( o ) = z ( m ， 俨) - 抄) + ) - ( 舄；川阿叫l = 胪) 一叫i ：o 5 0 0 0 ； y t 2 ，二；z c 。，+ ；z c l ，+ ；z c 2 ，= ( ；，；，；) ，田c 2 ，j j = o y c 砷一z 刈= o z s 0 0 ； y c 3 ，= ；z c 。，+ j z c l ，+ ；z c 2 ，+ ；z c 砷= ( ；，；，；) ，i i 叩c 3 ，o = l i y c 3 ，一矿o = o ，。s o 注2 3 1 本例中所用的范数均为最大模范数，即叫l 。= 丹努k i ，其中= 1 1 0 ! n ( z l ，现，z 。) r 注2 3 2 文献【1 7 】中的半迭代法只适用于迭代矩阵的特征值为实数的情形，但本 文的迭代法则同样适用迭代矩阵的特征值为纯虚数或零的情形如例2 3 1 ，例2 3 2 注2 3 3 例2 3 1 表明，半迭代法提高了j a c o b i 迭代方法的收敛速度；例2 3 2 表 明半迭代法使对原方程组发散的迭代法收敛实际上，也可以加快j o r ，r f ，g a u 睁 s e i d e l 迭代方法的收敛速度，由于篇幅限制，著者将另文给出 1 3 第三章b 2 特征值为非负情形时s s o r 半迭代法的收敛性 在本章中，我们将在线性方程组a $ = 6 的j a c o b i 迭代矩阵口是弱循环指数 为2 的相容次序矩阵，b 2 的特征值皆为非负实数，且满足 盯( 口2 ) c 【o ，卢2 】卢：= p ( b ) 1 的条件下，研究半迭代法加速s s o r 方法时的渐近收敛因子七( f k j ) 的特点 3 1预备知识 考虑线性方程组 月z = 6 ，a r 。，6 冗( 3 1 1 ) 系数矩阵a 的标准分裂为，a = d 一工一u ，此处d 是非奇异的块对角阵，一l 和一u 分别是a 的严格下和严格上三角矩阵假设相应的块j a c o b i 矩阵 b ：= d 1 ( l + u )( 3 1 2 ) 是弱循环指数为2 的相容次序矩阵，b 2 的特征值为非负实数且都小于1 ，即日2 的 谱满足 。 口( b 2 ) c 【o ，卢2 】卢：= p ( b ) 1 这些假设保证了方程( 3 1 ) 式有唯一的叫唯 下面我们回顾s s o r 迭代方法的经典结果： 互m = 协。互研一 十仁m ( m = 1 ，2 ，) 此处 钆= 【( j r u 三) ( ，一，c ，) 】一1 【( 1 一u ) ，+ u 三1 【( 1 一( ，) j + u u 】， 岛= p 一u ) 一1 ( j 一“，工) 一1 6 ( 3 1 3 ) ( 3 1 4 ) ( 3 1 5 ) 在关于b 和u 的假设下，当且仅当o p ( 帆山) = 卢2 ，o c ， 2 ，u 1 1 5 ( 3 1 6 ) ( 3 1 7 ) 如d a n c i 8 在【3 3 】中所述，当u ( o ，2 ) ，对( 3 1 4 ) 式应用半迭代法。也就是 说，我们考虑向量序列 m = r 。j 巧( m = o ，l ，) ( 3 1 8 ) = 0 此处系数丌m j 是( 复) 常数且满足黑丌m j = 1 ( m = o ，1 ，) 为方便注明，把( 3 1 8 ) 式中的系数丌。j 写成下三角矩阵 p = 罄_ ， 称p 是半迭代法( 3 1 8 ) 式的生成矩阵如果1g 盯( ) ，那么相应的误差向量 f 3 1 ，p 1 3 4 】 m = ( j r 一) - 1 一， 满足 e 。= f k ( ) e o ( m = o ，l ，) ， 此处 p 仇( z ) ：= 丌m j ， j = 0 m 显然，l m ( 1 ) = 1 ( 表示所有次数不超过m 的复多项式的集合) 对给定的p 及1 仁盯( ) ，等式 七( ，p ) = 1 骠磐潞( 错) 1 ”， ( 3 1 9 ) m - 勘士0i j c 0 是刻画误差向量e 。范数的渐近下降速度，它与迭代矩阵的约当标准型的形式有 关，与向量范数的选取无关在理论上，总能找到一个半迭代法，使( ，p ) = 0 ( 比 方说。根据c a y l e y h a m i l t o n 理论，若f m 是的特征多项式的倍数) ，但是这种 方法需要知道迭代矩阵的所有特征值在这里，我们引进仃( 灿) 覆盖域q 的概 念，qcc 是一个紧致集，1gq ，仃( 钆) q 引入覆盖域之后，用下式来刻画误 差向量e 。范数的渐近下降速度， 七( q ，p ) = m a x ( ，p ) ：j ”，n 是任意的自然甄盯( ) q 1 6 用半迭代法可达到的最好( 小) 的收敛因子是q 的渐近收敛因子，定义为 七( q ) = i “七(