第2章线性方程组求解的数值方法课件.ppt

1、1第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1.高斯消元法高斯消元法2.矩阵分解法矩阵分解法3.向量范数与矩阵范数向量范数与矩阵范数4.迭代法求解迭代法求解5.方程组的病态问题与误差分析方程组的病态问题与误差分析主要内容：主要内容：2第二章第二章 线性方程组求解的数值方法线性方程组求解的数值方法1. 理解各种线性方程组数值求解；理解各种线性方程组数值求解；2. 掌握求解方法和解的误差分析方法；掌握求解方法和解的误差分析方法；3. 能编程实现求解算法。能编程实现求解算法。特别强调：遇到问题养成用计算机编程求解特别强调：遇到问题养成用计算机编程求解的习惯，不要习惯性的用笔算，而

2、这是国内的习惯，不要习惯性的用笔算，而这是国内外学生的一个主要差距。外学生的一个主要差距。教学要求：教学要求：3 在自然科学和工程技术中，有很多问题的解决都需在自然科学和工程技术中，有很多问题的解决都需要用到线性方程组的求解。因此，求解线性方程组的问要用到线性方程组的求解。因此，求解线性方程组的问题是一个在科学技术中常见的普遍问题。题是一个在科学技术中常见的普遍问题。 解线性方程组的数值解法：有直接法和迭代法两类。解线性方程组的数值解法：有直接法和迭代法两类。直接法：直接法：计算过程没有舍入误差，经过有限次四则运算可求得方计算过程没有舍入误差，经过有限次四则运算可求得方程组得精确解。（实际计算

3、有舍入误差）程组得精确解。（实际计算有舍入误差）高斯消元法，矩阵分解法高斯消元法，矩阵分解法迭代法：迭代法：核心是迭代求解的收敛条件和收敛速度。核心是迭代求解的收敛条件和收敛速度。雅可比（雅可比（JacobiJacobi）迭代，高斯）迭代，高斯- -赛德尔（赛德尔（Gauss-SeidelGauss-Seidel）迭代）迭代4123112321233471()2581()36111()xxxExxxExxxE基本思想方法：基本思想方法：由由行初等变换行初等变换将系数矩阵约化为三角将系数矩阵约化为三角 矩阵；用矩阵；用回代回代的方法求解方程组。的方法求解方程组。例例1 1 用消去法（高斯消元法）

4、解方程组用消去法（高斯消元法）解方程组高斯消元法高斯消元法是求解方程组的古典方法。是求解方程组的古典方法。 (2.1)3.1 3.1 高斯消元法高斯消元法5结论：结论：整个计算过程可分为两部分：整个计算过程可分为两部分：（1 1）消元消元：把原方程组转化为系数矩阵为上三角矩：把原方程组转化为系数矩阵为上三角矩阵的方程组；阵的方程组；（2 2）回代回代：由系数矩阵为上三角矩阵的方程组求解：由系数矩阵为上三角矩阵的方程组求解（2 2）回代求解，得：）回代求解，得：30 x 。213x ，113x ，1 47 12 58 13 6 11 1A212313( ) 2( )( ) 3( )EEEEEE解

5、：解：（1 1）消元：）消元：14710 -3-6-10 -6 -10 -2323( ) 2( )EEE147103610020，6对于一般情形：对于一般情形：n n阶线性方程组的高斯消元法阶线性方程组的高斯消元法11 112 21121 122 2221 12 2n nn nnnnn nna xa xa xba xa xa xba xa xa xb111212122212nnnnnnaaaaaaAaaa其系数矩阶，12nbbbb。12,nxxxx7(1)(1)(1)(),ijAAabb，若记若记(1)(1)(2.2)Axb则可写为，即(1)(1)(1)(1)1111211(1)(1)(1)(

6、1)2212222(1)(1)(1)(1)12nnnnnnnnxaaabxaaabxaaab(1)(1)(1)(1)111211(1)(1)(1)(1)212222(1)(1)(1)(1)12nnnnnnnaaabaaabAaaab增广矩阵增广矩阵（2.2）8（1 1）第）第1 1步步( (k k=1)=1)，(1)1(1)111(2)iiamina ，一般形式的高斯消元法一般形式的高斯消元法：(1)110a设设 ，首先对行计算乘数，首先对行计算乘数对增广矩阵对增广矩阵 进行进行行初等变换：行初等变换：1 1(2,3 , )iiirm rrin ，A(即用即用 乘以乘以2.2式的第式的第1个方

7、程，加到第个方程，加到第i个方个方程上，消去程上，消去2.2式的第二个方程直到第式的第二个方程直到第n个方程中个方程中的未知数的未知数 )( 代表第代表第i行行)1 imir1x9得到与原方程组得到与原方程组 等价的方程组等价的方程组 。记为记为(2)(2)Axb（2）一般第）一般第k步消元步消元( )(1)(1)Axb(1)(1)(1)(1)1111211(2)(2)(2)22222(2)(2)(2)2nnnnnnnxaaabxaabxaab0，00(1)(1)111,10,0kkkaa设已完成上述消元过程第设已完成上述消元过程第1 1步，第步，第2 2步，步，第，第k k-1-1步，且步，

8、且 )1()1(bxA 11kn( )( )kkAxb10(1)(1)(1)11121(2)(2)222( )( )( )( )( )nnkkkkkknkknknnaaaaaAaaaa(1)1(2)2( )( )( )kkkknbbbbb其中：其中：设设 ，计算乘数，计算乘数( )0kkka( )( )(1, )kikkikkkamikna，11(即用即用 乘以乘以2.2式的第式的第k个方程，加到第个方程，加到第i个方程上，消去个方程上，消去2.2式的第式的第k+1个方程直到第个方程直到第n个方程中的未知数个方程中的未知数 )ikmkx那么第那么第k步消元操作即：步消元操作即：(3)(3)继续

9、这一过程，直到完成第继续这一过程，直到完成第n-1n-1次消元，最后我们得到次消元，最后我们得到与原方程组等价的三角形方程组与原方程组等价的三角形方程组 1111111211122222222nnnnnnnnaaabxxaabxab nnAxb(1, )iik kirm rrikn，(2.3)(2.3) 消元过程结束消元过程结束12求解三角形方程组求解三角形方程组2.3，得到求解公式，得到求解公式 ( )1,(1,2,2,1)nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 这个过程称为这个过程称为回代过程。回代过程。13例题：例题： 考虑方程组考虑方程组 Gauss Gauss

10、消去法中每步用来消去其他元素的消去法中每步用来消去其他元素的 称为该称为该步的主元素。步的主元素。GaussGauss消去法作为数值方法，主元素的选择消去法作为数值方法，主元素的选择是否会影响计算的结果呢？是否会影响计算的结果呢？121,1xx412121012xxxx kkka则该方程的精确解为则该方程的精确解为而采用而采用( ( ，1)1)作为主元素，利用高斯消去法得到的解为作为主元素，利用高斯消去法得到的解为120,1xx410显然结果是错误的。显然结果是错误的。14 错误在哪个地方呢？错误在哪个地方呢？ 原因是我们在消元时，利用了小主元原因是我们在消元时，利用了小主元 ，使得约化后，使

11、得约化后的方程组元素数量级大大增长，再经舍入，而计算机的有的方程组元素数量级大大增长，再经舍入，而计算机的有效位数有限，造成消元后的三角形方程组就不准确了。效位数有限，造成消元后的三角形方程组就不准确了。410 结论：结论：在消元过程中可能出现主元素为零的情况，这时消在消元过程中可能出现主元素为零的情况，这时消去法将无法进行；即使不为零，在主元素很小时，用其做去法将无法进行；即使不为零，在主元素很小时，用其做除数，也会导致其他元素数量级的严重增长和舍入误差的除数，也会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠。扩散，最后也使得计算解不可靠。 解决方法：解决方法：对一般

12、的矩阵来说，最好每一步选取系数矩阵对一般的矩阵来说，最好每一步选取系数矩阵（或消元后的低阶矩阵）的该列中绝对值最大的元素作为（或消元后的低阶矩阵）的该列中绝对值最大的元素作为主元素，以使高斯消去法具有较好的数字稳定性。主元素，以使高斯消去法具有较好的数字稳定性。( (高斯高斯列主元素消去法列主元素消去法) )151. 1. 列主元法列主元法1233264107075156xxx 第一列中绝对值最大是第一列中绝对值最大是1010，取，取1010为主元为主元32641070751561070732645156n n阶方程组第阶方程组第k k轮消元时，选第轮消元时，选第k k列的后列的后(n-k+1

13、)(n-k+1)个元素中绝对个元素中绝对值最大作主元。值最大作主元。16107070.166.12.552.5107072.552.56.26.2x3=6.2/6.2=1x2=(2.5-5x3)/2.5=-1x1=(7+7x2-0 x3)/10=0 x1=0 x2=-1x3=1第二列的后两个数中选出主元第二列的后两个数中选出主元 2.52.5172 2 完全主元素消去法完全主元素消去法1233264107075156xxx 整个矩阵中绝对值最大是整个矩阵中绝对值最大是1010，取，取1010为主元为主元32641070751561070732645156n n阶方程组第阶方程组第k k轮消元时

14、，选消元后元素中绝对值最大作主元。轮消元时，选消元后元素中绝对值最大作主元。18107070.166.12.552.51007760.16.102.58332.5833x1=0 x2=-1x3=1方框中方框中6 6最大，交换行列，交换列的时候要做记录最大，交换行列，交换列的时候要做记录（即（即x3x3和和x2x2交换了位置）：交换了位置）：22.5833/2.58331x 326.10.1/61xx123770/100 xxx19 完全主元素消除法与列主元素消完全主元素消除法与列主元素消除法的优缺点比较：除法的优缺点比较：优点：优点： 数值更加稳定；数值更加稳定；缺点：缺点： 计算量大；计算量

15、大；20 对矩阵对矩阵A A实行初等行变换相当于用初等矩阵左乘实行初等行变换相当于用初等矩阵左乘A A，于，于是对是对(2.2)(2.2)做第一次消元后，做第一次消元后， 化为化为 化为化为 ，即，即 ，其中，其中 (1)(2)(1)(2)11,L AALbb(1)(2)(1)(2),AAbb3.1 矩阵的三角分解矩阵的三角分解 LULU分解分解2113111000100010001nmLmm 21第第k k步的初等矩阵为步的初等矩阵为1,10000100010001kkknkLmm 1kkkL AA 1kkkL bb并且并且重复这一过程，最后得到重复这一过程，最后得到 11211121nnn

16、nLL L AALL Lbb将上三角矩阵将上三角矩阵 记为记为U U，则，则 nA111121nAL LL ULU22将上三角矩阵将上三角矩阵 记为记为U U，则，则 ，其中其中 nA111121nAL LL ULU21111313212112,11111nnnn nmmmLL LLmmm则，则，L L为单位下三角矩阵。为单位下三角矩阵。 高斯消去法实质上是产生了一个将高斯消去法实质上是产生了一个将A A分解为两个三角形分解为两个三角形矩阵相乘的因式分解。如果矩阵相乘的因式分解。如果A A是非奇异阵，则是非奇异阵，则LULU分解是唯一分解是唯一的，否则分解不唯一。的，否则分解不唯一。231AL

17、U、 先求，消元法：消元法：12,UxL b、 后回代 即解。消元法与三角分解法间的关系：消元法与三角分解法间的关系： 1AxbAn对，设 的 至 阶顺序主子式不等于零。三角分解法：三角分解法：2LybUxy、 再求解。1111( , )(,)( , )(,)A bU L bLA bU L b、 先消元，即，讨论讨论24直接三角分解法解线性方程组（直接三角分解法解线性方程组（ ）的具体流程：）的具体流程：11(1,2, )iiuainAxb1111(1, )iilauin 1.2. 2. 计算计算U U的第的第r r行，行，L L的第的第r r列元素列元素 r=2,3,n11(,1, )rri

18、rirkkikual uir rn3.11(,1, ;)riririkkrrrklal uuir rn rn(一一)LU分解分解25再求解再求解Ly=b, Ux=yLy=b, Ux=y计算公式：计算公式：1111;(2,3, );iiiikkkybybl yin1;(1,2,1);nnnnniiikkiik ixyuxyu xuinn (二二)x的的计算计算26例例 用直接三角分解法解方程组用直接三角分解法解方程组 1231471258136111xxx 1111121213131,4,7uauaua21211131311121 231 3la ula u，解解:(一一)矩阵矩阵LU分解分解1

19、11111;(1, );(2, )iiiiuainlauin(1)(1)故：故：27222221 12232321 13323231 1222333331 1332 235 2 438 2 76()/2() 2ual uual ulal uuual ul u 1111(,1, )(,1, ;)rririrkkikriririkkrrrkual uir rnlal uuir rn rn(2)经计算：经计算：281471147258213636113212ALU (3)(1, 1,0)TLyby求解，得，(4)( 1/3,1/3,0)TUxyx 求解，得方程组的解。(二二)求解求解x：从而从而11

20、11;(2,3, );iiiikkkybybl yin1;(1,2,1);nnnnniiikkiik ixyuxyu xuinn 29 3.2 3.2 矩阵的矩阵的CholeskyCholesky分解分解 对称正定矩阵对称正定矩阵A A：AT = A, A的各阶顺序主子式大于零的各阶顺序主子式大于零. . 前面指出非奇异的矩阵可以有三角分解，当前面指出非奇异的矩阵可以有三角分解，当A A是某些特殊是某些特殊矩阵时，它的矩阵时，它的LULU分解会有更加简洁的形式。分解会有更加简洁的形式。A A的的LULU分解分解1112121221,1,1111nnnnn nnnuuumuAummu (2.4)

21、30uii 0 (i =1,n)由于由于A A是对称正定的，则有是对称正定的，则有11121222111211111221,1,11/1/1nnnnnnnnnnnuuuuuUuuuuuuuuuuDR将将U U进一步分解：进一步分解：31根据根据A A的对称性：的对称性：ALDRTTTTTAAR DLRDL1122TTTALDLLDLDP P故：故：由分解的唯一性知：由分解的唯一性知：故：故：TLR其中其中P P为上三角矩阵，这种对称正定矩阵的分解称为为上三角矩阵，这种对称正定矩阵的分解称为CholeskyCholesky分解。分解。在在MatlabMatlab中函数中函数“cholchol”给

22、出对称正定矩阵的给出对称正定矩阵的CholeskyCholesky分解。分解。32经过经过n n步可直接求得步可直接求得思路思路: :(1)(1)分解对称正定矩阵分解对称正定矩阵TALL.TLybyL xyx，求，求TAxbLL xb求解1112111112112122221222221212nnnnnnnnnnnnnnaaallllaaallllAaaallll 111jnijik jkik jkij jjkkal ll ll l设设n n阶对称正定矩阵阶对称正定矩阵A A有分解有分解 , ,先用待定系数法求先用待定系数法求L L的的元素元素TALL(0)jkkjl时，ijlijlChole

23、sky分解的具体步骤分解的具体步骤( (平方根法平方根法) )：(2)(2)分解分解求解方程组求解方程组33Cholesky方法方法具体计算公式：具体计算公式：分解计算：分解计算： TALL：(1,2, )in121/21(2)()iiiiiikklal11(1)(),jijijik jkjjklal ll(1,2,1)()jij i11(3)()(1,2, )iiiikkiikybl yl in，1(4)()(,1,2,1)niikikiik ixyl xl in n TLybyL xyx， 求， 求111jnijik jkik jkij jjkkal ll ll l(1,2, )in(0)

24、jkkjl当时，求解：求解： 34 3.3 3.3 向量范数与矩阵范数向量范数与矩阵范数向量、向量、矩阵与线性方程组有着密切的关系，矩阵与线性方程组有着密切的关系，向量、矩阵范数是向量、矩阵范数是解方程组以及研究与探讨方程组本身性质的工具。解方程组以及研究与探讨方程组本身性质的工具。一、向量范数的定义一、向量范数的定义定义定义 范数为范数为pl11pnpipixx其中的其中的 ，最常用的范数是，最常用的范数是 ，以及，以及1p1,2ppp11niixx1 2221niixxmaxiixx35容易证明向量范数满足如下性质：容易证明向量范数满足如下性质：(1)如果如果 ，则，则 ；而且；而且 ，当

25、且仅当，当且仅当 (2)对任何的数对任何的数c，都有，都有 (3) 范数也称为范数也称为2-2-范数或范数或EuclideanEuclidean函数；函数； 范数也称为范数也称为 - -范数或一致范数。在范数或一致范数。在MatlabMatlab中用函数中用函数 用来计算用来计算向量向量x x的的 范数。范数。2ll,norm x ppl0 x 0 x 0 x 0 x cxc xxyxy由性质由性质(3),还容易得到：还容易得到：xyxy36二二 矩阵范数的定义矩阵范数的定义在向量范数的基础上可以进一步定义矩阵范数在向量范数的基础上可以进一步定义矩阵范数0maxxAxAx1l1l 如果上式中的

26、向量范数取为如果上式中的向量范数取为 范数，则可以证明定义出范数，则可以证明定义出的矩阵范数（称为矩阵的矩阵范数（称为矩阵 范数或者列范数）为范数或者列范数）为11maxnijjiAa 如果向量范数取为如果向量范数取为2-范数，则范数，则122TAA A 其中其中 （模），称为矩阵（模），称为矩阵B的谱半径。的谱半径。( 为为B的任意特征值。的任意特征值。 ) maxiiBB37 类似地，类似地，Matlab函数函数norm(A,p)给出矩阵给出矩阵p=1,2或或 范数范数 如果向量范数取如果向量范数取为为 ，则可以证明定义出的矩阵，则可以证明定义出的矩阵范数（称为矩阵的范数（称为矩阵的 范数

27、或者行范数）为范数或者行范数）为 ll1maxnijijAa 容易证明矩阵范数满足如下性质：容易证明矩阵范数满足如下性质： (1) (1)如果如果 ，则，则 ；而且；而且 ，而且仅当，而且仅当 (2) (2)对任何的数对任何的数 ， (3)(3) (4) (4)0A0A 0A 0A AAABABABAB而且由矩阵范数的定义还有而且由矩阵范数的定义还有称之为矩阵范数与相应的向量范数是相容的。称之为矩阵范数与相应的向量范数是相容的。AxAx3838 3.4 古典迭代法的构造古典迭代法的构造求解线性代数方程组的方法求解线性代数方程组的方法中小规模中小规模问题问题直接法直接法迭代法迭代法 大规模，大规

28、模，超大规模问题超大规模问题 古典方法古典方法现代方法现代方法3939Axb线性方程组的一般形式为：线性方程组的一般形式为：如果如果 是非奇异的，则上式有唯一解。是非奇异的，则上式有唯一解。n nA R我们将通过一个具体线性方程组的例子来讲解迭代法。我们将通过一个具体线性方程组的例子来讲解迭代法。取：取：410141014A565b 1212323454645xxxxxxx即线性方程组为：即线性方程组为： 方程的精确解方程的精确解 ( (直接法计算直接法计算) )111x 4040 如果对该方程组进行变形，将变量如果对该方程组进行变形，将变量 分别从三个分别从三个方程中分离出来：方程中分离出来

29、：1212323454645xxxxxxx122133215441164441544xxxxxxx 123,xxx(1)(1)令令初初值值(0)000 x (1)1.251.51.25x(2)0.8750.8750.875x(3)1.03131.03131.0313x(10)1.00001.00001.0000 x41(1)( )12(1)( )( )213(1)( )3215441164441544kkkkkkkxxxxxxx 所以所以(1)式可以表示为迭代形式：式可以表示为迭代形式：0,1,2k k 所以我们可以得到一个向量的序列所以我们可以得到一个向量的序列 ，只要该序列当，只要该序列当

30、 时有极限，那么这个极限就是该线性方程组的解。时有极限，那么这个极限就是该线性方程组的解。上面这种迭代求解线性方程组的方法称为上面这种迭代求解线性方程组的方法称为Jacobi迭代法迭代法。( )kx42Axb1,1,2,nijjija xbin考虑线性方程组的一般形式：考虑线性方程组的一般形式：其中矩阵其中矩阵A为为nn阶方阵，则方程的分量形式为：阶方阵，则方程的分量形式为：1213111231111111121232221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa 改写成：改写成：4323213

31、121(1)( )( )( )121311111111111(1)( )( )( )21232222222222(1)( )( )( )121,1,2,3,nnnnkkkknkkkknkkkknnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxkaaaa 从而得到迭代公式：从而得到迭代公式：上面式子就是一般形式的上面式子就是一般形式的Jacobi迭代法，也可也记做：迭代法，也可也记做：1(1)( )( )111,2,1()0,1,2,ijjinkkkiijijjj iiiinxba xa xka 44在在Jacobi迭代法中充分利用新值，可得到下面迭代：迭

32、代法中充分利用新值，可得到下面迭代：23213121(1)( )( )( )121311111111111(1)(1)( )( )21232222222222(1)(1)(1)(1)121,1,2,3,nnnnkkkknkkkknkkkknnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxkaaaa 上面这种迭代方法也叫做上面这种迭代方法也叫做Gauss-Seidel迭代，也可以记为：迭代，也可以记为：1(1)(1)( )111,2,1()0,1,2,ijjinkkkiijijjj iiiinxba xa xka 45方程组的精确解为方程组的精确解为x x

33、* *=(1,1,1)=(1,1,1)T T. . 解解 JacobiJacobi迭代法计算公式为迭代法计算公式为123123123103142103531014xxxxxxxxx (1)( )( )37112310105(1)( )( )3112135102(1)( )( )37131210105kkkkkkkkkxxxxxxxxx 取初始向量取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T, ,迭代可得迭代可得(1)(1)(1)1231.4,0.5,1.4xxx(2)(2)(2)1231.11,1.2,1.11xxx例例1：利用：利用Jacobi法和法和Gauss-Sei

34、del法求解线性方程组法求解线性方程组46kx1(k)x2(k)x3(k)x(k)-x* 0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636可见可见, ,迭代序列逐次收敛于方程组的解迭代序列逐次收敛于方程组的解, , 而且迭代而且迭代7 7次得到精确到小次得到精确到小数点后两位的近似解数点后两

35、位的近似解. .计算结果列表如下计算结果列表如下: :47Gauss-SeidelGauss-Seidel迭代法的计算公式为迭代法的计算公式为: :同样取初始向量同样取初始向量x x(0)(0)=(0,0,0)=(0,0,0)T T, , 计算结果为计算结果为 由计算结果可见由计算结果可见,Gauss-Seidel,Gauss-Seidel迭代法收敛较快迭代法收敛较快. .取精确到小取精确到小数点后两位的近似解数点后两位的近似解,Gauss-Seidel,Gauss-Seidel迭代法只需迭代迭代法只需迭代3 3次次, ,而而JacobiJacobi迭代法需要迭代迭代法需要迭代7 7次次. .

36、(1)( )( )37112310105(1)(1)( )3112135102(1)(1)(1)37131210105kkkkkkkkkxxxxxxxxx kx1(k)x2(k)x3(k)x(k)-x* 012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 48为了进一步研究为了进一步研究, ,从矩阵角度来讨论上述迭代法从矩阵角度来讨论上述迭代法. . 对线性方程组对线性方程组Ax=b,Ax=b,记记D=diag(aD=diag(a1111,a,a2222, ,a,ann

37、nn) )213132121000nnnnaaaaaaL12131232100,0nnnnaaaaaaU则有则有 A=D-L-UA=D-L-U于是线性方程组于是线性方程组 Ax=b Ax=b 可写成可写成 (D-L-U)x=b(D-L-U)x=b等价于等价于 Dx=(L+U)x+b Dx=(L+U)x+b 或或 x=Dx=D-1-1(L+U)x+D(L+U)x+D-1-1b b 49由此建立由此建立JacobiJacobi迭代法迭代公式迭代法迭代公式 x x(k+1)(k+1)=D=D-1-1(L+U)x(L+U)x(k)(k)+D+D-1-1b k=0,1,2,b k=0,1,2,或写成或写

38、成 x x(k+1)(k+1)=Bx=Bx(k)(k)+f k=0,1,2,+f k=0,1,2,其中其中1211111212122221200()0nnnnnnnnaaaaaaaaaaaaBDLU1112122,nnnbabafbaD b50所以所以Gauss-SeidelGauss-Seidel迭代法可以写成迭代法可以写成其中其中Gauss-SeidelGauss-Seidel迭代法迭代公式为迭代法迭代公式为1(1)(1)( )111,2,1()0,1,2,ijjinkkkiijijjj iiiinxba xa xka 写成矩阵形式为：写成矩阵形式为： 1(1)1kkkxDLxUxb 11

39、1111kkkkkkkDxLxUxbDL xUxbxDLUxDLb 10,1,2,kkxBxfk11,BDLUfDLb51 3.5 3.5 迭代法的分析迭代法的分析 构造迭代法的途径可以有很多，那么是不是所有的构造迭代法的途径可以有很多，那么是不是所有的方法都能收敛呢？收敛速度的快慢与什么有关系呢？方法都能收敛呢？收敛速度的快慢与什么有关系呢？它的精确解为它的精确解为1 1 1Tx例：例：123123123103142103531014xxxxxxxxx 52kx1(k)x2(k)x3(k)x(k)-x* 0123401416.792.8168104.7-41.4-52.4-254.30-1.

40、74.56-151-238.211342.41521680可见可见, ,并不是所有的方程组都收敛，即使收敛对于不同的方法并不是所有的方程组都收敛，即使收敛对于不同的方法( (例例如如JacobiJacobi与与Gauss-Seidel)Gauss-Seidel)收敛速度也是不同的收敛速度也是不同的. .计算结果列表如下计算结果列表如下: :53 设设 是矩阵是矩阵B任意一个特征值，任意一个特征值， 是相应的特征向是相应的特征向量，即量，即0 x ,nBxxxRR 再假设再假设 为任意的向量范数及与之相融的矩阵范数，为任意的向量范数及与之相融的矩阵范数，则有：则有：xxBxB x首先引入几个定义

41、、引理：首先引入几个定义、引理：所以对矩阵所以对矩阵B任意一个特征值任意一个特征值 ，都有，都有记记 ，称之为矩阵，称之为矩阵B的的谱半径谱半径，则，则B maxkkB BB54先引入两个引理（详细证明见附录）：先引入两个引理（详细证明见附录）：引理引理3.1 矩阵矩阵 ，则，则 的充分必要条的充分必要条件是件是 引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是非奇异的。非奇异的。 n nBRlim0kkB 1Bn nBR 1BIB55 定理定理3.1 对任意的对任意的 和任意的初始向量和任意的初始向量 ，迭，迭代法收敛的充分必要条件是代法收敛的充分必要条件是nfR 0nxR 1B证明：证明

42、： 必要性必要性 设迭代法产生的序列设迭代法产生的序列 收敛，记收敛，记 是该序列的极是该序列的极限点，所以限点，所以 满足满足xBxf 1kkxxx又由迭代关系又由迭代关系 ，可以得到，可以得到 -1kkxBxf 1220kkkkxxB xxBxxBxx56由由 的任意性，知：的任意性，知： 0nxRlim0kkB由引理由引理3.1知：知： 1B充分性充分性 由由 及引理及引理2知知 （即（即 ）有唯一解，记为有唯一解，记为 1BxBxfIB xfxBxf 0kkxxBxx类似于必要性的证明，得到类似于必要性的证明，得到再由第一步知再由第一步知 ，故，故lim0kkB kxxk 57 定理定

43、理3.1给出了迭代收敛的充要条件，但给出了迭代收敛的充要条件，但 不宜计不宜计算，所以在实际使用中通常并不好用。由算，所以在实际使用中通常并不好用。由 知，只知，只要对某种相容的矩阵范数有要对某种相容的矩阵范数有 BB 1B1B 那么当然那么当然 ，所以这常常是实际中很有效的收，所以这常常是实际中很有效的收敛判别准则。敛判别准则。 1BB严格对角占优矩阵：严格对角占优矩阵：考虑考虑 ，设，设 ，当，当 时的矩阵。时的矩阵。n nARijn nAa1niiijjj iaa58定理定理3.2 如果如果A是严格对角占优的矩阵，则它一定非奇异。是严格对角占优的矩阵，则它一定非奇异。由于由于A是对角占优

44、矩阵，所以是对角占优矩阵，所以 ，故矩阵，故矩阵0,1,2,iiain1122,nnDdiag aaa是可逆的。考虑是可逆的。考虑12111112121222212000nnnnnnnnaaaaaaaaID Aaaaa59 矩阵的矩阵的 范数为范数为1ID A11maxnijijiij iaID Aa由由A是对角占优矩阵，得是对角占优矩阵，得111ID AID A 由引理由引理3.2知知 是非奇异的，又由于是非奇异的，又由于 是非奇异的，所以是非奇异的，所以A是非奇异的。是非奇异的。1D AD得证！得证！引理引理3.2 矩阵矩阵 ，若，若 ，则，则 是是非奇异的。非奇异的。 n nBR 1BI

45、B60 定理定理3.3 系数矩阵为严格对角占优的线性代数方程组，它的系数矩阵为严格对角占优的线性代数方程组，它的Jacobi迭代法和迭代法和Gauss-Seidel迭代都是收敛的。迭代都是收敛的。证明：证明： Jacobi方法的迭代矩阵为方法的迭代矩阵为1BID A由定理由定理3.2中的证明知，严格对角占优矩阵满足：中的证明知，严格对角占优矩阵满足：11ID A再由定理再由定理3.1，得，得Jacobi迭代法收敛。迭代法收敛。(a)Jocobi的证明的证明161再考虑再考虑Gauss-Seidel方法，其迭代矩阵为方法，其迭代矩阵为1BDLU用反证法，假设用反证法，假设Gauss-Seidel

46、迭代不收敛，则由定理迭代不收敛，则由定理3.1知：知： 11BDLU所以存在模大于所以存在模大于1的特征值的特征值. 设有设有 ，使得行列式：，使得行列式：1110detdet1detdetnIBIDLUDLDLU(b) Gauss-Seidel的证明的证明62 故，只有故，只有才能使得才能使得 成立。成立。1det0DLU由于由于A是对角占优的，所以矩阵是对角占优的，所以矩阵1DLU 也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵也是对角占优的，那么该矩阵一定非奇异，这与上面该矩阵 的行列式等于的行列式等于0矛盾。矛盾。1det0DL由于由于 可逆，所以可逆，所以1DLdet0IB得证

47、！得证！63定理定理3.4 若迭代矩阵若迭代矩阵B满足满足 ，则迭代生成的序列，则迭代生成的序列 满足满足收敛速度问题收敛速度问题1B 1kkx 0(1)1( )( )1( )1kkkkkBaxxxxBBbxxxxB其中其中 表示精确解。表示精确解。x证明：证明：先证明先证明(b), 然后证明然后证明(a)64 1(1)( )1( )=kkkkkkxxxxxxxxxx而而 1kkxxB xx所以所以 1kkxxB xx故，本页第一个式子可写为故，本页第一个式子可写为 1(1)( )( )=1kkkkkxxxxxxBxx65由于由于 ，故，故1B ( )(1)1( )111kkkkkxxxxBB

48、xxB(b)得证得证显然对于任意的正整数显然对于任意的正整数p，都有，都有 1(1)( )ppppxxB xx那么在本页第一个式子中反复利用上式就可以得到那么在本页第一个式子中反复利用上式就可以得到(a)(a)得证得证66 给出的关系可以作为计算终止的判别准则。即只要给出的关系可以作为计算终止的判别准则。即只要 和和 已足够接近，表明已足够接近，表明 与与 便已足够靠近。便已足够靠近。定理定理3.4 (a) 0(1)1kkBxxxxB 给出的是迭代收敛速度的一个估计。显然给出的是迭代收敛速度的一个估计。显然 越接近越接近0，生成序列生成序列 收敛得越快。收敛得越快。1B 1kkx定理定理3.1

49、4 (b)1kx 1( )1kkkBxxxxB kx kxx定理定理3.4的讨论的讨论67 3.6 超松弛迭代超松弛迭代(SOR)及分块迭代方法及分块迭代方法 对于给定的迭代法，每步迭代所需的工作量是确定对于给定的迭代法，每步迭代所需的工作量是确定的。如果迭代法收敛速度缓慢，则需要比较多的迭代次的。如果迭代法收敛速度缓慢，则需要比较多的迭代次数，由此导致算法工作量太大而失去使用价值，因此各数，由此导致算法工作量太大而失去使用价值，因此各种迭代法的加速技术具有重要意义。种迭代法的加速技术具有重要意义。 假设假设 是已经得到的迭代值，以是已经得到的迭代值，以 为初值进行一为初值进行一步步Gauss

50、-Seidel迭代得：迭代得： kx kx 11111inkkkiijjijjiiijj ixa xa xba 68将这一迭代值与将这一迭代值与 的值组合作为新一步的迭代值的值组合作为新一步的迭代值 kx 111111111,2,kkkiiiinkkkijjijjiiiiiijj ixxxa xa xa xbain 其中其中 为待定的参数，写成矩阵形式为：为待定的参数，写成矩阵形式为： 1111kkxDLUD xDLb这时迭代矩阵：这时迭代矩阵：11BDLUD69 新的迭代每步的计算代价与新的迭代每步的计算代价与Gauss-Seidel方法相差无几，如方法相差无几，如果能取得恰当的果能取得恰当