《第二章解线性方程组的迭代法省公共课一等奖全国赛课获奖课件.pptx》由会员分享，可在线阅读，更多相关《第二章解线性方程组的迭代法省公共课一等奖全国赛课获奖课件.pptx（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学解线性方程组迭代法 直接法得到解是理论上准确，不过它们计算量都是n3数量级，存放量为n2量级，这在n比较小时候还比较适当（n400），不过在很多实际问题中，我们要求解方程组n很大，而系数矩阵中含有大量0元素。对于这类矩阵，在用直接法时就会花费大量时间和存放单元。所以我们有必要引入一类新方法：迭代法。迭代法是一个逐次迫近方法，其基本思想是：使用某个固定公式，对解近似值进行重复校正，从而得到一个近似解序列，使之收敛于方程组解。迭代法含
2、有算法简单、运算速度快特点。但这种方法取得是方程组解近似值。第1页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学对方程组做等价变换从某一初值 x(0)出发，我们能够结构序列若同时：所以，序列收敛与初值选取无关与初值选取无关如令A=D-L-U，于是 x=D-1(L+U)x+D-1b,第2页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学定义5.1：设G为n阶方阵
3、，若Gk0，则称G为收敛矩阵定理：即矩阵G为收敛矩阵，当且仅当G谱半径1由知，若有某种范数则，迭代收敛第3页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学迭代法收敛性迭代法收敛性定理定理：迭代法X(m+1)=GX(m)+g 收敛充分必要条件是迭代矩阵G为收敛矩阵，即G谱半径(G)1。定理定理：迭代法X(m+1)=GX(m)+g 迭代矩阵G某种范数|G|qeps)x1=x2;for(i=0;i=n;i+)x2i=0;for(j=0;ji;j+)x2i+=Aij*x1j for(
4、j=i+1;j1.Jacobi迭代不收敛。迭代矩阵为G特征值为：1=4.02408,2=-2.01204 3.10115 i,1=4.02408；2,3=3.69668第11页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学将方程组变形，化为：第12页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学G谱半径(G)=0.308507 1.Jacobi迭代收敛。此时
5、迭代矩阵为G特征值分别为：0.308507,-0.154254+0.18304 i,-0.154254-0.18304 i第13页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 收敛条件收敛条件 迭代格式收敛充要条件是G谱半径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、输出解x2Gauss-Siedel迭代算法第17页理学院Unive
6、rsity of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 迭代矩阵迭代矩阵是否是原来方程解？A=(D-L)-UGauss-Siedel迭代法收敛性迭代法收敛性第18页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 收敛条件收敛条件 迭代格式X=GX+g 对任意初值X0和向量g，收敛充要条件充要条件是G谱半径 (G)1.Jacobi迭代不收敛。G谱半径(G)=0.5eps)for(i=
7、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)*x2i+omega*temp 4、输出解x2第30页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 迭代矩阵迭代矩阵定理：松弛迭代收敛定理：A对称正定，则松弛迭代收敛是否是原来方程解？第31页理学院University of Shanghai for Science
8、and TechnologyCollege of Science 上海理工大学上海理工大学 SORSOR方法收敛快慢与松弛因子选择有亲密关系.不过怎样选取最正确松弛因子,即选取=*,使(G)到达最小,是一个还未很好处理问题.实际上可采取试算方法来确定很好松弛因子.经验上可取1.41.6.当松弛因子1时，称该算法为超松弛因子法；第32页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 定理定理 若SORSOR方法收敛,则02.证证 设SORSOR方法收敛,则(G)1,所以|det
9、(G)|=|12 n|1而 det(G)=det(D-L)-1(1-)D+U)=det(E-D-1L)-1det(1-)E+D-1U)=(1-)n于是|1-|1,或 02第33页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学 定理定理 用SORSOR法法解方程组Ax=b，证证 设是G 任一特征值,y是对应特征向量,则 (1-)D+Uy=(D-L)y于是 (1-)(Dy,y)+(Uy,y)=(Dy,y)-(Ly,y)1）若A是对称正定矩阵,则当02时收敛；2）若矩阵A按行(列)
10、严格对角占优,则当00 (Uy,y)=(y,Ly)=(Ly,y)=-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以第35页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学当02时,有 (-+)2-(-)2=(2-)(2-)=(2-)(2-)0所以|21,所以(G)1,即S0R方法收敛.可得 =2/设是B任一特征值,y是对应特征向量,则 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)第36页理学院University of Shangha
11、i for Science and TechnologyCollege of Science 上海理工大学上海理工大学当A对称正定时,即2-0时,|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定.第37页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学共轭梯度法给定对称正定矩阵ARnn，求解方程组AX=b共轭梯度法以下：1.选定初值X(0)Rn,设r(0)=d(0)=b-AX(0);2.r(k+1)=r(k)-(k)A d(k);其中3.d(k+1)=r(k+1)+(k)d(k);其中4.X(k+1)=X(k)+(k)d(k);第38页理学院University of Shanghai for Science and TechnologyCollege of Science 上海理工大学上海理工大学定理：设矩阵ARnn对称正定，X(k)为用共轭梯度法求解方程组AX=b所产生迭代序列，并取条件数那么：1)用不超出n次迭代即可取得准确解；2)对每次迭代结果误差预计为：其中范数|X|A=(AX,X)第39页