第三章线形方程组直接求根法优秀课件.ppt

第三章线形方程组直接求根法第1页，本讲稿共66页1.1 消元法的描述矩阵形式：矩阵形式：矩阵形式：矩阵形式：第2页，本讲稿共66页线性方程组解唯一的条件：线性方程组解唯一的条件：线性方程组解唯一的条件：线性方程组解唯一的条件：其解为：其解为：其解为：其解为：其中，其中，Ai为方程组右端向量为方程组右端向量B代替代替A中第中第i列向量列向量所得的矩阵。所得的矩阵。克莱姆克莱姆克莱姆克莱姆(CramerCramer)法则法则法则法则1.1 消元法的描述第3页，本讲稿共66页直接法：假设计算过程中不产生舍入误差，经过直接法：假设计算过程中不产生舍入误差，经过直接法：假设计算过程中不产生舍入误差，经过直接法：假设计算过程中不产生舍入误差，经过 有限次运算可求得方程组的精确解法。有限次运算可求得方程组的精确解法。有限次运算可求得方程组的精确解法。有限次运算可求得方程组的精确解法。思路：思路：思路：思路：将线性方程组变形成等价的三角方程组。将线性方程组变形成等价的三角方程组。将线性方程组变形成等价的三角方程组。将线性方程组变形成等价的三角方程组。例：例：先消去方程组中后两个方程中的变量先消去方程组中后两个方程中的变量先消去方程组中后两个方程中的变量先消去方程组中后两个方程中的变量x x1 1，得同解方程组：，得同解方程组：，得同解方程组：，得同解方程组：1.1 消元法的描述第4页，本讲稿共66页再消去上方程组第三个方程中的变量再消去上方程组第三个方程中的变量再消去上方程组第三个方程中的变量再消去上方程组第三个方程中的变量x x2 2，得同解方，得同解方，得同解方，得同解方程组：程组：程组：程组：上三角方程组1.1 消元法的描述第5页，本讲稿共66页1.1 方法描述思路思路:先逐次消去先逐次消去变量，将方程量，将方程组化解成同解的化解成同解的上三角方程上三角方程组，此，此过程称程称为消元消元过程程；然；然后按方程相反后按方程相反顺序求解上三角方程序求解上三角方程组，得，得到原方程的解，此到原方程的解，此过程称程称为回代回代过程程。设有有线方程方程组:（1）1.1 消元法的描述第6页，本讲稿共66页(1)(1)为消元方便，经常用为消元方便，经常用l11除除(3.1)(3.1)1：其中其中:(3.2)(2)为把为把(3.1)(3.1)2,(3.1),(3.1)3中的中的x1项消去，引入如项消去，引入如下参数下参数:1.1 消元法的描述第7页，本讲稿共66页(3)按以下方式消去式按以下方式消去式(3.1)2,(3.1)3中的中的x1项：项：0+(a22-l21u12)x2+(a23-l21u13)x3=b2-l21z1(3.1)(3.1)2-l21(3.2)(3.2):(3.1)(3.1)3-l31 (3.2)(3.2)0+(a32-l31u12)x2+(a33-l31u13)x3=b3-l31z1a32(1)x2+a33(1)x3=b3(1)(3.4)简记为简记为a22(1)x2+a23(1)x3=b2(1)(3.3)1.1 消元法的描述第8页，本讲稿共66页(4)用用l22除除(3.3)式得：式得：aij(1)=aij(0)-li1u1j,bi(1)=bi(0)-li1z1aij(0)=aij,bi(0)=bi其中其中其中其中(3.5)1.1 消元法的描述第9页，本讲稿共66页(5)为将为将(3.4)中的中的x2项消去，引入乘数项消去，引入乘数a33(2)=a33(1)l32u23=a33 l31u13 l32u23,b3(2)=b3(1)-l32z2=b3 l31z1-l32z2(6)消去消去(3.4)式中的式中的x2项：项：(3.4)-l32(3.5):0+(a33(1)l32u23)x3=b3(1)-l32z2简记为:a33(2)x3=b3(2)(3.6)其中其中1.1 消元法的描述第10页，本讲稿共66页同样对同样对(3.6)式遍除式遍除l33得得 u33x3=z3 (3.7)以上的计算过程称为以上的计算过程称为消元过程消元过程。其中其中1.1 消元法的描述第11页，本讲稿共66页v消元过程结束就可得到下列线组：消元过程结束就可得到下列线组：u11x1+u12x2+u13x3=z1 u22x2+u23x3=z2 (3.8)u33x3=z3v简记为简记为UX=Z，其中，其中1.1 消元法的描述第12页，本讲稿共66页v其中其中(3.8)式右端的式右端的z由下列公式确定：由下列公式确定：v简记为简记为LZ=B，其中，其中1.1 消元法的描述第13页，本讲稿共66页v按照线组按照线组(3.8)可以逐次求出可以逐次求出x1、x2、x3，称为回代过程。称为回代过程。v由由UX=Z,LZ=B得得LUX=B，与，与AX=B比较知比较知:A=LU (3.9)消元过程实质上就是将原线组消元过程实质上就是将原线组AX=B分解为分解为两个三角形线组两个三角形线组LZ=B和和UX=Z的计算过程，的计算过程，也称为杜利特尔（也称为杜利特尔（Doolittle）分解）分解.1.1 消元法的描述第14页，本讲稿共66页v系数系数lij、uij的计算公式的计算公式:（择定）（择定）（择定）1.1 消元法的描述第15页，本讲稿共66页系数系数lij、uij的计算公式规律的计算公式规律:v系数由系数由上三角上三角、下三角下三角和和z向量向量组成，上三角为组成，上三角为u系数系数矩阵，下三角为矩阵，下三角为l系数矩阵。系数矩阵。vu,z系数矩阵元素的系数矩阵元素的分母分母为所在为所在行行对应的对应的l对角线元素；对角线元素；l系数矩阵的系数矩阵的分母分母为所在为所在列列对应的对应的u对象线元素；对象线元素；vuij,zi ,lij系数矩阵的系数矩阵的分子分子为原方程对应的系数为原方程对应的系数aij与LU矩矩阵中阵中i行行j列的列的对应元素乘积之和的差对应元素乘积之和的差；v系数矩阵的系数矩阵的分子分子为原方程对应的系数为原方程对应的系数aij与LU矩阵中矩阵中i行行j列的列的对应元素乘积之和的差对应元素乘积之和的差；1.1 消元法的描述第16页，本讲稿共66页系数系数lij、uij的计算顺序的计算顺序:u11u12u13z1li1l21u22u23z2l22l31l32u33z3l331234561.1 消元法的描述第17页，本讲稿共66页v这种计算规律可用一般公式表示为这种计算规律可用一般公式表示为1.1 消元法的描述第18页，本讲稿共66页v回代过程回代过程:在已知在已知lij的基础上的基础上,建立求解建立求解x1,x2,xn的三角形线组，按由上而下的方程次序解出的三角形线组，按由上而下的方程次序解出x1,x2,xn。1.1 消元法的描述第19页，本讲稿共66页1.1 消元法的描述第20页，本讲稿共66页思路：取思路：取lii=1(i=1,2,n)相应的计算公式为：相应的计算公式为：1.2 1.2 高斯消元法高斯消元法第21页，本讲稿共66页1.2 1.2 高斯消元法高斯消元法用高斯消元法解下列线性方程组例例3.13.1：解解:u系数的第一列系数的第一列值为原方程第一列的系数原方程第一列的系数紧凑格式第22页，本讲稿共66页进一步求得进一步求得:z1=0,z2=3,z3=1.01921-23x1 +11x2 +x3 =0 2.26086x2+1.52174x3=3 1.01924x3=1.01921x1=0.99999x2=1.99999x3=0.999971.2 1.2 高斯消元法高斯消元法第23页，本讲稿共66页思路思路：取：取l11=a11(0)=a11,l22=a22(1),l33=a33(2),lnn=ann(n-1)，即，即uii=11.3 1.3 克劳特消元法克劳特消元法相应的计算公式为：相应的计算公式为：第24页，本讲稿共66页用克劳特消元法解下列线性方程组例例3.23.2：解解:按克按克劳特消元法的特消元法的计算公式算公式,计算算结果如下果如下:1.3 1.3 克劳特消元法克劳特消元法第25页，本讲稿共66页1.3 1.3 克劳特消元法克劳特消元法l系数的第一列系数的第一列值为原方原方程第一列的系数；程第一列的系数；u系数系数对角角线上的上的值为1 1第26页，本讲稿共66页x1+1.5x2 +2x3 =3 x2 -8x3=-8 x3=2x1=3-1.5*8-2*2=13x2=-8+8*2=8x3=21.3 1.3 克劳斯特消元法克劳斯特消元法第27页，本讲稿共66页v取取lii=uii(i=1,2,n),则：则：1.4 1.4 平方根法平方根法系数矩阵必须为对称矩阵才可用此法第28页，本讲稿共66页线性方程组具有对称性，即线性方程组具有对称性，即aij=aji，则有，则有1.4 1.4 平方根法平方根法第29页，本讲稿共66页由此推得由此推得uij=lji，即即lij与与uij相对于对角线是对称分布相对于对角线是对称分布的。这样得到消元的计算公式为：的。这样得到消元的计算公式为：1.4 1.4 平方根法平方根法P76页公式改正。第30页，本讲稿共66页1.4 1.4 平方根法平方根法第31页，本讲稿共66页1.4 1.4 平方根法平方根法用平方根法解下列线性方程组例例3.23.2：解解:按平方根法的按平方根法的计算公式算公式,计算算结果如下果如下:系数矩阵为对称矩阵第32页，本讲稿共66页1.4 1.4 平方根法平方根法对角线上的对角线上的l,u系数系数值为消元消元法法对角角线上分子的上分子的值开平方开平方第33页，本讲稿共66页x1+0.42x2 +0.54x3 =0.30.90752x2 0.10270 x3=0.41211 0.83537x3=0.59336x1=-0.24052x2=0.37372x3=0.710301.4 1.4 平方根法平方根法第34页，本讲稿共66页v追赶法就是应用追赶法就是应用克劳特消元法克劳特消元法求解求解三对角三对角线形线形的线性方程组的解的线性方程组的解1.5 1.5 追赶法追赶法b1x1+c1x2 =d1a2x1+b2x2 +c2x3 =d2 a3x2+b3x3 +c3x4 =d3 an-1xn-2+bn-1xn-1+cn-1xn =dn-1 an xn-1+bnxn=dn第35页，本讲稿共66页（1）lij,uij(克劳特消元法的公式克劳特消元法的公式)l11=b1 u12=c1/l11 0 0 .0l21=a2 l22=b2-a2u12 u23=c2/l22 00 l32=a3 l33=b3-a3u23 u34=c3/l33 0 ln-1 n-2=an-1 ln-1 n-1=bn-1-an-1un-2 n-1 un-1 n=cn-1/ln-1 n-10 0 ln n-1=an lnn=bn-anun-1 n 0li i-1=ai (i=2,3,n)li i=bi aiui-1 i (i=1,2,n)a1=0,u0 1=0 ui i+1=ci/li i(i=1,2,n-1)1.5 1.5 追赶法追赶法第36页，本讲稿共66页（2）zi(i=1,2,n)1.5 1.5 追赶法追赶法或或追过程第37页，本讲稿共66页（3）xi(i=n,n-1,2,1)1.5 1.5 追赶法追赶法或或赶过程第38页，本讲稿共66页1.5 1.5 追赶法追赶法用追赶法解下列线性方程组例例3.23.2：解解:按追赶法的按追赶法的计算公式算公式,计算算结果如下果如下:第39页，本讲稿共66页1.5 1.5 追赶法追赶法第40页，本讲稿共66页x1-0.5x2=1x2 -0.66667x3=0 x3=3.00001x1=2.00001x2=2.00002x3=3.000011.5 1.5 追赶法追赶法第41页，本讲稿共66页定理定理1:若若A的各阶主子式均不为的各阶主子式均不为0,即即1.6 1.6 消元法的应用条件消元法的应用条件则则lii 0,uii 0，消元法可用。，消元法可用。第42页，本讲稿共66页因因A=LU 0 A1=|a11|=L1U1=|l11|u11|=|l11u11|,所以所以,l11 0,u11 01.6 1.6 消元法的应用条件消元法的应用条件证明：证明：第43页，本讲稿共66页1.6 1.6 消元法的应用条件消元法的应用条件命题得证第44页，本讲稿共66页证明：因实对称矩阵为正定的必要且充分证明：因实对称矩阵为正定的必要且充分条件是其所有的主子式都大于零，即条件是其所有的主子式都大于零，即|A1|0,|A2|0,|An|0显然满足定理显然满足定理1中中|Ai|0的条件的条件,因此定理因此定理2得证。得证。1.6 1.6 消元法的应用条件消元法的应用条件定理定理2 若若A为实对称正定矩阵为实对称正定矩阵,则则lii 0,uii 0(i=1,2,n)消元法可用。消元法可用。第45页，本讲稿共66页v如果系数矩阵对称正定且采用平方根法进行求如果系数矩阵对称正定且采用平方根法进行求解，则必有解，则必有lii20(i=1,2,n)，这是因为这是因为不必进行复数运算不必进行复数运算1.6 1.6 消元法的应用条件消元法的应用条件第46页，本讲稿共66页阿达马定理 r阶线组阶线组|Ar|0的一个充分条件为的一个充分条件为 下述强对角线条件下述强对角线条件 假设假设|Ar|=0,则线组则线组ArX=0有非零解有非零解 1,2,设设 k=max(1,2,r)，代入第，代入第k个方程，个方程，有如下等式与等式成立有如下等式与等式成立:1.6 1.6 消元法的应用条件消元法的应用条件证明：证明：反证法（假设结论不成立）反证法（假设结论不成立）成立成立第47页，本讲稿共66页此结论与条件此结论与条件矛盾矛盾，故假设，故假设|Ar|=0不对，定不对，定理得证。理得证。1.6 1.6 消元法的应用条件消元法的应用条件第48页，本讲稿共66页定理3 若若A为强对角线优势矩阵，则为强对角线优势矩阵，则 lii 0,uii 0(i=1,2,n)在这种情况下，在这种情况下，A的各阶主子矩阵的各阶主子矩阵A1,A2An均是强对角均是强对角线优势矩阵线优势矩阵.根据阿达马定理知根据阿达马定理知,|Ai|0,按按定理定理1知知lii 0,uii 0(i=1,2,n)，证毕。，证毕。1.6 1.6 消元法的应用条件消元法的应用条件证明：证明：所谓所谓强对角线优势矩阵强对角线优势矩阵是指其对角线上元是指其对角线上元素的绝对值大于同行上其余元素绝对值之和的矩素的绝对值大于同行上其余元素绝对值之和的矩阵，用公式表示为阵，用公式表示为:第49页，本讲稿共66页2 主元素法1.消元法有缺点v对于几个公式对于几个公式lij=分子分子/ujj,uij=分子分子/lii,zi=分子分子/lii,xi=分子分子/uii,如果分母小会把分子的误差放大如果分母小会把分子的误差放大v公式公式 lik ukj，这些累计量在运算量大时累积的，这些累计量在运算量大时累积的误差也会很大。误差也会很大。v分母为零的时候无法计算分母为零的时候无法计算提出主元素法是为控制舍入误差第50页，本讲稿共66页2.1 列主元素法列主元素法就是在待消元方程的所在列中列主元素法就是在待消元方程的所在列中选取主元素选取主元素,经方程的行交换经方程的行交换,置主元素置主元素于于对角线位置对角线位置后进行消元的方法后进行消元的方法.思路思路:主元素主元素:绝对值最大的元素。最大的元素。列主元素法交列主元素法交换原原则：在第在第k k列中将主元素所列中将主元素所在的方程与第在的方程与第k k个方程个方程进行交行交换，使主元素位，使主元素位于第于第k k个个对角角线元素位置上。元素位置上。第51页，本讲稿共66页 10 x1-19x2-2x3=3 (1)-20 x1+40 x2+x3=4 (2)x1+4x2+5x3=5 (3)第一列选择第一列选择-20作为该列的作为该列的主元素主元素2.1 列主元素法用列主元素法解下列线性方程组例例3.23.2：解解:1第52页，本讲稿共66页2.1 列主元素法-20 x1+40 x2+x3=3 (4)10 x1-19x2-2x3=4 (5)x1+4x2+5x3=5 (6)计算计算l21,l31(消去消去(5)(6)中的中的x1)经过方程的行交换经过方程的行交换,将将-20置于置于a11的位置的位置l21=-10/20=-0.5，l31=-1/20=-0.05(5)-l21(4),(6)-l31(4)后得后得:第53页，本讲稿共66页 x2 1.5x3=5 (7)6x2+5.05x3=5.2 (8)选选6为主元素为主元素,同上方程换行同上方程换行,消去消去x26x2+5.05x3=5.2 (9)x2 1.5x3=5 (10)2.1 列主元素法x1被消去了被消去了1-2.34168x3=4.13332 (11)(换行换行)(消去消去x2)第54页，本讲稿共66页保留有主元素的方程保留有主元素的方程:-2.34168x3=4.13332 (11)-20 x1+40 x2+x3=4 (4)6x2+5.05x3=5.2 (9)回代回代x3=-1.76511x2=2.35230 x1=4.416342.1 列主元素法第55页，本讲稿共66页如果不是按列选主元素，而是在全体待选如果不是按列选主元素，而是在全体待选系数中选取，则得系数中选取，则得全主元素法。全主元素法。10 x1-19x2-2x3=3 (1)-20 x1+40 x2+x3=4 (2)x1+4x2+5x3=5 (3)选择所有系数中绝对值最大的选择所有系数中绝对值最大的40作为作为主元素，主元素，交换第一、二行和交换第一、二列使该主元交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得素位于对角线的第一个位置上，得2.2 全主元素法用全主元素法解下列线性方程组例例3.33.3：解解:第56页，本讲稿共66页计算计算l21=-19/40=0.475，l31=4/40=0.1(5)-l21(4),(6)-l31(4)得得 0.5x1 1.525x3=4.9 (7)3x1+4.9x3=4.6 (8)选选4.9为主元素为主元素,重复前面两个步骤重复前面两个步骤2.2 全主元素法40 x2-20 x1+x3=4 (4)-19x2+10 x1-2x3=3 (5)4x2+x1+5x3=5 (6)第57页，本讲稿共66页2.2 全主元素法 4.9x3+3x1=4.6 (9)1.525x3+0.5x1=4.9 (10)1.43366x1=6.33161 (11)保留有主元素的方程保留有主元素的方程40 x2-20 x1+x3=4 (4)4.9x3+3x1=4.6 (9)1.43366x1=6.33161 (11)回代回代x1=4.41634 x3=-1.76511x2=2.35230第58页，本讲稿共66页2.2 全主元素法主元素高斯消元法较普通消元法的好处：主元素高斯消元法较普通消元法的好处：在消元过程中减小了舍入误差；在回代过程中采用在消元过程中减小了舍入误差；在回代过程中采用数值较大的主元素作分母，可以减小除法运算的误数值较大的主元素作分母，可以减小除法运算的误差；差；具有良好的数值稳定性具有良好的数值稳定性全主元素法的精度优于列主元素法，但排序时全主元素法的精度优于列主元素法，但排序时间较列主元素法长，既要进行行交换，又要进间较列主元素法长，既要进行行交换，又要进行列交换，还需要进行未知量序号的恢复，导行列交换，还需要进行未知量序号的恢复，导致运算量较大。致运算量较大。第59页，本讲稿共66页本章小结1.消元法的过程（消元，回代）消元法的过程（消元，回代）2.消元过程的计算公式（紧凑格式）消元过程的计算公式（紧凑格式）3.几种经典算法几种经典算法高斯消元法（高斯消元法（lii=1）克劳特消元法（克劳特消元法（uii=1）平方根法（系数矩阵为对称阵；平方根法（系数矩阵为对称阵；uijlji）追赶法（系数矩阵为三对角矩阵）追赶法（系数矩阵为三对角矩阵）4.上述上述4种消元法的应用条件种消元法的应用条件5.选选主元主元的的高斯高斯消元法消元法列主元素法列主元素法全主元素法全主元素法第60页，本讲稿共66页本章小结第61页，本讲稿共66页v系数系数lij、uij的计算公式的计算公式:（择定）（择定）（择定）本章小结本章小结第62页，本讲稿共66页本章小结平方根法平方根法第63页，本讲稿共66页本章小结追赶法追赶法第64页，本讲稿共66页本章小结定理定理1 若若A的各阶主子式均不为的各阶主子式均不为0,则则lii 0,uii 0，消元法可用消元法可用。定理定理2 若若A为实对称正定矩阵为实对称正定矩阵,则则lii 0,uii 0(i=1,2,n)，消元法可用，消元法可用。定理定理3 若若A为强对角线优势矩阵，则为强对角线优势矩阵，则 lii 0,uii 0(i=1,2,n)消元法可用消元法可用。阿达马定理 r阶线组阶线组|Ar|0的一个充分条件为的一个充分条件为 强对角线条件成立。强对角线条件成立。消元法应用条件：消元法应用条件：第65页，本讲稿共66页总结消元法的紧凑格式高斯消元法克劳特消元法平方根法追赶法消元法的使用条件（2个）列主元素全主元素第66页，本讲稿共66页