第五章方程组-Gauss消去法1课件.ppt

1、引言引言 高斯消去法高斯消去法选主元素的高斯消去法选主元素的高斯消去法矩阵的三角分解矩阵的三角分解解三对角方程组的追赶法解三对角方程组的追赶法 第六章第六章 方程组的数值解法方程组的数值解法解对称正定方程组的平方根法解对称正定方程组的平方根法解线性方程组的迭代法解线性方程组的迭代法病态方程组和迭代改善法病态方程组和迭代改善法向量和矩阵的范数向量和矩阵的范数实际问题中的线性方程组分类：实际问题中的线性方程组分类：按系数矩阵中按系数矩阵中零元素的个数：零元素的个数：稠密线性稠密线性方程组方程组稀疏线性稀疏线性方程组方程组按未知量按未知量的个数：的个数：高阶线性高阶线性方程组方程组低阶线性低阶线性方

2、程组方程组(如如1000)1000)(80%)(80%)按系数矩按系数矩阵的形状阵的形状对称正定对称正定方程组方程组三角形三角形方程组方程组三对角占三对角占优方程组优方程组1 1、消元与回代计算、消元与回代计算bAx 对线性方程组对线性方程组对其增广矩阵施行行初等变换对其增广矩阵施行行初等变换:)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa),(bAA),()1()1(bA记0)det(A如果1 1、GaussGauss消去法直接法消去法直接法)2()2()2(2)2(2)2(2)2(22)1(1)1(

3、1)1(12)1(1100nnnnnnbaabaabaaa),()2()2(bA0)1(11a假定定义行乘数定义行乘数niaamii,3,2)1(11)1(11则行第行第,11imi)1(11)1()2(jiijijamaa)1(11)1()2(bmbbiiinji,3,2,ni,3,2),()1()1(bA0)1(11a如果0)det(A由于元素不为零的第一列中至少有一个则 A行交换后消元的第一行与第则将如1)1()1()1(1),(,01ibAai)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(1100nnnnnnbaabaabaaa且且0)det(将化为步后

4、第因此),(,1,)1()1(bAk)()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11knknnknkkkkknkkknnbaabaabaabaaa),()()(kkbA),()1()1(bA0)det(定义行乘数定义行乘数nkiaamkkkkikik,1)()(则行第行第,ikmki)()()1(kkjikkijkijamaa)()()1(kkikkikibmbbnkji,1,nki,1)()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa),()1()1(bA将化为步后当经过),(,1)1()1(bAnk)

5、,()()(nnbA0)det(A由于niaiii,2,10)(可知的解：因此可得线性方程组bAx 有唯一解上三角形方程组因此)()(,nnbxA()()nnnnnnbxa 1,2,2,1nni()()1()niiiijjj iiiiibaxxa 上述过程的求解过程叫做回代过程上述过程的求解过程叫做回代过程定理定理1 1：如果如果A A为为n n阶非奇异矩阵，则可通阶非奇异矩阵，则可通过过GaussGauss消去法将方程组的系数阵化为三角消去法将方程组的系数阵化为三角型系数阵。型系数阵。定理定理2 2：如果如果n n阶矩阵阶矩阵A A的所有顺序主子式均不为零的所有顺序主子式均不为零，则可通过，

6、则可通过GaussGauss消去法，将方程组的系数阵化为消去法，将方程组的系数阵化为三角型系数阵。三角型系数阵。直接法是将原方程组化为一个或若干个三角形直接法是将原方程组化为一个或若干个三角形方程组的方法，共有若干种方程组的方法，共有若干种对于线性方程组对于线性方程组系数矩阵系数矩阵未知量向量未知量向量 常数项常数项Axb 111212122212nnnnnnaaaaaaAaaa 12nxxxx 12nbbbb 其中其中-(1)-(1)2 2、矩阵的三角分解直接法、矩阵的三角分解直接法根据根据Cramer(Cramer(克莱姆克莱姆)法则法则,若若0)det(A有唯一解则方程组bAx dete

7、rminantaldeterminantal|)det(AA 行列式的记号行列式的记号若用初等变换法求解若用初等变换法求解,则对其增广矩阵作行初等变换则对其增广矩阵作行初等变换:),(bAA),()1()1(bA),()2()2(bA经过经过n-1n-1次次),()()(nnbA为上三角阵目标：)(nA的解不难得到则方程组)()(nnbxAbAx bAx)()(nnbxA同解同解即即以上求解线性方程组的方法称为以上求解线性方程组的方法称为GaussGauss消去法消去法即和两个三角形矩阵分解成的系数矩阵如果将线性方程组,ULAbAx LUA 则则bLUx bLy yUx 都是三角都是三角形方程

8、组形方程组上述方法称为直接三角形分解法上述方法称为直接三角形分解法-(2)-(2),()1()1(bAGaussGauss消元过程与系数矩阵的分解消元过程与系数矩阵的分解GaussGauss消去法消元过程的矩阵描述消去法消元过程的矩阵描述)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaaniaamii,3,2)1(11)1(11行变换相行变换相当于左乘当于左乘初等矩阵初等矩阵由于1111211nmmL令令则则),()1()1(1bAL),()2()2(bA1111,1knkkkmmL显然若令显然若令则有：则

9、有：),()()(kkkbAL),()1()1(kkbA1,3,2,1nk为上三角矩阵)(nAU 为单位下三角矩阵111211nLLLL故故:)(111211nnALLLALU因此因此:),()1()1(1bAL 2L1nL),()()(nnbA从而从而:AL 12L1nL)(nA111111,3,2,1,2,12,11,1323121nnnnnnnnmmmmmmmmmmL即)()2(2)2(22)1(1)1(12)1(11nnnnnaaaaaa)(nAU 且UdetAdet顺序主元niiiia1)(定义定义1.1.不带行交换的不带行交换的Gauss Gauss 消去法的消元过程消去法的消元过

10、程,产生产生一个单位下三角矩阵一个单位下三角矩阵L L和一个上三角矩阵和一个上三角矩阵U,U,即即该过程称之为该过程称之为LUA.分解的矩阵LUA由上述分析不难得到由上述分析不难得到nnnknknkkknkaaaaaaaaaA11111111111nknkmmm)()()()1(1)1(1)1(11nnnkknkkknkaaaaaa阶顺序主子式kkAkkkULA kAdetkUdetkiiiia1)(kLkUnkAk,2,10detniaiii,2,10)(GaussGauss消去法消去法可以执行可以执行定理定理1.1.,0detkkADAn的顺序主子式阶方阵若,1,2,1nk存在且唯一分解结

11、果的则LUALUA在定理中在定理中,可能注意到可能注意到0detnnAD0)(nnna即可能存在可能存在分解并不影响的这对LUA起决定作用消去法的回代能否进行用但对方程组GaussbAx 不论是不论是GaussGauss消去法还是直接三角形分解法消去法还是直接三角形分解法,最都归结为解三角形方程组最都归结为解三角形方程组2 2、三角形线性方程组的解法、三角形线性方程组的解法Lxb Uxb 11212212nnnnlllLlll 11121222nnnnuuuuuUu 若记若记下三角形线性方程组下三角形线性方程组上三角形线性方程组上三角形线性方程组的求解思路：下三角形方程组bLx 1112122

12、212nnnnnlxllxlllx 12nbbb Lxb 2112222l xl xb 1122nnnnnnl xlxlxb1111l xb 1122iiiiiil xl xl xb 即即回代方向回代方向1111lbx iiijjijiilxlbx11ni,3,2的求解思路：上三角形方程组bUx nnnnnxxxuuuuuu2122211211nbbb21bUx 其解为其解为11212111bxuxuxunnnnnnbxu1,111,1nnnnnnnbxuxuininiiiiiibxuxuxu11,其解为其解为:nnnnubx iinijjijiiuxubx11,2,2,1nni回回代代方方向

13、向3 3、GaussGauss消去法的运算量消去法的运算量计算机作乘除运算所耗时间要远远多于加减运算计算机作乘除运算所耗时间要远远多于加减运算且在一个算法中，加减运算和乘除运算次数大体相当且在一个算法中，加减运算和乘除运算次数大体相当故在衡量一个算法的运算量时只需统计乘除的运算次数故在衡量一个算法的运算量时只需统计乘除的运算次数步消元时作第k乘法次数：乘法次数：次)1)(knkn除法次数：除法次数：次)(kn数为步消元乘除法运算总次作第k次)2)(knkn总次数为步消元需作乘除法运算完成全部1n11)2)(nkknkn652323nnn全部回代过程需作乘除法的总次数为全部回代过程需作乘除法的总

14、次数为niin1)1(222nn于是于是GaussGauss消去法的乘除法运算总的次数为消去法的乘除法运算总的次数为MD3323nnn)(323nOn数级数级很大时当n3323nnnMD33n时如20nGaussGauss消去法乘除法约为消去法乘除法约为27002700次次而如果用而如果用CramerCramer法则的乘除法运算次数约为法则的乘除法运算次数约为20)120)(120(!2020109或或2700)120(用行列式定义用行列式定义用行列式性质用行列式性质例例1.1.用用GaussGauss消去法解线性方程组消去法解线性方程组(用用3 3位十进制浮位十进制浮点数计算）点数计算）21

15、0001.02121xxxx解解:本方程组的精度较高的解为本方程组的精度较高的解为Tx)99989999.0,00010001.1(*用用GaussGauss消去法求解消去法求解(用用3 3位十进制浮点数计算位十进制浮点数计算)1 1、GaussGauss列主元消去法的引入列主元消去法的引入),(bAA21111000100.01000021m441000.111000.101000100.09999999900.1,00.021xx回代后得到回代后得到与精确解相比与精确解相比,该结果相当糟糕该结果相当糟糕究其原因究其原因,在求行乘数时用了很小的数在求行乘数时用了很小的数0.00010.000

16、1作除数作除数主元主元),(bAA121000100.011 0001.021m00.1200.1011如果在求解时将如果在求解时将1,21,2行交换行交换,即即0.99990.999900.1,00.121xx回代后得到回代后得到这是一个相当不错的结果这是一个相当不错的结果),(bAA例例2.2.解线性方程组解线性方程组(用用8 8位十进制尾数的浮点数计算位十进制尾数的浮点数计算)321643.5072.12623.4712.3132103218xxx解解:这个方程组和例这个方程组和例1 1一样一样,若用若用GaussGauss消去法计算会消去法计算会有小数作除数的现象有小数作除数的现象,若

17、采用换行的技巧若采用换行的技巧,则可避则可避免免321643.5072.12623.4712.3132108行交换因此的列元素为绝对值最大很小3,1,2,10138a 31rr1233210623.4712.31643.5072.12883121105.05.0mm101.05.03103.0102.001018015.0103176.00643.5072.12绝对值最大绝对值最大不需换行不需换行92722629.032m54138685.05.031041555186.0001018015.0103176.00643.5072.12),()1()1(bA),()2()2(bA),()3()3

18、(bA)3()3(3333abx 经过回代后可得经过回代后可得)1(113)1(132)1(12)1(11axaxabx54138685.01041555186.039257367.0)2(223)2(23)2(22axabx103176.01018015.05.03x05088607.049105820.0事实上事实上,方程组的准确解为方程组的准确解为Tx)367257384.0,050886075.0,491058227.0(*例例2 2所用的方法是在所用的方法是在GaussGauss消去法的基础上消去法的基础上,利用利用换行避免小主元作除数换行避免小主元作除数,该方法称为该方法称为GaussGauss列主列主元消去法元消去法开始开始EPSnbA,输入输出无解信息输出无解信息k1x输出解EPSnnA|),(|nk kk1P选取主元素EPSP|消元消元换行换行停机停机回代求解回代求解TTTFFFGaussGauss列主元消去法的算法设计列主元消去法的算法设计(一一)流程图流程图