計(jì)算方法(B)課件：第5章 解線性方程組的直接法

1、第5章 解線性方程組的直接法,實(shí)際中，存在大量的解線性方程組的問題。很多數(shù)值方法到最后也會(huì)涉及到線性方程組的求解問題：如樣條插值的M和m關(guān)系式，曲線擬合的法方程，方程組的Newton迭代等問題。,對(duì)線性方程組：,或者：,我們有Gram法則：當(dāng)且僅當(dāng),時(shí)，有唯一的解為：,但Gram法則不能用于計(jì)算方程組的解， 如n100，1033次/秒的計(jì)算機(jī)要算10120年,解線性方程組的方法可以分為2類：,直接法：準(zhǔn)確，可靠，理論上得到的解是精確的,迭代法：速度快，但有誤差,本章講解直接法,5.1 消元法,我們知道，下面有3種方程的解我們可以直接求出：,n次運(yùn)算,(n1)n/2次運(yùn)算,(n1)n/2次運(yùn)算,

2、消元法就是對(duì)方程組做些等價(jià)的變換，變?yōu)槲覀円阎?種類型之一，而后求根,對(duì)方程組，作如下的變換，解不變,交換兩個(gè)方程的次序,一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0的數(shù),一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0數(shù)，加到另一個(gè)方程,因此，對(duì)應(yīng)的對(duì)增廣矩陣(A,b)，作如下的變換，解不變,交換矩陣的兩行,某一行乘以一個(gè)非0的數(shù),某一個(gè)乘以一個(gè)非0數(shù)，加到另一行,1、Gauss消元法,步驟如下：,第一步：,運(yùn)算量： (n-1)*(1+n),運(yùn)算量： (n-2)*(1+n-1)=(n-2)n,第二步：,第k步：,類似的做下去，我們有：,運(yùn)算量： (nk)*(1nk1)=(nk)(nk2),n1步以后，我們可以得到變換后的

3、矩陣為：,因此，消元過程總的運(yùn)算量為：,加上 解上述上三角陣的運(yùn)算量(n+1)n/2，總共為：,注意到，計(jì)算過程中,處在被除的位置，,所以，Gauss消元法的可行條件為：,就是要求A的所有順序主子式均不為0，即,因此，有些有解的問題，不能用Gauss消元求解,另外，如果某個(gè),很小的話，會(huì)引入大的誤差,因此整個(gè)計(jì)算過程要保證它不為0,小主元可能導(dǎo)致計(jì)算失敗。,例：單精度解方程組,用Gaussian 消元法計(jì)算：,8個(gè),2、列主元消元法,在Gauss消元第k步之前，做如下的事情：,若,交換 k 行和 j 行,行的交換，不改變方程組的解，同時(shí)又有效地克服了Gauss消元的缺陷,例：,3、Gauss-

4、Jordan消元法,將在Gauss消元第k步，變?yōu)?將該行上三角部分也變?yōu)?,最后變?yōu)橐粋€(gè)對(duì)角陣。,它的運(yùn)算次數(shù)比Gauss消元多。用于計(jì)算多個(gè)系數(shù)一樣的方程組，如,X,B均為矩陣,Lab05 線性方程組求根的直接法,1.編寫列主元消元法的通用程序,2.用如上程序求根，并打印出來,Gauss消元法的第k步：,從矩陣?yán)碚搧砜?，相?dāng)于左乘矩陣,因此，整個(gè)Gauss消元法相當(dāng)于左乘了一個(gè)單位下三角陣,所以有,L為單位下三角陣，U為上三角陣,因此,我們可以通過2次反代過程求解方程組,注意：,分解的理論由Gauss消元得出，因此分解能夠進(jìn)行的條件與Gauss消元一樣,1、Doolittle分解,L為單位下三角，U為上三角,5.2 直接分解法,比較第2行：,比較第2列：,比較第k行：,比較第k列：,k-1次,k-11次,比較第1行：,比較第1列：,分解過程完畢，加上兩次反代過程,總運(yùn)算量為：,存儲(chǔ)在矩陣的原來位置，且不影響計(jì)算,2、Courant 分解,L為下三角，U為單位上三角,兩次反代過程,下面，我們對(duì)一下特殊的矩陣，提出一些特定的分解法,比較第k列：,比較第k行：,3. 三對(duì)角陣的追趕法,計(jì)算過程如下：,3.