數(shù)值分析-線性方程組的直接解法課件

1、線性方程組的直接解法劉 斌線性方程組的直接解法劉 斌線性方程組的直接解法1 Gauss消去法 1.1 順序Gauss消去法 1.2 列主元Gauss消去法 2 直接三角分解方法 2.1 Gauss消去法的矩陣運(yùn)算 2.2 Doolittle分解法 2.3 平方根法 2.4 追趕法 線性方程組的直接解法1 Gauss消去法 引入 在科學(xué)計算中，經(jīng)常需要求解含有n個未知量 的n個方程構(gòu)成的線性方程組方程組還可以用矩陣形式表示為: Ax=b (1)引入 在科學(xué)計算中，經(jīng)常需要求解含有n個未知量 引入 根據(jù) Gramer（克萊姆）法則，求解方程組（1）時，要計算大量的行列式，所需乘法次數(shù)大約為 當(dāng) n

2、 較大時,這個計算量是驚人的。例 如，當(dāng) n= 20 時，約需乘法次數(shù)為 N=9.71020 若系數(shù)矩陣A非奇異，即 det (A)0，則方程組有惟一解 x =( x1, x2, , xn )T . 如果用每秒一億次的計算機(jī)來計算，需要三十萬年時間?？梢奊ramer法則不是一種實用的方法。 因此，必須構(gòu)造出適合于計算機(jī)使用的線性方程組的求解方法。N=(n2-1)n!引入 根據(jù) Gramer（克萊姆）法則，求解方程組（1）引入 直接方法的特點(diǎn)是，如果不考慮計算過程中的舍入誤差，運(yùn)用此類方法經(jīng)過有限次算術(shù)運(yùn)算就能求出線性方程組的精確解。 求解線性方程組的數(shù)值方法可分為兩大類：直接方法和迭代方法。本

3、章討論直接方法，迭代方法將在下一章中討論。 需要指出，由于實際計算中舍入誤差的存在，用直接方法一般也只能求得方程組的近似值。引入 直接方法的特點(diǎn)是，如果不考慮計算過程中的舍 1 Gauss消去法 Gauss（高斯）消去法是一種規(guī)則化的加減消元法 基 本 思 想 通過逐次消元計算把需求解的線性方程組轉(zhuǎn)化成上三角形方程組，也就是把線性方程組的系數(shù)矩陣轉(zhuǎn)化為上三角矩陣，從而使一般線性方程組的求解轉(zhuǎn)化為等價（同解）的上三角形方程組的求解。 Gauss消去法由消元和回代兩個過程組成，先討論一個具體的線性方程組的求解。 1 Gauss消去法 Gauss（高斯）消去法是一、順序Gauss消去法例1. 用Ga

4、uss消去法解方程組用增廣矩陣進(jìn)行進(jìn)算一、順序Gauss消去法例1. 用Gauss消去法解方程組用一、順序Gauss消去法或者 Ax=b 我們用增廣矩陣表示，并給出gauss消去法的具體算法一、順序Gauss消去法或者 Ax=一、順序Gauss消去法第一步，設(shè) a11(1) 0 ，將第一列a11(1)以下各元素消成零乘以矩陣A（1），b（1）的第一行再加到第i 行，得到矩陣 (i2，3，n)即依次用一、順序Gauss消去法第一步，設(shè) a11(1) 0 一、順序Gauss消去法其中 第二步，設(shè) a22(2) 0 ，將第二列a22(2)以下各元素消成零，（i3，4，n） 即依次用乘以矩陣A（2），

5、b（2）的第二行再加到第i行，得到矩陣一、順序Gauss消去法其中 第二步，設(shè) a22(2) 0一、順序Gauss消去法其中 如此繼續(xù)消元下去第n1步結(jié)束后，得到矩陣一、順序Gauss消去法其中 如此繼續(xù)消元下去第n1步結(jié)束一、順序Gauss消去法增廣矩陣A（n），b（n）對應(yīng)如下上三角形方程組 這是與原線性方程組（1）等價的方程組.一、順序Gauss消去法增廣矩陣A（n），b（n）對應(yīng)如一、順序Gauss消去法對于等價方程組進(jìn)行回代求解，可以得到：一、順序Gauss消去法對于等價方程組進(jìn)行回代求解，可以得到算法 Gauss(A,a,b,n,x) 1. 消元 For k=1,2, , n-1

6、1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, , n 1.2.1 l ik=aik /akk = aik 1.2.2 For j=k+1，k+2, ,n ai j -aik ak j =aij 1.2.3 bi -aik bk= bi 2. 回代2.1 bn / an=xn;2.2 For i=n-1,n-2, , 2,1 2.2.1 bk = S 2.2.2 For j=k+1，k+2, ,n S akj xj =S 2.2.3 S/ akk = xk a1 1 a1 2 a13 a1 n b1a2 1 a2 2 a23 a2 n b2a3 1 a3 2 a

7、33 a3 n b3an 1 an 2 an3 an n bnl21 l31 l41 .l n1 a22 a23 . a2n b2 l32 l42 .l n2 . a33 . a 3n b3l43 .l n3 a1 1 a1 2 a13 . a1 n b1a 4n b4. . .ann bn 算法 Gauss(A,a,b,n,x) 1. 消元 For 一、順序Gauss消去法用Gauss消去法解方程組，應(yīng)注意：1. 適用條件： 原方程組系數(shù)矩陣的各階順序主子 式不等于零。2 . 運(yùn)算量?。汗灿谐顺ù螖?shù)為而Gramer 法則的乘除法次數(shù)為: (n2 -1) n！當(dāng) n=20 時一、順序Gaus

8、s消去法用Gauss消去法解方程組，應(yīng)注意：二 列主元Gauss消去法 順序Gauss消去法計算過程中的 akk(k) 稱為主元素，在第k步消元時要用它作除數(shù),則可能會出現(xiàn)以下幾種情況若出現(xiàn) akk(k) 0，消元過程就不能進(jìn)行下去。 akk(k) 0 ，消去過程能夠進(jìn)行，但若|akk(k)| 過小，也會造成舍入誤差積累很大導(dǎo)致計算解的精度下降。 例2 在四位十進(jìn)制的限制下，試用順序Gauss消去法求解如下方程組二 列主元Gauss消去法 順序Gauss消去二 列主元Gauss消去法此方程組具有四位有效數(shù)字的精確解為x117.46，x245.76，x35.546 解 用順序Gauss消去法求解

9、，消元過程如下二 列主元Gauss消去法此方程組具有四位有效數(shù)字的精確解二 列主元Gauss消去法經(jīng)回代求解得 x35.546，x2100.0，x1104.0和此方程組的精確解相比x35.546 ，x245.76， x117.46有較大的誤差。 對于此例，由于順序Gauss消去法中的主元素絕對值非常小，使消元乘數(shù)絕對值非常大，計算過程中出現(xiàn)大數(shù)吃掉小數(shù)現(xiàn)象，產(chǎn)生較大的舍入誤差，最終導(dǎo)致計算解 x1104.0 和 x2100.0 已完全失真。 為避免這種現(xiàn)象發(fā)生，可以對原方程組作等價變換，再利用順序Gauss消去法求解。二 列主元Gauss消去法經(jīng)回代求解得和此方程組的精確解相寫出原方程組的增廣

10、矩陣：針對第一列找出絕對值最大的元素，進(jìn)行等價變換：寫出原方程組的增廣矩陣：針對第一列找出絕對值最大的元素，進(jìn)行求得方程的解為：x35.546，x245.76，x117.46精確解為： x35.546 ，x245.76， x117.46 由此可見，第二種Gauss消去法的精度明顯高于順序Gauss消去法，我們稱它為列主元Gauss消去法。 列主元Gauss消去法與順序Gauss消去法的不同之處在于： 后者是按自然順序取主元素進(jìn)行消元 前者在每步消元之前先選取主元素然后再進(jìn)行消元 求得方程的解為：x35.546，x245.76，x1下面將列主元Gauss消去法的計算步驟敘述如下： 給定線性方程組

11、 Axb, 記A（1）, b（1） A,b，列主元Gauss消去法的具體過程如下： 1. 首先在增廣矩陣A（1）,b（1）第一列的n個元素中選取絕對值最大的一個作為主元素，并把此主元素所在的行與第一行交換，即 2. 其次進(jìn)行第一步消元得到增廣矩陣A（2）,b（2），在矩陣A（2）,b（2） 第二列的后 n1個元素中選取絕對值最大的一個作為主元素，并把此主元素所在的行與第二行交換，即下面將列主元Gauss消去法的計算步驟敘述如下： 3. 再進(jìn)行第二步消元得到增廣矩陣A（3），b（3）。按此方法繼續(xù)進(jìn)行下去，經(jīng)過n1步選主元和消元運(yùn)算，得到增廣矩陣A（n），b（n），它對應(yīng)的方程組A（n）xb（n

12、）是一個與原方程組等價的上三角形方程組，可進(jìn)行回代求解。 容易證明，只要det（A）0，列主元Gauss消去法就可以順利完成，即不會出現(xiàn)主元素為零或者絕對值太小的情形出現(xiàn)。 下面給出列主元Gauss消去法的計算流程： 3. 再進(jìn)行第二步消元得到增廣矩陣A（3），列主元Gauss消去算法 用列主元Gauss消去法求解線性方程組Axb 輸入 A（aij），b（b1，bn）T，維數(shù)n輸出 方程組解x1，xn，或方程組無解信息1： 對于k1，2，n1，循環(huán)執(zhí)行步2到步52： 按列選主元素 aik ，即確定下標(biāo) I 使3： 若aik0，輸出 no unique solution，停機(jī)4： 若ik，換行列主元Gauss消去算法 用列主元Gauss消去法求解線性方5：消元計算，對于ik1，n，計算 6：若 ann 0 輸出 no unigue solution，停機(jī)7：回代求解 8：輸出 x1，x2，xn5：消元計算，對于ik1，n，計算 6：若 ann 二 列主元Gauss消去法 由于這兩種方法的精度差不多，且全主元Gaus