数值分析课件-第二章解线性方程组的直接方法.ppt
课件,1,第2章 解线性方程组的直接法,本章讨论n元线性方程组,（2.1）,的直接解法。方程组(2.1)的矩阵形式为,Ax=b,其中,课件,2,若矩阵A非奇异,即det(A)0,则方程组(2.1)有唯一解。,所谓直接解法是指，若不考虑计算过程中的舍入误差，,经过有限次算术运算就能求出线性方程组的精确解的方法。,但由于实际计算中舍入误差的存在，用直接解法一般也只,能求出方程组的近似解。,Cramer法则是一种不实用的直接法，下面介绍几种实,用的直接法。,1 Gauss消去法,Gauss消元法是一种规则化的加减消元法，其基本思,想是通过逐次消元计算，把一般线性方程组的求解转化为,等价的上三角形方程组的求解。,1.1 顺序Gauss消去法,为了清楚起见,先看一个简单的例子.,考虑线性方程组,课件,3,消去后两个方程中的x1得,再消去最后一个方程的x2得,消元结束,经过回代得解:,课件,4,上述求解的消元过程可用矩阵表示为:,(A,b)=,这是Gauss消去法的计算形式,新的增广矩阵对应的线性,方程组就是上三角形方程组,可进行回代求解。,现在介绍求解线性方程组（2.1)的顺序Gauss消去法:,记,则,线性方程组(2.1)的增广矩阵为,课件,5,第一步.设,依次用,乘矩阵的第1行加到第i行,得到矩阵:,课件,6,其中,第二步.设,依次用,乘矩阵的第2行加到第i行,得到矩阵:,其中,课件,7,如此继续消元下去,第n-1步结束后得到矩阵:,这就完成了消元过程。,对应的方程组变成：,对此方程组进行回代，就可求出方程组的解。,课件,8,顺序Gauss消去法求解n元线性方程组的乘除运算量是：n2-1,+(n-1)2-1,+22-1,+1+2+n,n=20时,顺序Gauss消去法只需3060次乘除法运算.,顺序Gauss消去法通常也简称为Gauss消去法.,顺序Gauss消去法中的,称为主元素.,主元素都不为零矩阵A的各阶顺序主子式都不为零.,课件,9,1.2 主元Gauss消去法,(用十进制四位浮点计算):,(用Cramer法则可得精确解x1*=1.00010,x2*=0.99990),解 用顺序Gauss消去法,消元得,回代得解:x2=1.00,x1=0.00,若将方程组改写成:,例1 解线性方程组,课件,10,用顺序Gauss消去法,消元得,回代得解:x2=1.00,x1=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,方程组具有四位有效数字的精确解为 x1*=17.46,x2*=-45.76,x3*=5.546,解 1.用顺序Gauss消去法求解,消元过程为,回代得:x3=5.546,x2=100.0,x1=-104.0,课件,13,2.用列主元Gauss消去法求解,消元过程为,课件,14,回代得:x3=5.545,x2=-45.77,x1=17.46,可见，列主元Gauss消去法是在每一步消元前,在主元所在的一列选取绝对值最大的元素作为主元素.,而全主元Gauss消去法是在每一步消元前,在所有元素中选取绝对值最大的元素作为主元素.但由于运算量大增,实际应用中并不经常使用.,课件,15,2 直接三角分解法,2.1 Gauss消去法的矩阵表示,对矩阵,若,令,记,课件,16,则有,A(2)=,记,令,若,则有,课件,17,A(3)=,如此进行下去,第n-1步得到:,A(n)=,其中,课件,18,也就是:,A(n)=Ln-1A(n-1),其中,=Ln-1Ln-2A(n-2),=Ln-1Ln-2L2L1A(1),课件,19,所以有:,A=A(1)=L1-1L2-1Ln-1-1A(n)=LU,而且有,其中L=L1-1L2-1Ln-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,计算,设,akj=lk1u1j+lk2u2j+lkk-1uk-1j+ukj,aik=li1u1k+li2u2k+likukk,课件,22,课件,23,对k=2,3,n,计算,课件,24,由,可得,这就是求解方程组Ax=b的Doolittle三角分解方法。,课件,25,利用三角分解方法解线性方程组,解 因为,所以,例3,课件,26,先解,得,再解,得,解线性方程组Ax=b的Doolittle三角分解法的计算量约为1/3n3,与Gauss消去法基本相同.其优点在于求一系列同系数的线性方程组Ax=bk,(k=1,2,m)时,可大大节省运算量.,例如,求上例中矩阵A的逆矩阵.可分别取常向量 b1=(1,0,0)T,b2=(0,1,0)T,b3=(0,0,1)T,课件,27,由,所以,课件,28,为了提高数值稳定性,可考虑列主元三角分解法,设已完成A=LU的k-1步分解计算,矩阵分解成,设,令 rkri,相当于取,为第k步分解的主元素.,但要注意方程组的常数项也要相应变换.,课件,29,例如,用列主元三角分解解例3中方程组.则有,课件,30,设A为对称正定矩阵,则有唯一分解A=LU,且ukk0.,则有 A=LDM,又因为(LDM)T=MTDLT=LDM 所以 M=LT,=LDLT,则有,2.3 平 方 根 法,课件,31,分解A=GGT称为对称正定矩阵的Cholesky分解.,Ax=b 转换为 Gy=b,GTx=y,若记G=(gij),则有:对k=1,2,n,实际计算时,可采用紧凑格式,_平方根法.,课件,32,解三角方程 Gy=b,GTx=y 可得,解,例4 解线性方程组,课件,33,平方根法是求对称正定系数线性方程组的三角分解法,对称正定矩阵的Cholesky分解的计算量和存贮量均约为一般矩阵的LU分解的一半.且Cholesky分解具有数值稳定性.,课件,34,追赶法是求三对角线性方程组的三角分解法.即方程,三对角矩阵A的各阶顺序主子式都不为零的一个充分条件是:,|a1|c1|0;|an|dn|0;|ai|ci|+|di|,cidi 0,i=2,3,n-1.,在此条件下,A=LDM=TM,称之为矩阵A的Crout分解.,对三对角矩阵A进行Crout分解,有,2.4 追 赶 法,课件,35,其中,解三角方程 Ty=b,Mx=y 可得,称之为解三对角方程组的追赶法.,课件,36,解,例5 解线性方程组,课件,37,当满足条件|a1|c1|0;|an|dn|0;|ai|ci|+|di|,cidi 0,i=2,3,n-1.时,追赶法是数值稳定的,追赶法具有计算程序简单,存贮量少,计算量小的优点.,课件,38,3 向量和矩阵的范数,3.1 向量的范数,定义2.1 设是向量空间Rn上的实值函数,且满足条件:,(1)非负性:对任何向量xRn,x0,且x=0当 且仅当x=0,(2)齐次性:对任何向量x Rn 和实数,x=|x,(3)三角不等式:对任何向量x,yRn x+yx+y,则称为空间Rn上的范数,x为向量x的范数.,课件,39,记x=(x1,x2,xn)T,常用的向量范数有:,向量的1-范数:x1=|x1|+|x2|+|xn|,向量的2-范数:x2=,向量的-范数:x=,例6 设向量x=(2,-4,3,1)T,求向量范数xp,p=1,2,.,解 由定义x1=10,x2=,x=4.,虽然不同范数的值可能不同，但它们间存在等价关系.,定理2.2(范数的等价性),对于 Rn 上的任何两种范数和,存在正常数m,M,使得 m x x M x,xRn,课件,40,常用的三种向量范数满足如下等价关系 x x1 nx,xRn,定义2.2 设向量序列,k=1,2,向量,如果,则称向量序列x(k)收敛于向量x*,记作,易见,课件,41,3.2 矩阵的范数,定义2.3 设是以n阶方阵为变量的实值函数,且满足条件:,(1)非负性:A0,且A=0当且仅当A=0,(2)齐次性:A=|A,R,(3)三角不等式:A+BA+B,(4)三角不等式:ABAB,则称A为矩阵A的范数.,记A=(aij),常用的矩阵范数有:,矩阵的1-范数:A1,也称矩阵的列范数.,矩阵的2-范数:A2,也称为谱范数.,课件,42,矩阵的-范数:A,也称为行范数.,矩阵的F-范数:AF,例7 设矩阵,求矩阵A的范数Ap,p=1,2,F.,解 A1=4,A=5,AF,课件,43,设是一种向量范数,则定义,称之为由向量范数派生的矩阵算子范数.,矩阵的算子范数满足,AxAx,xRn,把满足上式的矩阵范数称为与向量范数相容的矩阵范数.,对于p=1,2,矩阵范数Ap是由向量范数xp派生的矩阵算子范数,所以Ap是与xp相容的矩阵范数.但AF不是一种算子范数,却与x2是相容的.,设是一种算子范数,则,课件,44,矩阵的范数与矩阵的特征值之间也有密切的联系.,设是矩阵A的特征值,x是对应的特征向量,则有,Ax=x,利用向量和矩阵范数的相容性,则得,|x=x=AxAx,于是|A,设n阶矩阵A的n个特征值为1,2,n,则称,为矩阵A的谱半径.,对矩阵的任何一种相容范数都有,(A)A,另外,0,一种相容范数,使 A(A)+,课件,45,任何两种矩阵范数也具有等价性 m A A M A,ARnn,矩阵序列的收敛性也定义为,4 线性方程组固有性态与误差分析,4.1 线性方程组的固有性态,考虑线性方程组,其精确解为 x*=(-9800b1+9900b2,9900b1-10000b2)T,课件,46,若把线性方程组变为,解为x=(-9800b1+9900b2-19700,9900b1-10000b2+19900)T,可见 x-x*=(-19700,19900)T,解的误差可能放大到常数项的误差的近2万倍。,若把线性方程组变为,则线性方程组可能无解.,这种由于原始数据微小变化而导致解严重失真的线性方程组称为病态方程组,相应的系数矩阵称为病态矩阵.,课件,47,设线性方程组 Ax=b,系数矩阵是精确的,常数项有误差b,此时记解为x+x,则 A(x+x)=b+b,于是 Ax=b,所以 x=A-1b A-1 b,又由于 b=Ax A x,因此 x b AA-1bx,即,课件,48,再设b是精确的,A有误差A,此时记解为x+x,则(A+A)(x+x)=b,则有 Ax+A(x+x)=0,所以 x=-A-1A(x+x)=0,于是 x A-1Ax+x,也就是,记 Cond(A)=AA-1,称为方程组Ax=b或矩阵A的条件数.,课件,49,经常使用的条件数有 Condp(A)=ApA-1p p=1，2，。,当A为对称矩阵时，有 Cond2(A)=|1|/|n|其中1，n分别是A的按绝对值最大和最小的特征值。,例如，对前面方程组的系数矩阵A有,Cond1(A)=Cond(A)=39601，Cond2(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|=76/10=4.2,课件,56,课间,休息,
