数值计算方法-第6章解线性方程组的迭代法.ppt

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

1、数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS第6章 解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在n比较小的时候还比较合适（n400），但是对于现在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是系数矩阵就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一个

2、等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS对方程组 做等价变换如：令，则则，我们可以构造序列若同时：所以，序列收敛与初值的选取无关数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS定义6.1：（收敛矩阵）定理：矩阵G为收敛矩阵，当且仅当G的谱半径1由 知，若有某种范数 则，迭代收敛数 学 系University of Scienc

3、e and Technology of ChinaDEPARTMENT OF MATHEMATICS6.1 Jacobi 迭代数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS格式很简单：数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSJacobi迭代算法1、输入系数矩阵A和向量b，和误差控制eps2、x1=0,0,.,0,x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)x1

4、=x2;for(i=0;in;i+)x2i=0;for(j=0;ji;j+)x2i+=Aij*x1j for(j=i+1;jn;j+)x2i+=Aij*x1j x2i=-(x2i-bi)/Aii 4、输出解x2数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 迭代矩阵记数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS易知，Jacobi迭代有数 学 系University of Science

5、and Technology of ChinaDEPARTMENT OF MATHEMATICS 收敛条件 迭代格式收敛的充要条件是G的谱半径1。对于Jacobi迭代，我们有一些保证收敛的充分条件定理：若A满足下列条件之一，则Jacobi迭代收敛。A为行对角占优阵 A为列对角占优阵 A满足数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS证明：A为列对角占优阵，则AT为行对角占优阵，有证毕数 学 系University of Science and Technology of ChinaDEPA

6、RTMENT OF MATHEMATICS6.2 Gauss Seidel 迭代在Jacobi迭代中，使用最新计算出的分量值数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSGauss-Siedel迭代算法1、输入系数矩阵A和向量b，和误差控制eps2、x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)for(i=0;in;i+)for(j=0;ji;j+)x2i+=Aij*x2j for(j=i+1;jn;j+)x2i+=Aij*x2j x2i=-(x2i-bi)/Aii 4

7、、输出解x2数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 迭代矩阵是否是原来的方程的解？A=(D-L)-U数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 收敛条件 迭代格式收敛的充要条件是G的谱半径1。我们看一些充分条件定理：若A满足下列条件之一，则Jacobi迭代收敛。A为行或列对角占优阵 A对称正定阵数 学 系University of Science and Technology

8、of ChinaDEPARTMENT OF MATHEMATICS证明：设G的特征多项式为，则为对角占优阵，则 时 为对角占优阵即即证毕注：注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel 法收敛时，Jacobi 法可能不收敛；而Jacobi 法收敛时，Gauss-Seidel 法也可能不收敛。数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS1、预处理2、格式数 学 系University of Science and Technology of ChinaDEPARTMEN

9、T OF MATHEMATICS3、结果数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS1、Jacobi迭代特征值为2、GaussSiedel迭代数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS6.3 松弛迭代记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有对GaussSeidel迭代格式数 学 系University of Science and Technology of

10、ChinaDEPARTMENT OF MATHEMATICS写成分量形式，有数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS松弛迭代算法1、输入系数矩阵A、向量b和松弛因子omega，和误差控制eps2、x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)for(i=0;in;i+)temp-0 for(j=0;ji;j+)temp+=Aij*x2j for(j=i+1;jn;j+)temp+=Aij*x2j temp=-(x2i-bi)/Aii x2i=(1-omega)*x

11、2i+omega*temp 4、输出解x2数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 迭代矩阵定理：松弛迭代收敛定理：A对称正定，则松弛迭代收敛是否是原来的方程的解？数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使()达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经

12、验上可取1.41.6.数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 定理 若SOR方法收敛,则02.证 设SOR方法收敛,则()1,所以|det()|=|12 n|1而 det()=det(D-L)-1(1-)D+U)=det(E-D-1L)-1 det(1-)E+D-1U)=(1-)n于是|1-|1,或 0 2数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 定理 设A是对称正定矩阵,则

13、解方程组Ax=b的SOR方法,当02时收敛.证 设是的任一特征值,y是对应的特征向量,则(1-)D+Uy=(D-L)y于是(1-)(Dy,y)+(Uy,y)=(Dy,y)-(Ly,y)数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS由于A=D-L-U是对称正定的,所以D是正定矩阵,且L=UT.若记(Ly,y)=+i,则有(Dy,y)=0(Uy,y)=(y,Ly)=(Ly,y)=-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2 所以数 学 系University of Sci

14、ence and Technology of ChinaDEPARTMENT OF MATHEMATICS当0 2时,有(-+)2-(-)2=(2-)(2-)=(2-)(2-)0所以|21,因此()1,即S0R方法收敛.可得=2/设是B的任一特征值,y是对应的特征向量,则(L+U)y=Dy于是(Ly,y)+(Uy,y)=(Dy,y)数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS当A对称正定时,即2-0时,|0而(2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2 即,当A对称正定时,Jacobi迭代法收敛 2D-A正定.