第三章线性方程组的迭代解法PPT讲稿.ppt

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

1、第三章 线性方程组的迭代解法第1页，共23页，编辑于2022年，星期二任取一个向量任取一个向量x(0)作为作为x的近似解，用迭代公式的近似解，用迭代公式则有则有 x*=Bx*+f，即，即x*是是(3.2)的解，当然的解，当然x*也就是也就是Ax=b的解的解.1如如何何构构造造迭迭代代公公式式x(k+1)=Bx(k)+f.这这样样的的构构造造形形式式不不止止一一种种，它们各对应一种迭代法它们各对应一种迭代法.2迭代法产生的向量序列迭代法产生的向量序列x(k)的收敛条件是什么，收敛速度如何的收敛条件是什么，收敛速度如何.结束结束 2从以上的讨论中，可以看出，迭代法的关键有：从以上的讨论中，可以看出

2、，迭代法的关键有：x(k+1)=Bx(k)+f,(k=0,1,2,)(3.3)产生一个向量序列产生一个向量序列x(k)，若，若第2页，共23页，编辑于2022年，星期二先看一个算例：先看一个算例：按下式进行迭代按下式进行迭代 (k=0,1,2,)结束结束 33.2 3.2 几种常用的迭代法公式几种常用的迭代法公式例例1 3.2.1 Jacobi3.2.1 Jacobi迭代法迭代法从以上三个方程中分别解出从以上三个方程中分别解出x1,x2,x3第3页，共23页，编辑于2022年，星期二 任任取取一一初初始始向向量量，例例如如x(0)=(0,0,0)T，得得 到到 迭迭 代代 序序 列列 x(k)

3、(k=0,1,2,)，列表如下表，列表如下表3-1。容容易易验验证证，原原方方程程组组的的精精确确解解为为 x=(1,2,3)T，从从上上面面的的计计算算可可看看出，出，x(k)收敛于精确解收敛于精确解.一般说来，对方程组：一般说来，对方程组：设设aii0(i=1,2,n)，从第，从第i个方程解出个方程解出xi，得等价的方程组：，得等价的方程组：k012345678x100.30000.80000.91800.97160.98040.99620.99850.9998x201.50001.76001.92601.97001.98971.99611.99861.9998x302.00002.660

4、02.95402.95402.98232.99382.99772.9997结束结束 4第4页，共23页，编辑于2022年，星期二迭代公式为：迭代公式为：i=1,2,n (3.5)(3.6)这这种种迭迭代代形形式式称称为为Jacobi迭迭代代法法(雅雅可可比比迭迭代代法法)，也也称称简简单单迭迭代代法法.Jacobi迭代法的矩阵迭代形式迭代法的矩阵迭代形式:(推导推导)结束结束 5其中其中第5页，共23页，编辑于2022年，星期二3.2.2 Gauss-Seidel 3.2.2 Gauss-Seidel 迭代法迭代法 在在Jacobi迭代法的迭代形式迭代法的迭代形式(3.6)中，可以看出，在计算

5、中，可以看出，在计算 时，要使用时，要使用 .但此时但此时 已计算出来已计算出来.看来此时可提前使看来此时可提前使用用 代替代替 ，一般地，计算，一般地，计算 (ni2)时，使时，使用用 代代替替 (i p1)，这这样样可可能能收收敛敛会会快快一一些些，这这就就形形成成一一种种新新的的迭代法，称为迭代法，称为Gauss-Seidel迭代法。迭代法。例例2 2 用用 Gauss-Seidel 迭代法计算例迭代法计算例1并作比较并作比较.(k=0,1,2,)结束结束 6解解 迭代公式为：迭代公式为：第6页，共23页，编辑于2022年，星期二用它计算得到的序列用它计算得到的序列x(k)列表如表列表如

6、表3-2：可见它对这一方程组比可见它对这一方程组比Jacobi迭代法收敛快一些。迭代法收敛快一些。Gauss-Seidel迭代法的公式如下：迭代法的公式如下：(3.9)Gauss-Seidel迭代法的矩阵迭代形式：迭代法的矩阵迭代形式：（推导推导）k0123456x100.30000.88040.98430.99780.99971.0000 x201.50001.94481.99221.99891.99982.0000 x302.68402.95392.99382.99912.99993.0000结束结束 7其中其中第7页，共23页，编辑于2022年，星期二SOR迭代法也称为逐次超松弛法，它可

7、看成迭代法也称为逐次超松弛法，它可看成Gauss-Seidel迭代法的加迭代法的加速，速，Gauss-Seidel迭代法是迭代法是SOR迭代法的特例迭代法的特例.改写为改写为结束结束 83.2.3 SOR3.2.3 SOR迭代法迭代法将将Gauss-Seidel迭代法的迭代法的(3.9)式式记记则则第8页，共23页，编辑于2022年，星期二为加快收敛，在增量为加快收敛，在增量 前加一个因子前加一个因子 ,得得称此公式为称此公式为SOR法法(逐次超松弛法逐次超松弛法).从从(3.13)式不难推出式不难推出SOR法的矩阵迭代形式：法的矩阵迭代形式：今后可以看到，必须取今后可以看到，必须取02，当，

8、当=1时时,就是就是Gauss-Seidel迭代法迭代法.当当取得适当时，对取得适当时，对Gauss-Seidel迭代法有加速效果迭代法有加速效果.结束结束 9其中其中改写为改写为第9页，共23页，编辑于2022年，星期二例例3 3 用用Gauss-Seidel迭代法和取迭代法和取=1.45的的SOR法计算下列方程组的解，法计算下列方程组的解，当当 时退出迭代，初值取时退出迭代，初值取x(0)=(1,1,1)T。由表由表-和表和表-可见，达到同样的精度可见，达到同样的精度Gauss-Seidel迭代法要迭代法要72步，而步，而取取=1.45的的SOR法只要法只要25步，可见当松弛因子选择适当时

9、，步，可见当松弛因子选择适当时，SOR法有明显加速收敛作用，它常用于求解大型线性方程组。法有明显加速收敛作用，它常用于求解大型线性方程组。结束结束 10第10页，共23页，编辑于2022年，星期二3.3 3.3 迭代法的一般形式的收敛条件迭代法的一般形式的收敛条件定理定理3.13.1 对任意初始向量对任意初始向量x(0)和和 f,由上式产生的迭代序列由上式产生的迭代序列x(k)收敛的充收敛的充要条件是要条件是(B)1.3.3.1 3.3.1 一般迭代过程一般迭代过程 的收敛的收敛条件条件.结束结束 11证证:1)必要性：必要性：x(k)收敛收敛于于 x*,有有x*=Bx*+f 成立成立,记记

10、k=x(k)-x*有有 k+1=x(k+1)-x*=Bx(k)+f-Bx*-f=B(x(k)-x*)=B k有有 k+1=B k=B2 k-1=Bk+1 0,这里这里 0=x(0)-x*,对任意的对任意的 x(0),0=x(0)-x*也是任意的也是任意的,因此要有因此要有 Bk+1 00 (k),必须有必须有Bk0 (k)由上章定理由上章定理2.8,必有必有 (B)1.第11页，共23页，编辑于2022年，星期二2)充分充分性：性：定理定理3.1是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况的情况.但由于但由于(B)的计算

11、往往比解方程组本身更困难，所以本定理在理的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义论上的意义大于在实用上的意义.结束结束 12从上面的定理可以看到从上面的定理可以看到,迭代法的收敛与否与迭代法的收敛与否与B的性态有关，而与的性态有关，而与初始向量初始向量x(0)和右端向量和右端向量 f 无关无关.由于由于(B)难于计算，而由定理难于计算，而由定理2.7有有(B)|B|，|B|1时时,必有必有(B)1，于是得到：，于是得到：设设 (B)1,则则1不是不是B的特征值的特征值,有有|I-B|0,于是于是(I-B)x=f 有唯一解有唯一解,记为记为x*,即有即有 x*=

12、Bx*+f 成立成立,则则 k+1=B(x(k)-x*)=B k 仍成立仍成立,k+1=B k+1 0 仍成立仍成立,因此因此 k+1 0 (k)成立成立,也即是也即是 x(k)x*(k)由上章定理由上章定理2.8,由由 (B)1,可得可得 Bk+1 0 (k)成立成立,第12页，共23页，编辑于2022年，星期二定理定理3.23.2 若若|B|=q1，则由迭代格式，则由迭代格式x(k+1)=Bx(k)+f 和任意初始向量和任意初始向量x(0)产产生的迭代序列生的迭代序列x(k)收敛于准确解收敛于准确解x*.本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当本定理是迭代法收敛的充分条件，它

13、只能判别收敛的情况，当|B|1时时,不能断定迭代不收敛不能断定迭代不收敛.但由于但由于|B|,特别是特别是|B|1和和|B|的计算比较容易，的计算比较容易，也不失为一种判别收敛的方法。也不失为一种判别收敛的方法。利用此定理可以在只计算出利用此定理可以在只计算出x(1)时，就估计迭代次数时，就估计迭代次数k，但估，但估计偏保守，次数偏大计偏保守，次数偏大.称为事前误差估计称为事前误差估计.定理定理3.33.3 若若|B|=q1，则迭代格式，则迭代格式x(k+1)=Bx(k)+f产生的向量序列产生的向量序列 x(k)中中结束结束 13同时当同时当|B|1时可以用来估计迭代的次数，或用来设置退出计算

14、的条时可以用来估计迭代的次数，或用来设置退出计算的条件件.这时有定理这时有定理3.3和定理和定理3.4第13页，共23页，编辑于2022年，星期二例例4 4 就例就例1中的系数阵中的系数阵A1和例和例3中的系数阵中的系数阵A2讨论讨论Jacobi迭代法和迭代法和Gauss-Seidel迭代法的收敛性迭代法的收敛性.因为因为|BJ|=0.61，由定理，由定理3.2知知Jacobi迭代法收敛。迭代法收敛。解解：1）就）就A1讨论讨论结束结束 14定理定理3.43.4 若若|B|=q1，则，则x(k)的第的第k次近似值的近似程度有如下估计式：次近似值的近似程度有如下估计式：本定理可用于程序中设置退出

15、条件，即只要相邻两次的迭代结果本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小之差足够小时，迭代向量对精确解的误差也足够小.称为事后误差称为事后误差估计估计.第14页，共23页，编辑于2022年，星期二用定理用定理3.2无法判断无法判断Jacobi迭代法收敛性，现计算迭代法收敛性，现计算(BJ)。2）就）就A2讨论讨论解之有三实根：解之有三实根：1=0.9207,2=-0.2846,3=-0.6361.所以所以(BJ)=0.92071，故，故Jacobi迭代法收敛迭代法收敛.结束结束 15因为因为|BS|=0.31，由定理，由定理3.2知知G

16、auss-Seidel迭代法收敛。迭代法收敛。第15页，共23页，编辑于2022年，星期二|BS|=0.875，故，故Gauss-Seidel迭代法收敛迭代法收敛.3.3.2 3.3.2 从矩阵从矩阵 A 判断收敛的条件判断收敛的条件下下面面讨讨论论直直接接由由矩矩阵阵 A 的的性性态态,判判定定 Ax=b 使使用用迭迭代代法法是是否否收收敛敛.讨讨论前必须先介绍几个概念：论前必须先介绍几个概念：1对角优势对角优势 若若 A=(aij)nn 满足满足且至少有一个且至少有一个I 值，使值，使 成立成立,称称A具有对角优势；具有对角优势；结束结束 16第16页，共23页，编辑于2022年，星期二若

17、若 称称A具有严格对角优势具有严格对角优势.定理定理3 3.5 5 若若 A 具有严格对角优势，则具有严格对角优势，则A非奇异。非奇异。定理定理3 3.6 6 A不可约，且具有对角优势，则不可约，且具有对角优势，则A非奇异非奇异.结束结束 172不可约不可约 如果矩阵如果矩阵 A 能通过行对换和相应的列对换，变成：能通过行对换和相应的列对换，变成：矩阵矩阵 A是否可约是不易判别的，但以下两条准则比较常用是否可约是不易判别的，但以下两条准则比较常用:A没有零元素或零元素太少没有零元素或零元素太少(少于少于n-1)时不可约时不可约;三对角阵如果三条对角线上的元素都不为零时不可约三对角阵如果三条对角

18、线上的元素都不为零时不可约.的形式的形式,其中其中 A11 和和 A22 为方阵为方阵,则称则称 A可约可约,反之称反之称 A 不可约不可约.第17页，共23页，编辑于2022年，星期二例例5 用用定定理理3.7检检验验例例1中中方方程程组组的的矩矩阵阵A，判判断断该该方方程程组组用用迭迭代代法法时时是否收敛？是否收敛？解解 因为因为10 -2+-1，10 -2+-1，5 -1+-2，结束结束 18定定理理3 3.7 7 A 具具有有严严格格对对角角优优势势或或 A 不不可可约约且且具具有有对对角角优优势势，则则Jacobi迭代法和迭代法和Gauss-Seidel迭代法都收敛迭代法都收敛.证明

19、证明所以所以A具有严格对角优势，具有严格对角优势，该方程组用该方程组用Jacobi迭代法和迭代法和Gauss-Seidel迭迭代法时收敛代法时收敛.第18页，共23页，编辑于2022年，星期二定理定理3.83.8 逐次超松弛法收敛的必要条件是逐次超松弛法收敛的必要条件是02.定理定理3.93.9 如果如果A实实对称正定对称正定，且，且02，则，则SOR法收敛法收敛.推论推论:当当A实对称正定时，实对称正定时，Ax=b 使用使用Gauss-Seidel迭代法收敛迭代法收敛.注意注意A实实对称正定对称正定时时,Jacobi 法并不一定收敛法并不一定收敛，这时有结论，这时有结论:定理定理3.103.

20、10 如果如果A实对称实对称,且对角元全为正且对角元全为正,且且A 和和 2D-A 均正定，均正定，则则Jacobi 迭代法迭代法收敛收敛.第19页，共23页，编辑于2022年，星期二可见即使有估计公式，计算可见即使有估计公式，计算(B)也是困难的，一般采取试算方法确也是困难的，一般采取试算方法确定定.加速收敛的效果也随问题而异加速收敛的效果也随问题而异,对有的问题可加速好几十倍，甚至对有的问题可加速好几十倍，甚至更多，对有的问题则加速不明显更多，对有的问题则加速不明显.结束结束 20最后提一下关于最后提一下关于的选取，的选取，的选取影响的选取影响(B)的大小，使的大小，使(B)最小最小的的值

21、称为最佳松弛因子，记为值称为最佳松弛因子，记为opt .opt的选取是一个复杂问题，尚的选取是一个复杂问题，尚无完善结果无完善结果,只有针对一些特殊矩阵的结果，比如只有针对一些特殊矩阵的结果，比如定理定理3.11 如如A对称正定，且是三对角阵，则对称正定，且是三对角阵，则其中其中BJ 是是Jacobi迭代法的迭代矩阵迭代法的迭代矩阵.第20页，共23页，编辑于2022年，星期二所以所以Ax=b对对Gauss-Seidel迭代法及迭代法及SOR法法(0 2)都收敛，都收敛，(定理定理3.9及推论及推论)；例例6若方程组的系数阵如下：试判断它对各种迭代法的收敛性若方程组的系数阵如下：试判断它对各种

22、迭代法的收敛性.解解结束结束 21Ax=b对称对称,且且所以所以 A 正定正定,第21页，共23页，编辑于2022年，星期二 2222结束结束所以对所以对Jacobi迭代法不收敛迭代法不收敛.但但A不是对角占优阵，无法判断不是对角占优阵，无法判断Jacobi迭代法收敛性，求迭代法收敛性，求(BJ)第22页，共23页，编辑于2022年，星期二判断收敛是本章的重点，所以要熟练掌握。应按如下顺序使用定理：判断收敛是本章的重点，所以要熟练掌握。应按如下顺序使用定理：）定理）定理3.7；）定理）定理3.9及推论；及推论；）计算）计算|B|,应用定理应用定理3.2；）计算）计算(B);应用定理应用定理3.1.第23页，共23页，编辑于2022年，星期二