線(xiàn)性方程組的直接解法.ppt

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

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

3、的原理是找一個(gè)可逆矩陣M，使得MA是一個(gè)上三角陣，這一過(guò)程一般稱(chēng)為“消元”過(guò)程，消元之后再進(jìn)行“回代”，即求解MAx=Mb。本章討論Gauss消去法及其變形，以及一些情況下的特殊方法，最后進(jìn)行誤差分析。,4.1 Gauss消去法,我們知道，下面有3種方程的解我們可以直接求出：,n次運(yùn)算,（n1）n/2次運(yùn)算,（n1）n/2次運(yùn)算,對(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ù)，加到另一行,

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

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

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

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

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

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

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

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