線性方程組的直接法

1、第二章 線性方程組的直接法在近代數(shù)學(xué)數(shù)值計(jì)算和工程應(yīng)用中，求解線性方程組是重要的課題。例如，樣條插值中形成的關(guān)系式，曲線擬合形成的法方程等，都落實(shí)到解一個(gè)元線性方程組，尤其是大型方程組的求解，即求線性方程組（2.1）的未知量的數(shù)值。 （2.1）其中ai j，bi為常數(shù)。上式可寫成矩陣形式Ax = b，即 （2.2）其中，為系數(shù)矩陣，為解向量，為常數(shù)向量。當(dāng)detA=D0時(shí)，由線性代數(shù)中的克萊姆法則，方程組的解存在且惟一，且有 為系數(shù)矩陣的第列元素以代替的矩陣的行列式的值。克萊姆法則在建立線性方程組解的理論基礎(chǔ)中功不可沒，但是在實(shí)際計(jì)算中，我們難以承受它的計(jì)算量。例如，解一個(gè)100階的線性方程組

2、，乘除法次數(shù)約為（101100！99），即使以每秒的運(yùn)算速度，也需要近年的時(shí)間。在石油勘探、天氣預(yù)報(bào)等問題中常常出現(xiàn)成百上千階的方程組，也就產(chǎn)生了各種形式方程組數(shù)值解法的需求。研究大型方程組的解是目前計(jì)算數(shù)學(xué)中的一個(gè)重要方向和課題。解方程組的方法可歸納為直接解法和迭代解法。從理論上來說，直接法經(jīng)過有限次四則運(yùn)算，假定每一步運(yùn)算過程中沒有舍入誤差，那么，最后得到方程組的解就是精確解。但是，這只是理想化的假定，在計(jì)算過程中，完全杜絕舍入誤差是不可能的，只能控制和約束由有限位算術(shù)運(yùn)算帶來的舍入誤差的增長(zhǎng)和危害，這樣直接法得到的解也不一定是絕對(duì)精確的。2 / 36迭代法是將方程組的解看作某種極限過程的

3、向量極限的值，像第2章中非線性方程求解一樣，計(jì)算極限過程是用迭代過程完成的，只不過將迭代式中單變量換成向量而已。在用迭代算法時(shí)，我們不可能將極限過程算到底，只能將迭代進(jìn)行有限多次，得到滿足一定精度要求的方程組的近似解。在數(shù)值計(jì)算歷史上，直接解法和迭代解法交替生輝。一種解法的興旺與計(jì)算機(jī)的硬件環(huán)境和問題規(guī)模是密切相關(guān)的。一般說來，對(duì)同等規(guī)模的線性方程組，直接法對(duì)計(jì)算機(jī)的要求高于迭代法。對(duì)于中等規(guī)模的線性方程組，由于直接法的準(zhǔn)確性和可靠性高，一般都用直接法求解。對(duì)于高階方程組和稀疏方程組（非零元素較少），一般用迭代法求解。1 消元法一、 三角形方程組的解形如下面三種形式的線性方程組較容易求解。對(duì)角

4、形方程組 （2.3）設(shè)，對(duì)每一個(gè)方程，。顯然，求解n階對(duì)角方程的運(yùn)算量為 。下三角方程組 （2.4）按照方程組的順序，從第一個(gè)方程至第個(gè)方程，逐個(gè)解出。由方程，得。將的值代入到第二個(gè)方程得將的值代入到第個(gè)方程得計(jì)算需要次乘法或除法運(yùn)算，。因此，求解過程中的運(yùn)算量為上三角方程組 （2.5）與計(jì)算下三角方程組的次序相反，從第個(gè)方程至第一個(gè)方程，逐個(gè)解出。由第個(gè)方程。將的值代入到第個(gè)方程得將的值代入到第個(gè)方程得解的通式 計(jì)算需要次乘法或除法運(yùn)算。因此求解過程中的運(yùn)算量為消元法的基本思想就是通過對(duì)方程組做初等變換，把一般形式的方程組化為等價(jià)的具有上述形式的易解方程組。二、 高斯消元法與列主元消元法高斯

5、消元法高斯消元法是我們熟悉的古老、簡(jiǎn)單而有效的解方程組的方法。下面是中學(xué)階段解二元方程組（高斯消元法）的步驟：（2.6）（2.7）方程（2.6）乘以3加到第（2.7）個(gè)方程中得代入（2.6）得。其方法相當(dāng)于對(duì)方程組的增廣矩陣做行的初等變換：已是上三角矩陣，而為原方程組的等價(jià)方程組，已化成易解的方程組形式。再用回代方法求解，得到：這就是高斯消元法解方程組的消元和回代過程。一般地，可對(duì)線性方程組（2.1）施行以下一系列變換；（1）對(duì)換某兩個(gè)方程的次序；（2）對(duì)其中某個(gè)方程的兩邊同乘一個(gè)不為零的數(shù)；（3）把某一個(gè)方程兩邊同乘一個(gè)常數(shù)后加到另一個(gè)方程的兩邊。記變換后的方程組為： （2.8）顯然方程組（

6、2.1）與（2.8）是等價(jià)方程組，或者說它們有相同的解。分別記方程組（2.1）與（2.8）的增廣矩陣為：可以看出，實(shí)際上是由按一系列初等換后得到的（1）對(duì)換某兩行元素；（2）中的某行乘一個(gè)不為零的數(shù)；（3）把的某一行乘一個(gè)常數(shù)后加到另一行。高斯消元法就是通過以上（3）的變換，把化為等價(jià)的上三角形式。下面我們以為例演示消元過程。設(shè)方程組： （2.9）其增廣矩陣為：（1）若，則將第一行乘以加到第二行上；將第一乘以加到第三行上；將第一行乘以 加到第四行上得到 （2.10）即其中：（2）若則將第二行乘以加到第三行上；將第二行乘以加到第四行上，得到（2.11）其中：（3）若則將第三行乘以加到第四行上，得

7、到 （2.12）其中：已是上三角矩陣，于是得到了與原方程等價(jià)的易解形式的方程組：（2.13）再對(duì)方程組（2.13）依次回代解出。從式（2.12）可以得到系數(shù)矩陣的行列式的值為的對(duì)角元素的乘積。即這也正是在計(jì)算機(jī)上計(jì)算方陣的行列式的常規(guī)方法。要將上述解方程步驟推廣到階方程組，只需將對(duì)控制量“4”的操作改成對(duì)控制量的操作即可。元方程組高斯消元法的步驟如下：對(duì)于約定有（2.14）經(jīng)過以上消元，我們已得到與等價(jià)的方程組，其中已是一個(gè)上三角矩陣。為簡(jiǎn)單起見，仍記的元素為 （2.15）即已得到原方程組的解。高斯消元法算法在算法中略去了變量，矩陣和向量的定義部分。在消元過程中，將仍放在元素的位置上。1輸入：

8、方程組階數(shù)n，方程組系數(shù)矩陣A和常數(shù)向量b。2FOR k:=1 TO n-1 /消元過程 FOR i:=k+1 TO n / 假定 FOR j:=k+1 TO n / ENDFORJ / ENDFORI / ENDFORK3FOR i:=n TO1/回代求解 s:=bi FOR j:=i+1 TO n DO 4輸出方程組的解。高斯消元法的運(yùn)算量整個(gè)消元過程即式（2.14）的乘法和除法的運(yùn)算量為回代過程即式（2.15）的乘除運(yùn)算量為故高斯消元法的運(yùn)算量為 （2.16）高斯消元法的可行性在上面的消元法中，未知量是按照在方程組中的自然順序消去的，也叫順序消元法。在消元過程中假定對(duì)然元素，消元步驟才能

9、順利進(jìn)行，由于順序消元不改變的主子式值，故高斯消元法可行的充分必要條件為的各階主子式不為零。但是，實(shí)際上只要方程組就有解。故高斯消元法本身具有局限性。另一方面，即使高斯消元法可行，如果很小，在運(yùn)算中用它作為除法的分母，會(huì)導(dǎo)致其它元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散。這是高斯消元法的另一缺陷。例2.1 方程組（2.17）（2.18）的精確解為：。在高斯消元法計(jì)算中取5位有效數(shù)字。解：方程（2.17）（1）/0.0003+方程（2.18）得：，代入方程（2.17）得。由此得到的解完全失真，如果交換兩個(gè)方程的順序，得到等價(jià)方程組經(jīng)高斯消元后有由此可看到，在有些情況下，調(diào)換方程組的次序?qū)Ψ匠探M的解是有

10、影響的，對(duì)消元法中抑制舍入誤差的增長(zhǎng)是有效的。如果不調(diào)換方程組的次序，取6位有效數(shù)字計(jì)算方程組的解，得到取9位有效數(shù)字計(jì)算方程組的解，得到由此可見有效數(shù)字在數(shù)值計(jì)算中的作用。列主元消元法如果在一列中選取按模最大的元素，將其調(diào)到主干方程位置再做消元，則稱為列主元消元法。調(diào)換方程組的次序是為了使運(yùn)算中做分母量的絕對(duì)值盡量地大，減少舍入誤差的影響。用列主元方法可以克服高斯消元法的額外限制，只要方程組有解，列主元消元法就能暢通無阻地順利求解，同時(shí)又提高了解的精確度。更具體地，第一步在第一列元素中選出絕對(duì)值最大的元素，交換第一行和第行的所有元素，再做化簡(jiǎn)為零的操作。對(duì)于每個(gè)在做消元前，選出中絕對(duì)值最大的

11、元素，對(duì)行和行交換后，再做消元操作，這就是列主元消元法的操作步驟。由于，可證中至少有一個(gè)元素不為零，從理論上保證了列主元消元法的可行性。列主元消元法與高斯消元法相比，只增加了選列主元和交換兩個(gè)方程組（即兩行元素）的過程。列主元消元法算法1輸入：方程組階數(shù)，方程組系數(shù)矩陣和常數(shù)向量項(xiàng)。2 /選主元的消元過程 /選擇 / 交換第行和第行 / ENDFORI / ENDFORK3FOR i:=n TO 1 / 回代求解4輸出方程組的解 。如果對(duì)于第步，從行至行和從列至列中選取按模最大的，對(duì)第行和第行交換，對(duì)第列和第v列交換，這就是全主元消元法。在k列和第v列交換時(shí)，還要記錄下v的序號(hào)，以便恢復(fù)未知量

12、xk和xv的位置。3.1.3 高斯若爾當(dāng)（GaussJordan）消元法高斯消元法將系數(shù)矩陣化為上三角矩陣，再進(jìn)行回代求解；高斯若爾當(dāng)消元法是將系數(shù)矩陣化為對(duì)角矩陣，再進(jìn)行求解，即對(duì)高斯消元法或列主元消元法得到的等價(jià)增廣矩陣：用第4行乘加到第3行上，用第4行乘加到第2行上，用第4行乘加到第1行上，得到用第3行乘加到第2行上，用第3行乘加到第1行上，再用第2行乘加到第1行上，得到（2.19）為方便起見，仍記式（2.19）系數(shù)矩陣元素為 ，常數(shù)項(xiàng)元素為。那么用初等變換化系數(shù)矩陣為對(duì)角矩陣的方法稱為高斯若爾當(dāng)消元法。從形式上看對(duì)角矩陣（2.15）比上三角矩陣（2.11）更為簡(jiǎn)單，易于計(jì)算 ，但是將上

13、三角矩陣（2.11）化為對(duì)角矩陣（2.15 ）的工作量略大于上三角矩陣回代的工作量。高斯若爾當(dāng)消元法求逆矩陣設(shè)為非奇異矩陣，方程組的增廣矩陣為。如果對(duì)應(yīng)用高斯-若爾當(dāng)消元法化為，則。例2.2 用高斯-若爾當(dāng)消元法求的逆矩陣。解：解得：2 直接三角分解法仍以為例，在高斯消元法中，從對(duì)方程組進(jìn)行初等變換的角度觀察方程組系數(shù)矩陣的演變過程。第一次消元步驟將方程組（2.9）化為方程組（2.10），相當(dāng)于用了三個(gè)初等矩陣左乘 和。記，容易驗(yàn)證，由得到其中將方程組（2.10）化為方程組（2.11），相當(dāng)于用了兩個(gè)初等矩陣左乘 和。記有同理，將方程組（2.11）化為方程組（2.12），相當(dāng)于用一個(gè)初等矩陣左

14、乘 和。記，有完成了消元過程，有亦有所有消元步驟表示為：左乘一系列下三角初等矩陣。容易驗(yàn)證，這些下三角矩陣的乘積仍為下三角矩陣，并有于是有或這里仍為下三角矩陣，其對(duì)角元素為1，稱為單位下三角矩陣，而已是上三角矩陣。記，則有結(jié)果表明若消元過程可行，可以將分解為單位下三角矩陣與上三角矩陣的乘積。由此派生出解方程組的直接分解法。由高斯消元法得到啟發(fā)，對(duì)消元的過程相當(dāng)于將分解為一個(gè)上三角矩陣和一個(gè)下三角矩陣的過程。如果直接分解得到和，。這時(shí)方程化為，令，由解出；再由，解出。這就是直接分解法。將方陣分解為，當(dāng)是單位下三角矩陣，是上三角矩陣時(shí)，稱為多利特爾（Doclittle）分解；當(dāng)是下三角矩陣，是單位

15、上三角矩陣時(shí)，稱為庫朗（Courant）分解。分解的條件是若方陣的各階主子式不為零，則多利特爾分解或庫朗分解是可行和惟一的。一、 多利特爾分解多利特爾分解步驟若的各階主子式不為零，可分解為，其中為單位下三角矩陣，為上三角矩陣，即（2.20）矩陣和共有個(gè)未知元素，按照的行元素的列元素的順序，對(duì)每個(gè)列出式（2.16）兩邊對(duì)應(yīng)的元素關(guān)系式，一個(gè)關(guān)系式解出一個(gè)或的元素。下面是計(jì)算和的元素的步驟：（1）計(jì)算的第一行元素要計(jì)算,則列出式（2.20）等號(hào)兩邊的第1行第1列元素的關(guān)系式：故。一般地，由的第一行元素的關(guān)系式得到（2）計(jì)算的第一列元素要計(jì)算，則列出式（2.20）等號(hào)兩邊的第2行第1列元素的關(guān)系式：

16、故。一般地，由的第1列元素的關(guān)系式得到（3）計(jì)算的第2行元素（4）計(jì)算的第2列元素若已算出的前行，的前列的元素，則（5）計(jì)算的第行元素由的第行元素的關(guān)系式：是上三角矩陣，列標(biāo)行標(biāo)。得到（2.21）（6）計(jì)算的第列元素由的第列元素的關(guān)系式：是下三角矩陣，行標(biāo)標(biāo)行標(biāo)。得到（2.22）一直做到的第列，的第行為止。用直接分解方法求解方程組所需要的計(jì)算量仍為，和用高斯消元法的計(jì)算量基本相同?？梢钥吹皆诜纸庵械拿總€(gè)元素只在式（2.21）或（2.22）中做而且僅做一次貢獻(xiàn)，如果需要節(jié)省空間，可將 以及的元素直接放在矩陣相應(yīng)元素的位置上。用直接分解法解方程，首先作出分解令，解方程組。由于是單位下三角矩陣，容易

17、得到（2.23）再解方程組，其中（2.24）對(duì)進(jìn)行分解時(shí)，并不涉及常數(shù)項(xiàng)。因此，若需要解具有相同系數(shù)的一系列線性方程組時(shí)，使用直接分解法可以達(dá)到事半功倍的效果。多利特爾直接分解算法1.輸入：方程組階數(shù)，系數(shù)矩陣和常數(shù)項(xiàng)。2. /計(jì)算的第行元素/計(jì)算的第列元素 / 完成分解3. / 解方程組4. / 解方程組5.輸出方程組的解例3.2 用多利特爾分解求解方程組：解：對(duì)，有對(duì)，有對(duì)，有解,即解,即二、 追趕法很多科學(xué)計(jì)算問題中，常常所要求解的方程組為三對(duì)角方程組(3.25)其中 （2.26）并且滿足條件：稱為對(duì)角占優(yōu)的三對(duì)角線矩陣。其特征是非零元素僅分布在對(duì)角線及對(duì)角線兩側(cè)的位置。在樣條插值函數(shù)的

18、關(guān)系式中就出現(xiàn)過這類矩陣。事實(shí)上，許多連續(xù)問題經(jīng)離散化后得到的線性方程組，其系數(shù)矩陣就是三對(duì)角或五對(duì)角形式的對(duì)角矩陣。利用矩陣直接分解法，求解具有三對(duì)角線系數(shù)矩陣的線性方程組十分簡(jiǎn)單而有效?，F(xiàn)將分解為下三角矩陣，及單位上三角矩陣的乘積。即，其中，(3.27)利用矩陣乘法公式，比較兩邊元素，可得到于是有(3.28)由些可見將分解為及，只需計(jì)算及 兩組數(shù)，然后解 ，計(jì)算公式為： (3.29)再解則得 (3.30)整個(gè)求解過程是先由(3.28)及(3.29)求， 及 ，這時(shí) 是“追”的過程，再由(3.24)求出，這時(shí) 是往回趕，故求解方程組(3.25)的整個(gè)過程稱為追趕法。三、 平方根法對(duì)稱正定矩陣

19、也是很多物理問題產(chǎn)生的一類矩陣，正定矩陣的各階主子式大于零。可以證明，若正定，則存在下三角矩陣，使，直接分解的分解方法，稱為平方根法。由于在平方根法中含有計(jì)算平方根的步驟，因此很少采用平方根法的分解形式。對(duì)于對(duì)稱矩陣，常用的是分解。對(duì)作多利特爾分解，即(提出矩陣的對(duì)角元素)由對(duì)稱正定，可得，令由的對(duì)稱性和分解的惟一性可證即。(3.31) 是對(duì)角元素為1的單位下三角矩陣。對(duì)矩陣作多利特爾或庫朗分解，共計(jì)算個(gè)矩陣元素；對(duì)稱矩陣的分解，只需計(jì)算個(gè)元素，減少了近一半的工作量。借助于多利特爾或庫朗分解計(jì)算公式，容易得到分解計(jì)算公式。設(shè)有多利特爾分解形式： 其中在分解可套用多利特爾分解公式，只要計(jì)算下三角矩陣和的對(duì)角元素。計(jì)