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

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

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

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

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