线性方程组的简单迭代法精品文稿.ppt

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

1、线性方程组的简单迭代线性方程组的简单迭代法法第1页，本讲稿共32页n n引言引言3.1 3.1 简单迭代法简单迭代法 考虑线性方程组（1.1）其中 为非奇异矩阵，当 为低阶稠密矩阵时，第2章所讨论的选主元消去法是有效方法.但对于 的阶数 很大，零元素较多的大型稀疏矩阵大型稀疏矩阵方程组，利用迭代法求解则更为合适.迭代法通常都可利用迭代法通常都可利用 中有大量零元素的特点中有大量零元素的特点.第2页，本讲稿共32页两个简单的例子两个简单的例子例例1 1 已知已知 ，任取，任取 ，则由，则由 例例2 2 已知方程已知方程 在在 附近有根附近有根.那么我们就能从那么我们就能从 开始，通过迭代公式开始

2、，通过迭代公式 逐步得到所要求的根逐步得到所要求的根.假定我们已会计算假定我们已会计算第3页，本讲稿共32页 例例1 1求解方程组求解方程组 （1.2）记为 ,方程组的精确解是方程组的精确解是 .其中其中 现将现将(1.2)(1.2)改写为改写为 第4页，本讲稿共32页（1.3）或写为或写为 ,其中其中 第5页，本讲稿共32页 将这些值代入将这些值代入(1.3)(1.3)式右边式右边(若若(1.3)(1.3)式为等式即求得方程组的式为等式即求得方程组的解，但一般不满足解，但一般不满足).).任取初始值，例如取任取初始值，例如取 再将 分量代入(1.3)式右边得到 ，反复利用这个计算程序，得到一

3、向量序列和一般的计算公式(迭代公式迭代公式)得到新的值 第6页，本讲稿共32页（1.4）简写为 其中 表示迭代次数 迭代到第10次有 第7页，本讲稿共32页 从此例看出，由迭代法产生的向量序列 逐步逼近方程组的精确解 .第8页，本讲稿共32页迭代法的基本思想是构造一个向量序列迭代法的基本思想是构造一个向量序列 X X X X(k)(k)(k)(k)，使其收敛，使其收敛到某个极限向量到某个极限向量 X X*，而，而X X*就是就是 AX=AX=b b b b 的准确解。的准确解。问题：如何构造迭代序列？问题：如何构造迭代序列？迭代序列在什么情况下收敛？迭代序列在什么情况下收敛？第9页，本讲稿共3

4、2页简单迭代法的迭代格式简单迭代法的迭代格式n阶线性代数方程组a11x1+a12x2+.+a1nxn=b1a21x1+a22x2+.+a2nxn=b2 an1x1+an2x2+.+annxn=bn若用矩阵和向量的记号来表示，可写成 AX=b b第10页，本讲稿共32页 设 ,并将 写为三部分 迭代矩阵迭代矩阵第11页，本讲稿共32页易知，雅各布（易知，雅各布（JacobiJacobi）迭代有）迭代有A=D-L-UA=D-L-UL+U=D-AG G为迭代矩阵为迭代矩阵第12页，本讲稿共32页第13页，本讲稿共32页 的雅可比(Jacobi)迭代公式如下:研究雅可比迭代法的分量计算公式研究雅可比迭

5、代法的分量计算公式.记 或 第14页，本讲稿共32页于是，解 的雅可比迭代法的分量计算公式为 第15页，本讲稿共32页方程组的迭代式的展开式如下：第16页，本讲稿共32页第17页，本讲稿共32页 由可知计算过程可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和计算一次矩阵和向量的乘法向量的乘法且计算过程中原始矩阵矩阵A A始终不变.第18页，本讲稿共32页例例1 1 用用J J法求解线性方程组法求解线性方程组方程组的精确解为方程组的精确解为方程组的精确解为方程组的精确解为x x x x*=(1,1,1)=(1,1,1)T T.解：解：第19页，本讲稿共32页取初始向量取初始向量x x

6、(0)(0)=(0,0,0)=(0,0,0)T T,迭代可得迭代可得计算结果列表如下:第20页，本讲稿共32页k kx x1 1(k)(k)x x2 2(k)(k)x x3 3(k)(k)xx(k)(k)-x-x*0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 70 01.41.41.111.110.9290.9290.99060.99061.011591.011591.0002511.0002510.99823640.99823640 00.50.51.201.201.0551.0550.96450.96450.99530.995

7、31.0057951.0057951.00012551.00012550 01.41.41.111.110.9290.9290.99060.99061.011591.011591.0002511.0002510.99823640.99823641 10.50.50.20.20.0710.0710.03550.03550.011590.011590.0057950.0057950.00176360.0017636可见可见,迭代迭代7次使得次使得迭代序列逐次迭代序列逐次收敛于方程组的解收敛于方程组的解,。第21页，本讲稿共32页简单迭代法的算法如下：简单迭代法的算法如下：1.输入矩阵 A，右端项

8、b，维数 n，初始迭代向量 X(0),容许误差 e，容许最大迭代次数 N。2.置 k=1。3.对 i=1,2,n4.若 ，输出X，停机，否则转5。5.若 ，转3；否则输出失败信息，停机。第22页，本讲稿共32页 对于任何由 变形得到的等价方程组 ，迭代法产生的向量序列 不一定都能逐步逼近方程组的解 .如对方程组第23页，本讲稿共32页n n一般迭代法收敛性的基本定理迭代法的收敛性迭代法的收敛性 设 其中 为非奇异矩阵，记 为精确解，于是 且设有等价的方程组（2.1）第24页，本讲稿共32页 设有解 的迭代法 问题是：迭代矩阵 满足什么条件时，由迭代法产生的向量序列 收敛到 引进误差向量 由(2

9、.1)式减(2.2)式得到误差向量的递推公式（2.2）第25页，本讲稿共32页因此，研究迭代法(2.2)收敛性问题就是要研究迭代矩阵 满足什么条件时，有 设有矩阵序列 ,如果 个数列极限存在且有 则称 收敛于 ，记为 定义定义1第26页，本讲稿共32页 定理定理1 1（2.3）(迭代法基本定理)设有方程组 及一阶定常迭代法（2.4）对任意选取初始向量 ，矩阵 的谱半径 迭代法(2.4)收敛的充要条件是 所谓所谓“谱半径谱半径”，就是最大特征值（对于实数而言），就是最大特征值（对于实数而言）,如果是特征值是复数的话，谱半径就是特征值的最大模。如果是特征值是复数的话，谱半径就是特征值的最大模。第2

10、7页，本讲稿共32页 推论推论设 ，其中 为非奇异矩阵且 非奇异，则 (1)解方程组的雅可比迭代法收敛的充要条件是 ，其中 定义定义2 2：若n阶矩阵A A=(aij)满足:则称矩阵A A是严格对角占优矩阵严格对角占优矩阵.定理定理2 2 设设A A是严格对角占优矩阵是严格对角占优矩阵,则解线性方程组则解线性方程组Ax=bAx=b的的J J迭代法收敛迭代法收敛.第28页，本讲稿共32页计算机实现程序计算机实现程序n n用雅各比迭代法下面线性方程组 第29页，本讲稿共32页#include#include#include#include#include#include#include#inclu

11、de#define eps 1e-3#define eps 1e-3#define eps 1e-3#define eps 1e-3#define max 100#define max 100#define max 100#define max 100void Jacobi(float*a,int n,float x)void Jacobi(float*a,int n,float x)void Jacobi(float*a,int n,float x)void Jacobi(float*a,int n,float x)int i,j,k=0;int i,j,k=0;int i,j,k=0;in

12、t i,j,k=0;double epsilon,s;double epsilon,s;double epsilon,s;double epsilon,s;double*y=new doublen;double*y=new doublen;double*y=new doublen;double*y=new doublen;for(i=0;in;i+)xi=0;for(i=0;in;i+)xi=0;for(i=0;in;i+)xi=0;for(i=0;in;i+)xi=0;while(1)while(1)while(1)while(1)epsilon=0;epsilon=0;epsilon=0;

13、epsilon=0;k+;k+;k+;k+;for(i=0;in;i+)for(i=0;in;i+)for(i=0;in;i+)for(i=0;in;i+)s=0;s=0;s=0;s=0;for(j=0;jn;j+)for(j=0;jn;j+)for(j=0;jn;j+)for(j=0;jn;j+)if(j=i)continue;if(j=i)continue;if(j=i)continue;if(j=i)continue;s+=*(a+i*(n+1)+j)*xj;s+=*(a+i*(n+1)+j)*xj;s+=*(a+i*(n+1)+j)*xj;s+=*(a+i*(n+1)+j)*xj;yi

14、=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);epsilon+=fabs(yi-xi);epsilon+=fabs(yi-xi);epsilon+=fabs(yi-xi);epsilon+=fabs(yi-xi);for(i=0;in;i+)xi=yi;for(i=0;in;i+)xi=yi;for(i=0;in;i+)xi=yi;for(i=

15、0;in;i+)xi=yi;if(epsiloneps)if(epsiloneps)if(epsiloneps)if(epsilon=max)if(k=max)if(k=max)if(k=max)printf(printf(printf(printf(迭代发散迭代发散迭代发散迭代发散);return;);return;);return;);return;delete y;delete y;delete y;delete y;第30页，本讲稿共32页void main()int i;float a45=10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,

16、11,25;/*float a910=31,-13,0,0,0,-10,0,0,0,-15,-13,35,-9,0,-11,0,0,0,0,27,0,-9,31,-10,0,0,0,0,0,-23,0,0,-10,79,-30,0,0,0,-9,0,0,0,0,-30,57,-7,0,-5,0,-20,0,0,0,0,7,47,-30,0,0,12,0,0,0,0,0,-30,41,0,0,-7,0,0,0,0,-5,0,0,27,-2,7,0,0,0,0,0,0,0,-2,29,-10;*/float x4;/float x9;Jacobi(a0,4,x);/Jacobi(a0,9,x);for(i=0;i4/*9*/;i+)；printf(x%d=%fn,i,xi);第31页，本讲稿共32页n n作业题:P104 1第32页，本讲稿共32页