線性方程組的直接解法.ppt

1、4.1 Gauss消去法,4.1.4 Gauss-Jordan消元法,4.1.3 主元素消去法,4.1.2 矩陣的三角分解,4.1.1 Gauss消去法的計算過程,第4章 線性方程組的直接解法,教學目的 1. 掌握解線性方程組的高斯消去法、高斯選主元素消去法； 2. 掌握用直接三角分解法解線性方程組的方法； 3. 了解解對稱正定矩陣線性方程組的平方根法與解三對角線方程組的追趕法； 4. 掌握向量，矩陣范數(shù)，矩陣的條件數(shù)等概念及方程組的擾動分析。 教學重點及難點 重點是 1. 解線性方程組的高斯消去法、高斯選主元素消去法； 2. 直接三角分解法解線性方程組的方法； 3. 向量，矩陣范數(shù)，矩陣的條

2、件數(shù)等概念及方程組的擾動分析； 難點是方程組的擾動分析。,實際中，存在大量的解線性方程組的問題。很多數(shù)值方法到最后也會涉及到線性方程組的求解問題：如樣條插值的M和m關系式，曲線擬合的法方程，方程組的Newton迭代等問題。,第4章 線性方程組的直接解法,對線性方程組：,或者：,我們有Gram法則：當且僅當,時，有唯一的解，而且解為：,但Gram法則不能用于計算方程組的解，如n100，1033次/秒的計算機要算10120年,解線性方程組的方法可以分為2類：,直接法：準確，可靠，理論上得到的解是精確的,迭代法：速度快，但有誤差,本章講解直接法,對于中小型方程組，常用直接解法。從本質(zhì)上來說，直接方法

3、的原理是找一個可逆矩陣M，使得MA是一個上三角陣，這一過程一般稱為“消元”過程，消元之后再進行“回代”，即求解MAx=Mb。本章討論Gauss消去法及其變形，以及一些情況下的特殊方法，最后進行誤差分析。,4.1 Gauss消去法,我們知道，下面有3種方程的解我們可以直接求出：,n次運算,（n1）n/2次運算,（n1）n/2次運算,對方程組，作如下的變換，解不變,交換兩個方程的次序,一個方程的兩邊同時乘以一個非0的數(shù),一個方程的兩邊同時乘以一個非0數(shù)，加到另一個方程,因此，對應的對增廣矩陣(A，b)，作如下的變換，解不變,交換矩陣的兩行,某一行乘以一個非0的數(shù),某一個乘以一個非0數(shù)，加到另一行,

4、消元法就是對增廣矩陣作上述行的變換，變?yōu)槲覀円阎?種類型之一，而后求根.,4.1.1 Gauss消去法的計算過程,(4.1.1), 這樣,方程組(4.1.1)又可寫成 。消元過程就是要按確定的計算過程對方程組進行初等行變換,將方程組化為上三角方程組.,第一步消元:假設 ,作初等行變換運算,步驟如下：,運算量： (n-1)*(1+n),運算量： (n-2)*(1+n-1)=(n-2)n,第二步：,第k步消元:設消去法已進行k-1步,得到方程組 ,此時對應的增廣矩陣是,第k步：,類似的做下去，我們有：,運算量： (nk)*(1nk1)=(nk)(nk2),n1步以后，我們可以得到變換后的矩陣為：

5、,這就完成了消元過程。,(4.1.4),因此，總的運算量為：,加上 解上述上三角陣的運算量(n+1)n/2，總共為：,求解上式的過程稱為回代過程。 以上由消去過程和回代過程合起來求解（4.1.1）的過程就稱為Gauss消去法，或稱為順序Gauss消去法。,如果我們用Cramer法則計算（4.1.1）的解，要計算n+1個階行列式，并作n次除法。如果用子式展開的方法計算行列式，則計算 每個行列式有n ！次乘法。所以用Cramer法則大約需要（n+1）！ 次乘除法運算。例如，當n=10時，約需乘除法運算，而用Gauss消 去法只需430次乘除法運算。,例4.1 用Gauss消去法解方程組,解 第一步

6、消元，令 得增廣矩陣,4.1.2 矩陣的三角分解,從上面的消元過程可以看出，消元過程能順利進行的重要條件是主元素 。若用 表示矩陣A的k階順序主子陣，則有下面的定理。,定理4.1 全不為零的充要條件是A的順序主子式 其中 。,證 先證必要性設 ，則可進行k-1步消元程。顯然 ，對 ，由于每步進行的初等變換不改變順序主子式的值，所以第i-1步消元后有,用歸納法證充分性。k=1時，命題顯然成立。設命題對m-1成立。 現(xiàn)設 由歸納假設有 Gauss 消去法可進行第m-1步，矩陣A變換為,其中 是對角元素為 的上三角陣。因 是通過消元過程由A逐步經(jīng)初等變換得到的，A的m 階順序主子式等于 的m 階順序

7、主子式，即 由 可推出 ，定理得證。,不難驗證 即,利用矩陣（4.1.6），第k步消元過程相當于 這樣經(jīng)過n-1步消元過程得到,這里， 是上三角陣。記 ，又記,這種矩陣稱為單位下三角陣。L的對角線以下各元素就是各步消元過程的乘數(shù)。最后我們得到 A=LU （4.1.7） 稱該式為A的LU分解。,定理4.3 矩陣 ，若其順序主子式 皆非零，則存在唯一的單位下三角陣L和上三角陣U，使A=LU。,4.1.3 主元素消去法,解 這個方程組的準確解顯然應接近 .但是系數(shù) 是 個小主元，如果用Gauss消去法求解，則有,列主元素消去法也稱按列部分主元的消去法。一般地，在完成 了第k-1步消元運算后，在 的第

8、k 列元素 之下的所有 元素中選一個絕對值最大的元素作為主元素，即若,完成了n-1步主元，換行與消元運算后，得到 ，這是 與原方程組等價的方程組,是一個上三角陣,再代回求解.這就是列 主元素消去法的計算過程.,除了列主元素消去法外,還有一種完全主元素消去法.在其過程的第k 步 ,不是按列來選主元,而是在右下角的n-k+1階子陣中選主元 ,即 然后將 的第 行與第k行交換將第 列與第k列交換,同時 將自變量 與 的位置交換并記錄自變量的排列次序.直到消去法完成后,再按記錄恢復自變量為自然次序.完全主元法比列主元法,運算量大得多,由于列主元法的舍如誤差一般已較小,所以在實際計算中多用列主元法.,例

9、4.3 用列主元素消去法解方程組Ax=b,計算過程中五位有效數(shù)字進行運算,其中,消去過程至此結(jié)束?；卮嬎阋来蔚玫浇?這個例題的精確解是 而用不選住主元的順序Gauss消去法，則解得,這個結(jié)果誤差較大，這是因為消去法的第1步中， 按絕對值比其他元素小很多所引起的。從此例看到列主元素消去法是有效的方法。,下面討論矩陣的含換行的三角分解，即列主元法中消去過程的矩陣表示。一般的，將矩陣A的第i行與第j行交換，其結(jié)果相當于矩陣A左乘一個初等排列矩陣 ，即 ，這里 是單位陣I交換第i行與第j行后所得的矩陣，不難驗證,若矩陣A右乘 得 ，其結(jié)果是將A的第i列與第j列交換后所得的矩陣。,我們把若干個初等排列

10、矩陣的乘積稱作排列矩陣，其結(jié)果是將單位矩陣經(jīng)過若干次交換所得的矩陣。,列主元素消去法的每一步，一般是先按列選主元再交換行，然后進行消元計算，所以有 其中 為(4.1.6)所示， 是初等排列陣， 是第k步列選主元所在的行號。如果第k步不需換行，則,列主元素消去法的消元過程進行n-1步之后得到上三角陣 ,記 這就是列主元法消去過程的矩陣表示。由于列主元的選取，我們可知 及 原始的絕對值不大于1。,定理4.4 設A為非奇異矩陣，則存在排列陣，單位小三角矩陣L和上三角陣U，使PA=LU.,證 從(4.1.9)可得 其中U為上三角陣。令排列陣 則利用 有,4.1.4 Gauss-Jordan消元法,考慮

11、Gauss消去法的一種修正：消去對角線下方和上方的元素。稱這種方法為Gauss-Jordan消去法。設用Gauss-Jordan消去法已完成k-1步，得到與方程Ax=b等價的方程組 ，此時對應的增廣矩陣是,這里，略去了矩陣元素的上標。在第k步計算時，考慮對上述矩陣地k列中的第k行上，下都進行消元計算。若用列主元素消去法，仍然是第k列元素 之下的所以元素中選一個絕對值最大的元素做為主元素,即,定理4.5 設A為為n階非奇異矩陣，方程組Ax=I的增廣矩陣為 C=（A，I）。如果對C用Gauss-Jordan消去法化為（I，T），則 .,證 設 ,則 這里， 為單位矩陣I的第j列，用Gauss-Jordan消去法