数值方法线性方程组的迭代法精品文稿.ppt

《数值方法线性方程组的迭代法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数值方法线性方程组的迭代法精品文稿.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值方法线性方程组的迭代法第1页，本讲稿共35页引言引言直接法是通过有限步运算后得到线性方程组的解,解线性方程组还有另一种解法，称为迭代法,它的基本思想是将线性方程组 Ax=b 化为 x=Bx+f 再由此构造向量序列x(k):x(k+1)=Bx(k)+f若x(k)收敛至某个向量x*,则可得向量x*就是所求方程组 AX=b 的准确解.线性方程组的迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(Sor)迭代法.第2页，本讲稿共35页迭代法的特点迭代法的特点 若在求解过程中 xkx*(k)，由 xk+1=(xk)产生的迭代 xk向x*的逼近，在数次迭代求解之后，由于机器跳动产生的xk值误

2、差或是有效数字产生的舍入误差，都会在第k+1次迭代计算中自动弥补过来或逐步纠正过来。因此，在 迭代求解过程中产生的各种误差是可以忽略的，即迭代求解无累积误差，实际上，xk只是解的一个近似，机器的舍入误差并不改变它的此性质。迭代过程中经常要遇到向量范数，矩阵范数以及序列极限的概念。为此，下面先介绍这方面的知识和有关概念。单击此处即可单击此处即可第3页，本讲稿共35页几个基本概念及性质1.向量范数向量范数：对任一向量X，按一定规则确定一个实数与其相对应，该实数记 为|X|，若|X|满足下面三个性质：（1）|X|0，|X|=0当且仅当X=0。（2）对任意实数，|X|=|X|。（3）对任意向量YRn，

3、|X+Y|X|+|Y|。则称该实数|X|为向量X的范数2.矩阵范数矩阵范数：设A是NN 阶矩阵，定义|A|=Max（|AX|/|X|）=Max|AX|x0,xRn|x|=1,xRn 为矩阵A的(算子）范数。|Ax|A|x|第4页，本讲稿共35页三种常用的向量范数：三种常用的向量范数：例例：设：设 x=(1 ,-4,0,2)T 求它的向量范数求它的向量范数第5页，本讲稿共35页三种常用的矩阵范数：三种常用的矩阵范数：例例：设：设 A，求它的矩阵范数，求它的矩阵范数 第6页，本讲稿共35页矩阵范数的性质：（1）对任意非零矩阵A,有|A|恒为正数，当且仅当A=0，|A|=0.（2）|aA|=|a|A

4、|（a为任意实数）（3）对于任意两个阶相同的矩阵A，B恒有|A+B|A|+|B|.（4）对于与矩阵A有相同维数的向量X，恒有|AX|A|X|.（5）对于同阶矩阵A，B 恒有|AB|.|A|B|谱半径：设 nn 阶矩阵A的特征值为 i(i=1,2,3n),则称 (A)=MAX|i|为矩阵A的谱半径.1 in 矩阵范数与谱半径之间的关系为:(A)|A|.单击此处单击此处试做例题试做例题第7页，本讲稿共35页5 几个定理及定义设x(k)为 Rn中的向量序列,x(*)为Rn中的向量对矩阵也有类似的结论 下一页下一页第8页，本讲稿共35页 如果 矩阵 A=(aij)满足 n|aii|aij|i=1,2,

5、n,j=1,ji 则称方阵则称方阵则称方阵则称方阵A A是严格是严格是严格是严格(行行行行)对角占优的对角占优的对角占优的对角占优的.a11 a12 a13 a1n a21 a22 a23 a2n A=L+D+U an1 an3 an4 ann -4 2 1例 矩阵 A=1 -9 7 2 -6 10U ULDD第9页，本讲稿共35页Jacobi 迭代一：设有方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .an1x1+an2x2+annxn=bn用矩阵表示：Ax=b （A 为系数矩阵，非奇异；b为右端，x为解向量）上一页上一页第10页，本讲稿共35页

6、假设 aii0 令 cij=-aij/aii (ij)gi=bi/aij,i=1,2,3,n 则 x1(k+1)=c12x2(k)+c13x3(k)+c1nxn(k)+g1 x2(k+1)=c21x1(k)+c23x3(k)+c2nxn(k)+g2 。xn(k+1)=cn1x1(k)+cn2x2(k)+cn(n-1)xn-1(k)+gn Jacobi迭代格式迭代格式若令若令 0 c12 c13 c1n x1 c21 0 c23 c2n x2BJ=x=.cn1 cn3 cn4 0 xn a11 g1 a22 g=g2 易看出：BJ=D-1(D-A)=I-D-1,D=.ann gn 把方程组写成容

7、易迭代的形式：第11页，本讲稿共35页Jacobi迭代公式迭代公式第12页，本讲稿共35页Seidel迭代法迭代法 为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：这样所得的迭代法就称为Gauss-Seidel迭代法，也称为“异步迭代法”，简称为GS迭代法利用Ax=b 及A=L+D+U,其中D为对角矩阵,L,U分别为严格下，上三角矩阵则有，GS迭代法的矩阵形式为:第13页，本讲稿共35页Seidel迭代法的具体形式迭代法的具体形式Seidel迭代格式迭代格式 x1(k+1)=c12x2(k)+c13x3(k)+c

8、1nxn(k)+g1 x2(k+1)=c21x1(k+1)+c23x3(k)+c2nxn(k)+g2 。xn(k+1)=cn1x1(k+1)+cn2x2(k+1)+cn(n-1)xn-1(k+1)+gn 假设 aii0 令 cij=-aij/aii (ij)gi=bi/aij,i=1,2,3,n 第14页，本讲稿共35页收敛性及误差估计Jacobi迭代和GS迭代格式可表述为统一形式:对于其收敛性，我们有如下定理：定理：对任意初始向量x(0)及任意右段向量 g，由此产生的迭代向量序列x(k)收敛的充要条件是证明：必要性：设x(k)收敛，其极限为 x*，则第15页，本讲稿共35页因上式对任意均成立

9、，故Bk 0 (k ),(B)1 充分性：设(B)1,则IB为非奇异阵,且 =0,所以 有唯一解,记为 则 定理：若|B|R THEN R=ABS(S(I)-T)240 NEXT I250 PRINT K;”-”;:FOR I=1 TO N:PRINT“X(;I;”)=“;INT(X(I)*100000+0.5)/100000;:NEXT I:PRINT 255 IF R1 THEN 280 260 NEXT K.:第28页，本讲稿共35页270 PRINT“DRE DAI SH BAI”280END290DATA 10,-1,-2,7.2300DATA-1,10,-2,8.3310DATA-

10、1,-1,5,4.2320DATA 0,0,0 RUN?3,10E-6,20 返回第29页，本讲稿共35页五.方法优缺点讨论由以上例题的求解过程可明显看出GS迭代法的收敛速度比简单迭代法快，但对于任意给定的一个方程组分别用简单迭代法和GS迭代法求解时，两种迭代法可能都收敛，也可能都不收敛也有可能是GS迭代法收敛而J迭代法不收敛但亦有相反情况，即简单迭代法收敛而GS迭代法不收敛而且交换方程组中的方程和未知数的次序都会影响GS迭代法的计算结果，但这种交换对简单迭代法是没有影响的返回第30页，本讲稿共35页SOR法介绍法介绍利用利用Seidel Seidel 迭代法迭代法 ，考虑如下，考虑如下Sor

11、 Sor 迭代格式迭代格式一步一步SeidelSeidel迭代迭代松弛因子松弛因子Sor Sor 迭代格式也是线性迭代形式迭代格式也是线性迭代形式第31页，本讲稿共35页第32页，本讲稿共35页第33页，本讲稿共35页举例检验举例检验Jacoai迭代的收敛性迭代的收敛性以知三阶线性方程组：8x1-3x2+2x3=204x1+11x2-x3=336x1+3x2+12x3=36首先将原方程组写为迭代形式的方程组，即：x1=20/8 0+3/8 x2 2/8x3x2=33/114/11x1 0+1/11x3x3=36/12 6/12x1 3/12x2 0求任一行之和的最大值1,即：|M|=max5/

12、8,5/11,9/12=9/121i或求任一列之和的最大值1,即：|M|1=max114/132,60/96,30/88=114/1321结论：该方程组采用Jacoai迭代法计算是收敛的。第34页，本讲稿共35页迭代法的特点方法简单，每次迭代都是简单的重复运算，易于编制程序；与求解线性方程的精确法相比，简单迭代法对于字长位数较少的计算机更为适用，它可以用增加迭代次数来弥补字长位数少的不足.初值可以任取，因而中间结果偶然错误不影响最后结果的获得。缺点：迭代速度较慢。用计算机计算时，。就其收敛性而言，某些用Seidel迭代法不能收敛而无法得出结果的线性代数方程组，用Jacoai迭代法却能进行收敛计算,反之亦染.第35页，本讲稿共35页