計(jì)算方法第三講

1、第二章第二章 解線性代解線性代數(shù)方程組的直接法數(shù)方程組的直接法 Gauss 消去法 三角分解法 矩陣求逆 舍入誤差對(duì)解的影響第三講 Gauss 消去法11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb3.1 Gauss 消去法 3.3 列主元的Gauss 消去法3.2 Jordan 消去法 3.4 LU分解法不考慮舍入誤差，通過(guò)有限四則運(yùn)算進(jìn)行求解，不考慮舍入誤差，通過(guò)有限四則運(yùn)算進(jìn)行求解，這就是所謂這就是所謂直接法直接法。1112121222121212,nnnnnnTTnnaaaaaaAaaabb bbxx xxA

2、xb方程類型： n個(gè)方程，n個(gè)未知量 |A|0方法1. Gramer 法則，運(yùn)算量為 ，完美但不現(xiàn)實(shí)。方法2. Gauss 消去法，它的發(fā)現(xiàn)可疑追溯2BC的中國(guó)，該算法以其高效性為諸多計(jì)算機(jī)系統(tǒng)廣泛使用。,1,2,iiDxinD(1)!(1)nnn引例：123123123471225815361019xxxxxxxxx1232334712369 1xxxxxx 123111xxx注：Gauss 消元法包括兩個(gè)主要步驟：1. 消去（一般方程組 上三角形式的方程組）2. 回代，即求上三角形是方程組的解。消元步驟的實(shí)質(zhì)是用初等變換作用于系數(shù)矩陣A的增廣矩陣 上，將 化為上三角形式矩陣，即AA1471

3、225815361019213123rrrr 147120369061117322rr 14712036900113.1 高斯（高斯（ Gauss ）消去法）消去法第一步消元：不妨設(shè)第一步消元：不妨設(shè)a11 0，記，記 li1= ai1 / a11 ，用，用 li1 乘乘第一個(gè)方程加到第第一個(gè)方程加到第i個(gè)方程上去，個(gè)方程上去，如此繼續(xù)下去，第如此繼續(xù)下去，第k-1步可將方程轉(zhuǎn)化為步可將方程轉(zhuǎn)化為(1)(1)(1)(1)(1)(1)111122121111(2)(2)(2)(2)22222221 1(2)(2)(2)(2)221 1,nnjjnnjjijnnnnnnjnjijaxaxaxbaa

4、bbaxaxbaal aaxaxbaal a(2)(2)1 11 1,ijijijiiiaal abbl b(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )( )( )( )( )1,1,111,1( )( )( )( ),11nnnnkkkkkkknnkkkkkkkkkkkknnkkkkkn kknkknnnka xa xa xbaxaxbaxaxbaxaxaxbaxaxaxb( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaki jnaal abbl b (1)(1)(1)(1)1111

5、2211(2)(2)(2)22222( )( )( )(1)(1)(1)1,111,1(1)(1)(1)11nnnnkkkkkkknnkkkkkkkknnkkkknkknnnka xa xa xbaxaxbaxaxbaxaxbaxaxb( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaki jnaal abbl b 按上述消元手續(xù)做按上述消元手續(xù)做n-1n-1步后，原方程組即可加工步后，原方程組即可加工成上三角方程組的形式成上三角方程組的形式(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )(

6、 )( )( )0nnnnkkkkkkknnknnnnnnnnna xa xa xbaxaxbaxaxbaxba第二步，回代第二步，回代 即是利用回代求解經(jīng)過(guò)消元手續(xù)最終得到的方即是利用回代求解經(jīng)過(guò)消元手續(xù)最終得到的方程組，其程組，其回代回代公式為：公式為： ( )( )1/()/,1,2,1nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 消去法計(jì)算量的估計(jì)：消去法計(jì)算量的估計(jì)：消去法中消去法中第第k步步的乘除法計(jì)算量為的乘除法計(jì)算量為(n-k)(n-k+2) 加減法計(jì)算量為加減法計(jì)算量為(n-k)(n-k+1)做完做完n1步后總計(jì)算量：步后總計(jì)算量：乘除法：乘除法：加減法：加

7、減法：321115()(2)326nknnnNnk nk3111()(1)33nknnQnk nk回代過(guò)程計(jì)算量：回代過(guò)程計(jì)算量： 乘除法計(jì)算量乘除法計(jì)算量 加減法計(jì)算量加減法計(jì)算量總計(jì)算量為：總計(jì)算量為：乘除法計(jì)算量乘除法計(jì)算量加減法計(jì)算量加減法計(jì)算量221(1)22nknnNnk2121()22nknnQnk321233nnNNNn32125326nnnQQQ消去過(guò)程算法如下：for k=1,n-1for i=k+1,nC=A(i,k)/A(k,k)for j=k+1,n+1A(i,j)= A(i,j)-C*A(k,j)endendend回代過(guò)程算法如下：x(n)=A(n,n+1)/A(n

8、,n)for k=n-1,1for j=k+1,nA(k,n+1)= A(k,n+1)-A(k,j)*x(j)endx(k)=A(k,n+1)/A(k,k)end3.2 Jordan 消去法14712258153610192 2 13 3 1rrrr 14712036906111731243 2 2rrrr 101003690011132 6 3rrrr 100103030011123r 100101010011Jordan 消去法包含n+1步，其第k步為：若 ，則( )( )(1)( )( )(1)( )( )/,1,kkikikkkkkkkkkijijikkjiiikklaaaal abb

9、l bik jkn ( )0,1,kkkakn其第n+1步為：( )(1)( )( ),1,1,iiniiiiiiibbaina 其復(fù)雜度為321()(2)22nknnnk nknnn=25時(shí)，Gauss 消去法計(jì)算乘除共Jordan消去法計(jì)算乘除共注：Gauss 法要優(yōu)于Jordan 法32582833nnnflop32842522nnnflop3.3 選主元的高斯消去法選主元的高斯消去法稱稱 為消去法第為消去法第k步計(jì)算的主元，當(dāng)步計(jì)算的主元，當(dāng) 絕絕對(duì)值很小時(shí)，會(huì)導(dǎo)致誤差增加，從而引起算對(duì)值很小時(shí)，會(huì)導(dǎo)致誤差增加，從而引起算法不穩(wěn)定。法不穩(wěn)定。因此，在消去法中，我們需要引入選主元法。因此

10、，在消去法中，我們需要引入選主元法。即每次消元時(shí)，從該列中選取系數(shù)絕對(duì)值最即每次消元時(shí)，從該列中選取系數(shù)絕對(duì)值最大者作為主元進(jìn)行消元，大者作為主元進(jìn)行消元，稱為列主元消去法稱為列主元消去法。( )kkka( )kkka全主元的Gauss消去法 一類特殊的矩陣（對(duì)角占有矩陣，對(duì)稱正定陣）在Gauss消去的意義下，不改變其性質(zhì)，不必選主元。 可以證明，全主元的Gauss消去法對(duì)于非奇異矩陣是穩(wěn)定的。3.4 高斯消去法的矩陣形式高斯消去法的矩陣形式消去法消元過(guò)程可以通過(guò)對(duì)下面增廣矩陣作初消去法消元過(guò)程可以通過(guò)對(duì)下面增廣矩陣作初等變換來(lái)實(shí)現(xiàn)。等變換來(lái)實(shí)現(xiàn)。11121121222212 , nnnnnnnaaabaaabA baaab設(shè)設(shè) ， 記記( )0kkka( )( )/,1,kkikikkklaaikn 1,100010010001kkkn kLll則消去法相當(dāng)于則消去法相當(dāng)于記記(1)(1)(1)(1)111211(2)(2)(2)222211( )( )0 , 00nnnnnnnnaaabaabLL A bab111121nLLLL則則2131321,11,21,31231101111nnnnnnnnlllLlllllll我們記我們記于是可得矩陣于是可得矩陣A的如下分解的如下分解這稱為這稱為矩陣矩陣A的的LR分解分解(1)(1)(1)11121(2)(2)222( )0