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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 解线性方程组的直接法,考虑一个简单的例。保持人体健康需要多种微量元素，主要通过食物摄取，并且不同的年龄，职业和身体条件要求的量也不同。,每千克食品含量,菠菜,萝卜,苹果,要求值,铁,a,11,a,12,a,13,b,1,锌,a,21,a,22,a,23,b,2,钙,a,31,a,32,a,33,b,3,考虑,n,元线性方程组,(2.1),方程组,(2.1),的矩阵形式为,A,x,=b,其中,若矩阵,A,非奇异,即,det(,A,)0,则方程组,(2.1),有唯一解。,所谓直接解法是指，若不考虑计算过程中的舍入误差，,经过有限次算术运算就能求出线性方程组精确解的方法。,但由于实际计算中舍入误差的存在，用直接解法一般也只,能求出方程组的近似解。,在线性代数中我们学过用,Cramer,法则求解线性方程组。,行列式,而每个,n,阶行列式按定义,D=,需要计算,(n-1)n!,次乘法,则,Cramer,法则至少需要,(n,2,-1)n!,次乘法,当,n=20,时,有,(20,2,-1)20!,9.710,20,次乘法运算。,如果用每秒钟计算,1,百万次乘除运算的计算机，约需要：,60,24,60,365,3000,万年,Cramer,法则求,n,元线性方程组,Ax=b,的解,需要计算,n+1,个,n,阶,9.710,20,10,6,可见,Cramer,法则不是一种实用的直接法，下面介绍几种实,用的直接法。,1 Gauss,消去法,Gauss,消元法是一种规则化的加减消元法，其基本思,想是通过逐次消元计算，把一般线性方程组的求解转化为,等价的上三角形方程组的求解。,对角,上三角,下三角,1.1,顺序,Gauss,消去法,为了清楚起见,先看一个简单的例子,.,考虑线性方程组,单位,上三角,单位,下三角,上三角方程组,Ax=b:,可按,x,n,x,n-1,x,1,，,顺序进行回代求解,消去后两个方程中的,x,1,得,再消去最后一个方程的,x,2,得,消元结束,经过回代得解,:,上述求解的消元过程可用矩阵表示为,:,(,A,b,)=,这是,Gauss,消去法的矩阵计算形式,新的增广矩阵对应的,线性方程组就是上三角形方程组,可进行回代求解。,现在介绍求解线性方程组,Ax=b,的顺序,Gauss,消去法,:,记,则,线性方程组,Ax=b,的增广矩阵为,第一步,.,设,依次用,乘矩阵的第,1,行加到第,i,行,(i=2,3,n),得到矩阵,:,其中,第二步,.,设,依次用,乘矩阵,(A,(2),b,(2),),的第,2,行加到第,i,行,得到矩阵,:,其中,如此继续消元下去,第,n-1,步结束后得到矩阵,:,这就完成了消元过程。,对应的方程组变成：,对此方程组进行回代，就可求出方程组的解。,顺序,Gauss,消去法求解,n,元线性方程组的乘除运算量是,：,n=20,时,顺序,Gauss,消去法只需,3060,次乘除法运算,.,顺序,Gauss,消去法通常也简称为,Gauss,消去法,.,顺序,Gauss,消去法中的,称为,主元素,.,主元素都不为零,矩阵,A,的各阶顺序主子式都不为零,.,例,用高斯消去法求解,Ax=b,其中,解,回代求解：,x,3,=3,x,2,=2,x,1,=2,1.2,主元,Gauss,消去法,(,用十进制四位浮点计算,):,此问题的精确解为,x,1,*,=1.0001,x,2,*,=0.9999,。,解,用顺序,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),.,A=LU,L,为单位下三角矩阵,;,U,是上三角矩阵,.,分解式,A,=,LU,称为矩阵,A,的,直接三角分解,.,2.2 Doolittle,分解法,设,n,阶方阵,A,的各阶顺序主子式不为零,则存在唯一单位下三角矩阵,L,和上三角矩阵,U,使,A,=,LU,.,证明,只证唯一性,设有两种分解,A,=,LU,则有,=,E,所以得,设,A,有分解,A=LU,于是,Ax,=,b,LUx,=,b,令,Ux=y,则得,定理,2.1,这是与,Ax=b,等价的线性方程组,下面介绍矩阵三角分解的,Doolittle,分解方法,利用矩阵乘法规则依次求,U,的第,k,行，,L,的第,k,列,(k=1,2,),对,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,计算,要按顺序先求,U,的第,1,行，,L,的第,1,列，,U,的第,2,行，,L,的第列,，,U,的第,k,行，,L,的第,k,列，,。可导出计算公式：,在完成分解,A=LU,后，依次求解方程组,Ly=b,和,Ux=y,，既,可得,这就是求解方程组,Ax,=,b,的,Doolittle,三角分解方法。,利用三角分解方法解线性方程组,解,令,利用矩阵乘法规则，先求,U,的第,1,行元素，可得：,例,3,2=u,11,2=u,12,-3=u,13,再求,L,的第,2,列。利用矩阵乘法规则建立方程得到：,2=2l,21,3=2l,31,则有,再求,U,的第,2,行。利用矩阵乘法规则建立方程得到：,-1=2+u,22,3=-3+u,23,则有,:u,22,=-3,u,23,=6,然后，再求,U,的第,3,行，,2=-9/2+10+u,33,最终得,得,先解,再解,得,解线性方程组,Ax,=,b,的,Doolittle,三角分解法的计算量约为,1/3n,3,与,Gauss,消去法基本相同,.,其优点在于求一系列同系数的线性方程组,Ax,=,b,k,(k=1,2,m),时,可大大节省运算量,.,求解：,Ly=b,和,Ux=y,例如,求如下,3,阶矩阵,A,的逆矩阵：,这等价于求,X,使,AX=E,。设,X=(x,1,x,2,x,3,),，,可分别取,3,维单位,向量：,e,1,=(1,0,0),T,e,2,=(0,1,0),T,e,3,=(0,0,1),T,由矩阵分块乘法：,Ax,1,=e,1,Ax,2,=e,2,Ax,3,=e,3,利用三角分解法得,:,依次求解,Ly,i,=e,i,Ux,i,=y,i,i=1,2,3.,则,X=(x,1,x,2,x,3,),为所求,.,所以,为了提高数值稳定性,可考虑列主元三角分解法,设已完成,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,分解,.,若记,G,=(g,ij,),则有,:,对,k=1,2,n,按列求矩阵,G,的元素。实际计算时,可采用紧凑格式,Ax=b,GG,T,x=b,Gy=b,G,T,x,=,y,称为,平方根法,Ax=b,GG,T,x=b,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,追 赶 法,其中,Ax=b,TMx=b,Ty=b,Mx=y ,解三角方程可得,称之为解三对角方程组的,追赶法,.,计算量为,0(n).,例,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,设,是以向量,x,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,则称,x,为向量,x,的范数，,为空间,R,n,上的,范数。,记,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,*,记作,易见,按,|x|,1,范数：,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,nn,矩阵序列的收敛性定义为,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,万倍。,若把线性方程组变为,因系数行列式为,0,，则线性方程组可能无解,.,这种由于原始数据微小变化而导致解严重失真的线性方程组称为,病态方程组,相应的系数矩阵称为,病态矩阵,.,设线性方程组,Ax,=,b,系数矩阵是精确的,右端项有误差,b,此时记解为,x,+,x,则,A,(,x,+,x,)=,b,+,b,于是,Ax+A x=b+b,A,x,=,b,x,=,A,-1,b,所以,x,=,A,-1,b,A,-1,b,又由于,b,=,Ax,A,x,因此,x,b,A,A,-1,b,x,即,可见误差是否可控制取决于,A,A,-1,的大小。,再设,b,是精确的,A,有误差,A,此时记解为,x,+,x,则,(,A,+,A,)(,x,+,x,)=,b,则有,Ax+A,x,+,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(,A,)1,，则称,A,为,病态矩阵,。,经常使用的条件数有,Cond,p,(,A,)=,A,p,A,-1,p,p=1,，,2,，。,当,A,为对称矩阵时，有,Cond,2,(,A,)=,A,2,A,-1,2,=|,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,考虑线性方程组,其中,称之为,预条件方程组,显然与原方程组等价,.,(1),条件数,(2),方程组,Cz,=,d,容易求解。,比,Cond(A),明显小,.,对于一般的矩阵,A,没有十分有效的方法去选择预条件矩阵,.,当,A,是对称正定矩阵时,可取,C .,2.,线性方程组的迭代改善,设已求得方程组,Ax,=,b,的近似解,x,(1),计算剩余向量,r,(1),=,b-Ax,(1),再求解余量方程组,Ax,=,r,(1),得到解,则,x,(1),的迭代改善解为,:,可逆矩阵,C,称为,预条件矩阵,.,矩阵,C,应满足条件,练习题,第,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,课间,休息,