计算方法-6.1Gauss消去法

1、2021-12-131第六章 线性方程组的解法 6.1 Gauss消去法消去法第六章 线性方程组的解法6.3 对称矩阵对称矩阵直接三角分解法直接三角分解法 6.2 直接三角分解法直接三角分解法 6.5 误差分析误差分析 6.4 追赶法追赶法(Thomas法法) 6.6 迭代法迭代法2 本章要点线性方程组的解法:直接解法和迭代法主要归结为三角形方程组的求解包括一般线性方程组的Gauss消去法、Gauss列主元法、对称正定方程组的平方根法、三对角方程组的追赶法等及雅可比迭代和塞德尔迭代法2021-12-133实际问题中的线性方程组分类：按系数矩阵中零元素的个数：稠密线性方程组稀疏线性方程组按未知量

2、的个数：高阶线性方程组低阶线性方程组(如1000)按系数矩阵的形状对称正定方程组三角形方程组三对角占优方程组2021-12-134(80%)解线性方程组的两类方法：直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）直接法概述直接法是将原方程组化为一个或若干个三角形方程组的方法，共有若干种对于线性方程组bAx nnnnnnaaaaaaaaaA212222111211nxxxx21nbbbb21其中系数矩阵未知量向量常数项-(1)2021-12-136根据Cramer(克莱姆)法则,若

3、0)det(A有唯一解则方程组bAx 若用初等变换法求解,则对其增广矩阵作行初等变换:),(bAA),()1()1(bA),()2()2(bA经过n-1次),()()(nnbA为上三角阵目标：)(nA的解不难得到则方程组)()(nnbxA2021-12-137bAx bAx )()(nnbxA同解即以上求解线性方程组的方法称为Gauss消去法即和两个三角形矩阵分解成的系数矩阵如果将线性方程组,ULAbAx LUA 则bLUx bLy yUx 都是三角形方程组上述方法称为直接三角形分解法直接三角形分解法-(2)2021-12-138的求解思路：上三角形方程组bUx nnnnnxxxuuuuuu2

4、122211211nbbb21bUx 2021xuxuxunnnnnnbxu1,111,1nnnnnnnbxuxuininiiiiiibxuxuxu11,其解为:nnnnubx iinijjijiiuxubx11 ,2 ,2, 1nni回代方向2021-12-1310),(bAA6.1 Gauss消去法消去法一、消元与回代计算)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaabAx 对线性方程组对其增广矩阵施行行初等变换:),()1()1(bA记0)det(A如果2021-1

5、2-1311)2()2()2(2)2(2)2(2)2(22)1(1)1(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(bA2021-12-1312行交换后消元的第一行与第则将如1)1()1()1(1),(, 01ibAai0)1(11a如果0)det(A由于元素不为零的第一列中至少有一个则 A)2()2()2(2)2(2)2(2)2(2

6、2)1(1)1(1)1(12)1(1100nnnnnnbaabaabaaa且0)det(将化为步后第因此),( ,1,)1()1(bAk 2021-12-1313则行第行第,ikmki)()()()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11knknnknkkkkknkkknnbaabaabaabaaa),()()(kkbA),()1()1(bA0)det(定义行乘数nkiaamkkkkikik, 1)()()()()1(kkjikkijkijamaa)()()1(kkikkikibmbbnkji, 1,nki, 1 2021-12-1314)()()2(2)2(2

7、)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa),()1()1(bA将化为步后当经过),( ,1)1()1(bAnk),()()(nnbA0)det(A由于niaiii,2 , 10)(可知有唯一解上三角形方程组因此)()(,nnbxA2021-12-1315)(nnnnnabx 1 ,2 ,2, 1nni)(1)()(iiinijjiijiiiaxabx2021-12-1316的解：因此可得线性方程组bAx 以上讨论告诉我们，对具有上三角形系数矩阵的方程组求解极为方便。当然,若方程组的系数矩阵为下三角形,则求解也很方便。于是对于一般形式的方程组，我们总设法把它

8、化为系数矩阵呈上(或下)三角形的方程组来求解。为了达到目的，可利用消去法进行。现举例如下: 解方程组 2021-12-1317(66)2240532321321321xxxxxxxxx 作-消去中的x1，作-4消去中的x1，则方程组化为 对方程组(66)作- ，得到三角形方程组7312323323363123xxxxxx 2021-12-1318(66) (66) 1027363323232321xxxxxxx 从方程组(66“)的方程解出x3,将所得的结果代入方程求出x2,再把x3、x2同时代入方程解出x1。这样可求出方程组的解为 上述求解方程组的方法就是高斯(Gauss)消去法。从式(66

9、)到 (66)的过程称为消元过程而由(66)求出x3、x2、x1的过程称为回代过程。因此用高斯消去法求解性方程组要经过消元和回代两个过程。123131,424xxx2021-12-13192021-12-13二、Gauss消去法的运算量计算机作乘除运算所耗时间要远远多于加减运算且在一个算法中，加减运算和乘除运算次数大体相当故在衡量一个算法的运算量时只需统计乘除的运算次数步消元时作第k乘法次数：次)1)(knkn除法次数：次)(kn数为步消元乘除法运算总次作第k次)2)(knkn20总次数为步消元需作乘除法运算完成全部1n11)2)(nkknkn652323nnn全部回代过程需作乘除法的总次数为

10、niin1)1(222nn于是Gauss消去法的乘除法运算总的次数为MD3323nnn)(323nOn2021-12-1321很大时当n3323nnnMD33n时如20nGauss消去法乘除法约为2700次而如果用Cramer法则的乘除法运算次数约为20)120)(120( !2020109或2700)120(用行列式定义用行列式性质2021-12-1322例1.用Gauss消去法解线性方程组(用3位十进制浮点数计算）210001. 02121xxxx解:本方程组的精度较高的解为Tx)00010001. 1 ,99989999. 0(* 用Gauss消去法求解(用3位十进制浮点数计算)Gaus

11、s列主元消去法的引入2021-12-1323三、 Gauss列主元消去法),(bAA21111000100. 01000021m441000. 111000. 101000100. 0999900. 1,00. 021xx回代后得到与精确解相比,该结果误差较大究其原因,在求行乘数时用了很小的数0.0001作除数主元2021-12-1324前述顺序消去法是按序通过用 a11,a(1)22,a(n-2)n-1(a(k-1)kk0)作为除数来达到消元目的的。在实际计算时,由于舍入误差的影响,计算结果会改变很大,甚至于完全失真。2021-12-1325),(bAA121000100. 011 0001

12、. 021m00. 1200. 1011如果在求解时将1,2行交换,即0.999900. 1,00. 121xx回代后得到该结果与精确解近似程度很高2021-12-1326例2.解线性方程组(用8位十进制尾数的浮点数计算)321643. 5072. 12623. 4712. 3132103218xxx解:这个方程组和例1一样,若用Gauss消去法计算会有小数作除数的现象,若采用换行的技巧,则可避免),(bAA321643. 5072. 12623. 4712. 3132108行交换因此的列元素为绝对值最大很小3 , 1,2,10138a2021-12-1327 31rr1233210623.

13、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(bA2021-12-1328)3()3(3333abx 经过回代后可得)1(113)1(132)1(12)1(11axaxabx54138685. 01041

14、555186. 039257367. 0)2(223)2(23)2(22axabx103176. 01018015. 05 . 03x05088607. 049105820. 0方程组的准确解为Tx)367257384. 0 ,050886075. 0,491058227. 0(*2021-12-1329例2所用的方法是在Gauss消去法的基础上,利用换行避免小主元作除数,该方法称为Gauss列主元消去法列主元消去法2021-12-1330 高斯列主元素消去法是顺序消去法的一种改进。它的基本思想是在逐次消元时总是选系数子矩阵的第一列元素中绝对值最大的元素(称之为主元)做除数,按顺序消去法的步骤

15、消元。 除了列主元消去法，求解线性方程组常用的还有全主元消去法。四、 Gauss-Jordan消去法 前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把线性方程组的系数矩阵化为对角阵 *Dxb1ndDd2021-12-1331 此时求解就不要回代了。这种无回代过程的主元素消去法称为 高斯约当(Jordan)消去法。 特别是方程组还可化为( )11( )22( )1nnnnnnbxxbaxb322021-12-13显然等号右端即为方程组的解。阵。途是求一个矩阵的逆矩方法主要用法大。乘除法，要比高斯消去次需求解过程。计算量大约常数项得到，无需回代解就在约化为单位矩阵，计算阵将线性方程组的系数矩下方和上方的元素，消去法通过消去对角线