（应用数学专业论文）解方程组迭代法的几何理论与方法及工程问题.pdf

新江大学博士学位论文 摘要 ，8 本文从几何的观点出发，建立了线性方程组迭代解法的几何理论，揭示了线性方程 组迭代法的几何实质，明确指出了如j a c o b i 、g a u s s s e i d e l 、s o r 等迭代法的几何本质并 得到了一个有趣的结论：著名的克兰姆( c r a m e ) 法则可以看作是一个迭代法，即线性方程 组的克兰姆法则解可以用迭代法来得到，从而使这些著名方法以崭新的面貌呈现在人们的 面前，也使得我们对解线性方程组的迭代法有了更充分的理解。在此基础上，本文设计出 了解线性方程组的几何方法( 如正投射法、跨步前进法和降维法等) ，并进行了收敛性分析， 给出了收敛性定理。这些方法方便有效，且非常适合并行计算。特别是降维法具有几何 意义明确，计算简单及迭代有有限终止性等特点，数值例子表明它比j a c o b i 、g a u s s s e i d e l 、s o r 及c g 法更有效。本文还从几何出发对如何度量线性方程组的病态程度作了一 定的讨论。在研究线性方程组及其解法的同时，还研究了非线性方程组及其解法，揭示了 n e w t o n 法、割线法等迭代法的几何本质，明确了j a e o b i 矩阵的几何意义，揭开了j a c o b i 矩阵的神秘面纱，对解非线性方程组的迭代法有了更深的认识，也为解非线性方程组的研 究提供了一条新的途径，并设计了仿射n e w t o n 法、调整步氏n e w t o n 法等几何方法。这些 研究思想是由金通? 光教授提出的，本文是在干匝的直接指导下完成的。 i 跆合7 5 程计算问题，在混凝土受高温作用时温度场的计算研究中，本文对非稳态导 i 热微分方程设计了合适的计算方法，使得计算简单、步长选择灵活、应用方便，克服了通 常采用的有限单元法结合差分法所存在的计算繁琐、误差大等缺点，得到的结果与实验数 。 据比较吻合，误差完全满足工程上的要求。r ”。 关键词：方程组、迭代法、几何、工程应用 浙江大学博士学位论文 t h e g e o m e t r i c a lt h e o r y a n di t e r a t i v em e t h o d s f o rs o l v i n ge q u a t i o n sa n da n e n g i n e e r i n gp r o b l e m a b s t r a c t t h i sp a p e ri n v e s t i g a t e st h ei t e r a t i v em e t h o d sf o rs o l v i n ge q u a t i o n sf r o m t h e p o i n to fg e o m e t r i c a lv i e w t h eg e o m e t r i c a l t h e o r yo fi t e r a t i v em e t h o d sa n dt h e g e o m e t r i c a l e s s e n c eo ft h ei t e r a t i v em e t h o d sf o r s o l v i n g1 i n e a rs y s t e m sa r e p r e s e n t e d t h eg e o m e t r i c a le s s e n c eo fj a c o b i ，g a u s s s e i d e l ，s o ri t e r a t i v em e t h o d s a n dc r a m e r sr u l ea r ed e s c r i b e d ，b a s eo n i t ，t h eg e o m e t r i c a l m e t h o d s ( u p r i g h t r e f l e c t i o nm e t h o d l - dm e t h o d sa n dr e f l u c i n gd i m e n s i o nm e t h o d ) f o rs o l v i n gf i n e a r s y s t e m sa r ed e s i g n e d ，t h ec o n v e r g e n c ea n a l y s i si sg i v e n r e d u c i n gd i m e n s i o nm e t h o d h a sp r o p e r t i e ss u c ha sc l e a rg e o m e t r i c a ls i g n i f i c a n c e ，n om a n yc o m p u t a t i o n e t c ，i t i st e r m i n a t e da f t e rf i n i t e s t e p s s o m en u m e r i c a le x a m p l e ss h o wt h a t r e d u c i n g d i m e n s i o nm e t h o di ss u p e r i o rt oj a e o b i ，、g a u s s s e i d e l ，s o bi t e r a t i v em e t h o d sa n dc g m e t h o d i n a d d i t i o n ，t h i sp a p e ri n v e s t i g a t e ss o m ei t e r a t i v em e t h o d sf o rs o i v i n g n o n li n e a re q u a t i o n s ，d e s c r i b e st h eg e o m e t r i c a le s s e n c eo fn e w t o ni t e r a t i v e m e t h o d c u t t i n gp l a n em e t h o de t c ，a n dp o i n t so u tt h eg e o m e t r i cs i g n f i c a n c eo ft h ej a c o b i m s t r i x i ta d v a e e sa nn e ww a yt o i n v e s t i g a t et h em e t h o d sf o rs o l v i n gn o n l i n e a r e q u a t i o n s n e wi t e r a t i v em e t h o d sa r ed e s i g n e df r o mg e o m e t r y t h eg e o m e t r i c a lt h e o r ya n dm e t h o d sf o r s o l v i n gi i n e a rs y s t e m sc a nb ee x t e n s i v e l v a p p l i e di nt h e 。c i v i le n g i n e e r i n g i na p p l i c a t i o nt oc o m p u t i n gr e s e a r c ho fc o n c r e t e t e m p e r a t u r ef i e l ds u b j e c t e dt oe l e v a t e dt e m p e r a t u r ei nt h i sp a p e r ，a na p p r o p r i a t e c a l c u l a t i n gm e t h o dh a sb e e nc o n s i d e r e df o rt h en o n s t a t i o n a r yt h e r m a lc o n d u e t i o n e q u a t i o n ，a sar e s u l t ，t h i sm e t h o dh a sm a n ya d v a n t a g e s ，s u c ha s s i m p l i f y i n gt h e c a l c u l a t i o np r o c e s s ，f l e x i b l es e l e c t i o no ft i m es t e p ，b e i n gc o n v e n i e n tt od r a wu d t h ep r o g r a ma n ds oo n b e s i d e s ，s o m e s h o r t c o m i n g s ，f o re x a m p l e ，c o m p l i c a t e da n a l y s i s s t e p sa n du n a s s u r e de r r o r ，w h i c he x is ti nt h ef i n i t ee l e m e n ti nc o m b i n a t i o nw i t h f i n i t ed e f f e r e n c em e t h o d ，c a nh eo v e r c o m e ，t h ec a l c u l a t i n gr e s u l t sc o i n c i d ew i t h t h ee x p e r i m e n t a ld a t aq u i t ew e l l ，a n dt h ee r r o ro b t a i n e db ym e a n so fo u rm e t h o dm a y s a t is f yt h er e q u i r e m e n to fe n g i n e e r i n gd e s i g n k e yw o r d ：e q u a t i o n s ，i t e r a t i v em e t h o d s ，g e o m e t r y ，e n g i n e e r i n ga p p li c a t i o n 浙江大学博士学位论文 第一章绪论 1引言 对于线性方程组a x = b ( 其中a r 为非奇矩阵，x r ”为未知向量，b r ”为 已知向量) ，求解的方法一般可分为三类： ( i ) 直接法 ( 2 ) 迭代法 ( 3 ) 其他方法( 如共轭梯度法) 实践中如何选择计算方法是个比较复杂的问题，需要考虑的因素比较多，如方程组性 质( 系数矩阵的性质) 、方程组的阶数、运算的速度和稳定性以及结果的精度要求等等。但 一般来说，对于中等阶数的线性方程组，直接法有其优越性，如高斯消去法、柯朗消去法、 高斯约当消去法以及选主元消去法等【4 ”，它们的运算步骤一定，运算次数有限，解的精 度也较高。对于大型稀疏矩阵，如用有限差分或有限元法求偏微分方程数值解时常常出现 的这种方程组，其未知数的个数可以有几百个直到几百万个之多，如果用直接法求解，则 需要过多的存贮空间和算术运算量，所以是效率不高的或有时是不可能的，而象共轭梯度 法等其他方法，对方程组系数矩阵的限制比较大( 如要求系数矩阵对称正定等) ，故迭代法 是解大型稀疏矩阵线性代数方程组的最佳选择。迭代法具有存贮省、编写程序易、算法选 择灵活和适用性广等特点。本文首先将对解线性方程组的迭代法作一个系统全面的论述， 然后阐述迭代法的几何实质，建立迭代法的几何理论，从而提出新的算法。 迭代法的提出可以追溯到g a u s s ( 1 8 2 3 ) 。它最基本的一般形式是将线性代数方程组的 系数矩阵4 进行分裂 a = m n ( 其中m ，n r “”且 彳容易求逆) 将线性方程组a x = b 转化为m x = n x + b 从而得到迭代公式 x “= m 一1 n x 。+ m 1 b ( 1 1 1 ) 若记g ：m n ，i = m b ，则上式可写成 x “= + 百 ( 1 1 2 ) 这类方法称为一阶线性定常法，也称为基本迭代法，其中g 称为迭代矩阵，i 为已知 向量。 对彳进行不同的分裂，即选择不同的 彳或某些变形，就得到不同的迭代法。属于以 上基本迭代法的有著名的r f ( r i c h a r d s o n ) 法、j a c o b i 法、g a u s s s e i d e l 法、逐次超松驰( s o r ) 法以及对称逐次超松驰( s s o r ) 法等，这些迭代法对解线性方程组提供了极大的便利，其 收敛的充分必要条件是迭代矩阵的谱半径小于l ，即p ( g ) 1 。但这条件且较难判断。当 然，对于一些特殊的矩阵，可以找出使p ( g ) 1 成立的容易判断的充分条件。例如j a c o b i 法，若a 为具有性质a 的对称正定阵，或者是不可约且弱对角占优，则p ( g ) l 成立。 1 塑堡查兰竖圭兰垡堕苎 文 8 一 1 7 对j a c o b i 法，g a u s s s e i d e l 法等基本方法的收敛性进行了较仔细的研究，得到了 一些收敛的必要条件和充分条件。提出了有关收敛性判别准则，促进了这些方法的应用。 但是总的来说，以上这些基本迭代法的收敛性受到很大的限制，特别对大型矩阵，即使收 敛收敛速度往往是较慢的，这样在实际应用中就会遇到困难。 m o k a r i b o l h a s s a n 和t r i c k l 9 8 5 年提出了一种新的迭代法l lj ，它是将最多n 1 个初等行 变换矩阵作用于a x = b 两边得到a x = b ，使得a 的上余对角元素全为零。然后再对 a x = b 进行一般的迭代法求解，如j a c o b i 法，g a u s s s e i d e l 法等，这样能加快收敛速度。 许多人还研究了各种各样的方法来加速迭代法的收敛，特别，m i l a s z e w i c z ”1 提出，如果初 始迭代矩阵t 是非负的和不可约的，则对t 的选定列进行g a u s s 消去法使其为0 。这将改 善迭代的收敛性。而a n a n d ad g u n a w a r d e n a , s k j a i n 和l a r r y s n y d e r l 9 9 1 年在 1 】的基 础上提出的修正迭代法”1 ，对爿为非奇m 阵或奇异三对角m 阵的迭代法收敛速度有很大 的改善。另外，对其他某些矩阵，这个方法比别的修正迭代法优越。特别，当标准( 非修 正) 迭代法发散时，它却可以收敛且速度相当快，这大大拓宽了标准迭代法的适用范围。 1 9 7 8 年，a h a d l i d i m o s 提出了快速松驰法( a o r ) “，是对s o r 法的推广( 具有二 个参数) ，使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 在1 9 8 3 年将基本迭代法进行了推广”1 ，而提出的广义基本迭代法使得 j a c o b i 法，g a u s s s e i d e l 法和s o r 法以及它们的外推方法皆为其特例。这个迭代法除了具 有四个自由参数使得算法非常灵活外，它的另外一个主要特点是即使爿的某些对角元素为 0 ，它还是可以进行下去。在 6 中对其中的广义快速松驰法( g a o r ) 进行了收敛性分析， 特别是当a 为对称正定阵时得到了一些新的收敛性理论结果。1 9 9 0 年，刘兴平研究了广义 预条件迭代方法”，定义了四个参量的迭代法，称之为g p s d ( g e n e f a l j z e dp r e c o n d i t i o n s i m u l t a n e o u sd i s p l a c e m e n 0 法。当选取不同的参量，可得到法j a c o b i 法( j ) ，外推j a c o b i 法 ( j o r ) 、对称法g a u s s s e i d e l 法( s g s ) 、预条件j a c o b i 法( p j ) 、s s o r 法以及预条件同 时置换法( p s d ) 等。而且，当爿的对角元素至少有一个为零时，通常p s d 方法和j o r ， j ，s g s ，p j ，s s o r 以及它们的外推方法是不能求解的。但是，g p s d 和相应的g j o r ，g j ， g s g s ，g s s o r ，g p j 以及它们的外推方法计算是可以进行下去的。同时文中还讨论了g p s d 和相应的上述方法的收敛性以及最优参数的选取，并举例说明了g p s d 方法比p s d 方法好。 m m m a r t i n s 于1 9 8 6 年提出了解线性方程组的m s o r ( 修正超松驰) 方法”，当系 数矩阵彳具有性质a 时得到了迭代矩阵谱半径的界，当爿为严格对角占优时得到了m s o r 法收敛条件，并推广到4 为h 阵，l 阵，m 阵及s 阵的情形。同时当4 为块h 阵时，得 到了m s o r 法的收敛条件。其实这m s o r 方法是 1 9 中g a o r 方法的特例。在 2 0 】中讨论 了g s a o r 方法，收敛性条件只含j a c o b i 迭代矩阵的谱半径，不含方程组系数，并建立了 g a o r 或g s a o r 收敛和方程组系数矩阵4 为h 阵的等价性。【1 9 】在【2 0 】的基础上进一步 2 浙江大学博士学位论文 讨论了a 为可约的情况，并得出一些迭代矩阵的谱半径的上界。推广了 2 0 和 2 1 的结果。 而【2 2 又推广了【1 8 的结果。 另外，对一些特殊的系数矩阵彳，人们提出了各种各样的算法，如当爿为大型稀疏矩 阵( m 阵，l 阵等) 的不完全因子分解注及其预处理方法1 2 3 1 q 圳，解非对称线性方程组的 混合迭代法【3 忡q 等等。 从七十年代以来，随着计算机的不断发展，并行机的出现使得人们越来越重视并行计 算的研究，迭代法的并行计算方法当然成为广大科技工作者研究的热点之一。从而也相应 地产生了许多并行迭代算法 4 9 7 卜【4 6 1 。这为解大型，特别是超大型的线性方程组提供了 有效的方法，为生物工程，能源工程等领域的研究提供了有力的工具。而且，随着计算机 的高速发展，并行计算方法的研究将越来越受到重视，并行计算方法有望在科学研究中发 挥更大的作用。 纵观解线性方程组的迭代法的研究过程，人们皆是从代数的方法去考虑，提出算法， 证明其收敛性等，而极少涉及其几何实质。没有从几何的观点去研究迭代法。而几何特性 是最本质的东西。譬如，在线性方程中，每一个方程相当于一张超平面，胛个方程就代表 - 张超平面，它们相互的位置关系是固定不变的，即解是与方程的次序无关的。但对某一 种迭代法而言( 如g a u s s s e i d e l 法) ，它的收敛性是与方程的次序有关的。同一方程组，不 同的次序有可能导致算法的收敛或发散。同时，玎张超平面的位置关系也确定了线性方程 组的性质，即系数矩阵爿的性质( 如是否病态等) 。因此，我们有必要去研究迭代法的几 何特性和线陛方程组的几何实质，从而更好地认识和把握解线性方程组迭代法，设计出具 有较快收敛速度和较好稳定性的理想迭代方法。本文希望能在解线性方程组的理论与方法 中开辟一个新的研究方法，并推广到其他数值方法的研究中去，特别是推广到解非线性方 程组的研究中去。 对非线性方程组刖= 0 ，其中x e r ”，以功= 阢，正，一，工酬。，求解的 方法甚多，有各种迭代法、同伦延拓算法、单纯形算法和区间迭代法等 5 3 4 1 ，在【5 5 中， 系统地介绍了力阶非线性方程组删= 0 的基本理论，完整地分析了该类方程组数值解的 几种主要迭代法。在众多的迭代法中，以著名的n e w t o n 法垆d 最为引人注目，它的最大优 点是平方收敛且是强有力的( 有自校正性) ，但缺点是求j a c o b i 矩阵及其逆矩阵的代价很高， 且对初始点的要求较高，不具有大范围收敛性。另外，当j a c o b i 矩阵奇异或病态时，计算 难以顺利进行。 针对以上问题，许多工作者对n e w t o n 法作了种种改进、修正，得到了些对一般或 某特定型方程比较好的方法，如所谓n e w t o n 型迭代法一常见的有修正n e w t o n 法、n e w t o n 下降法、带参数的n e w t o n 法、n - s o r 法和s o r - n 法等”4 。 对于解非线性方程组迭代法的研究虽有较长的历史但问题远没有完全解决，为此针 浙江大学博士学位论文 对这一老问题，新的思想、方法也不断出现。如对奇异、病态问题， 5 6 】一 6 1 】进行了研究 并提出了一些处理方法和算法。 6 2 、 6 3 较系统地分析了n e w t o n 型方法的点估计。其他 常见的解非线性方程组的方法还有拟牛顿法、b r o w n 法和b r e n t 法等。【6 4 提出了解非线性 方程组的一类方法，使得b r o w n 法、b r e n t 法等为其特例，并与离散牛顿法进行了比较。 另外，还有自适应拟n e w t o n l 修正方法、球形迭代法和对称矩阵分解因子的直接换元修 正法等等 6 5 卜 7 0 】。 过去对方程组及其解法的研究，很少从几何上去考虑，从几何的方法入手去研究理论、 设计算法，因此也不能揭示其真正的几何本质，了解其真正的几何意义。本文第二章、第 三章从几何的观点出发，揭示了线性方程组的几何本质和若干线性方程组解法的几何实质， 建立了解线性方程组的几何理论，从而提出解线性方程组的几何方法。并分析了其收敛性， 用数值例子检验了这些几何方法的优越性和有效性。 本文第四章用几何理论及方法对非线性方程组的迭代解法进行研究，即从解非线性方 程组迭代法的几何实质出发，用几何的观点研究迭代法，揭示迭代法的几何本质，从而设 计出有效的算法。 2 解线性方程组的基本迭代法介绍 在这一节中，我们介绍几种最著名、常用的基本迭代法，也是后几章研究中要涉及到 的基本方法，至于前面提到的其他的方法可见相应的参考文献。这里不作一一介绍。 设胛阶线性方程组为 a x = b 其中a = f ) 。，b - - ：( b , ，6 2 ，色) 7 ，x = ( ，毪，_ ) 7 一、r f 法 r f 法是r i c h a r d s o n 1 9 1 0 方法的一种变型，其定义为 x “1 = g o x 。+ 6( 七= o ，l ，2 ，) ( 1 - 2 n 其中迭代矩阵6 ；= ，一a ( 即将彳分裂为a = i - g ，为单位矩阵，相应于( 1 11 ) 中 m = i ，n = i - a ) 。 r f 法收敛的充要条件是彳的最大特征值小于2 。 二、j a c o b i 法 若将4 分裂为 a = d l u 4 浙江大学博士学位论文 其中。=：1吒2二，三=一主妻墨以二一。i u = 0 a 1 2 o o a 1 3 q ” a 2 3 0 0 a h 一1 ，” 0 即相应于( 1 - i 1 ) 中m = d ，= 三+ u ，则得到j a c o b i 迭代法 x m = g i x + 厂( 后= 0 , 1 ，2 ，) 这里迭代矩阵q = d - 1 ( 三+ ，向量厂= d _ 1 b ，若写成分量形式即为 设初始向量为z o = ( x ? ，x 2 0 ，x o ) r ：_ i ( 6 ，一窆d 。z ；) n ij 氧； t 1 = 1 ( 1 2 2 ) ( 1 23 ) ( i = 1 ，2 ，行；k = 0 , 1 ，2 ，) j a c o b i 法收敛的充要条件是以q ) 1 ，且有一些收敛的充分条件： ( 1 ) 如果爿为严格对角占优矩阵或为不可约弱对角占优矩阵，则j a c o b i 法收敛【5 0 ( 2 ) 如果彳为具有性质a 的对称正定阵，则j a c o b i 法收敛 5 。 三、g a u s s s e i d e l 法 若a 分裂成4 = d l u 时，令( 1 1 1 ) 中 彳= d 一五，= u ，则得到g a u s s s e i d e 迭代法如下 x m = q x + g( j = 0 , 1 ，2 ，) 其中迭代矩阵( 乏= ( d d u ，g = 一d 。b 若写成分量形式即为 ( 1 2 4 ) 浙江大学博士学位论文 设初始向量x o = ( x ? ，x 2 0 ，x o ) r = ( 6 ，一a ，x ，k “一口f x j ) ( 1 _ 2 5 ) “i l j = lj = i + l ( i = l ，2 ，r l ；k = o ，1 ，2 ，) g a u s s s e i d e j 法的收敛充要条件亦为p ( g 2 ) 1 ，但当一为对称正定阵时或a y j u 格对 角占优( 或不可约弱对角占优) 时，g a u s s s e i d e l 法必收敛【5 0 】， 5 。 从分量表达式可以看出，j a c o b i 方法是在迭代的每一步计算过程中是用的全部分量 来计算x 的所有分量，而g a u s s - s e i d e l 法是利用新计算出来的x j “，x 2 k + l ，x 竺1 和 x ? ，x 二1 ，艽：来计算膏“1 的分量。所以，在一定条件下，g a u s s s e i d e l 法比j a c 。b i 法收敛要快，但也有相反的情况，甚至有这样的方程组，j a c o b i 法收敛而g a u s s s e i d e i 法却 发散。事实上，我们在后面将清楚地看到，j a c o b i 法与g a u s s s e i d e l 法从几何上看是两个不 同的过程，有着不同的几何实质。 四、s o r 法 若a dl u ，而引进一因子使 c o a = c o d c o l c o u = d c o l 一( 1 一国) d c o u 方程组变为 曲a x = 国b 在( 1 1 1 ) 中令 彳= d c o l ，n = ( 1 一c o ) d c o u ，则得到s o r 法 x 。+ 1 = g 3 x + h ( i = o ，1 ，2 ，) ( 1 - 2 6 1 这里迭代矩阵g 3 = ( d d 江) - 1 【( 1 一c o d ) + c o u ，h = 国( d 一三) - 。b ，写成分量形 式为 设初始向量x o = ( x ? ，x 2 0 ，x ：) 7 z ? “亍x ? + ，山- - - - ( b ，一口，z ，k “一口f x j )( 1 - 2 7 ) 。i f j = lj = i ( f = l ，2 ，n ；k = 0 ，1 ，2 ，) 其中国称为松驰因子，它的适当选取可加快迭代法的收敛速度。s o r 法收敛的充要条件是 p ( g 3 ) 1 ，丽这就要求我们选择最佳松驰因子使p ( g 3 ) 达到最小，而s o r 法收敛 的必要条件是0 曲 2 。当a 为对称正定阵且0 田 2 时，s o r 法必为收敛。最佳 松驰因子的理论是由y o u n g ( 1 9 5 0 年) 针对一类椭圆型微分方程数值解得到的代数方程组 6 浙江大学博士学位论文 ( 其中系数矩阵a 具有性质a 和相容次序) 所建立的，他给出了最佳松驰因子公式 2 其中p ( g 1 ) 是j a c o b i 法迭代矩阵的谱半径。但在实际应用中，一般计算p ( g i ) 较困难 故可求其近似值或在计算实践中摸索出( 近似) 最佳松驰因子。 3 工程应用 解线性方程组的几何理论与几何方法可在工程中得到广泛应用，如在生物工程、能源 工程和土木建筑工程等等。本文在混凝土结构受火烧的强度分析研究中，用几何方法对非 稳态场的导热微分方程数值求解中的线性方程组进行求解与通常采用的g a u s s 消去法、 j a c o b i 迭代法、g a u s s - s e i d e l 迭代法和s o r 法等相比较在收敛性和精度上皆具有优越性。 在本文第五章中，对非稳态场的导热微分方程进行了进一步的研究，改变通常使用的有限 单元法结合差分法求解的方法，在c - n 法的基础上设计出有效、方便的求解方法，较好地 解决了工程中的一个问题。 金通? 光教授八十年代就在曲面求交等问题中提出有关几何思想，并已开始以几何的观 点与方法研究解方程组的迭代法8 2 ”，在多年的研究中，提出了迭代法的几何思想和 理论，本文是以金老师豹研究思想并在他的直接指导下完成的。 7 浙扛大学博士学位论文 第二章解线性方程组若干方法的几何本质 1 记号与定义 一、记”阶线性方程组为 a x = b ( 2 - l ，1 ) 其中a r “1 为n 阶系数矩阵，b 月”为 维已知向量，x r ”为 维未知向量。 即 4 = 口1 ia 1 2 日l n a 2 1a 2 2。c 2 n a n id n 2 n n 二、记一的n 个行向量为 x 1 z 2 ： x b 降 a = ( 口1 1 ，口，2 ，- ，a 。) 7( f = 1 , 2 ，一，”) 方程组( 2 1 1 ) 的聆个方程为”维空间中的n 个超平面，记为万。( j = 1 , 2 ，n ) ，即 石，： b 一( 口。i x i + 口，2 工2 + + 盯。z 。) = o( ，= 1 , 2 ，一，一) 三、设 个向量 s = ( i ，0 , 0 ，0 ) 7 占2 = ( 0 , t ，0 ，o ) 7 s = ( 0 ，0 ，0 ，1 ，0 ，0 ) 7 占“= ( 0 ，0 ，0 ，一，1 ) 7 称s 1 ，占2 ，5 ”为维空间的一组基本基。 定义2 1 设有两个向量“= ( “，“：，“。) 7 ，v = ( v ，v ：，v 。) 7 ，称芝，v ， 为两向量“、v 的内积，记为“v 。 定义2 2 称( 工) = b ，一a 。z ( f = 1 , 2 ，”) 为方程组( 2 一1 1 ) 的”个剩余向量函 数。 由以上定义，线性方程组( 2 - 1 1 ) 的n 个超平面可记为 8 浙江大学博士学位论文 丌：b ，一a x = 0 ( 即，( x ) = 0 ) ( f _ 1 ，2 ，n ) 其中a 为超平面的法向。 定义2 3 称任一 维空间的向量e = ( 8 1 ，e2 ，e 。) 7 为n 维空间的一个方向。称 占1 ，占2 ，占”为门个基本方向。 定义2 4 在盯维空间中，月一l 张超平面的交线称为棱，与此 一1 张超平面法向皆垂 直( 即两方向的内积等于0 ) 的方向称为棱方向。 2 解线性方程组迭代法的两个基本过程 在解线性方程组的迭代荤中，从几何形式上看，一般可归结为两个基本过程，一种我 们称其为反射( 投射) 过程，另一种称为张伞过程。 一、反射( 投射) 过程： 对线性方程组( 2 一1 1 ) ，每一个方程为一个n 维的超平面，即对n 个超平面 ，( x ) = 6 ，一爿7 x = 0( i = 1 , 2 ，一，”) 选定一组方向e r ”( f = 1 , 2 ，h ) ，且e 1 ，e2 ，e ”线性无关，则以下的过程 称为反射( 投射) 过程： ( i ) 首先从初值x o r ”出发，沿e 1 方向投射到万。上得交点p 0 1 ，即 p 0 1 = x o + t ：e 1 石l ( 其中t j 为一待定常数) ，有a ( p 0 1 ) = 0 ，所以 6 l a 1 z o 一靠( 4 1 e ) = 0 ( z o ) = 露( 4 1 e 1 ) 再从b 1 出发，沿e2 方向投射到厅2 上得交点r 2 ，即 尸0 2 = 岛1 + e2 石2 ( 其中f ? 为待定常数) ，有厶( 尸0 2 ) = 0 ，所以 ( x o ) = 矗( 一2 - e 1 ) + f ；( 一2 e2 ) 异2 = zo + t ：e 1 + f ? e 2 9 浙江大学螂士学位论文 从p o - 1 出发，沿e 。方向投射到石。上得交点掰( f 月) ，有 尸。= z 。+ r 占。口。 j = 1 j 工( z ) = r j ( 爿。e ) ( f ) j = i 当i = 时，得交点p o t 记为x ，即 x 1 = 聪 也就是说，从xo 出发，投射”次，完成迭代法的一步。由x o 得到x 1 作为方程组新的近 似解( 图2 - 2 1 ) 。 图2 - 2 1 ( i i ) 从z 1 出发重复( i ) 的过程，即以x 1 代替x 。沿e 。到口，( f = 1 , 2 ， ) 进行又一轮投 射，分别得交点p 。1 ，鼻2 ，只”，得z2 = 只”。重复以上过程同样可得z 3 ，x4 ，z ， 从而得到迭代序列 x ) 。且有 z “1 = x + r ；e ( 七= o ，1 “2 - ) = l 这样的过程我们又称为反射迭代。 ( i i i ) 在以上的迭代过程中，z ( x ) 、a - e 皆为已知，要得到 z ，只要依次计算 1 0 浙江大学博士学位论文 出f ? 这个量，我们记 r 。= a j j 称为荚联系数a 从表达式一( x ) = t d ( a7 e ) ( f = 1 , 2 ，”；女= o ，1 ，2 o r e , ) ，= l 可得方程组 rl】0 月2 l r 2 2 胄。ir 。2 - 月加= 陉 ( 2 - 21 ) 其中r 称为关联矩阵记t 丁。( t i ，f ，f ：) 7 ，f ( x ) = 一( x ) ， ( x ) ，工( 工t ) 】r 可以看出，从( 2 2 1 ) 可容易地解出t 。，即得t ；( f = l ，2 ，n ) 的值。 1 ”在上述反射迭代过程中，我们可以利用i f ，( z ) 8 来控制迭代是否停止。因为 f ( x 。) 是在计算过程中已经得到的向量，所以迭代精度的控制是比较方便的。即每得到 一个z ，就用i 厂( xk ) | | 来判断是否符合精度要求( 可以根据要求选择某一种范数) ，从 而决定是否停止迭代。 从以上的反射迭代可以看到，迭代收敛与否以及收敛的速度快慢，主要取决于所选取 的方向e ( f = 1 , 2 ， ) 和超平面的次序( 投射次序) 。事实上，取不同的投射方向 e 。( f = 1 , 2 ，以) ，就可以得到不同的迭代法。当然，选择方向时要使 r 。0 ( f = 1 ，2 ，月) ，以保证反射过程的顺利进行。 二、张伞过程 与反射过程相同，对方程组的n 个超平面石，( f = l ，2 ，以) ，选取一组线性无关 的基e 。( f = 1 , 2 ，胛) ，即 个方向，则以下过程我们称之为张伞过程 ( 从z 到x + 1 的步骤，七= 0 , i ，2 ，) 浙江大学博士学位论文 从z 出发，同时沿个月方向e 1 ( i = 1 ，2 ，h ) 分别到月个超平面万 ( f = 1 ，2 ， ) ，得到 个交点9 ：( i = 1 ，2 ，”) ( 图2 - 2 2 ) 。显然 q ! = x + “：e 。石，( 即一( q j ) = o )( f = 1 ，2 ，n ) ，所以 i 糌e ( 2 2 2 ) 这样，每一次迭代就像张一把伞，故称张伞过程。在图( 2 2 2 ) 中，x 。称为伞顶点 q ；称为伞尖点，甜：称为伞骨长( 由( 2 2 2 ) 式计算得到) 。 图2 - 2 2 张伞以后求z 。“一般有如下二个方式 ( a ) 求重心张伞过程 一。吉毫啦 ( 女_ 0 1 ，2 ，) 7 r ( 2 2 3 ) 得到x 。+ 1 以后，像反射迭代一样，进行精度控制判断。若不满足精度要求，以xk + i 代替 x 。继续张伞过程( 图2 - 2 3 ) 。 ( b ) 坐标表示张伞过程 x “1 = x + “：e ( 七= o , i “2 ) 与求重心张伞过程样，得到z “1 后进行精度判断，若满足即停止迭代 替x 继续张伞过程( 图2 - 2 4 ) 。 1 2 ( 2 2 4 ) 否则以z + 1 代 浙江大学博士学位论文 图2 2 3图2 2 4 上述这两种张伞过程亦称为张伞迭代过程。 事实上，若把这把“伞”看作一个仿射标架扛；e 1 ，e 2 ，e ”) ，则上述张伞迭代过 程求解方程组( 2 一i1 ) 就是在此标架中求出解x 的“坐标”。 同样，张伞迭代过程的收敛性及收敛速度与选取的方向e ( i = 1 ，2 ，n ) 有直接 的关系，即这组方向起着决定性的作用。选取不同的方向可得到不同的迭代法。 从反射迭代和张伞迭代的过程看，迭代计算似乎是串行的，它们主要计算工作量是求 f ：和“：的值，而从f ：和“：的计算公式( 2 2 1 ) 和( 2 22 ) 可以清楚地看到，m 个值的计 算皆是相互独立的，所以反射迭代法和张伞迭代法是天然适合并行计算的方法。 3 线性方程组若干解法的几何实质 从前面所述的迭代法的两个基本过程，我们可以来揭示几个著名的解线性方程组的迭 代法的几何本质，以便更多地更充分地了解这些方法。 一、j a c o bi 选代法的几何实质 在张伞过程中。我们选取一组方向e = 占1 坐标表示张伞过程( 2 2 4 ) x k + l = x + “ f = l 因为q ：= 、x + “：占。刀t ，材： ( i = 1 ，2 ，n ) 作为张伞方向，考虑 ( k = 0 ，1 ，2 ，) ( f = 1 ，2 ，h ) x 川：z i + 芝上( 6 一一，工) g 一( 2 - 3 1 ) 鲁l a “。 7 。 显然，( 2 - 3 1 ) 式写成分量形式即为j a c o b i 迭代法的分量表达式( 卜2 3 ) 式。 所以，j a c o b i 迭代法是选取”个基本方向的坐标表示张伞迭代过程。这就是j a c o b i 迭代法的几何本质。 鼍糌 浙江大学博士学位论文 二、g a u s s - s e i d e l 迭代法的几何实质 在反射迭代过程中，我们选取一组反射方向e 。= 占。( f = 1 ，2 ，n ) ，这时，在 迭代过程中，从到要进行n 步，即 x = p 女”，p 1 + l ，p ：l ，一，p 1 0 1 = x k + l 而p ：“= p ：0 + t2 s i 且p “汀j ，由f 。( p ：“) = o 褥 f ：1 _ ( 6 ，一爿尸? ：) a “ ( i = 1 ，2 ，n ) 可以看出，从p ? ：i 到p ? + ，只有第f 个分量发生改变，而且恰好是g a u s s s e i d e l 迭 代法第f 个分量的改变量( 卜2 5 ) 。因此，g a u s s s e i d e i 迭代法是一个反射迭代过程，是 选取基本方向的反射迭代过程。它与j a c o b i 迭代法在几何本质上有着实质性的区别。而一 般只说j a c o b i 迭代法与g a u s s s e i d e l 迭代法的区别只是在于o a u s s - s e i d e l 迭代法及时利 用了新算出的分量，并没有指出它们之间的本质区别。 了解了g a u s s s e i d e l 迭代法的几何实质，我们可以清楚地看到，g a u s s s e i d e l 迭代 法的收敛性是与反射过程的超平面次序有关的。例如以下二图，图2 - 3 1 和图2 - 3 2 中， 同样两张超平面，反射次序不同，收敛性绝然相反。也就是说，g a u s s s e i d e i 迭代法的收 敛性与方程组( 2 一l j1 ) 的n 个方程次序有关。 图2 - 3 ，l ( 发散)图2 - 3 2 ( 收敛) 三、s o r 迭代法的几何实质 在g a u s s s e i d e l 迭代法的反射迭代中，若按方向占( f = 1 ，2 ，n ) 投射到各平面 7 ，( i = 1 ，2 ，即) 时，再进行一个缩放过程( 图2 - 3 3 ) ，在x 到x + 。的第f 步迭代 1 4 一+ p 、一6 上 + 一+ 尸 i i ， p 2 一 ft。1lllll 浙江大学博士学位论文 中，记 q ；= j p 女卜1 + r ：占7 石 尸7 = p 女卜1 + 五：( ，：占) ( i = 1 ，2 ，月) 其中五：称为伸缩因子。通过伸缩可加快迭代法的收敛。 因为 i ii 图2 3 3 若令x 1 = x ( 精确解) 则有 x1=x o + x 一x o = “占 因。( f = 1 ,