消元法

　　又稱消去法。解線性代數方程組的主要方法之一。早在東漢以前，中國古代著名的數學著作《九章算術》中就有瞭用消元法解方程組的方法。直到今日，消元法仍是解線性代數方程組的一個很重要的方法。在一些國傢的數學著作中也常用高斯消去法這一名詞。

　　消元法解線性代數方程組時，將某一方程乘以某些常數分別加到其他方程上，以消去這些方程中的某一未知量。重複施行這一步驟，就可逐步消去未知量，最後隻剩下一個未知量。用矩陣的語言來說也就是對方程組的係數數矩陣或增廣矩陣(加上右端項所成的矩陣)進行初等變換，使它的一些元素(例如主對角線以下的元素)為零。具體地說，設方程組為 　　

　　　　　　(1)

式中 α _ij( i， j=1，2，…， n)和 f ₁， f ₂，…， f _n都是已知數， x ₁， x ₂，…， x _n為待求的解。設 α ₁₁不為零，將第一個方程分別乘以- α ₂₁/ α ₁₁，- α ₃₁/ α ₁₁，…，- α _n1/ α ₁₁加到第2至第 n個方程上，就消去瞭這些方程中的 x ₁，方程組化成

　　　 (2)

這裡為瞭統一起見，已將 α ₁₁， α ₁₂，…， α _1n和 f ₁分別寫為 α ₁₁ ⁽¹⁾， α ₁₂ ⁽¹⁾，…， α _1n ⁽¹⁾和 f ₁ ⁽¹⁾。對(2)的後 n-1個方程進行類似處理，消去後 n-2個方程的 x ₂，這樣繼續下去，若 α 都不為零，最後得到

　 　　　(3)

上述過程可表示為：對 k=1，2，…， n-1，　

式中

　　有瞭(3)就可反推求出(1)的解：

這稱為回代過程，而前面消去的步驟稱為消去過程。

　　在消去過程中，有時可能遇到α

=0的情況，但若方程組(1)有惟一解，則在 中至少有一個不為零，例如 α _jk ^(k)≠0，那麼隻要將這時的第 k個方程和第 j個方程互換，即可繼續進進消去。有時雖 α ≠0，但｜ α ｜很小，此時往往帶來較大誤差，從而使最後得到的解不夠精確，甚至面目全非。為避免這種情況，也要進行上述交換，將 中最大者所在的方程與第 k個方程交換，這叫做列主元素消元法或部分主元素消元法，也可在後 n- k+1個方程的所有的系數中找出絕對值最大的而後進行方程和未知量的交換，這叫做全主元素消元法，但這種方法工作量較大，一般用列主元素消去法較好。

　　方程組(1)可寫成矩陣的形式

　　 　(4)

式中 A為(1)的系數 α _ij所成的矩陣， x和 f分別為列向量( x ₁， x ₂，…， x _n) ^T和( f ₁， f ₂，…， f _n) ^T;則以上的消去過程可寫為

式中

而

p _k為使矩陣的第 k行與其後的某行交換的排列陣，當不需進行交換時，則無此 p _k因子或 p _k= I（ n階單位陣）。

　　三角分解法　又稱因子分解法，是由消元法演變而來的解線性代數方程組的一種方法，它將方程組(4)中的系數矩陣A分解成下三角形矩陣L和上三角形矩陣U之積。它有幾種形式，例如可取L的對角線元素為1，即L為單位下三角形矩陣。這種情形下將L和U相乘，並與A比較，可知L和U的元素l_ij和u_ij可由下列遞推公式給出：對k=1，2，…，n，

計算順序為先算 U的第一行，再算 L的第一列，然後 U的第二行， L的第二列等等，其中規定和數 為零（下同）。得到 L和 U後，(4)可寫為兩個方程組

　　設y的分量為y₁，y₂，…，y_n，容易得出

　　　(5)

和

　　　(6)

在分解因子時，為瞭避免除數 u _{k k}為零或｜ u _{k k}｜甚小帶來較大誤差，也可在 U的每行元素 u _{k k}， u _k， _{k +1}， u _k， _n算好後，在這些元素中選主元，然後進行列的交換。此時要註意， x的分量也應相應地進行交換。以上的方法稱為杜利特爾分解法。若取 L為下三角形矩陣， U為單位上三角形矩陣，則為克勞特分解法，其算式為：對 k＝1，2，…， n，

計算時，先算 L的第一列，再算 U的第一行等等，同樣可在算完 l _{k k}， l _{k +1， k}，…， l _{n k}後選主元，進行行的交換，但同時要將 f的分量進行相應的交換。其求解的過程也和(5)、(6)類似。

　　若A為對稱正定矩陣，可設

此處 L為下三角形矩陣， L ^T為其轉置，計算公式為：對 k=1，2，…， n。

計算時先算 L的第一列，再順次算其後各列，這叫做平方根法或喬勒斯基法。在 A為對稱正定時， l _{k k}均不為零，故可以不選主元，但這個方法需要 n次開方運算，而開方的工作量較多。若設

此處 L為單位下三角形矩陣， D為對角矩陣，其對角線元素記為 d ₁， d ₂，…， d _n，則計算公式為：對 k=1，2，…， n，

對每個 k，先算 d _k，再算 L的第 k列。為瞭節省運算量，可保存乘積 而對 k=1，2，…， n，按

一行行地計算，即按 d ₁， ₂₁， l ₂₁， d ₂， ₃₁， l ₃₁， ₃₂， l ₃₂， d ₃，…的順序計算。求解過程為

這叫做改進的喬勒斯基方法。

　　追趕法　解系數矩陣A為三對角矩陣的線性代數方程組的常用方法。設方程組為

第一個方程可寫為

一般地，有

　　　 　(7)

把它代入第 i+1個方程中，可得

　 　(8)

由(8)可以逐次遞推求出 p ₁， q ₁， p ₂， q ₂，…， p _n， q _n，這稱為“追”的過程，易知 p _n=0，然後由(7)可依次求得 x _n， x _{n -1}，…， x ₁，這叫“趕”的過程。可以證明，在

即 A為強對角優勢矩陣情況下，計算是穩定的，即舍入誤差的影響很小。因此追趕法是行之有效的。實際上追趕法就是克勞特分解法。對塊三對角矩陣，也有類似的所謂“塊追趕“的方法，然而它需要求一系列的逆矩陣，計算量可能較大。

　　直接法的某些問題　解線性代數方程組的方法分直接法和迭代法兩大類，上面的方法都屬直接法的范疇。在用直接法求解時，要根據系數矩陣的性質和計算機的性能，從內存、計算量、穩定性等一些方面來考慮。就一些計算機而言，乘除法所需時間較加減法多得多，故應盡量減少乘除法。上面的高斯消去法、杜利特爾法、克勞特法中的乘除法和加減法的次數均

數量級，而喬勒斯基法由於利用瞭對稱的性質，就隻有 。在計算中，中間量應盡量存儲在原矩陣 A以後不再用的元素的位置，例如分解法的 L和 U的元素即可占用 A的相應元素的位置。特別對稀疏矩陣，應根據矩陣的形狀，選擇特殊的計算方法以盡量節省計算量和避免產生較多的非零元素。對三對角矩陣情形的追趕法就是一個突出的例子。

　　當用某種方法求出方程組(1)或(4)的解時，由於舍入誤差的影響，它一般不是方程組的精確解x，而隻是一個近似解鿧。將鿧代入原方程，若剩餘向量r=A鿧-f各分量的絕對值均甚小，一般就可認為 鿧是比較精確的近似解，也可任取一已知向量z，較精確地（例如用雙精度）算出向量b=Az，然後用解Ax=f同樣的方法解Az=b，得近似解z。一般就用

作為 x的近似解鿧的誤差。然而這種方法也不是絕對可靠的。特別對病態矩陣、矩陣的元素或方程組的右端的微小變動可以導致方程組的解很大變動。這種誤差估計的方法是威爾金遜的一個重要結果，然而作出的上界往往偏高。如何更好地估計誤差仍待研究。

　　為瞭提高解的精度，下述迭代改進法還是可取的：設x₀為(4)的近似解，計算

，

再逐步求出方程組

的近似解Δ x ₁，Δ x ₂，…，此處

這樣得到的序列 x ₀， x ₁= x ₀+Δ x ₁， x ₂= x ₁+Δ x ₂，…往往能逐步更近似於方程組的精確解。此外也還有其他一些方法。

　　矩陣求逆法　給定一個非奇異矩陣A，求A的逆矩陣A^-1本質上是解一組線性代數方程組的問題。事實上由Ap=I(單位矩陣)，可知逆矩陣p的第i列所成的向量p_i應為方程組Ap_i=e_i的解，此處e_i為第i個分量為1、其餘分量為零的列向量。實際求逆矩陣時，可用消元法來計算。在前面的高斯消元法中，每步可以不僅將對角線以下的元素消成零而且將對角線以上的元素也消成零，並使對角線元素為1。與高斯消元法相類似，可以得到

這裡 N _k為在第 k步將矩陣 A ^(k)= N _{k -1}… N ₂ N ₁ A的第 k列變為 e _k的矩陣。具體求逆時，可按下列步驟進行，其中 α _ij， α _ik， α _{k j}， α _{k k}均指當時在 A的相應元素位置上的數：對 k＝1，2，…， n的每個 k，依次做①計算 d=1/ α _{k k}，並放在 α _{k k}處；②對 i≠ k計算－ d α _ik，並放在 α _ik處；③當 i和 j均不等於 k時計算 α _ij＋ α _ik α _{k j}並放在 α _ij處；④對 j≠ k計算 d α _{k j}，並放在 α _{k j}處。可證，最後在矩陣 A原來的位置上就得到 A的逆陣 A ^-1。為瞭提高精度，也可采取選主元的方法。

　　和解線性代數方程組的三角分解法一樣，也可將A分解為下三角陣L和上三角陣U之積，即A=LU，從而A^-1=U^-1L^-1，而三角形矩陣的逆矩陣是易於求出的。

　　此外還有分塊法、加邊法、迭代法等一些求逆矩陣的方法。

　　

參考書目

　馮康等編：《數值計算方法》，國防工業出版社，北京，1978。