第4章-线形方程组求根课件.ppt

《第4章-线形方程组求根课件.ppt》由会员分享，可在线阅读，更多相关《第4章-线形方程组求根课件.ppt（88页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章 解线性方程组的迭代法1 1 向量范数,矩阵范数,谱半径 及有关性质2 简单迭代法3 3 赛德尔迭代法赛德尔迭代法4 4 松弛迭代法松弛迭代法1 向量范数,矩阵范数,谱半径 及有关性质对任一向量对任一向量X Rn，按照一定规则确定，按照一定规则确定一个实数与它对应，该实数记为一个实数与它对应，该实数记为|X|，若，若|X|满足下面三个性质：满足下面三个性质：v|X|0；|X|=0当且仅当当且仅当X=0；(正定性正定性)v对任意实数对任意实数，|X|=|X|；(齐次齐次性性)v对任意向量对任意向量Y Rn，|X+Y|X|+|Y|则称该实数则称该实数|X|为向量为向量X的的范数范数 (半可加

2、性半可加性)1.范数的定义1 向量范数,矩阵范数,谱半径 及有关性质2.Rn中常用的几种向量范数1-范数范数2-范数范数 -范数范数其中其中x1,x2,xn分别是分别是X的的n个分量个分量上述范数都是上述范数都是p范数范数的特例的特例v当不需要指明使用哪一种向量范数时当不需要指明使用哪一种向量范数时,就就用记号用记号|.|泛指任何一种向量范数。泛指任何一种向量范数。1 向量范数,矩阵范数,谱半径 及有关性质3.关于范数的几点说明v设设 为为AX=B的精确解，的精确解，X为其近似解为其近似解,则则其绝对误差可表示成其绝对误差可表示成|X-|,其相对误差可表其相对误差可表示成示成|X-|/|或或|

3、X-|/|X|v向量的范数可以用来衡量向量的向量的范数可以用来衡量向量的大小大小和表和表示向量的示向量的误差误差。设设A,B为为n阶方阵，若对应的非负实数阶方阵，若对应的非负实数|A|满足：满足：v|A|0;|A|=0，当且仅当，当且仅当A=0时；时；v对任意实数对任意实数，|A|=|A|；v|A+B|A|+|B|v|AB|A|B|(相容性相容性)1 向量范数,矩阵范数,谱半径 及有关性质4.矩阵范数的引入则称则称|A|为为矩阵矩阵A的范数。的范数。设设Rn中规定的向量范数为中规定的向量范数为|X|,在在Rn*n中规中规定的矩阵范数为定的矩阵范数为|A|，若，若以下不等式成立以下不等式成立时，

4、时，|AX|A|X|1 向量范数,矩阵范数,谱半径 及有关性质5.向量范数和矩阵范数的关系v矩阵范数和向量范数相容矩阵范数和向量范数相容称称矩阵范数矩阵范数|A|和向量范数和向量范数|X|相容相容定理定理4.14.1 设在设在R Rn n中给定了一种向量范数中给定了一种向量范数X,对任一对任一n n阶方阵阶方阵A,A,令令则由上式所定义的则由上式所定义的|.|是一种矩阵范数，并是一种矩阵范数，并且它与所给定的向量范数且它与所给定的向量范数X相容相容1 向量范数,矩阵范数,谱半径 及有关性质v定义一种矩阵范数时定义一种矩阵范数时,应当使它能与某种应当使它能与某种向量范数相容。向量范数相容。v在同

5、一个问题中需要同时使用矩阵范数和在同一个问题中需要同时使用矩阵范数和向量范数时，这两种范数应当是相容的。向量范数时，这两种范数应当是相容的。矩阵的算子范数(向量范数导出的矩阵范数向量范数导出的矩阵范数)1 向量范数,矩阵范数,谱半径 及有关性质v算子范数的必要条件:任何一个算子范数，当任何一个算子范数，当A为单位矩阵为单位矩阵I时时,必有必有|I|=1v向量范数1-范数,2-范数及-范数,从属于它们的矩阵范数分别为:1 向量范数,矩阵范数,谱半径 及有关性质行范数行范数:A A的行向量的行向量中中1-1-范数的最大值范数的最大值列范数列范数:A A的列向量中的列向量中1-1-范数的最大值范数的

6、最大值1 向量范数,矩阵范数,谱半径 及有关性质例子：设有方阵A，求其1-范数,2-范数及-范数。其中1 向量范数,矩阵范数,谱半径 及有关性质vF-F-范数范数(FrobeniusFrobenius OR Euclid OR Euclid范数范数)1 向量范数,矩阵范数,谱半径 及有关性质F-范数范数不是算子范数不是算子范数它与向量范数中的它与向量范数中的2-范数相容范数相容:|AX|F|A|F|X|2矩阵的从属范数必与给定的向量范数相容，矩阵的从属范数必与给定的向量范数相容，但是矩阵范数与向量范数相容，却未必有从但是矩阵范数与向量范数相容，却未必有从属关系。属关系。对于对于Rn中的向量序列

7、中的向量序列X(k),如果如果1 向量范数,矩阵范数,谱半径 及有关性质6.向量收敛的定义则称向量序列则称向量序列X(k)收敛于收敛于Rn中的向量中的向量X。上式通常表示成上式通常表示成:1 向量范数,矩阵范数,谱半径 及有关性质其中其中xj(k)和和xj分别表示分别表示X(k)和和X中的第中的第j个分量个分量7.向量收敛的充分必要条件定理4.2 Rn中的向量序列中的向量序列X(k)收敛于收敛于Rn中的向量中的向量X的必要充分条件是的必要充分条件是向量序列的收敛可以归结为对应元素向量序列的收敛可以归结为对应元素序列的收敛。序列的收敛。1 向量范数,矩阵范数,谱半径 及有关性质上式通常表示成上式

8、通常表示成:则称方阵序列则称方阵序列A(k)收敛于收敛于n阶方阵阶方阵A。对于对于n阶方阵序列阶方阵序列A(k),如果如果8.方阵收敛的定义定理定理4.34.3 n阶方阵序列阶方阵序列A(k)收敛于收敛于n阶方阵阶方阵A 的充分必要条件是的充分必要条件是:1 向量范数,矩阵范数,谱半径 及有关性质9.方阵收敛的充分必要条件(1)矩阵序列的收敛可以归结为对应元素矩阵序列的收敛可以归结为对应元素序列的收敛。序列的收敛。设设n阶方阵序列阶方阵序列A的特征值为的特征值为 i(i=1,2,n),v矩阵范数和谱半径的关系矩阵范数和谱半径的关系矩阵矩阵A的任一特征值的任一特征值 i与其对应的特征与其对应的特

9、征1 向量范数,矩阵范数,谱半径 及有关性质10.谱半径为矩阵为矩阵A的的谱半径谱半径。则称则称证明证明:向量向量Xi有关系式有关系式得得|i|X i|=|A X i|A|X i|1 向量范数,矩阵范数,谱半径 及有关性质对上式两端取范数，再利用相容性质对上式两端取范数，再利用相容性质|AX|A|X|由于由于Xi 0,|Xi|0,所以所以|i|A|，故，故 矩阵矩阵A的任何一种范数都大于它的谱半径的任何一种范数都大于它的谱半径,即即|A|是矩阵是矩阵A的特征值的上界。的特征值的上界。结论：结论：定理定理4.4 如果如果A Rnn，则，则 1 向量范数,矩阵范数,谱半径 及有关性质11.谱范数由

10、于由于2-范数具有上面的关系式，所以称范数具有上面的关系式，所以称|A|2为为谱范数谱范数。定理定理4.4 如果如果A Rnn，则，则 1 向量范数,矩阵范数,谱半径 及有关性质11.谱范数2）若）若A为对称矩阵，则为对称矩阵，则2）若）若A为对称矩阵，则为对称矩阵，则2）若）若A为对称矩阵，则为对称矩阵，则定理定理4.5 设设A是是任意任意n阶方阵，由阶方阵，由A的各次的各次幂所组成的矩阵序列幂所组成的矩阵序列收敛于零，即收敛于零，即的充分必要条件是的充分必要条件是1 向量范数,矩阵范数,谱半径 及有关性质12.方阵收敛的充分必要条件2 简单迭代法 将将AX=B改写为改写为0=-AX+B，两

11、边加上，两边加上X后，后，其中其中Cij=-aij(i j),Cii=1-aii(i=j)2.1.1 迭代格式1得得 X=(I-A)X+B=CX+B或写成或写成相应的迭代公式为相应的迭代公式为:X(k+1)=CX(k)+B或写成或写成2.1.1 迭代格式迭代格式1式中式中C=I-A称为迭代矩阵，它等于称为迭代矩阵，它等于对于方程对于方程AX=B,若若aii 0(i=1,2,n),可按可按照方程的顺序依次地解出照方程的顺序依次地解出x1,x2,xn得得2.1.2 迭代格式迭代格式22.1.2 迭代格式迭代格式2则上式可以用矩阵表示则上式可以用矩阵表示为为X=GX+F2.1.2 迭代格式迭代格式2

12、2.1.2 迭代格式迭代格式2迭代矩阵的特点：迭代矩阵的特点：对角线上的元素全部为对角线上的元素全部为0；其它元素为原系数矩阵的元素除以所在行其它元素为原系数矩阵的元素除以所在行对角线上的元素，然后在前面加负号。对角线上的元素，然后在前面加负号。2.1.2 迭代格式迭代格式22.1.2 迭代格式迭代格式22.1.2 迭代格式迭代格式2则则I-D-1A=G同理同理 F=D-1B相应的迭代公式为相应的迭代公式为X(k+1)=GX(k)+F这种迭代法称为这种迭代法称为雅克比迭代法雅克比迭代法(简单迭代法简单迭代法)2.1.2 迭代格式迭代格式22.1.2 迭代格式迭代格式2计算步骤：计算步骤：任取一

13、组初值任取一组初值X(0)=(x1(0),x2(0),xn(0)作为作为=(1,2,n)的零次近似值，按迭的零次近似值，按迭代公式代公式X(k+1)=GX(k)+F进行迭代计算；进行迭代计算；如果迭代序列如果迭代序列X(k+1)有极限存在，则此极有极限存在，则此极限为线性方程组的根。限为线性方程组的根。称这种解法为称这种解法为简单迭代法。简单迭代法。2.2 简单迭代法的收敛条件v为叙述方便，把为叙述方便，把AX=B改写后的变形等改写后的变形等价方程组表示为价方程组表示为X=MX+N，或或定理4.6 对任何初始向量和对任何初始向量和X(0)和常数项和常数项N，2.2 简单迭代法的收敛条件2.2.

14、1 迭代格式1由迭代公式由迭代公式:X(k+1)=MX(k)+N (k=0,1,2,)向量序列向量序列X(k)收敛的收敛的充分必要条件充分必要条件是是:设序列设序列X(k)收敛于收敛于，则有，则有 =M +N第第k次迭代的近似值和精确解之差为次迭代的近似值和精确解之差为 X(k+1)-=MX(k)-M=M(X(k)-)证明：证明：(1)(1)必要性必要性(收敛收敛=)反复使用上式得反复使用上式得 X(k+1)-=M(X(k)-)=M2(X(k-1)-)=Mk(X(0)-)对于任意初始向量对于任意初始向量(X(0)-)，为使，为使2.2 简单迭代法的收敛条件由定理由定理4.5即知即知(M)1。2

15、.2 简单迭代法的收敛条件(2)(2)充分性充分性(=(=收敛收敛)若若(M)1满足满足,则特征值则特征值|1,|1,|I-M|0成成立，从而方程组立，从而方程组(I-M)X=N有唯一解有唯一解,设为设为,则则X(k+1)-=MX(k)-M=M(X(k)-)仍然成立仍然成立X(k+1)-=M(X(k)-)=M2(X(k-1)-)=Mk(X(0)-)v迭代的收敛性只与迭代矩阵的谱半径有迭代的收敛性只与迭代矩阵的谱半径有关关v迭代矩阵是由迭代矩阵是由A A演变来的演变来的,因此迭代是否因此迭代是否收敛是与系数矩阵收敛是与系数矩阵A A以及演变的方式有关以及演变的方式有关,与常数项和初始向量的选择无

16、关。与常数项和初始向量的选择无关。2.2 简单迭代法的收敛条件即迭代过程收敛即迭代过程收敛。（证毕）（证毕）从上述定理得出从上述定理得出：2.2 简单迭代法的收敛条件定理定理4.5：设有迭代公式设有迭代公式x(k+1)=Mx(k)+f,若若|M|1,则对任意初始值则对任意初始值X(0)，与右端向量，与右端向量f,迭代方程产生的迭代方程产生的迭代序列为迭代序列为X(k)收敛于收敛于方方程程x=Mx+f的的唯一解唯一解x*,并且有误差估计式：并且有误差估计式：证明证明：|I-M|=0，若，若=1,必有必有|I-M|=0，由由|M|1可知可知:|I-M|0，所以原方程有唯一解，所以原方程有唯一解x*

17、,即即x*=Mx*+f,则则X(k+1)-x*=M(X(k)-x*)2.2 简单迭代法的收敛条件X(k+1)-x*=M(X(k)-x*)X(k)-x*=Mk(X(0)-x*)两边取范数得：两边取范数得：|Mk(X(0)-x*)|M|k|(X(0)-x*)|M|1,则则lim|M|k=0,lim|X(k)-x*|=0LimX(k)=x*2.2 简单迭代法的收敛条件X(k+n)-X(k)=(X(k+n)-X(k+n-1)+(X(k+n-1)-X(k+n-2)+(X(k+2)-X(k+1)+(X(k+1)-X(k)两边取范数得两边取范数得：|X(k+n)-X(k)|=|(X(k+n)-X(k+n-1

18、)+(X(k+n-1)-X(k+n-2)+(X(k+2)-X(k+1)+(X(k+1)-X(k)|X(k+n)-X(k+n-1)|+|X(k+n-1)-X(k+n-2)|+|X(k+2)-X(k+1)|+|X(k+1)-X(k)|推导误差估计式推导误差估计式2.2 简单迭代法的收敛条件|X(k+n)-X(k+n-1)|+|X(k+n-1)-X(k+n-2)|+|X(k+2)-X(k+1)|+|X(k+1)-X(k)|M|n-1|X(k+1)-X(k)|+|M|n-2|X(k+1)-X(k)|+|M|X(k+1)-X(k)|+|M|0|X(k+1)-X(k)|2.2 简单迭代法的收敛条件2.2

19、简单迭代法的收敛条件若若 则对任意初值则对任意初值,简单简单迭代法收敛迭代法收敛,且且若若 则对任意初值则对任意初值,简单简单迭代法收敛迭代法收敛,且且2.2 简单迭代法的收敛条件2.2.2 简单迭代法的三个收敛充分条件充分条件1:充分条件2:2.2 简单迭代法的收敛条件若若 ,则对任意初值则对任意初值,简单简单迭代法收敛迭代法收敛,且且充分条件3:v在线性方程组的情况下，由式在线性方程组的情况下，由式2.2 简单迭代法的收敛条件知知mij在任意初值下都为常数在任意初值下都为常数,因此属因此属大范围大范围收敛充分条件。收敛充分条件。定理定理4.8 若若|M|j,x(k+1)ij,x(k)上述迭

20、代方式可以表示为:3.1 赛德尔迭代法的解法赛德尔迭代法的解法用矩阵记为X(k+1)=L X(k+1)+U X(k)+N 3.1 赛德尔迭代法的解法赛德尔迭代法的解法高斯-赛德尔迭代法:3.1 赛德尔迭代法的解法赛德尔迭代法的解法采用迭代格式采用迭代格式2变形变形AX=B，其对应的赛德，其对应的赛德尔迭代公式为尔迭代公式为3.1 赛德尔迭代法的解法赛德尔迭代法的解法高斯-赛德尔迭代法:3.1 赛德尔迭代法的解法赛德尔迭代法的解法把式把式X(k+1)=L X(k+1)+UX(k)+N改写为改写为(I-L)X(k+1)=UX(k)+N X(k+1)=(I-L)-1 UX(k)+(I-L)-1 N

21、3.2 3.2 赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔赛德尔迭代法相当于迭代矩阵为迭代法相当于迭代矩阵为(I-L)-1 U的简单迭代法。的简单迭代法。由定理由定理4.6知，知，赛德尔赛德尔迭代法对于任意初迭代法对于任意初值值X(0)和常数项和常数项N都收敛的都收敛的必要充分条件必要充分条件是是迭代矩阵迭代矩阵(I-L)-1 U的谱半径小于的谱半径小于1结论结论:定理4.10 若若A为为不可约不可约,对角占优矩阵对角占优矩阵,则则 高斯高斯-赛德尔赛德尔迭代法必定收敛迭代法必定收敛.证明：证明：要证明要证明高斯高斯-赛德尔迭代法收敛，根赛德

22、尔迭代法收敛，根据定理据定理4.6，只要证明，只要证明(G)1即可，即可，G是是高斯高斯-赛德尔迭代法的迭代矩阵。赛德尔迭代法的迭代矩阵。因为因为高斯高斯-赛德尔迭代法的迭代公式赛德尔迭代法的迭代公式为为X(k+1)=-D-1LX(k+1)-D-1UX(k)+D-1B将它化成等价的简单迭代法形式：将它化成等价的简单迭代法形式：3.2 3.2 赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件2.高斯-赛德尔迭代法的收敛性X(k+1)=-D-1LX(k+1)-D-1UX(k)+D-1B(I+D-1L)X(k+1)=-D-1UX(k)+D-1B两边同乘以两边同

23、乘以(I+D-1L)-1X(k+1)=-(I+D-1L)-1 D-1UX(k)+(I+D-1L)-1D-1B =-D(I+D-1L)-1 UX(k)+D(I+D-1L)-1 B =-(D+L)-1UX(k)+(D+L)-1B所以所以高斯高斯-赛德尔迭代法的迭代矩阵为赛德尔迭代法的迭代矩阵为G=-(D+L)-1U下面用反证法推证定理。假设下面用反证法推证定理。假设G的特征值有的特征值有|1，则它必满足以下特征方程，则它必满足以下特征方程|I-G|=03.2 3.2 赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件(AB)-1=B-1A-1AA-1=I代入迭

24、代矩阵公式得代入迭代矩阵公式得|I+(D+L)-1U|=0|(D+L)-1 (D+L)+U|=0|(D+L)-1|(D+L)+U|=0由于由于A不可约且对角占优不可约且对角占优,所以所以aii 0(i=1,2,n),因此有因此有|(D+L)-1|0,所以所以|(D+L)+U|=03.2 3.2 赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件因为因为3.2 3.2 赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件赛德尔迭代法的收敛条件因为因为矩阵矩阵G中的零元素的位置与矩阵中的零元素的位置与矩阵A中零元素中零元素的位置全同，由的位置全同

25、，由A的不可约性可以推得的不可约性可以推得G的的不可约性；由不可约性；由A的对角占优得的对角占优得:两边同乘两边同乘|得，（因为得，（因为|1）所以所以G也是不可约性对角占优的矩阵也是不可约性对角占优的矩阵,根据根据引引理理4.1知知|G|0,与假设矛盾与假设矛盾,所以所以|1,即即(G)1 超松弛法超松弛法 1 低松弛法低松弛法4.1.3 带有松弛因子的逐次松弛法则迭代公式为则迭代公式为:迭代矩阵为迭代矩阵为:4.1.3 带有松弛因子的逐次松弛法用矩阵的形式可以表示为用矩阵的形式可以表示为:4.1.3 带有松弛因子的逐次松弛法用矩阵的形式可以表示为用矩阵的形式可以表示为:4.1.3 带有松弛

26、因子的逐次松弛法用矩阵的形式可以表示为用矩阵的形式可以表示为:4.2 松弛法的收敛条件松弛法收敛的必要条件是松弛法收敛的必要条件是0 2若若A为对称正定矩阵，则当为对称正定矩阵，则当0 2时，松时，松弛法恒收敛弛法恒收敛若若A为不可约、对角占优矩阵，且松弛因为不可约、对角占优矩阵，且松弛因子子 满足满足0 1时，则松弛法必定收敛时，则松弛法必定收敛使用松弛法求解线性方程组，关键是要选使用松弛法求解线性方程组，关键是要选好松弛因子的数值。使松弛法收敛最快的好松弛因子的数值。使松弛法收敛最快的松弛因子叫做最佳松弛因子。松弛因子叫做最佳松弛因子。2.2 简单迭代法的收敛条件例例4.3 4.3 用带有松弛因子的逐次用带有松弛因子的逐次松弛法解松弛法解线性线性方程组（方程组（=1.250）解：按照公式建立松弛迭代公式为：解：按照公式建立松弛迭代公式为：