解线性方程组的直接方法名师优质课赛课一等奖市公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 解线性方程组直接法,在工程技术、自然科学和社会科学中，经常碰到许多问题最终都可归结为解线性方程组，如用最小二乘法求试验数据曲线拟合问题，工程中三次样条函数插值问题，经济运行中投入产出问题以及大地测量、机械与建筑结构设计计算问题等等，都归结为求解线性方程组(或非线性方程组)数学问题。所以线性方程组求解对于实际问题是极其主要。,第1页,本章讨论n元线性方程组,（2.1）,直接解法。方程组(2.1)矩阵形式为,A,x,=b,其中,第2页,若矩阵,A,非奇异,即det(,A,)0,则方程组(2.1)有唯一解所谓直接解法是指，若不考虑计算过程中舍入误差，经过有限次算术运算就能求出线性方程组准确解方法。,但因为实际计算中舍入误差存在，用直接解法普通也只能求出方程组近似解。,Cramer法则是一个不实用直接法，下面介绍几个实,用直接法。,1 Gauss(高斯)消去法,Gauss,消去法是一个规则化加减消元法，其基本思,想是经过逐次消元计算，把普通线性方程组求解转化为,等价上三角形方程组求解。,1.1 次序Gauss消去法,为了清楚起见,先看一个简单例子.,考虑线性方程组,第3页,消去后两个方程中x,1,得,再消去最终一个方程x,2,得,消元结束,经过回代得解:,第4页,上述求解消元过程可用矩阵表示为:,(,A,b,)=,这是,Gauss,消去法计算形式,新增广矩阵对应线性,方程组就是上三角形方程组,可进行回代求解。,现在介绍求解线性方程组（2.1)次序,Gauss,消去法:,记,则,线性方程组(2.1)增广矩阵为,第5页,第一步.设 ,依次用,乘矩阵第1行加到第i行,得到矩阵:,第6页,其中,第二步.设 ,依次用,乘矩阵第2行加到第i行,得到矩阵:,其中,第7页,如此继续消元下去,第n-1步结束后得到矩阵:,这就完成了消元程。,对应方程组变成：,对此方程组进行回代，就可求出方程组解。,第8页,次序Gauss消去法求解n元线性方程组乘除运算量是,：,+(n-1),2,-1,+2,2,-1n,2,-1 -1,+1+2+n,n=20时,次序Gauss消去法只需3060次乘除法运算.,次序Gauss消去法通常也简称为,Gauss消去法,.,次序Gauss消去法中,称为,主元素,.,主元素都不为零,矩阵,A,各阶次序主子式都不为零.,第9页,1.2 列主元Gauss消去法,(用十进制四位浮点计算):,(用Cramer法则可得准确解x,1,*,=1.00010,x,2,*,=0.99990),解,用次序Gauss消去法,消元得,回代得解:x,2,=1.00,x,1,=0.00,若将方程组改写成:,例1,解线性方程组,第10页,用次序Gauss消去法,消元得,回代得解:x,2,=1.00,x,1,=1.00,为了提升计算数值稳定性,在消元过程中采取选择主元方法.常采取是,列主元消去法,和,全主元消去法,.,给定线性方程组,Ax,=,b,记,A,(1),=,A,b,(1),=,b,列主元Gauss消去法,详细过程以下:,首先在增广矩阵,B,(1),=(,A,(1),b,(1),)第一列元素中,取,然后进行第一步消元得增广矩阵,B,(2),=(,A,(2),b,(2),).,再在矩阵,B,(2),=(,A,(2),b,(2),)第二列元素中,取,第11页,然后进行第二步消元得增广矩阵,B,(3),=(,A,(3),b,(3),),.,按此方法继续进行下去,经过n-1步选主元和消元运算,得到增广矩阵,B,(n),=(,A,(n),b,(n),),.则方程组,A,(n),x,=,b,(n),是与原方程组等价上三角形方程组,可进行回代求解.,易证,只要|,A,|,0,列主元Gauss消去法就可顺利进行.,采取十进制四位浮点计算,分别用次序Gauss消去法和列主元Gauss消去法求解线性方程组:,例2,第12页,方程组含有四位有效数字准确解为,x,1,*,=17.46,x,2,*,=-45.76,x,3,*,=5.546,解 1.,用次序Gauss消去法求解,消元过程为,回代得:x,3,=5.546,x,2,=100.0,x,1,=-104.0,第13页,2.,用列主元Gauss消去法求解,消元过程为,第14页,回代得:x,3,=5.545,x,2,=-45.77,x,1,=17.46,可见，列主元Gauss消去法是在每一步消元前,在主元所在一列选取绝对值最大元素作为主元素.,而全主元Gauss消去法是在每一步消元前,在全部元素中选取绝对值最大元素作为主元素.但因为运算量大增,实际应用中并不经常使用.,第15页,2 矩阵三角分解法,2.1 Gauss消去法矩阵运算,对矩阵,若,令,记,第16页,则有,A,(2),=,记,令,若,则有,第17页,A,(3),=,如此进行下去,第n-1步得到:,A,(n),=,其中,第18页,也就是:,A,(n),=,L,n-1,An-1),其中,=,L,n-1,L,n-2,A,(n-2),=,L,n-1,L,n-2,L,2,L,1,A,(1),第19页,所以有:,A,=,A,(1),=,L,1,-1,L,2,-1,L,n-1,-1,A,(n),=,LU,而且有,其中,L,=,L,1,-1,L,2,-1,L,n-1,-1,U,=,A,(n),.,L,为单位下三角矩阵;,U,是上三角矩阵.,第20页,式,A,=,LU,称为矩阵,A三角分解.,2.2 Doolittle（直接三角）分解法,设n阶方阵,A,各阶次序主子式不为零,则存在唯一单位下三角矩阵,L,和上三角矩阵,U,使,A,=,LU,.,证实,只证唯一性,设有两种分解,A,=,LU,则有,=,E,所以得,于是,Ax,=,b,LUx,=,b,令,Ux,=,y,得,定理2.1,第21页,下面介绍矩阵三角分解Doolittle分解方法,则得,对k=2,3,n,计算,设,a,kj,=,l,k1,u,1j,+,l,k2,u,2j,+,l,kk-1,u,k-1j,+u,kj,a,ik,=,l,i1,u,1k,+,l,i2,u,2k,+,l,ik,u,kk,第22页,第23页,对k=2,3,n,计算,第24页,由,可得,这就是求解方程组,Ax,=,b,Doolittle三角分解方法。,第25页,利用三角分解方法解线性方程组,解,因为,所以,例3,第26页,先解,得,再解,得,解线性方程组,Ax,=,b,Doolittle三角分解法计算量约为（1/3)n,3,与Gauss消去法基本相同.其优点在于求一系列同系数线性方程组,Ax,=,b,k,(k=1,2,m)时,可大大节约运算量.,比如,求上例中矩阵,A,逆矩阵.可分别取常向量,b,1,=(1,0,0),T,b,2,=(0,1,0),T,b,3,=(0,0,1),T,第27页,由,所以,第28页,为了提升数值稳定性,可考虑列主元三角分解法,设已完成,A,=,LU,k-1步分解计算,矩阵分解成,设,令 r,k,r,i,相当于取,为第k步分解主元素.,但要注意方程组常数项也要对应变换.,第29页,比如,用列主元三角分解解例3中方程组.则有,第30页,设,A,为对称正定矩阵,则有唯一分解,A,=,LU,且u,kk,0.,则有,A,=,LDM,又因为 (,LDM,),T,=,M,T,DL,T,=,LDM,所以,M,=,L,T,=,LDL,T,则有,2.3,平 方 根 法,第31页,分解,A,=,GG,T,称为对称正定矩阵,Cholesky分解.,Ax,=,b,转换为,Gy=b,G,T,x,=,y,若记,G,=(g,ij,),则有:对k=1,2,n,实际计算时,可采取紧凑格式,_,平方根法,.,第32页,解三角方程,Gy=b,G,T,x,=,y,可得,解,例4,解线性方程组,第33页,平方根法是求对称正定系数线性方程组三角分解法,对称正定矩阵Cholesky分解计算量和存贮量均约为普通矩阵,LU,分解二分之一.且Cholesky分解含有数值稳定性.,第34页,追赶法是求三对角线性方程组三角分解法.即方程,三对角矩阵,A,各阶次序主子式都不为零一个充分条件是:,|a,1,|c,1,|0;|a,n,|d,n,|0;|a,i,|,|c,i,|+|d,i,|,c,i,d,i,0,i=2,3,n-1.,在此条件下,A,=,LDM,=,TM,称之为矩阵,A,Crout分解.,对三对角矩阵,A,进行Crout分解,有,2.4 追 赶 法,第35页,其中,解三角方程,Ty=b,Mx,=,y,可得,称之为解三对角方程组,追赶法,.,第36页,解,例5,解线性方程组,第37页,当满足条件,|a,1,|c,1,|0;|a,n,|d,n,|0;|a,i,|,|c,i,|+|d,i,|,c,i,d,i,0,i=2,3,n-1.,时,追赶法是数值稳定,追赶法含有计算程序简单,存贮,量少,计算量小优点.,第38页,3 向量和矩阵范数,3.1 向量范数,定义2.1,设,是向量空间R,n,上实值函数,且满足条件:,(1),非负性,:,对任何向量,x,R,n,x,0,且,x,=0当,且仅当,x,=,0,(2),齐次性,:,对任何向量,x,R,n,和实数,x,=|,|,x,(3),三角不等式,:,对任何向量,x,y,Rn,x+y,x,+,y,则称,为空间R,n,上,范数,x,为向量,x范数,.,第39页,记,x,=(x,1,x,2,x,n,),T,惯用向量,范数有:,向量1-范数,:,x,1,=|x,1,|+|x,2,|+|x,n,|,向量2-范数,:,x,2,=,向量,-范数,:,x,=,例6,设向量,x,=(2,-4,3,1),T,求向量,范数,x,p,p=1,2,.,解,由定义,x,1,=10,x,2,=,x,=4.,即使不一样范数值可能不一样，但它们间存在等价关系.,定理2.2,(范数等价性),对于 R,n,上任何两种范数,和,存在正常数m,M,使得,m,x,x,M,x,x,R,n,第40页,惯用三种向量范数满足以下等价关系,x,x,1,n,x,x,R,n,定义2.2,设向量序列,k=1,2,向量,假如,则称,向量序列,x,(k),收敛于向量,x,*,记作,易见,第41页,3.2 矩阵范数,定义2.3,设,是以n阶方阵为变量实值函数,且满足条件:,(1),非负性:,A,0,且,A,=0当且仅当,A,=,0,(2),齐次性,:,A,=|,|,A,R,(3),三角不等式:,A+B,A,+,B,(4),三角不等式,:,AB,A,B,则称,A,为矩阵,A,范数.,记,A,=(a,ij,),惯用矩阵,范数有:,矩阵1-范数,:,A,1,也称矩阵,列范数.,矩阵2-范数,:,A,2,也称为,谱范数第42页,矩阵,-范数,:,A,也称为,行范数.,矩阵,F,-范数,:,A,F,例7,设矩阵,求矩阵,A,范数,A,p,p=1,2,F,.,解,A,1,=4,A,=5,A,F,第43页,设,是一个向量范数,则定义,称之为由向量范数派生,矩阵算子范数,.,矩阵算子范数满足,Ax,A,x,x,R,n,把满足上式矩阵范数称为与,向量范数相容矩阵范数,.,对于p=1,2,矩阵范数,A,p,是由向量范数,x,p,派生矩阵算子范数,所以,A,p,是与,x,p,相容矩阵范数.但,A,F,不是一个算子范数,却与,x,2,是相容.,设,是一个算子范数,则,第44页,矩阵范数与矩阵特征值之间也有亲密联络.,设是矩阵,A,特征值,x,是对应特征向量,则有,Ax,=,x,利用向量和矩阵范数相容性,则得,|,|,x,=,x,=,Ax,A,x,于是|,|,A,设n阶矩阵,A,n个特征值为,1,2,n,则称,为矩阵,A,谱半径,.,对矩阵任何一个相容范数都有,(,A,),A,另外,0,存在一个相容范数,使 ,A,(,A,)+,第45页,任何两种矩阵范数也含有等价性,m,A,A,M,A,A,R,nn,矩阵序列收敛性也定义为,4 线性方程组固有性态与误差分析,4.1 线性方程组固有性态,考虑线性方程组,其准确解为 x*=(-9800b,1,+9900b,2,9900b,1,-10000b,2,),T,第46页若把线性方程组变为,解为x=(-9800b,1,+9900b,2,-19700,9900b,1,-10000b,2,+19900),T,可见 x-x*=(-19700,19900),T,解误差可能放大到常数项误差近2万倍。,若把线性方程组变为,则线性方程组可能无解.,这种因为原始数据微小改变而造成解严重失真线性方程组称为,病态方程组,对应系数矩阵称为,病态矩阵.,第47页,设线性方程组,Ax,=,b,系数矩阵是准确,常数项有误差,b,此时记解为,x,+,x,则,A,(,x,+,x,)=,b,+,b,于是,A,x,=,b,所以,x,=,A,-1,b,A,-1,b,又因为,b,=,Ax,A,x,所以,x,b,A,A,-1,b,x,即,第48页,再设,b,是准确,A,有误差,A,此时记解为,x,+,x,则,(,A,+,A,)(,x,+,x,)=,b,则有,A,x,+,A,(,x,+,x,)=,0,所以,x,=-,A,-1,A,(,x,+,x,),于是,x,A,-1,A,x,+,x,也就是,记 Cond(,A,)=,A,A,-1,称为方程组,Ax,=,b,或矩阵,A,条件数,.,第49页,经常使用条件数有,Cond,p,(,A,)=,A,p,A,-1,p,p=1,，2，。,当,A,为对称矩阵时，有,Cond,2,(,A,)=,|,1,|/|,n,|,其中,1,，,n,分别是,A,按绝对值最大和最小特征值。,比如，对前面方程组系数矩阵,A,有,Cond,1,(,A,)=Cond,(,A,)=39601，Cond,2,(,A,)39206,因为计算条件数运算量较大,实际计算中若碰到下述情况之一,方程组就有可能是病态:,第50页,(1)矩阵元素间数量级差很大,且无一定规律;,(2)矩阵行列式值相对来说很小;,(3)列主元消去法求解过程中出现量级很小主元素;,(4)数值求解过程中,计算解,x,剩下向量,r=b-Ax,已经很小,但,x,仍不符合要求.,4.2 预条件和迭代改进,1.线性方程组预条件处理,对病态方程组,Ax,=,b,考虑线性方程组,其中,第51页,称之为,预条件方程组,显然与原方程组等价.可逆矩阵,C,称为,预条件矩阵,.矩阵,C,应满足条件,(1)条件数,(2)方程组,Cz,=,d,轻易求解。,比Cond(A)显著小.,对于普通矩阵,A,没有十分有效方法去选择预条件矩阵.当,A,是对称正定矩阵时,可取,C .,2.线性方程组解迭代改进,设已求得方程组,Ax,=,b,近似解,x,(1),计算剩下向量,r,(1),=,b-Ax,(1),再求解余量方程组,Ax,=,r,(1),得到解,则,x,(1),迭代改进解为:,第52页,练习题,第50页 习题2,2-2(1),2-6(1)（用二位浮点计算）,第53页,练习题,第50页 习题2,2-3(1),2-4,2-5,2-8,第54页,练习题,第50页 习题2,2-10,2-11,2-12,2-14,2-16,2-17,第55页,课 堂 练 习,1.对矩阵A=进行LU分解.,2.设矩阵A=,求(A)和Cond(A),.,解 1.因为,故 A=,2.因为|A-E|=,2,-3-10=(+2)(-5),所以:,1,=-2,2,=5,于是(A)=5.,A,-1,=,Cond(A),=|A|,|A,-1,|,=7,6/10=4.2,第56页,课间,休息,第57页,