《第三章线性方程组的迭代解法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章线性方程组的迭代解法优秀课件.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 线性方程组的迭代解法第1页，本讲稿共23页任取一个向量任取一个向量x(0)作为作为x的近似解，用迭代公式的近似解，用迭代公式则有则有 x*=Bx*+f，即，即x*是是(3.2)的解，当然的解，当然x*也就是也就是Ax=b的解的解.1如如何何构构造造迭迭代代公公式式x(k+1)=Bx(k)+f.这这样样的的构构造造形形式式不不止止一种，它们各对应一种迭代法一种，它们各对应一种迭代法.2迭迭代代法法产产生生的的向向量量序序列列x(k)的的收收敛敛条条件件是是什什么么，收收敛敛速速度如何度如何.结束结束 2从以上的讨论中，可以看出，迭代法的关键有：从以上的讨论中，可以看出，迭代法的关键有：x
2、(k+1)=Bx(k)+f,(k=0,1,2,)(3.3)产生一个向量序列产生一个向量序列x(k)，若若第2页，本讲稿共23页先看一个算例：先看一个算例：按下式进行迭代按下式进行迭代 (k=0,1,2,)结束结束 33.2 3.2 几种常用的迭代法公式几种常用的迭代法公式例例1 3.2.1 Jacobi3.2.1 Jacobi迭代法迭代法从以上三个方程中分别解出从以上三个方程中分别解出x1,x2,x3第3页，本讲稿共23页 任任取取一一初初始始向向量量，例例如如x(0)=(0,0,0)T，得得到到迭迭代代序序列列x(k)(k=0,1,2,)，列表如下表，列表如下表3-1。容容易易验验证证，原原
3、方方程程组组的的精精确确解解为为 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.66002.95402.95402.98232.99382.99772.9997
4、结束结束 4第4页，本讲稿共23页迭代公式为：迭代公式为：i=1,2,n (3.5)(3.6)这这种种迭迭代代形形式式称称为为Jacobi迭迭代代法法(雅雅可可比比迭迭代代法法)，也也称称简简单单迭迭代法代法.Jacobi迭代法的矩阵迭代形式迭代法的矩阵迭代形式:(推导推导)结束结束 5其中其中第5页，本讲稿共23页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页用它计算得到的序列用它计算得到的序列x(k)列表如表列表如表3-2：可见它对这一方程组比可见它对这一方程组比Jacobi迭代法收敛快一些。迭代法收敛快一些。Gauss-Seidel迭代法的公式
6、如下：迭代法的公式如下：(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页SOR迭代法也称为逐次超松弛法，它可看成迭代法也称为逐次超松弛法，它可看成Gauss-Seidel迭代法迭代法的加速，的加速，Gauss-Seidel迭代法是迭代法是SOR迭代法的特例迭代法
7、的特例.改写为改写为结束结束 83.2.3 SOR3.2.3 SOR迭代法迭代法将将Gauss-Seidel迭代法的迭代法的(3.9)式式记记则则第8页，本讲稿共23页为加快收敛，在增量为加快收敛，在增量 前加一个因子前加一个因子 ,得得称此公式为称此公式为SOR法法(逐次超松弛法逐次超松弛法).从从(3.13)式不难推出式不难推出SOR法的矩阵迭代形式：法的矩阵迭代形式：今后可以看到，必须取今后可以看到，必须取02，当，当=1时时,就是就是Gauss-Seidel迭代法迭代法.当当取得适当时，对取得适当时，对Gauss-Seidel迭代法有加速效果迭代法有加速效果.结束结束 9其中其中改写为
8、改写为第9页，本讲稿共23页例例3 3 用用Gauss-Seidel迭代法和取迭代法和取=1.45的的SOR法计算下列方程法计算下列方程组的解，当组的解，当 时退出迭代，初值取时退出迭代，初值取x(0)=(1,1,1)T。由表由表-和表和表-可见，达到同样的精度可见，达到同样的精度Gauss-Seidel迭代法迭代法要要72步，而取步，而取=1.45的的SOR法只要法只要25步，可见当松弛因子选择步，可见当松弛因子选择适当时，适当时，SOR法有明显加速收敛作用，它常用于求解大型线性法有明显加速收敛作用，它常用于求解大型线性方程组。方程组。结束结束 10第10页，本讲稿共23页3.3 3.3 迭
9、代法的一般形式的收敛条件迭代法的一般形式的收敛条件定理定理3.13.1 对任意初始向量对任意初始向量x(0)和和 f,由上式产生的迭代序列由上式产生的迭代序列x(k)收收敛的充要条件是敛的充要条件是(B)1.3.3.1 3.3.1 一般迭代过程一般迭代过程 的收敛的收敛条件条件.结束结束 11证证:1)必要性：必要性：x(k)收敛收敛于于 x*,有有x*=Bx*+f 成立成立,记记 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)
10、,0=x(0)-x*也是任意的也是任意的,因此要有因此要有 Bk+1 00 (k),必须有必须有Bk0 (k)由上章定理由上章定理2.8,必有必有 (B)1.第11页，本讲稿共23页2)充分充分性：性：定理定理3.1是迭代法收敛的基本定理，它不但能判别收敛，也能是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况判别不收敛的情况.但由于但由于(B)的计算往往比解方程组本身更的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义困难，所以本定理在理论上的意义大于在实用上的意义.结束结束 12从上面的定理可以看到从上面的定理可以看到,迭代法的收敛与否与迭代法的收敛与否
11、与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*=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,可
12、得可得 Bk+1 0 (k)成立成立,第12页，本讲稿共23页定理定理3.23.2 若若|B|=q1，则由迭代格式，则由迭代格式x(k+1)=Bx(k)+f 和任意初始和任意初始向量向量x(0)产生的迭代序列产生的迭代序列x(k)收敛于准确解收敛于准确解x*.本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当|B|1时时,不能断定迭代不收敛不能断定迭代不收敛.但由于但由于|B|,特别是特别是|B|1和和|B|的计算比较容易，也不失为一种判别收敛的方法。的计算比较容易，也不失为一种判别收敛的方法。利用此定理可以在只计算出利用此定理可以在只
13、计算出x(1)时，就估计迭代次数时，就估计迭代次数k，但估，但估计偏保守，次数偏大计偏保守，次数偏大.称为事前误差估计称为事前误差估计.定理定理3.33.3 若若|B|=q1，则迭代格式，则迭代格式x(k+1)=Bx(k)+f产生的向量序产生的向量序列列 x(k)中中结束结束 13同时当同时当|B|1时可以用来估计迭代的次数，或用来设置退出计时可以用来估计迭代的次数，或用来设置退出计算的条件算的条件.这时有定理这时有定理3.3和定理和定理3.4第13页，本讲稿共23页例例4 4 就例就例1中的系数阵中的系数阵A1和例和例3中的系数阵中的系数阵A2讨论讨论Jacobi迭代法迭代法和和Gauss-
14、Seidel迭代法的收敛性迭代法的收敛性.因为因为|BJ|=0.61，由定理，由定理3.2知知Jacobi迭代法收敛。迭代法收敛。解解：1）就）就A1讨论讨论结束结束 14定理定理3.43.4 若若|B|=q1，则，则x(k)的第的第k次近似值的近似程度有如下次近似值的近似程度有如下估计式：估计式：本定理可用于程序中设置退出条件，即只要相邻两次的迭代结本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小果之差足够小时，迭代向量对精确解的误差也足够小.称为事后称为事后误差估计误差估计.第14页，本讲稿共23页用定理用定理3.2无法判断无法判断Jac
15、obi迭代法收敛性，现计算迭代法收敛性，现计算(BJ)。2）就）就A2讨论讨论解之有三实根：解之有三实根：1=0.9207,2=-0.2846,3=-0.6361.所以所以(BJ)=0.92071，故，故Jacobi迭代法收敛迭代法收敛.结束结束 15因为因为|BS|=0.31，由定理，由定理3.2知知Gauss-Seidel迭代法收敛。迭代法收敛。第15页，本讲稿共23页|BS|=0.875，故，故Gauss-Seidel迭代法收敛迭代法收敛.3.3.2 3.3.2 从矩阵从矩阵 A 判断收敛的条件判断收敛的条件下下面面讨讨论论直直接接由由矩矩阵阵 A 的的性性态态,判判定定 Ax=b 使使
16、用用迭迭代代法法是是否否收收敛敛.讨论前必须先介绍几个概念：讨论前必须先介绍几个概念：1对角优势对角优势 若若 A=(aij)nn 满足满足且至少有一个且至少有一个I 值，使值，使 成立成立,称称A具有对角优势；具有对角优势；结束结束 16第16页，本讲稿共23页若若 称称A具有严格对角优势具有严格对角优势.定理定理3 3.5 5 若若 A 具有严格对角优势，则具有严格对角优势，则A非奇异。非奇异。定理定理3 3.6 6 A不可约，且具有对角优势，则不可约，且具有对角优势，则A非奇异非奇异.结束结束 172不可约不可约 如果矩阵如果矩阵 A 能通过行对换和相应的列对换，变成：能通过行对换和相应
17、的列对换，变成：矩阵矩阵 A是否可约是不易判别的，但以下两条准则比较常用是否可约是不易判别的，但以下两条准则比较常用:A没有零元素或零元素太少没有零元素或零元素太少(少于少于n-1)时不可约时不可约;三对角阵如果三条对角线上的元素都不为零时不可约三对角阵如果三条对角线上的元素都不为零时不可约.的形式的形式,其中其中 A11 和和 A22 为方阵为方阵,则称则称 A可约可约,反之称反之称 A 不可约不可约.第17页，本讲稿共23页例例5 用用定定理理3.7检检验验例例1中中方方程程组组的的矩矩阵阵A，判判断断该该方方程程组组用用迭代法时是否收敛？迭代法时是否收敛？解解 因为因为10 -2+-1，
18、10 -2+-1，5 -1+-2，结束结束 18定定理理3 3.7 7 A 具具有有严严格格对对角角优优势势或或 A 不不可可约约且且具具有有对对角角优优势势，则则Jacobi迭代法和迭代法和Gauss-Seidel迭代法都收敛迭代法都收敛.证明证明所以所以A具有严格对角优势，具有严格对角优势，该方程组用该方程组用Jacobi迭代法和迭代法和Gauss-Seidel迭代法时收敛迭代法时收敛.第18页，本讲稿共23页定理定理3.83.8 逐次超松弛法收敛的必要条件是逐次超松弛法收敛的必要条件是02.定理定理3.93.9 如果如果A实实对称正定对称正定，且，且02，则，则SOR法收敛法收敛.推论推
19、论:当当A实对称正定时，实对称正定时，Ax=b 使用使用Gauss-Seidel迭代法收敛迭代法收敛.注意注意A实实对称正定对称正定时时,Jacobi 法并不一定收敛法并不一定收敛，这时有结论，这时有结论:定理定理3.103.10 如果如果A实对称实对称,且对角元全为正且对角元全为正,且且A 和和 2D-A 均正定，均正定，则则Jacobi 迭代法迭代法收敛收敛.第19页，本讲稿共23页可见即使有估计公式，计算可见即使有估计公式，计算(B)也是困难的，一般采取试算方也是困难的，一般采取试算方法确定法确定.加速收敛的效果也随问题而异加速收敛的效果也随问题而异,对有的问题可加速好几对有的问题可加速
20、好几十倍，甚至更多，对有的问题则加速不明显十倍，甚至更多，对有的问题则加速不明显.结束结束 20最后提一下关于最后提一下关于的选取，的选取，的选取影响的选取影响(B)的大小，使的大小，使(B)最小的最小的值称为最佳松弛因子，记为值称为最佳松弛因子，记为opt .opt的选取是一个复的选取是一个复杂问题，尚无完善结果杂问题，尚无完善结果,只有针对一些特殊矩阵的结果，比如只有针对一些特殊矩阵的结果，比如定理定理3.11 如如A对称正定，且是三对角阵，则对称正定，且是三对角阵，则其中其中BJ 是是Jacobi迭代法的迭代矩阵迭代法的迭代矩阵.第20页，本讲稿共23页所以所以Ax=b对对Gauss-S
21、eidel迭代法及迭代法及SOR法法(0 2)都收敛，都收敛，(定理定理3.9及推论及推论)；例例6若若方方程程组组的的系系数数阵阵如如下下：试试判判断断它它对对各各种种迭迭代代法法的的收收敛敛性性.解解结束结束 21Ax=b对称对称,且且所以所以 A 正定正定,第21页，本讲稿共23页 2222结束束所以对所以对Jacobi迭代法不收敛迭代法不收敛.但但A不是对角占优阵，无法判断不是对角占优阵，无法判断Jacobi迭代法收敛性，求迭代法收敛性，求(BJ)第22页，本讲稿共23页判断收敛是本章的重点，所以要熟练掌握。应按如下顺序判断收敛是本章的重点，所以要熟练掌握。应按如下顺序使用定理：使用定理：）定理）定理3.7；）定理）定理3.9及推论；及推论；）计算）计算|B|,应用定理应用定理3.2；）计算）计算(B);应用定理应用定理3.1.第23页，本讲稿共23页