線性方程組的直接法21

1、第1頁第二章線性方程組的直接法在近代數(shù)學數(shù)值計算和工程應用中，求解線性方程組是重要的課題。例如，樣條插值中形成的 K 關系式，曲線擬合形成的法方程等，都落實到解一個盒元線性方程組，尤其是大型方程組的求解，即求線性方程組(2.1 )的未知量7；- 的數(shù)值。其中 ai j，bi 為常數(shù)。上式可寫成矩陣形式Ax = b，即向量。當 detA=DO 時，由線性代數(shù)中的克萊姆法則，方程組 v 上的解存在且惟一，且 有為系數(shù)矩陣匸的第：列元素以=代替的矩陣的行列式的值?？巳R姆法則在建立線性方程組解的理論基礎中功不可沒，但是在實際計算中，我們難以承受它的計算量。例如，解一個 100 階的線性方程組， 乘除法

2、次數(shù)約為(101 -100! 99),即使以每秒 1*的運算速度， 也需要近年的時間。在石油勘探、天氣預報等問題中常常出現(xiàn)成百上千階的方程組，也就產(chǎn)生了各種形式方程組數(shù)值解法的需求。研究大型方程組的解是目前計算數(shù)學中的一個重要方向和課題。解方程組的方法可歸納為直接解法和迭代解法。從理論上來說，直接法經(jīng)過有限次四則運算，假定每一步運算過程中沒有舍入誤差，那么，最后得到方程組的解就是精確解。但是,這只是理想化的假定， 在計算過程中，完全杜絕舍入誤差是不可能的，只能控制和約束由有限位算術運算帶來的舍入誤差的增長和危害，這樣直接法得到的解也不一定是絕對精確的。厲 E 九旳 +-+兀血=曾(2.1)口1

3、1如%f、坷函1農(nóng)33涇*円】%嘰(2.2)其中，-為系數(shù)矩陣,為解向量為常數(shù)第2頁迭代法是將方程組的解看作某種極限過程的向量極限的值，像第 2 章中非線性方程求解一樣，計算極限過程是用迭代過程完成的，只不過將迭代式中單變量 一十一一小換成向量而已。在用迭代算法時，我們不可能將極限過程算到底，只能將迭代進行有限多次，得到滿足一定精度要求的方程組的近似解。在數(shù)值計算歷史上，直接解法和迭代解法交替生輝。一種解法的興旺與計算機的硬件環(huán) 境和問題規(guī)模是密切相關的。一般說來，對同等規(guī)模的線性方程組，直接法對計算機的要求 高于迭代法。對于中等規(guī)模的線性方程組二丄.，由于直接法的準確性和可靠性高，一般都用直

4、接法求解。對于高階方程組和稀疏方程組（非零元素較少），一般用迭代法求解。消元法一、三角形方程組的解形如下面三種形式的線性方程組較容易求解。對角形方程組(2.3)設、八，對每一個方程， I 廠廠顯然，求解 n 階對角方程的運算量為-?oF 三角方程組第3頁(2.4)按照方程組的順序，從第一個方程至第 個方程，逐個解出第4頁由方程_-，得-_1-。將心的值代入到第二個方程將H 亠.的值代入到第:個方程坳-包-以習3 -1,2,-j-i計算幾需要：次乘法或除法運算，一- -。因此，求解過程中的運算量為上三角方程組%磚（2.5）與計算下三角方程組的次序相反，從第卞個方程至第一個方程，逐個解出將?&am

5、p; 的值代入到第 1 個方程得解的通式計算幾需要；一 + 次乘法或除法運算-。因此求解過程中的運算量為消元法的基本思想就是通過對方程組做初等變換，把一般形式的方程組化為等價的具有上述形式的易解方程組。由第斗個方程，。將入的值代入到第- 個方程第5頁高斯消元法與列主元消元法高斯消元法高斯消元法是我們熟悉的古老、簡單而有效的解方程組的方法。下面是中學階段解二元 方程組（高斯消元法）的步驟:(2.6)(2.7)方程（2.6）乘以一 3 加到第（2.7）個方程中得羽.人代入（2.6）得石 2。其方法相當于對方程組的增廣矩陣做行的初等變換:亠已是上三角矩陣，而為原方程組的等價方程組，已化成易解的方程組

6、形式。再用回代方法求解，得到:x2= 1, = 2這就是高斯消元法解方程組的消元和回代過程。一般地，可對線性方程組（2.1 ）施行以下一系列變換；（1）對換某兩個方程的次序；（2）對其中某個方程的兩邊同乘一個不為零的數(shù)；（3）把某一個方程兩邊同乘一個常數(shù)后加到另一個方程的兩邊。 記變換后的方程組為：+知可十+芯耳=、a21Jcl叫Mu+*耳召=暫內+ -+耳后=嘰(2.8)第6頁顯然方程組(2.1)與(2.8)是等價方程組，或者說它們有相同的解。分別記方程組(2.1)與(2.8)的增廣矩陣為：(1)對換某兩行元素;(2)中的某行乘一個不為零的數(shù)；(3)把 CV) 的某一行乘一個常數(shù)后加到另一行

7、。高斯消元法就是通過以上(3)的變換，把化為等價的上三角形式。F 面我們以=丄為例演示消元過程。設方程組:111 十直匕工 2 *- 13-3 斗= 口也汕五+如乜十住婦瑪十釐魚兀ib2勺込1+氣丹5 內*知珥弋 盤和可+422*直護+盤卵天斗=3頁其增廣矩陣為:(1)若 1 -，則將第一行乘以； 加到第二行上；將第一乘以可以看出,1:按一系列初等換后得到的(2.9)加到第三行上；將第一行乘以4- 1-加到第四行上得到第7頁frl0aaL00J=hg17132220-)空0)壯udr凸dtB240)站弭aa& MB230站43aa a a第8頁v 已是上三角矩陣，于是得到了與原方程等價

8、的易解形式的方程組:2口工1十122十+如心=尊+吆妝4朗十囲比=陽(2.13)再對方程組(2.13)依次回代解出丁“門-廠匸。從式(2.12)可以得到系數(shù)矩陣 二的行列式的值為的對角元素的乘積。即這也正是在計算機上計算方陣 二的行列式的常規(guī)方法。要將上述解方程步驟推廣到 打階方程組，只需將對控制量“4 的操作改成對控制量卞的其中:將第二行乘以一上-加到第四行上， 得到f11a13巧40護00務00%其中：(2.11)柑鼻n(3)若；則將第三行乘以加到第四行上，得到(2.12)(2)若 則將第二行乘以第9頁操作即可。第10頁吆元方程組高斯消元法的步驟如下:對于A -JI 約定 I 氣有忙學“-

9、（盤嘰腫）/ms衛(wèi)+1“ 妒=鏟-儲-嚴尸址 t” 1 s “經(jīng)過以上消元，我們已得到與：等價的方程組一.一 -，其中工已是一個上三角矩陣。為簡單起見，仍記二的元素為-5二匚口 -叭料一I,-*-,!(2.15)即已得到原方程組的解。咼斯消兀法算法在算法中略去了變量，矩陣和向量的定義部分。在消元過程中，將 素的位置上。1輸入：方程組階數(shù)n,方程組系數(shù)矩陣 A 和常數(shù)向量 bo FOR i:=k+1 TO n/假定，亠FOR j:=k+1 TO nai: = aSI/ ENDFORJ/ ENDFORI/ ENDFORKJ 仍放在廠元2. FOR k:=1 TO n-1/消元過程第11頁 s:=b

10、iFOR j:=i+1 TO n DO4輸出方程組的解 - o高斯消元法的運算量整個消元過程即式（2.14）的乘法和除法的運算量為回代過程即式（2.15 ）的乘除運算量為故高斯消元法的運算量為(2.16)高斯消元法的可行性在上面的消元法中，未知量是按照在方程組中的自然順序消去的，也叫順序消元法。H n在消元過程中假定對然元素，消元步驟才能順利進行，由于順序消元不改變上的主子式值，故高斯消元法可行的充分必要條件為1 的各階主子式不為零。但是，實際上只要-1方程組就有解。故高斯消元法本身具有局限性。痕 T另一方面，即使高斯消元法可行，如果弘 很小，在運算中用它作為除法的分母i 乜二、會導致其它元素

11、數(shù)量級的嚴重增長和舍入誤差的擴散。這是高 斯消元法的另一缺陷。3. FOR i:=n TO1/回代求解(2.17)(2.18)1第12頁0 0003 +3.0000X2=2.00011.0000+1 0000 xa= 1.0000例2.1方程組第13頁1 2_=_的精確解為：33。在高斯消兀法計算中取 5 位有效數(shù)字。解：方程（2.17） X （- 1） /0.0003+ 方程（2.18）得：，代入方程（2.17）得1 -。由此得到的解完全失真，如果交換兩個 方程的順序，得到等價方程組經(jīng)高斯消元后有由此可看到，在有些情況下，調換方程組的次序對方程組的解是有影響的，對消元法中抑制舍入誤差的增長是

12、有效的。如果不調換方程組的次序，取6 位有效數(shù)字計算方程組的解，得到取 9 位有效數(shù)字計算方程組的解，得到由此可見有效數(shù)字在數(shù)值計算中的作用。列主元消元法如果在一列中選取按模最大的元素，將其調到主干方程位置再做消元，則稱為列主元消元法。調換方程組的次序是為了使運算中做分母量的絕對值盡量地大，減少舍入誤差的影響。用列主元方法可以克服高斯消元法的額外限制，只要方程組有解，列主元消元法就能暢通無阻地順利求解，同時又提高了解的精確度。maxkl=ki更具體地，第一步在第一列元素中選出絕對值最大的元素，交換第一行和第噸行的所有元素，再做化簡為零的操作。的元素 E 製上丨，對疋行和陀行交換后，再做消元操作

13、，這就是列主元消元法的操作步驟。0-1） 0-1）由于 ：兒】，可證”中至少有一個元素不為零，從理論上保證了列主元消元法的可行性。列主元消元法與高斯消元法相比，只增加了選列主元和交換兩個方程組（即兩行元素）的過程。對于每個r-在做消元前，選出中絕對值最大第14頁列主元消元法算法第15頁1 輸入：方程組階數(shù) 人，方程組系數(shù)矩陣和常數(shù)向量項二。/ ENDFORK4.輸出方程組的解如果對于第：步，從：行至行和從此列至咋列中選取按模最大的誣血，對第氏行和第肚行交換，對第比列和第 v 列交換，這就是全主元消元法。在k 列和第 v 列交換時，還要記錄下 v 的序號，以便恢 復未知量 xk和 xv 的位置。

14、3.1.3高斯若爾當(GaussJordan)消元法高斯消元法將系數(shù)矩陣化為上三角矩陣，再進行回代求解；高斯一若爾當消元法是將系數(shù)矩陣化為對角矩陣，再進行求解，即對高斯消元法或列主元消元法得到的等價增廣矩陣：用第 4 行乘加到第 3 行上，用第 4 行乘加到第 2 行上，用第 4行乘 N *4 加到第 1 行上，得到2. FOR k:=l TOn-1選主元的消元過程FOB. v:=kTOn/交換第*行和第朋行/ ENDFORI3. FOR i:=n TO 1/回代求解/選擇工：Ml第16頁用第 3 行乘加到第 2 行上，用第 3 行乘 f 加到第 1 行上，再用第 2行乘加到第 1 行上，得到

15、第17頁知00 0垃m0疵0 0貂0 0增。希/00舞昭2.19）系數(shù)矩陣元素為 一，常數(shù)項元素為 】。那么用初等變換化系數(shù)矩陣為對角矩陣的方法稱為高斯一若爾當消元法。從形式上看對角矩陣（2.15）比上三角矩陣（2.11 ）更為簡單，易于計算匚，但是將上三角矩陣（2.11）化為對角矩陣（2.15 ）的工作量略大于上三角矩陣回代的工作量。高斯一若爾當消元法求逆矩陣設二為非奇異矩陣，方程組；的增廣矩陣為I 。如果對：應用高斯-若爾當消元法化為（打門，則= TOX 2 435例 2.2 用高斯-若爾當消元法求V-12210o56001245(10T245C10解：3501123 10(2.19)為方

16、便起見，仍記式（5可的逆矩陣川 O解得:1-3r宀-332-10第18頁2 直接三角分解法仍以=為例，在高斯消元法中，從對方程組進行初等變換的角度觀察方程組系數(shù)矩陣的演變過程。第一次消元步驟將方程組（2.9）化為方程組（2.10），相當于用了三個初等矩陣左乘 止和記- 1：-，容易驗證，第19頁由丁 4、_ 丁得到t -其中將方程組（2.10）化為方程組（2.11），相當于用了兩個初等矩陣左乘上和丘。同理，將方程組（2.11）化為方程組（2.12），相當于用一個初等矩陣左乘丄和：。記Qs 小堪，有完成了消元過程，有亦有所有消元步驟表示為：w左乘一系列下三角初等矩陣。容易驗證，這些下三角矩陣的乘

17、積亠仍為下三角矩陣，并有于是有或這里丁 仍為下三角矩陣，其對角元素為 1,稱為單位下三角矩陣，而 二已是上三角矩陣。結果表明若消元過程可行， 可以將匸分解為單位下三角矩陣 二與上三角矩陣丁的乘積。 由此派生出解方程組的直接分解法。由高斯消元法得到啟發(fā)，對消元的過程相當于將 二分解為一個上三角矩陣和一個下三角矩陣的過程。如果直接分解 上得到和。這時方程匚一 I化為匸二=， 令-，由二1解出；再由一-，解出工。= L,A = U，則有第20頁這就是直接分解法。第21頁將方陣二分解為上=二二，當二是單位下三角矩陣， L 是上三角矩陣時，稱為多利特爾（Doclittle ）分解；當丄是下三角矩陣，二是

18、單位上三角矩陣時，稱為庫朗（Courant）分解。分解的條件是若方陣上的各階主子式不為零，則多利特爾分解或庫朗分解是可行和惟一的。一、多利特爾分解多利特爾分解步驟二可分解為A =-，其中-為單位下三角矩陣， 丁為上三角矩陣，即矩陣二和丁共有 J 個未知元素，按照 P 的行元素二的列元素的順序，對每個 一列出式（2.16）兩邊對應的元素關系式，一個關系式解出一個 二或丁的元素。下面是計算二和丁的元素的步驟：（1）計算丁的第一行元素 心：；芯要計算則列出式（2.20）等號兩邊的第 1 行第 1 列元素的關系式:故=，二。一般地，由丁的第一行元素的關系式得到（2）計算上的第一列元素-1若亠二的各階主

19、子式不為零，第22頁要計算 L，則列出式（2.20）等號兩邊的第 2 行第 1 列元素的關系式: 故一一一一-一一。一般地，由二的第 1 列元素的關系式 得到（3）計算丁的第 2 行元素（4）計算二的第 2 列元素若已算出丁的前行，匸的前-列的元素，則（5）計算丁的第行元素“ ;由的第：行元素的關系式：是上三角矩陣，列標行標。得到后1（2.21）（6）計算二的第 L 列元素由二的第：列元素的關系式：T 匚是下三角矩陣，二行標標：-行標。得到一直做到二的第列，T 的第吃行為止。第23頁十0（/）用匸-直接分解方法求解方程組所需要的計算量仍為，和用高斯消元法的計算量基本相同。可以看到在分解中 上的

20、每個元素只在式（2.21 ）或（2.22）中做而且僅做一次貢獻，如 果需要節(jié)省空間，可將丁以及二的元素直接放在矩陣 壬相應元素的位置上。用直接分解法解方程：，首先作出分解“二L令-1，解方程組。由 于二是單位下三角矩陣，容易得到!-1(2.23)再解方程組 L ，其中對以進行二丁分解時，并不涉及常數(shù)項 勺。因此，若需要解具有相同系數(shù)的一系列線 性方程組時，使用直接分解法可以達到事半功倍的效果。多利特爾直接分解算法1輸入：方程組階數(shù)，系數(shù)矩陣上和常數(shù)項卜。2F0Rk:=l TOn(2.24)第24頁 FORj：=kTOnII 計算的第行兀素完成丄一分解FORi-k+1 TO nII計算二的第不列

21、元素第25頁3F0Ri:=lT0n/解方程組4 匸口.： =1 匚二:-/解方程組一 5輸出方程組的解一 一例 3.2 用多利特爾分解求解方程組：r21I110(wll132=1應苗23解：11221 10對:：1，有 對丄】，有 對= 2,有 解丄，即 解-、，即二、追趕法很多科學計算問題中，常常所要求解的方程組為三對角方程組也/其中(3.25)(3.29)第26頁由些可見將二分解為及丁，只需計算 |及 公式為：兩組數(shù)，然后解；，計算再解則得并且滿足條件:稱心為對角占優(yōu)的三對角線矩陣。其特征是非零元素僅分布在對角線及對角線兩側的 位置。在樣條插值函數(shù)的-訂關系式中就出現(xiàn)過這類矩陣。事實上，許

22、多連續(xù)問題經(jīng)離散化 后得到的線性方程組，其系數(shù)矩陣就是三對角或五對角形式的對角矩陣。利用矩陣直接分解法，求解具有三對角線系數(shù)矩陣的線性方程組十分簡單而有效。上分解為下三角矩陣-，及單位上三角矩陣 丁的乘積。即豆=二&，其中利用矩陣乘法公式，比較“丄二兩邊元素，可得到于是有61A = 7 -1/(2.26)現(xiàn)將1q %1L =的 嗎1p-%、叭%1(3.27)(3.31)第27頁整個求解過程是先由(3.28)及(3.29)求，及門，這時 一 ： 是追”的過程，再由(3.24)求出-：,這時IT是往回趕，故求解方程組(3.25)的整個過程稱為追趕法。對稱正定矩陣也是很多物理問題產(chǎn)生的一類矩陣，正定矩陣的各階主子式大于零?？梢宰C明，若二正定，則存在下三角矩陣 二，使，直接分解-的分解方法， 稱為平方根法。由于在平方根法中含有計算平方根的步驟，因此很少采用平方根法的分解形式。對于對稱矩陣，常用的是- 丄二二 分解。(提出矩陣的對角元素)由二對稱正定，可得 J由的對稱性和分解的惟一性可證營旳一號舛我總一1(3.30)平方根法對二作多利特爾分解二二，即(3.31)第28頁1-是對角元素為 1 的單位下三角矩陣。(2.34)第29頁對矩陣二作多利特爾或庫朗分解，共計算 -個矩陣元素；對稱矩陣的 丄