线性方程组的简单迭代法省名师优质课赛课获奖课件市赛课一等奖课件.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,第三章 求解线性方程组迭代方法,年11月13日,第1页,引言,3.1 简单迭代法,考虑线性方程组,（1.1）,其中,为非奇异矩阵，当 为低阶稠密矩阵时，第2章所讨,论选主元消去法是有效方法.,但对于 阶数 很大，零元素较多,大型稀疏矩阵,方程组，利用迭代法求解则更为适当.,迭代法通常都可利用 中有大量零元素特点.,第2页,两个简单例子,例1,已知,，任取,，则由,例2,已知方程,在,附近有根.,那么我们就能从,开始，经过迭代公式,逐步得到所要求根.,假定我们已会计算,第3页,例1,求解方程组,（1.2）,记为 ,方程组准确解是 .,其中,现将(1.2)改写为,第4页,（1.3）,或写为 ,其中,第5页,将这些值代入(1.3)式右边(若(1.3)式为等式即求得方程组解，但普通不满足).,任取初始值，比如取,再将 分量代入(1.3)式右边得到 ，重复利用这个计,算程序，得到一向量序列和普通计算公式,(迭代公式),得到新值,第6页,（1.4）,简写为,其中 表示迭代次数,迭代到第10次有,第7页,从此例看出，由迭代法产生向量序列 逐步迫近,方程组准确解 .,第8页,迭代法基本思想是结构一个向量序列,X,(k),，使其收敛到某个极限向量 X,*,，而X,*,就是,AX=,b,准确解。,问题：怎样结构迭代序列？,迭代序列在什么情况下收敛？,第9页,简单迭代法迭代格式,n阶线性代数方程组,a,11,x,1,+a,12,x,2,+.+a,1n,x,n,=b,1,a,21,x,1,+a,22,x,2,+.+a,2n,x,n,=b,2,a,n1,x,1,+a,n2,x,2,+.+a,nn,x,n,=b,n,若用矩阵和向量记号来表示，可写成,AX=,b,第10页,设 ,并将 写为三部分,迭代矩阵,第11页,易知，雅各布（Jacobi）迭代有,A=D-L-U,L+U=D-A,G为迭代矩阵,第12页,第13页,雅可比(Jacobi)迭代公式以下:,研究雅可比迭代法分量计算公式.,记,或,第14页,于是，解 雅可比迭代法分量计算公式为,第15页,方程组,迭代式展开式以下：,第16页,第17页,由可知计算过程可知，雅可比迭代法计算,公式简单，每迭代一次只需,计算一次矩阵和,向量乘法,且计算过程中原始,矩阵A,一直不变.,第18页,例1,用J法求解线性方程组,方程组准确解为x,*,=(1,1,1),T,.,解：,第19页,取初始向量x,(0),=(0,0,0),T,迭代可得,计算结果列表以下:,第20页,k,x,1,(k),x,2,(k),x,3,(k),x,(k),-x,*,0,1,2,3,4,5,6,7,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,0,0.5,1.20,1.055,0.9645,0.9953,1.005795,1.0001255,0,1.4,1.11,0.929,0.9906,1.01159,1.000251,0.9982364,1,0.5,0.2,0.071,0.0355,0.01159,0.005795,0.0017636,可见,迭代7次使得,迭代序列逐次,收敛于方程组解,。,第21页,简单迭代法算法以下：,输入矩阵 A，右端项 b，维数 n，初始迭代向量 X,(0),允许误差,e，允许最大迭代次数,N。,置 k=1。,对 i=1,2,n,若 ，输出X，停机，不然转5。,若 ，转3；不然输出失败信息，停机。,第22页,对于任何由 变形得到等价方程组 ，,迭代法产生向量序列 不一定都能逐步迫近方程组,解 .,如对方程组,第23页,普通迭代法收敛性基本定理,迭代法收敛性,设,其中 为非奇异矩阵，,记 为准确解，,于是,且设有等价方程组,（2.1）,第24页,设有解 迭代法,问题是：迭代矩阵 满足什么条件时，由迭代法产生,向量序列 收敛到,引进误差向量,由(2.1)式减(2.2)式得到误差向量递推公式,（2.2）,第25页,所以，研究迭代法(2.2)收敛性问题就是要研究迭代矩阵 满足什么条件时，有,设有矩阵序列 ,假如 个数列极限存在且有,则称 收敛于 ，,记为,定义1,第26页,定理1,（2.3）,(迭代法基本定理),设有方程组,及一阶定常迭代法,（2.4）,对任意选取初始向量 ，,矩阵 谱半径,迭代法(2.4)收敛充要条件是,所谓“谱半径”，就是最大特征值（对于实数而言）,假如是特征值是复数话，谱半径就是特征值最大模。,第27页,推论,设 ，,其中 为非奇异矩阵,且 非奇异，则,(1)解方程组雅可比迭代法收敛充要条件是 ，,其中,定义2：,若n阶矩阵,A,=(a,ij,)满足:,则称矩阵,A,是,严格对角占优矩阵.,定理2,设A是严格对角占优矩阵,则解线性方程组Ax=bJ迭代法收敛.,第28页,计算机实现程序,用雅各比迭代法下面线性方程组,第29页,#include,#include,#define eps 1e-3,#define max 100,void Jacobi(float*a,int n,float x),int i,j,k=0;,double epsilon,s;,double*y=new doublen;,for(i=0;in;i+)xi=0;,while(1),epsilon=0;,k+;,for(i=0;in;i+),s=0;,for(j=0;jn;j+),if(j=i)continue;,s+=*(a+i*(n+1)+j)*xj;,yi=(*(a+i*(n+1)+n)-s)/(*(a+i*(n+1)+i);,epsilon+=fabs(yi-xi);,for(i=0;in;i+)xi=yi;,if(epsilon=max),printf(迭代发散);return;,delete y;,第30页,void main(),int i;,float a45=10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,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页,作业题:P104 1,第32页,