计算方法3_线性方程组迭代解法.ppt

《计算方法3_线性方程组迭代解法.ppt》由会员分享，可在线阅读，更多相关《计算方法3_线性方程组迭代解法.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3 3章章 线性方程组迭代解法线性方程组迭代解法Iterative11 Techniques for Solving Linear Systems(2.1)直接法是通过有限步运算后得到线性方程组的解直接法是通过有限步运算后得到线性方程组的解，解线性方程组还有另一种解法，称为迭代法解线性方程组还有另一种解法，称为迭代法迭代法：不是用有限步运算求精确解，通过迭代迭代法：不是用有限步运算求精确解，通过迭代产生近似解逼近精确解产生近似解逼近精确解基本思想是将线基本思想是将线性性方程组方程组 AXB 化为化为XBX+F,再由此再由此构造一个向量序列构造一个向量序列X(k)X(k+1)=BX(k)+F

2、若若X(k)收敛在某个极限向量收敛在某个极限向量X*，则可得则可得X*就是就是(2.1)式的准确解式的准确解线性方程组的迭代法主要有线性方程组的迭代法主要有JocobiJocobi迭代法、迭代法、GaussGauss SeidelSeidel迭代法和超松弛迭代法和超松弛(SOR)(SOR)迭代法迭代法JacobiJacobi迭代和迭代和SeidelSeidel迭代由于收敛速度较慢，已经迭代由于收敛速度较慢，已经越来越不适应当前信息时代人们对计算速度和精度越来越不适应当前信息时代人们对计算速度和精度的要求，所以在实际应用中使用的并不多。但是，的要求，所以在实际应用中使用的并不多。但是，他们体现了

3、迭代法的最基本的思想，是学习其它迭他们体现了迭代法的最基本的思想，是学习其它迭代法的基础代法的基础 如何构造迭代序列如何构造迭代序列X(n)?X(n)在什么条件下在什么条件下收敛收敛?收敛速率如何收敛速率如何?误差估计误差估计.若在求解过程中若在求解过程中 X(k)X*(k(k)，由由 X(k+1)=(X(k)产生的产生的迭代迭代X(k)向向X*的逼近的逼近 ，在数次，在数次迭代求解之后，由于机器跳动产生的迭代求解之后，由于机器跳动产生的X(k)值误差或是值误差或是有效数字产生的舍入误差，都会在第有效数字产生的舍入误差，都会在第k+1k+1次迭代计算次迭代计算中自动弥补过来或逐步纠正过来。因此

4、，在迭代求解中自动弥补过来或逐步纠正过来。因此，在迭代求解过程中产生的各种误差是可以忽略的，即迭代求解无过程中产生的各种误差是可以忽略的，即迭代求解无累积误差，实际上，累积误差，实际上，X(k)只是解的一个近似，机器的只是解的一个近似，机器的舍入误差并不改变它的性质。舍入误差并不改变它的性质。迭代过程中经常要遇到向量范数，矩阵范数以迭代过程中经常要遇到向量范数，矩阵范数以及序列极限的概念。及序列极限的概念。3.1 向量和矩阵的范数向量和矩阵的范数Norms of Vectors and Matrices 数值分析中数值分析中,经常要用向量和矩阵经常要用向量和矩阵,为了应用的需要为了应用的需要(

5、误差误差分析分析),引入衡量向量和矩阵大小的度量引入衡量向量和矩阵大小的度量范数范数.对于实数对于实数x R,我们定义了绝对值我们定义了绝对值,满足满足|x|0 非负性非负性|x|=|x|齐次性齐次性|x+y|x|+|y|三角不等式三角不等式 类似地类似地,定义向量范数定义向量范数 Def3.1 在实在实n维线性空间维线性空间Rn中定义一个映射中定义一个映射,它使任它使任意意X Rn 有一个非负实数与之对应有一个非负实数与之对应,记为记为|X|,且该映且该映射满足射满足:正定性正定性 任意任意XRn,|X|0,if and only if X=0时时,|X|=0 齐次性齐次性 任意任意XRn,

6、R,有有|X|=|X|三角不等式三角不等式 任意任意X,Y Rn,有有|X+Y|X|+|Y|则称该映射在则称该映射在Rn中定义了一个向量范数中定义了一个向量范数.注注:Rn中的范数不唯一中的范数不唯一.常用的向量范数有三种常用的向量范数有三种:设设X=(x1,x2,xn)T Rn.则则 注注:(1)用范数的定义可验证上述皆为向量范数用范数的定义可验证上述皆为向量范数 (2)p=1,2,|X|p 即为即为|X|1,|X|2.(3)任意任意xRn:定理定理3.2 设设|和和|是是Rn上任意两种范数，则存在正上任意两种范数，则存在正常数常数C1和和C2，使得对一切使得对一切X Rn 有有 C1|X|

7、X|C2|X|注注:Rn中范数的等价性表明中范数的等价性表明,虽范数值不同虽范数值不同,但考虑到向量但考虑到向量序列收敛性时序列收敛性时,却有明显的一致性却有明显的一致性.Def3.3 Rn中中X(x1,x2,xn)T和和Y(y1,y2,yn)T则有则有有解有解(x1,x2,x3)T(1,1,1)T，用，用Gauss消去法得到近似解消去法得到近似解Def3.4 Rn中中的的向向量量序序列列X(k),即即X0,X1,XK,其其中中XK(x1(k),x2(k),xn(k)T.若对任意若对任意i（i=1,2,n）都有都有注：向量序列收敛实际上是按分量收敛（数列收敛）注：向量序列收敛实际上是按分量收敛

8、（数列收敛）利用向量范数，也可以说明向量序列收敛的概念。利用向量范数，也可以说明向量序列收敛的概念。定理定理3.5 向量序列向量序列X(k)依分量收敛于依分量收敛于X*的充要条件是的充要条件是 则向量则向量X*(x1*,x2*,xn*)T称为称为X(k)的极限，记做的极限，记做 类似于向量范数，给出矩阵范数的定义。类似于向量范数，给出矩阵范数的定义。Def3.6 在线性空间在线性空间Rnn中定义一个映射，使任意中定义一个映射，使任意A Rnn对应一对应一个非负实数，记做个非负实数，记做|A|.如果该映射满足：如果该映射满足：1.正定性正定性：（4.是矩阵乘法的需要，而是矩阵乘法的需要，而1.2

9、.3.为向量范数的推广。）为向量范数的推广。）2.齐次性齐次性：3.三角不等性三角不等性：4.相容性相容性：在在Rnn中可定义多种范数。中可定义多种范数。有有 A=(aij)nnRnn 称为称为frobenius范数范数 称为列范数称为列范数 称为行范数称为行范数 3.2 Jacobi迭代法迭代法(3.1)设有方程组设有方程组用矩阵表示用矩阵表示(3.1)其中其中A是是系数矩阵系数矩阵，非奇异，非奇异，X是解向量，是解向量，B是是右端项右端项。(3.2)(3.3)若令若令则有则有 B=D-1(D-A)=I-D-1A,G=D-1B方程方程(3.3)可记为可记为 X=BX+G方程方程(3.3)可记

10、为可记为 X=BX+G选取初始向量选取初始向量X0(x10,x20,xn0)T，代入方程，代入方程(3.3)右右端，可得到一个新向量，记为端，可得到一个新向量，记为X1(x11,x21,xn1)T，一直进行下去，迭代格式一直进行下去，迭代格式 X(n+1)=BX(n)+G n=0,1,2,以上过程产生向量序列以上过程产生向量序列X(k),若收敛于若收敛于X*，则有，则有 X*=BX*+G (I-B)X*=G=D-1B AX*=B即即X*是方程是方程(3.1)的解的解(3.4)Jacobi 迭代公式迭代公式k012310 x1k0.00000.60001.04730.93261.0001x2k0

11、.00002.27271.71592.0531.9998x3k0.0000-1.1000-0.8052-1.0493-0.9998x4k0.00001.87500.88521.13090.9998 唯一解唯一解X(1,2,-1,1)T(3.5)简单迭代法用简单迭代法用X(k)计算计算X(k+1)时时,需要同时保留需要同时保留X(k)和和X(k+1)。为了加快为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：收敛速度，同时为了节省计算机的内存，我们作如下的改进：每每算出一个分量的近似值，立即用到下一个分量的计算中去算出一个分量的近似值，立即用到下一个分量的计算中去迭代格式为迭代格式为

12、这样所得的迭代法就称为这样所得的迭代法就称为Gauss-Seidel迭代法，也迭代法，也称为称为“异步迭代法异步迭代法”，简称为，简称为GS迭代法。迭代法。若令若令则则(3.5)式可写成式可写成 X(k+1)=LX(k+1)+UX(k)+G k=0,1,2,也可记为也可记为 X(k+1)=(I-L)-1UX(k)+(I-L)-1G称称(I-L)-1U为为Seidel迭代法的迭代矩阵迭代法的迭代矩阵(3.6)(3.7)例例3.4 用用SeidelSeidel迭代法求解方程组迭代法求解方程组解解：取初始向量取初始向量,要求要求 时迭代终止。时迭代终止。Seidel Seidel迭代格式为迭代格式为

13、计算结果可列表如下计算结果可列表如下 注意：未必注意：未必SeidelSeidel方法一定比方法一定比JacobiJacobi方法好。方法好。3.3 收敛性和误差估计收敛性和误差估计 设设 nn 阶矩阵阶矩阵A的特征值为的特征值为 i(i=1,2,3n),则称则称 为矩阵为矩阵A的谱半径。的谱半径。例：用GS迭代法求解例3.3 相关程序设计 原始数据（A,b)可用一个二维数组存储，也可将A用一个二维数组，b用一个一维数组分别存储，存储需要一个一维数组。程序中应方便地对迭代方法和终止条件的选择以及对初始向量和值的设置。在迭代过程中，为反映迭代情况，可设置一些中间数据的输出，如迭带次数，迭代向量，

14、迭代残向量等。当然不需要每迭代一次都作输出，这可作为收敛情况或不收敛情况的分析。作为不收敛的判定，可设置一个大的整数，当迭代次数超过该数时作为不收敛处理。GS 迭代法的计算公式为：请给出用C语言或其他语言求解下面方程组的程序及结果：方法优缺点讨论由以上例题的求解过程可明显看出GS迭代法的收敛速度比简单迭代法快，但对于任意给定的一个方程组分别用简单迭代法和GS迭代法求解时，两种迭代法可能都收敛，也可能都不收敛。也有可能是GS迭代法收敛而J迭代法不收敛。但亦有相反情况，即简单迭代法收敛而GS迭代法不收敛。而且交换方程组中的方程和未知数的次序都会影响GS迭代法的计算结果，但这种交换对简单迭代法是没有

15、影响的。3.4 松弛法松弛法当使用当使用JacobiJacobi迭代法或迭代法或SeidelSeidel迭代法解线性方程组时，可能会出迭代法解线性方程组时，可能会出现收敛极慢的情况，为了提高迭代收敛速度，我们再给出时现收敛极慢的情况，为了提高迭代收敛速度，我们再给出时SORSOR法法，此方法又称为此方法又称为超松弛法超松弛法（Successive Over Relaxation Successive Over Relaxation MethodMethod），它具有提高迭代收敛速度的功能。），它具有提高迭代收敛速度的功能。SORSOR法由法由SeidelSeidel迭代迭代法演变而来，其法演变

16、而来，其基本思想基本思想是利用原迭代的第次迭代值及由产生的是利用原迭代的第次迭代值及由产生的下一步下一步SeidelSeidel迭代值的加权平均构成新的迭代格式。迭代值的加权平均构成新的迭代格式。松弛法可认为是松弛法可认为是Seidel法的加速法的加速Seidel法法 X(k+1)=LX(k+1)+UX(k)+G k=0,1,2,令令 X=X(k+1)X(k)=LX(k+1)+UX(k)+G X(k)X(k+1)=X(k)X松弛法思想松弛法思想 X(k+1)=X(k)X松弛法松弛法 X(k+1)=(1-)X(k)(LX(k+1)+UX(k)+G)k=0,1,2,其中，其中，称为松弛因子，当称为

17、松弛因子，当1时叫超松弛，当时叫超松弛，当1时叫低松弛时叫低松弛也可记为也可记为 X(k+1)=(I-L)-1(1-)I+U)X(k)+(I-L)-1G称称(I-L)-1(1-)I+U)为松弛法的迭代矩阵为松弛法的迭代矩阵(3.8)(3.9)(3.10)唯一解唯一解X(3,4,-5)Tk01237x1k15.2500003.14062503.08789063.0134110 x2k13.8125003.88281253.92675783.9888241x3k1-5.046875-5.0292969-5.0183105-5.0027940Seidel法法k01237x1k16.3125002.6

18、2231453.13330273.0000498x2k13.51953133.95852664.01026464.0002586x3k1-6.6501465-4.6004238-5.0966863-5.0003486SOR法法 =1.253.5 迭代法的特点迭代法的特点方法简单，每次迭代都是简单的重复运算，易于编制程序；与求解线性方程的精确法相比，简单迭代法对于字长位数较少的计算机更为适用，它可以用增加迭代次数来弥补字长位数少的不足。初值可以任取，因而中间结果偶然错误不影响最后结果的获得。缺点：用计算机计算时，迭代速度较慢。就其收敛性而言，某些用Seidel迭代法不能收敛。而无法得出结果的线性代数方程组，用Jacoai迭代法却能进行收敛计算，反之已然。