計(jì)算方法-6.1Gauss消去法

1、2021-12-131第六章 線性方程組的解法 6.1 Gauss消去法消去法第六章 線性方程組的解法6.3 對(duì)稱矩陣對(duì)稱矩陣直接三角分解法直接三角分解法 6.2 直接三角分解法直接三角分解法 6.5 誤差分析誤差分析 6.4 追趕法追趕法(Thomas法法) 6.6 迭代法迭代法2 本章要點(diǎn)線性方程組的解法:直接解法和迭代法主要?dú)w結(jié)為三角形方程組的求解包括一般線性方程組的Gauss消去法、Gauss列主元法、對(duì)稱正定方程組的平方根法、三對(duì)角方程組的追趕法等及雅可比迭代和塞德爾迭代法2021-12-133實(shí)際問題中的線性方程組分類：按系數(shù)矩陣中零元素的個(gè)數(shù)：稠密線性方程組稀疏線性方程組按未知量

2、的個(gè)數(shù)：高階線性方程組低階線性方程組(如1000)按系數(shù)矩陣的形狀對(duì)稱正定方程組三角形方程組三對(duì)角占優(yōu)方程組2021-12-134(80%)解線性方程組的兩類方法：直接法: 經(jīng)過有限次運(yùn)算后可求得方程組精確解的方法(不計(jì)舍入誤差)迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）直接法概述直接法是將原方程組化為一個(gè)或若干個(gè)三角形方程組的方法，共有若干種對(duì)于線性方程組bAx nnnnnnaaaaaaaaaA212222111211nxxxx21nbbbb21其中系數(shù)矩陣未知量向量常數(shù)項(xiàng)-(1)2021-12-136根據(jù)Cramer(克萊姆)法則,若

3、0)det(A有唯一解則方程組bAx 若用初等變換法求解,則對(duì)其增廣矩陣作行初等變換:),(bAA),()1()1(bA),()2()2(bA經(jīng)過n-1次),()()(nnbA為上三角陣目標(biāo)：)(nA的解不難得到則方程組)()(nnbxA2021-12-137bAx bAx )()(nnbxA同解即以上求解線性方程組的方法稱為Gauss消去法即和兩個(gè)三角形矩陣分解成的系數(shù)矩陣如果將線性方程組,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消去法消去法一、消元與回代計(jì)算)1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaabAx 對(duì)線性方程組對(duì)其增廣矩陣施行行初等變換:),()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假定定義行乘數(shù)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由于元素不為零的第一列中至少有一個(gè)則 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(定義行乘數(shù)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將化為步后當(dāng)經(jīng)過),( ,1)1()1(bAnk),()()(nnbA0)det(A由于niaiii,2 , 10)(可知有唯一解上三角形方程組因此)()(,nnbxA2021-12-1315)(nnnnnabx 1 ,2 ,2, 1nni)(1)()(iiinijjiijiiiaxabx2021-12-1316的解：因此可得線性方程組bAx 以上討論告訴我們，對(duì)具有上三角形系數(shù)矩陣的方程組求解極為方便。當(dāng)然,若方程組的系數(shù)矩陣為下三角形,則求解也很方便。于是對(duì)于一般形式的方程組，我們總設(shè)法把它

8、化為系數(shù)矩陣呈上(或下)三角形的方程組來求解。為了達(dá)到目的，可利用消去法進(jìn)行。現(xiàn)舉例如下: 解方程組 2021-12-1317(66)2240532321321321xxxxxxxxx 作-消去中的x1，作-4消去中的x1，則方程組化為 對(duì)方程組(66)作- ，得到三角形方程組7312323323363123xxxxxx 2021-12-1318(66) (66) 1027363323232321xxxxxxx 從方程組(66“)的方程解出x3,將所得的結(jié)果代入方程求出x2,再把x3、x2同時(shí)代入方程解出x1。這樣可求出方程組的解為 上述求解方程組的方法就是高斯(Gauss)消去法。從式(66

9、)到 (66)的過程稱為消元過程而由(66)求出x3、x2、x1的過程稱為回代過程。因此用高斯消去法求解性方程組要經(jīng)過消元和回代兩個(gè)過程。123131,424xxx2021-12-13192021-12-13二、Gauss消去法的運(yùn)算量計(jì)算機(jī)作乘除運(yùn)算所耗時(shí)間要遠(yuǎn)遠(yuǎn)多于加減運(yùn)算且在一個(gè)算法中，加減運(yùn)算和乘除運(yùn)算次數(shù)大體相當(dāng)故在衡量一個(gè)算法的運(yùn)算量時(shí)只需統(tǒng)計(jì)乘除的運(yùn)算次數(shù)步消元時(shí)作第k乘法次數(shù)：次)1)(knkn除法次數(shù)：次)(kn數(shù)為步消元乘除法運(yùn)算總次作第k次)2)(knkn20總次數(shù)為步消元需作乘除法運(yùn)算完成全部1n11)2)(nkknkn652323nnn全部回代過程需作乘除法的總次數(shù)為

10、niin1)1(222nn于是Gauss消去法的乘除法運(yùn)算總的次數(shù)為MD3323nnn)(323nOn2021-12-1321很大時(shí)當(dāng)n3323nnnMD33n時(shí)如20nGauss消去法乘除法約為2700次而如果用Cramer法則的乘除法運(yùn)算次數(shù)約為20)120)(120( !2020109或2700)120(用行列式定義用行列式性質(zhì)2021-12-1322例1.用Gauss消去法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）210001. 02121xxxx解:本方程組的精度較高的解為Tx)00010001. 1 ,99989999. 0(* 用Gauss消去法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算)Gaus

11、s列主元消去法的引入2021-12-1323三、 Gauss列主元消去法),(bAA21111000100. 01000021m441000. 111000. 101000100. 0999900. 1,00. 021xx回代后得到與精確解相比,該結(jié)果誤差較大究其原因,在求行乘數(shù)時(shí)用了很小的數(shù)0.0001作除數(shù)主元2021-12-1324前述順序消去法是按序通過用 a11,a(1)22,a(n-2)n-1(a(k-1)kk0)作為除數(shù)來達(dá)到消元目的的。在實(shí)際計(jì)算時(shí),由于舍入誤差的影響,計(jì)算結(jié)果會(huì)改變很大,甚至于完全失真。2021-12-1325),(bAA121000100. 011 0001

12、. 021m00. 1200. 1011如果在求解時(shí)將1,2行交換,即0.999900. 1,00. 121xx回代后得到該結(jié)果與精確解近似程度很高2021-12-1326例2.解線性方程組(用8位十進(jìn)制尾數(shù)的浮點(diǎn)數(shù)計(jì)算)321643. 5072. 12623. 4712. 3132103218xxx解:這個(gè)方程組和例1一樣,若用Gauss消去法計(jì)算會(huì)有小數(shù)作除數(shù)的現(xiàn)象,若采用換行的技巧,則可避免),(bAA321643. 5072. 12623. 4712. 3132108行交換因此的列元素為絕對(duì)值最大很小3 , 1,2,10138a2021-12-1327 31rr1233210623.

13、4712. 31643. 5072. 12883121105 . 05 . 0mm101 . 05 . 03103 . 0102 . 001018015. 0103176. 00643. 5072. 12絕對(duì)值最大不需換行92722629. 032m54138685. 05 . 031041555186. 0001018015. 0103176. 00643. 5072. 12),()1()1(bA),()2()2(bA),()3()3(bA2021-12-1328)3()3(3333abx 經(jīng)過回代后可得)1(113)1(132)1(12)1(11axaxabx54138685. 01041

14、555186. 039257367. 0)2(223)2(23)2(22axabx103176. 01018015. 05 . 03x05088607. 049105820. 0方程組的準(zhǔn)確解為Tx)367257384. 0 ,050886075. 0,491058227. 0(*2021-12-1329例2所用的方法是在Gauss消去法的基礎(chǔ)上,利用換行避免小主元作除數(shù),該方法稱為Gauss列主元消去法列主元消去法2021-12-1330 高斯列主元素消去法是順序消去法的一種改進(jìn)。它的基本思想是在逐次消元時(shí)總是選系數(shù)子矩陣的第一列元素中絕對(duì)值最大的元素(稱之為主元)做除數(shù),按順序消去法的步驟

15、消元。 除了列主元消去法，求解線性方程組常用的還有全主元消去法。四、 Gauss-Jordan消去法 前面所述的消去法均要進(jìn)行兩個(gè)過程,即消元過程和回代過程。但對(duì)消元過程稍加改變可以把線性方程組的系數(shù)矩陣化為對(duì)角陣 *Dxb1ndDd2021-12-1331 此時(shí)求解就不要回代了。這種無回代過程的主元素消去法稱為 高斯約當(dāng)(Jordan)消去法。 特別是方程組還可化為( )11( )22( )1nnnnnnbxxbaxb322021-12-13顯然等號(hào)右端即為方程組的解。陣。途是求一個(gè)矩陣的逆矩方法主要用法大。乘除法，要比高斯消去次需求解過程。計(jì)算量大約常數(shù)項(xiàng)得到，無需回代解就在約化為單位矩陣，計(jì)算陣將線性方程組的系數(shù)矩下方和上方的元素，消去法通過消去對(duì)角線