線性方程組的高斯消去法

1、第四章方程組的直接解法4.1 Gauss消去法消去法4.1.4 Gauss-Jordan消元法消元法4.1.3 主元素消去法主元素消去法4.1.2 矩陣的三角分解矩陣的三角分解4.1.1 Gauss消去法的計(jì)算過程消去法的計(jì)算過程第四章方程組的直接解法第第4章章 線性方程組的直接解法線性方程組的直接解法教學(xué)目的教學(xué)目的 1. 掌握解線性方程組的高斯消去法、高斯選主元素消去法；掌握解線性方程組的高斯消去法、高斯選主元素消去法；2. 掌握用直接三角分解法解線性方程組的方法；掌握用直接三角分解法解線性方程組的方法；3. 了解解對稱正定矩陣線性方程組的平方根法與解三對角線方程了解解對稱正定矩陣線性方程

2、組的平方根法與解三對角線方程組的追趕法；組的追趕法；4. 掌握向量，矩陣范數(shù)，矩陣的條件數(shù)等概念及方程組的擾動(dòng)分掌握向量，矩陣范數(shù)，矩陣的條件數(shù)等概念及方程組的擾動(dòng)分析。析。教學(xué)重點(diǎn)及難點(diǎn)教學(xué)重點(diǎn)及難點(diǎn) 重點(diǎn)是重點(diǎn)是1. 解線性方程組的高斯消去法、高斯選主元素消去法；解線性方程組的高斯消去法、高斯選主元素消去法；2. 直接三角分解法解線性方程組的方法；直接三角分解法解線性方程組的方法；3. 向量，矩陣范數(shù)，矩陣的條件數(shù)等概念及方程組的擾動(dòng)分析；向量，矩陣范數(shù)，矩陣的條件數(shù)等概念及方程組的擾動(dòng)分析；難點(diǎn)是難點(diǎn)是方程組的擾動(dòng)分析。方程組的擾動(dòng)分析。第四章方程組的直接解法 實(shí)際中，存在大量的解線性方

3、程組的問題。很多數(shù)值方實(shí)際中，存在大量的解線性方程組的問題。很多數(shù)值方法到最后也會(huì)涉及到線性方程組的求解問題：如樣條插值的法到最后也會(huì)涉及到線性方程組的求解問題：如樣條插值的M和和m關(guān)系式，曲線擬合的法方程，方程組的關(guān)系式，曲線擬合的法方程，方程組的Newton迭代等迭代等問題。問題。第第4章章 線性方程組的直接解法線性方程組的直接解法第四章方程組的直接解法nnnnnnnbxaxabxaxa11111110)det(A對線性方程組：對線性方程組：或者：或者：bAx 我們有我們有Gram法則：當(dāng)且僅當(dāng)法則：當(dāng)且僅當(dāng)時(shí)，有唯一的解，而且解為：時(shí)，有唯一的解，而且解為：nnninninniiiiia

4、abaaaabaaDADDDx11111111111det),det(,第四章方程組的直接解法但但Gram法則不能用于計(jì)算方程組的解，如法則不能用于計(jì)算方程組的解，如n100，1033次次/秒的計(jì)算機(jī)秒的計(jì)算機(jī)要算要算10120年年解線性方程組的方法可以分為解線性方程組的方法可以分為2類：類：直接法直接法：準(zhǔn)確，可靠，理論上得到的解是精確的：準(zhǔn)確，可靠，理論上得到的解是精確的迭代法迭代法：速度快，但有誤差：速度快，但有誤差本章講解直接法本章講解直接法對于中小型方程組，常用直接解法。從本質(zhì)上來說，直接方法對于中小型方程組，常用直接解法。從本質(zhì)上來說，直接方法的原理是找一個(gè)可逆矩陣的原理是找一個(gè)可

5、逆矩陣M，使得，使得MA是一個(gè)上三角陣，這一過程一是一個(gè)上三角陣，這一過程一般稱為般稱為“消元消元”過程，消元之后再進(jìn)行過程，消元之后再進(jìn)行“回代回代”，即求解，即求解MAx=Mb。本章討論本章討論Gauss消去法及其變形，以及一些情況下的特殊方法，最后消去法及其變形，以及一些情況下的特殊方法，最后進(jìn)行誤差分析。進(jìn)行誤差分析。第四章方程組的直接解法4.1 Gauss消去法消去法我們知道，下面有我們知道，下面有3種方程的解我們可以直接求出：種方程的解我們可以直接求出：niabxaaadiagAiiiinn, 1,),(2211n次運(yùn)算nilxlbxllllllAiiijjijiinnnn, 1,

6、1121222111（n1）n/2次運(yùn)算第四章方程組的直接解法1 ,122211211niuxubxuuuuuuAiinijjijiinnnn（n1）n/2次運(yùn)算第四章方程組的直接解法對方程組，作如下的變換，解不變對方程組，作如下的變換，解不變交換兩個(gè)方程的次序交換兩個(gè)方程的次序一個(gè)方程的兩邊同時(shí)乘以一個(gè)非一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0 0的數(shù)的數(shù)一個(gè)方程的兩邊同時(shí)乘以一個(gè)非一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0 0數(shù)，加到另一個(gè)方程數(shù)，加到另一個(gè)方程因此，對應(yīng)的對增廣矩陣因此，對應(yīng)的對增廣矩陣(A，b)，作如下的變換，解不變，作如下的變換，解不變交換矩陣的兩行交換矩陣的兩行某一行乘以一個(gè)非某一行乘以

7、一個(gè)非0 0的數(shù)的數(shù)某一個(gè)乘以一個(gè)非某一個(gè)乘以一個(gè)非0 0數(shù)，加到另一行數(shù)，加到另一行消元法消元法就是對增廣矩陣作上述行的變換，變?yōu)槲覀円阎木褪菍υ鰪V矩陣作上述行的變換，變?yōu)槲覀円阎?種類型之一，種類型之一，而后求根而后求根.第四章方程組的直接解法思思路路首先將首先將A化為上三角陣，再回代求解化為上三角陣，再回代求解 。=4.1.1 Gauss消去法的計(jì)算過程消去法的計(jì)算過程我們把方程組我們把方程組Ax=b寫成寫成 1,22111,2222221211, 111212111nnnnnnnnnnnnnnabxaxaxaabxaxaxaabxaxaxa), 2 , 1nj),(),()1()1

8、(bAbA;, 2 , 1(niijijaa)1(設(shè)方程組設(shè)方程組(4,.1.1)的系數(shù)矩陣的系數(shù)矩陣A非奇異非奇異,記記(4.1.1)第四章方程組的直接解法 , 這樣這樣,方程組方程組(4.1.1)又可寫成又可寫成 。消元過程就是要按確定的。消元過程就是要按確定的計(jì)算過程對方程組進(jìn)行初等行變換計(jì)算過程對方程組進(jìn)行初等行變換,將方程組化為上三角方程組將方程組化為上三角方程組.)1()1(bxA nnnnnnnbaaabaaabaaa21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nn

9、nnnnnnaaaabaaabaabab第四章方程組的直接解法第一步消元第一步消元:假設(shè)假設(shè) ,作初等行變換運(yùn)算作初等行變換運(yùn)算0)1(11 a步驟如下：步驟如下：niiaai, 2,1111行第行第nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa運(yùn)算量：運(yùn)算量： (n-1)*(1+n)第四章方程組的直接解法)3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(221113121100000nnnnnnnbaabaabaaabaaaa運(yùn)算量：運(yùn)算量： (n-2

10、)*(1+n-1)=(n-2)n第二步：第二步：niiaai, 3,2)2(22)2(2行第行第)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa第四章方程組的直接解法第第k步消元步消元:設(shè)消去法已進(jìn)行設(shè)消去法已進(jìn)行k-1步步,得到方程組得到方程組 ,此時(shí)對此時(shí)對應(yīng)的增廣矩陣是應(yīng)的增廣矩陣是)()(kkbxA第四章方程組的直接解法第第k步：步：nkiiaakkkkik, 1,k)()(行第行第類似的做下去，我們有：類似的做下去，我們有：運(yùn)算量：運(yùn)算量： (nk)*(1nk1)=(nk)(nk2)()()3(3)3(3)3(33)2(2)2(2)2(2

11、3)2(2211131211000000nnnnnnnnbabaabaaabaaaan1步以后，我們可以得到變換后的矩陣為：步以后，我們可以得到變換后的矩陣為：這就完成了消元過程。這就完成了消元過程。(4.1.4)第四章方程組的直接解法因此，總的運(yùn)算量為：因此，總的運(yùn)算量為：11)2)(nkknkn加上加上 解上述上三角陣的運(yùn)算量解上述上三角陣的運(yùn)算量(n+1)n/2，總共為：，總共為：)(33323nOnnn第四章方程組的直接解法因?yàn)橐驗(yàn)锳非奇異，所以可求解上三角方程組（非奇異，所以可求解上三角方程組（4.1.4），通過逐次），通過逐次代入計(jì)算可得方程組的解，其計(jì)算公式為代入計(jì)算可得方程組的

12、解，其計(jì)算公式為 . 1 , 2, 1,/(,/)(1)(1,)(1,)()(1,nniaxaaxaaxiiinkjjnnniniinnnnnnn(4.1.5)求解上式的過程稱為求解上式的過程稱為回代過程回代過程。以上由消去過程和回代過程合起來求解（以上由消去過程和回代過程合起來求解（4.1.1）的過程就稱）的過程就稱為為Gauss消去法，或稱為順序消去法，或稱為順序Gauss消去法。消去法。第四章方程組的直接解法如果我們用如果我們用Cramer法則計(jì)算（法則計(jì)算（4.1.1）的解，要計(jì)算）的解，要計(jì)算n+1個(gè)階行列式，個(gè)階行列式，并作并作n次除法。如果用子式展開的方法計(jì)算行列式，則計(jì)算次除法

13、。如果用子式展開的方法計(jì)算行列式，則計(jì)算每個(gè)行列式有每個(gè)行列式有n ！次乘法。所以用！次乘法。所以用Cramer法則大約需要（法則大約需要（n+1）?。?！次乘除法運(yùn)算。例如，當(dāng)次乘除法運(yùn)算。例如，當(dāng)n=10時(shí)，約需乘除法運(yùn)算，而用時(shí)，約需乘除法運(yùn)算，而用Gauss消消去法只需去法只需430次乘除法運(yùn)算。次乘除法運(yùn)算。例例4.1 用用Gauss消去法解方程組消去法解方程組 .23132,22011209,23132321321321xxxxxxxxx.32979101011521070231321 解解 第一步消元，令第一步消元，令 得增廣矩陣得增廣矩陣,3/2,20/93121 ll第四章方程

14、組的直接解法第二步消元，令第二步消元，令 得增廣矩陣得增廣矩陣,63/1032 l.63536353001011521070231321 利用回代公式（利用回代公式（4.1.5）依次得到）依次得到在這個(gè)例子中我們寫出的是分?jǐn)?shù)運(yùn)算的結(jié)果。如果在計(jì)算機(jī)上在這個(gè)例子中我們寫出的是分?jǐn)?shù)運(yùn)算的結(jié)果。如果在計(jì)算機(jī)上進(jìn)行計(jì)算，系數(shù)矩陣和中間結(jié)果都用經(jīng)過舍入的機(jī)器數(shù)表示，中間進(jìn)行計(jì)算，系數(shù)矩陣和中間結(jié)果都用經(jīng)過舍入的機(jī)器數(shù)表示，中間結(jié)果和方程組的解都會(huì)有誤差。結(jié)果和方程組的解都會(huì)有誤差。. 1, 1, 1123 xxx4.1.2 矩陣的三角分解矩陣的三角分解從上面的消元過程可以看出，消元過程能順利進(jìn)行的重要條

15、件從上面的消元過程可以看出，消元過程能順利進(jìn)行的重要條件是主元素是主元素 。若用。若用 表示矩陣表示矩陣A的的k階順序階順序主子陣，則有下面的定理。主子陣，則有下面的定理。.1,2,1,0 nkakkkkA第四章方程組的直接解法定理定理4.1 全不為零的充要條件是全不為零的充要條件是A的順序主子的順序主子式式 其中其中 。)., 2 , 1( , 0)(kiaiii ,2,1,0detkiADii nk 證證 先證必要性設(shè)先證必要性設(shè) ，則可進(jìn)行，則可進(jìn)行k-1步消元程。步消元程。顯然顯然 ，對，對 ，由于每步進(jìn)行的初等變換不改，由于每步進(jìn)行的初等變換不改變順序主子式的值，所以第變順序主子式的

16、值，所以第i-1步消元后有步消元后有).,2 , 1( ,0)(kiaiii 01)1(11 Da2i. 0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(11 iiiiiiiiiaaaaaaaaaD,0)(22)(12)(11)( mmmmAAAA用歸納法證充分性。用歸納法證充分性。k=1時(shí)，命題顯然成立。設(shè)命題對時(shí)，命題顯然成立。設(shè)命題對m-1成立。成立?，F(xiàn)設(shè)現(xiàn)設(shè) 由歸納假設(shè)有由歸納假設(shè)有 Gauss消去法可進(jìn)行第消去法可進(jìn)行第m-1步，矩陣步，矩陣A變換為變換為, 2 , 1, 0detmiADii . 1, 2 , 1, 0)( miaiii第四章方程組的直接解法

17、其中其中 是對角元素為是對角元素為 的上三角陣。的上三角陣。因因 是通過消元過程由是通過消元過程由A逐步經(jīng)初等變換得到的，逐步經(jīng)初等變換得到的，A的的m 階順序主階順序主子式等于子式等于 的的m 階順序主子式，即階順序主子式，即由由 可推出可推出 ，定理得證。，定理得證。)(11mA)()1(1, 1)2(22)1(11,mmmmmmaaaa )(mA)(11mA)()1(1,1)2(22)1(11,mmmmmmaaaa 0mD0)( mmma定理定理4.2 在方程組在方程組Ax=b中，中，A非奇異，則當(dāng)非奇異，則當(dāng)A的所有順序主子式的所有順序主子式均不為零時(shí)，可用均不為零時(shí)，可用Gauss消

18、去法求解出方程組的解。消去法求解出方程組的解。特別地，若特別地，若A為對稱正定矩陣，則由對稱正定矩陣的性質(zhì)可知，為對稱正定矩陣，則由對稱正定矩陣的性質(zhì)可知，對原方程組不必作任何處理，可直接對原方程組不必作任何處理，可直接Gauss消去法求解方程組。消去法求解方程組。下面將消元過程用矩陣運(yùn)算表示。對第下面將消元過程用矩陣運(yùn)算表示。對第k步，利用（步，利用（4.1.3）給出）給出的乘數(shù)的乘數(shù) ，記，記 ，又記，又記 為第為第k 個(gè)分量為個(gè)分量為1的單位向量，令的單位向量，令Tnkkkklll),0,0(,1)( Tke)0 , 0 , 1 , 0 , 0( ikl,1111, 1)()( nkkk

19、TkkkllelIL(4.1.6)第四章方程組的直接解法不難驗(yàn)證不難驗(yàn)證即即IelIelIelIelITkkTkkTkkTkk )()()()()()(TkkkelIL)(1 利用矩陣（利用矩陣（4.1.6），第），第k步消元過程相當(dāng)于步消元過程相當(dāng)于這樣經(jīng)過這樣經(jīng)過n-1步消元過程得到步消元過程得到,)()1(121)()1(121nnnnnnbbLLLAALLL ).,(),()1()1()()( kkkkkbAbAL這里，這里， 是上三角陣。記是上三角陣。記 ，又記，又記)(nA)(nAU ,1111)(1,213231211121 nnnnnnllllllLLLL第四章方程組的直接解法

20、這種矩陣稱為單位下三角陣。這種矩陣稱為單位下三角陣。L的對角線以下各元素就是各步消元過的對角線以下各元素就是各步消元過程的乘數(shù)。最后我們得到程的乘數(shù)。最后我們得到 A=LU （4.1.7）稱該式為稱該式為A的的LU分解。分解。定理定理4.3 矩陣矩陣 ，若其順序主子式，若其順序主子式 皆皆非零，則存在唯一的單位下三角陣非零，則存在唯一的單位下三角陣L和上三角陣和上三角陣U，使，使A=LU。nnRA),2,1(niDi 其中，其中， 都是單位下三角陣，都是單位下三角陣， 都是上三角陣。因都是上三角陣。因A非奇異，非奇異，則則 都可逆。都可逆。A左乘左乘 ，右乘，右乘 即得即得因因 仍為上三角陣，

21、仍為上三角陣， 也是上三角陣，同理是單位下三角陣，所也是上三角陣，同理是單位下三角陣，所以只能有以只能有即即 。定理得證。定理得證證證 以上的分析已證明了以上的分析已證明了A可作可作LU分解，下面證明分解的唯一性。分解，下面證明分解的唯一性。設(shè)設(shè)A有兩個(gè)分解式有兩個(gè)分解式,ULLUA ,UULL,LL,UU1 U1 UU,11ILLUU .11LLUU 1 L1 U.,LLUU 第四章方程組的直接解法分解式（分解式（4.1.7）也稱為）也稱為Doolittle分解。由（分解。由（4.1.7）式可求出）式可求出A的的行列式，即行列式，即若將上三角若將上三角U寫成寫成 ，其中，其中D是對角陣，是對

22、角陣， 是單位上三角陣，是單位上三角陣，則有則有稱該式為稱該式為A的的LDU分解，顯然，這種分解具有唯一性。分解，顯然，這種分解具有唯一性。.det)()2(22)1(11nnnaaaA UDU ULDA U（4.1.8）4.1.3 主元素消去法主元素消去法在以上的在以上的Gauss消去法中，消元過程能進(jìn)行的條件是主元素消去法中，消元過程能進(jìn)行的條件是主元素 。例如，若。例如，若 ，消去過程的第，消去過程的第1步就步就不能進(jìn)行。有時(shí)雖然不能進(jìn)行。有時(shí)雖然 但是但是 很小，這時(shí)計(jì)算過程的很小，這時(shí)計(jì)算過程的舍入誤差會(huì)導(dǎo)致消去法數(shù)值不穩(wěn)定，以致結(jié)果不可靠。舍入誤差會(huì)導(dǎo)致消去法數(shù)值不穩(wěn)定，以致結(jié)果不

23、可靠。, 1, 0)( iaiii1,2 n011a,0)( iiia)(iiia例例4.2 用三位十進(jìn)制浮點(diǎn)運(yùn)算求解用三位十進(jìn)制浮點(diǎn)運(yùn)算求解 .00. 200. 100. 1,00. 100. 11000. 121215xxxx第四章方程組的直接解法解解 這個(gè)方程組的準(zhǔn)確解顯然應(yīng)接近這個(gè)方程組的準(zhǔn)確解顯然應(yīng)接近 .但是系數(shù)但是系數(shù) 是是個(gè)小主元，如果用個(gè)小主元，如果用Gauss消去法求解，則有消去法求解，則有T)00. 1 ,00. 1 (11a.1000. 100. 2,1000. 100. 1,1000. 15132323)2(235122122)2(225112121 alaaalaa

24、aal在三位十進(jìn)制運(yùn)算的限制下，得到在三位十進(jìn)制運(yùn)算的限制下，得到 ，代回第，代回第1個(gè)個(gè)方程得方程得 ，這個(gè)顯然不是正確的解。因?yàn)橛眯≈髟?，這個(gè)顯然不是正確的解。因?yàn)橛眯≈髟?做除法，做除法，使乘數(shù)使乘數(shù) 是個(gè)大數(shù)，在是個(gè)大數(shù)，在 的計(jì)算中，的計(jì)算中， 的值完全被掩蓋了。的值完全被掩蓋了。如果先把兩個(gè)方程的次序交換，再用如果先把兩個(gè)方程的次序交換，再用Gauss消去法，就不會(huì)出現(xiàn)消去法，就不會(huì)出現(xiàn)上述問題，解得上述問題，解得 ，這就是列主元素消去法的思想。，這就是列主元素消去法的思想。00. 1/)2(22)2(232 aax01 x11a21l)2(22a22a00. 1,00. 121

25、xx列主元素消去法列主元素消去法也稱按列部分主元的消去法。一般地，在完成也稱按列部分主元的消去法。一般地，在完成了第了第k-1步消元運(yùn)算后，在步消元運(yùn)算后，在 的第的第k 列元素列元素 之下的所有之下的所有元素中選一個(gè)絕對值最大的元素作為主元素，即若元素中選一個(gè)絕對值最大的元素作為主元素，即若),()()(kkbA)(kkka,max)()(,kiknikkkiaak 第四章方程組的直接解法則以則以 為主元素，這里為主元素，這里 ,且且 由于非奇異，由于非奇異，有有 .這樣，這樣， 有達(dá)到控制舍入誤差的作有達(dá)到控制舍入誤差的作用。用。)(kkka1/)(,)( kkikikikkaalkik

26、0)( kkka)(kA選出主元素后，若則進(jìn)行順序選出主元素后，若則進(jìn)行順序Gauss消去法的第消去法的第k步若步若 ，則將則將 的第的第 行與第行與第k行交換，然后進(jìn)行消元運(yùn)算。行交換，然后進(jìn)行消元運(yùn)算。),()()(kkbAkik ki完成了完成了n-1步主元，換行與消元運(yùn)算后，得到步主元，換行與消元運(yùn)算后，得到 ，這是，這是與原方程組等價(jià)的方程組與原方程組等價(jià)的方程組,是一個(gè)上三角陣是一個(gè)上三角陣,再代回求解再代回求解.這就是列這就是列主元素消去法的計(jì)算過程主元素消去法的計(jì)算過程.)()(nnbxA )(nA除了列主元素消去法外除了列主元素消去法外,還有一種還有一種完全主元素消去法完全主

27、元素消去法.在其過程的第在其過程的第k 步步 ,不是按列來選主元不是按列來選主元,而是在右下角的而是在右下角的n-k+1階子陣中階子陣中選主元選主元 ,即即然后將然后將 的第的第 行與第行與第k行交換將第行交換將第 列與第列與第k列交換列交換,同時(shí)同時(shí)將自變量將自變量 與與 的位置交換并記錄自變量的排列次序的位置交換并記錄自變量的排列次序.直到消直到消去法完成后去法完成后,再按記錄恢復(fù)自變量為自然次序再按記錄恢復(fù)自變量為自然次序.完全主元法比列主元法完全主元法比列主元法) 1( k.max)(,)(,kijnjikkjiaakk )(,kjikka),()()(kkbAkikxjkxk)(kA

28、第四章方程組的直接解法運(yùn)算量大得多運(yùn)算量大得多,由于列主元法的舍如誤差一般已較小由于列主元法的舍如誤差一般已較小,所以在實(shí)際計(jì)所以在實(shí)際計(jì)算中多用列主元法算中多用列主元法.例例4.3 用列主元素消去法解方程組用列主元素消去法解方程組Ax=b,計(jì)算過程中五位有計(jì)算過程中五位有效數(shù)字進(jìn)行運(yùn)算效數(shù)字進(jìn)行運(yùn)算,其中其中.4178. 745625. 5996. 33816. 1078125. 014 . 022002. 0),(bA解解 記記 . 第一步選列主元為第一步選列主元為 ，交換，交換第第1行與第行與第3行，再消元計(jì)算得行，再消元計(jì)算得),(),()1()1(bAbA 996. 3)1(31 a

29、.40371. 00020. 20028. 2047471. 00010. 161077. 004178. 745625. 5996. 3),()2()2(bA第二步選列主元為第二步選列主元為 ,交換第交換第2行與第行與第3行，再消元計(jì)行，再消元計(jì)算得算得0028. 2)2(32 a第四章方程組的直接解法.35159. 039047. 00040371. 00020. 20028. 204178. 745625. 5996. 3),()3()3( bA消去過程至此結(jié)束。回代計(jì)算依次得到解消去過程至此結(jié)束?；卮?jì)算依次得到解這個(gè)例題的精確解是這個(gè)例題的精確解是 而用不選住主元的順序而用不選住主元

30、的順序Gauss消去法，則解得消去法，則解得9273. 1,69850. 0,90043. 0123xxx,)900423. 0 ,698496. 0,92730. 1 (Tx,)88888. 0 ,68695. 0,9300. 1 (Tx這個(gè)結(jié)果誤差較大，這是因?yàn)橄シǖ牡谶@個(gè)結(jié)果誤差較大，這是因?yàn)橄シǖ牡?步中，步中， 按絕對值比按絕對值比其他元素小很多所引起的。從此例看到列主元素消去法是有效其他元素小很多所引起的。從此例看到列主元素消去法是有效的方法。的方法。)1(11a第四章方程組的直接解法下面討論矩陣的含換行的三角分解，即列主元法中消去過下面討論矩陣的含換行的三角分解，即列主元法中

31、消去過程的矩陣表示。一般的，將矩陣程的矩陣表示。一般的，將矩陣A的第的第i行與第行與第j行交換，其結(jié)果行交換，其結(jié)果相當(dāng)于矩陣相當(dāng)于矩陣A左乘一個(gè)初等排列矩陣左乘一個(gè)初等排列矩陣 ，即，即 ，這里，這里 是單位陣是單位陣I交換第交換第i行與第行與第j行后所得的矩陣，不難驗(yàn)證行后所得的矩陣，不難驗(yàn)證ijIAIijijI. 1det,1 ijijijjiijIIIII若矩陣若矩陣A右乘右乘 得得 ，其結(jié)果是將，其結(jié)果是將A的第的第i列與第列與第j列交換后列交換后所得的矩陣。所得的矩陣。ijIAIij我們把若干個(gè)初等排列矩陣的乘積稱作我們把若干個(gè)初等排列矩陣的乘積稱作排列矩陣排列矩陣，其結(jié)果是，其結(jié)

32、果是將單位矩陣經(jīng)過若干次交換所得的矩陣。將單位矩陣經(jīng)過若干次交換所得的矩陣。列主元素消去法的每一步，一般是先按列選主元再交換行，然后列主元素消去法的每一步，一般是先按列選主元再交換行，然后進(jìn)行消元計(jì)算，所以有進(jìn)行消元計(jì)算，所以有其中其中 為為(4.1.6)所示，所示， 是初等排列陣，是初等排列陣， 是第是第k步列選主元步列選主元所在的行號(hào)。如果第所在的行號(hào)。如果第k步不需換行，則步不需換行，則,)(,)1(kikkkAILAk kikikI,kL.,IIkikkk 第四章方程組的直接解法列主元素消去法的消元過程進(jìn)行列主元素消去法的消元過程進(jìn)行n-1步之后得到上三角陣步之后得到上三角陣 ,記記這

33、就是列主元法消去過程的矩陣表示。由于列主元的選取，我們可這就是列主元法消去過程的矩陣表示。由于列主元的選取，我們可知知 及及 原始的絕對值不大于原始的絕對值不大于1。)9 . 1 . 4(kL.121, 11,22, 11)(AILILILAUiiinnnn )(nA1 kL定理定理4.4 設(shè)設(shè)A為非奇異矩陣，則存在排列陣，單位小三角矩陣為非奇異矩陣，則存在排列陣，單位小三角矩陣L和上三角陣和上三角陣U，使，使PA=LU.證證 從從(4.1.9)可得可得其中其中U為上三角陣。令排列陣為上三角陣。令排列陣則利用則利用 有有,11, 112,211, 1121ULILILIAniniin ,121

34、, 1,2, 1iiinIIIPn ijijII 1ULIILIIIILIIPAniniiininiiinnnnn11,1,312,3,1,1,211,2,113311221)( .)()()(11,112,111,1,312,3,1,1,211,2,11113311221ULILILIILIIIILIIninninniniiininiiinnnnnnn 第四章方程組的直接解法4.1.4 Gauss-Jordan消元法消元法考慮考慮Gauss消去法的一種修正：消去對角線下方和上方的元素。消去法的一種修正：消去對角線下方和上方的元素。稱這種方法為稱這種方法為Gauss-Jordan消去法。設(shè)用消

35、去法。設(shè)用Gauss-Jordan消去法已消去法已完成完成k-1步，得到與方程步，得到與方程Ax=b等價(jià)的方程組等價(jià)的方程組 ，此時(shí)對應(yīng)，此時(shí)對應(yīng)的增廣矩陣是的增廣矩陣是)()(kkbxA 由此，若記由此，若記121111, 1, 11, 1, 1,2, 2 , 1,1111 nnninikkikinkLLLLLLnkIILIILnkkn則得則得PA=LU。由初等排列陣的性質(zhì)。由初等排列陣的性質(zhì) 是一個(gè)單位下三角陣，是一個(gè)單位下三角陣，L也是一個(gè)單元下三角陣。定理得證。也是一個(gè)單元下三角陣。定理得證。kL第四章方程組的直接解法,11),(1,1,1, 1, 1, 11111)()( nnnnnknkknkknknkkknnkkkaaaaaaaaaaaabA這里，略去了矩陣元素的上標(biāo)。在第這里，略去了矩陣元素的上標(biāo)。在第k步計(jì)算時(shí)，考慮對上述矩陣地步計(jì)算時(shí)，考慮對上述矩陣地k列中的第列中的第k行上，下都進(jìn)行消元計(jì)算。若用列主元素消去法，仍然是行上，下都進(jìn)行消元計(jì)算。若用列主元素消去法，仍然是第第k列元素列元素 之下的所以元素中選一個(gè)絕對值最大的元素做為主元素之下的所以元素中選一個(gè)絕對值最大的元素做為主元素,即即.max,iknikkikaa kka但是，將第但是，將第k行與第行交換后，