第二章解线性方程组的直接方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 解线性方程组的直接法,本章讨论,n,元线性方程组,（,2.1）,的,直接解法。方程组(2.1)的矩阵形式为,A,x,=b,其中,若矩阵,A,非奇异,即,det,(,A,)0,则方程组(2.1)有唯一解。,所谓直接解法是指，若不考虑计算过程中的舍入误差，,经过有限次算术运算就能求出线性方程组的精确解的方法。,但由于实际计算中舍入误差的存在，用直接解法一般也只,能求出方程组的近似解。,Cramer,法则是一种不实用的直接法，下面介绍几种实,用的,直接法。,1,Gauss,消去法,Gauss,消元法是一种规则化的加减消元法，其基本思,想是,通过逐次消元计算，把一般线性方程组的求解转化为,等价的上三角形方程组的求解。,1.1 顺序,Gauss,消去法,为了清楚起见,先看一个简单的例子.,考虑线性方程组,消去后两个方程中的,x,1,得,再,消去最后一个方程的,x,2,得,消元,结束,经过回代得解:,上述求解的消元过程可用矩阵表示为:,(,A,b,)=,这是,Gauss,消去法的计算形式,新的增广矩阵对应的线性,方程组就是上三角形方程组,可进行回代求解。,现在介绍求解线性方程组（2.1)的顺序,Gauss,消去法:,记,则,线性方程组(2.1)的增广矩阵为,第一步.设,依次用,乘,矩阵的第1行加到第,i,行,得到矩阵:,其中,第二步.设 ,依次用,乘,矩阵的第2行加到第,i,行,得到矩阵:,其中,如此继续消元下去,第,n-1,步结束后得到矩阵:,这就,完成了消元过程。,对应的方程组变成：,对此,方程组进行回代，就可求出方程组的解。,顺序,Gauss,消去法求解,n,元线性方程组的乘除运算量是,：,n,2,-1,+(,n-1),2,-1,+2,2,-1,+1+2+,n,n=20,时,顺序,Gauss,消去法只需3060次乘除法运算.,顺序,Gauss,消去法通常也简称为,Gauss,消去法,.,顺序,Gauss,消去法中的,称为,主元素,.,主元素都不为零,矩阵,A,的各阶顺序主子式都不为零.,1.2 主元,Gauss,消去法,(用十进制四位浮点计算):,(用,Cramer,法则可得精确解,x,1,*,=1.00010,x,2,*,=0.99990),解,用顺序,Gauss,消去法,消元得,回代得解:,x,2,=1.00,x,1,=0.00,若将方程组改写成:,例1,解线性方程组,用顺序,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),),的第二列元素中,取,然后进行第二步消元得增广矩阵,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,方程组具有四位有效数字的精确解为,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,2.,用列主元,Gauss,消去法求解,消元过程为,回代得:,x,3,=5.545,x,2,=-45.77,x,1,=17.46,可见，列主元,Gauss,消去法是在每一步消元前,在主元所在的一列选取绝对值最大的元素作为主元素.,而全主元,Gauss,消去法是在每一步消元前,在所有元素中选取绝对值最大的元素作为主元素.但由于运算量大增,实际应用中并不经常使用.,2 直接三角分解法,2.1,Gauss,消去法的矩阵表示,对矩阵,若,令,记,则有,A,(2),=,记,令,若,则有,A,(3),=,如此进行下去,第,n-1,步得到:,A,(n),=,其中,也就是:,A,(n),=,L,n,-1,A,(n-1),其中,=,L,n,-1,L,n-2,A,(n-2),=,L,n,-1,L,n-2,L,2,L,1,A,(1),所以有:,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,是上三角矩阵.,式,A,=,LU,称为矩阵,A,的,三角分解.,2.2,Doolittle,分解法,设,n,阶方阵,A,的各阶顺序主子式不为零,则存在唯一单位下三角矩阵,L,和上三角矩阵,U,使,A,=,LU,.,证明,只证唯一性,设有两种分解,A,=,LU,则有,=,E,所以得,于是,Ax,=,b,LUx,=,b,令,Ux,=,y,得,定理2.1,下面介绍矩阵三角分解的,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,对,k=2,3,n,计算,由,可得,这,就是求解方程组,Ax,=,b,的,Doolittle,三角分解方法。,利用三角分解方法解线性方程组,解,因为,所以,例3,先解,得,再解,得,解线性方程组,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,由,所以,为了提高数值稳定性,可考虑列主元三角分解法,设已完成,A,=,LU,的,k-1,步分解计算,矩阵分解成,设,令,r,k,r,i,相当于取,为第,k,步分解的主元素.,但要注意方程组的常数项也要相应变换.,例如,用列主元三角分解解例3中方程组.则有,设,A,为对称正定矩阵,则有唯一分解,A,=,LU,且,u,kk,0.,则有,A,=,LDM,又因为 (,LDM,),T,=,M,T,DL,T,=,LDM,所以,M,=,L,T,=,LDL,T,则有,2.3,平 方 根 法,分解,A,=,GG,T,称为对称正定矩阵的,Cholesky,分解.,Ax,=,b,转换为,Gy,=b,G,T,x,=,y,若记,G,=(,g,ij,),则有:对,k=1,2,n,实际计算时,可采用紧凑格式,_,平方根法,.,解,三角方程,Gy,=b,G,T,x,=,y,可得,解,例4,解线性方程组,平方根法是求对称正定系数线性方程组的三角分解法,对称正定矩阵的,Cholesky,分解的计算量和存贮量均约为一般矩阵的,LU,分解的一半.且,Cholesky,分解具有数值稳定性.,追赶法是求三对角线性方程组的三角分解法.即方程,三,对角矩阵,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 追 赶 法,其中,解,三角方程,Ty,=b,Mx,=,y,可得,称之为解三对角方程组的,追赶法,.,解,例5,解线性方程组,当满足条件,|,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.,时,追赶法是数值稳定的,追赶法具有计算程序简单,存贮,量少,计算量小的优点.,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,R,n,x+y,x,+,y,则称,为空间,R,n,上的,范数,x,为,向量,x,的,范数,.,记,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,常用的三种向量范数满足如下等价关系,x,x,1,n,x,x,R,n,定义2.2,设向量序列,k=1,2,向量,如果,则称,向量序列,x,(k),收敛于向量,x,*,记作,易见,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,也称为,谱范数.,矩阵的,-范数,:,A,也称为,行范数.,矩阵的,F,-,范数,:,A,F,例7,设矩阵,求矩阵,A,的范数,A,p,p=1,2,F,.,解,A,1,=4,A,=5,A,F,设,是一种向量范数,则定义,称之为由向量范数派生的,矩阵算子范数,.,矩阵的算子范数满足,Ax,A,x,x,R,n,把满足上式的矩阵范数称为,与,向量范数相容的矩阵范数,.,对于,p=1,2,矩阵范数,A,p,是,由向量范数,x,p,派生的矩阵算子范数,所以,A,p,是与,x,p,相容的矩阵范数.但,A,F,不是一种算子范数,却与,x,2,是,相容的.,设,是一种算子范数,则,矩阵的范数与矩阵的特征值之间也有密切的联系.,设,是矩阵,A,的特征值,x,是对应的特征向量,则有,Ax,=,x,利用向量和矩阵范数的相容性,则得,|,|,x,=,x,=,Ax,A,x,于是|,|,A,设,n,阶矩阵,A,的,n,个特征值为,1,2,n,则称,为矩阵,A,的,谱半径,.,对矩阵的任何一种相容范数都有,(,A,),A,另外,0,一种相容范数,使,A,(,A,)+,任何两种矩阵范数也具有等价性,m,A,A,M,A,A,R,n,n,矩阵序列的收敛性也定义为,4 线性方程组固有性态与误差分析,4.1 线性方程组的固有性态,考虑线性方程组,其,精确解为,x*=(-9800b,1,+9900b,2,9900b,1,-10000b,2,),T,若把线性方程组变为,解为,x=(-9800b,1,+9900b,2,-19700,9900b,1,-10000b,2,+19900),T,可见,x-x*=(-19700,19900),T,解的,误差可能放大到常数项的误差的近2万倍。,若把线性方程组变为,则线性方程组可能无解.,这种由于原始数据微小变化而导致解严重失真的线性方程组称为,病态方程组,相应的系数矩阵称为,病态矩阵.,设线性方程组,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,即,再设,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,的,条件数,.,经常使用的条件数有,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,由于计算条件数运算量较大,实际计算中若遇到下述情况之一,方程组就有可能是病态的:,(1)矩阵元素间数量级差很大,且无一定规律;,(2)矩阵的行列式值相对来说很小;,(3)列主元消去法求解过程中出现量级很小的主元素;,(4)数值求解过程中,计算解,x,的剩余向量,r=b-Ax,已经很小,但,x,仍不符合要求.,4.2 预条件和迭代改善,1.线性方程组的预条件处理,对病态方程组,Ax,=,b,考虑线性方程组,其中,称之为,预条件方程组,显然与原方程组等价.可逆矩阵,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),的迭代改善解为:,练习题,第,50页 习题2,2-2(1),2-6(1)（用二位浮点计算）,练习题,第,50页 习题2,2-3(1),2-4,2-5,2-8,练习题,第,50页 习题2,2-10,2-11,2-12,2-14,2-16,2-17,课 堂 练 习,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,课间,休息,