高斯消去法

本文的閱讀等級：初級

解線性方程組是線性代數處理的核心問題之一。考慮包含 $n$ 個未知數 $x_1, x_2,\ldots, x_n$ 的線性方程式

$a_1x_1+a_2x_2+\cdots+a_nx_n=b$ ，

其中係數 $a_1, a_2,\ldots,a_n$ 與 $b$ 是給定的純量 (實數或複數)。若線性方程組有 $m$ 個方程式，則可表示為陣列形式：

$\begin{array}{ccccccccc} a_{11}x_1 &\!\!\! + &\!\!\! a_{12}x_2 &\!\!\! + &\!\!\! \cdots &\!\!\! + &\!\!\! a_{1n}x_n &\!\!\! = &\!\!\! b_1 \\ a_{21}x_1 &\!\!\! + &\!\!\! a_{22}x_2 &\!\!\! + &\!\!\! \cdots &\!\!\! + &\!\!\! a_{2n}x_n &\!\!\! = &\!\!\! b_2 \\[-3pt] &\!\!\! &\!\!\! &\!\!\! \vdots &\!\!\! &\!\!\! &\!\!\! &\!\!\! &\!\!\! \\[-3pt] a_{m1}x_1 &\!\!\! + &\!\!\! a_{m2}x_2 &\!\!\! + &\!\!\! \cdots &\!\!\! + &\!\!\! a_{mn}x_n &\!\!\! = &\!\!\! b_m. \end{array}$

線性方程組的解 $x_1, x_2, \ldots, x_n$ 必須滿足上面 $m$ 個方程式，也就是說方程組的解是 $m$ 個方程式各自解的交集。線性方程組的系統化解法最早出現於公元前100年的中國古籍《九章算術》(見“《九章算術》的方程術”)，隨後傳入日本和歐洲。今天，我們稱此算法為高斯消去法或高斯消元法 (Gaussian elimination) 以紀念德國數學家高斯 (Carl Friedrich Gauss) 的廣泛使用進而推廣了這個方法。

Carl Friedrich Gauss (1777-1855) From Wikimedia

如果要將線性方程組存入電腦中，我們其實不在意未知數的名稱或記號為何，最簡單的簿記方式是用一個矩陣記錄係數。舉例來說，給定線性方程組

$\begin{array}{rrrrrrrrr} x_1 &\!\!\! + &\!\!\! 2x_2 &\!\!\! - &\!\!\! 3x_3 &\!\!\! - &\!\!\! x_4 &\!\!\! = &\!\!\! 7 \\ &\!\!\! &\!\!\! 3x_2 &\!\!\! + &\!\!\! 4x_3 &\!\!\! - &\!\!\! x_4 &\!\!\! = &\!\!\! -1 \\ -2 x_1 &\!\!\! + &\!\!\! x_2 &\!\!\! + &\!\!\! 5x_3 &\!\!\! + &\!\!\! 2x_4 &\!\!\!= &\!\!\! 0, \end{array}$

將係數與等號右邊的常數併在一起，可得對應此方程組的增廣矩陣 (augmented matrix)

$\left[\!\begin{array}{rrrrrr} 1 & 2 & -3 & -1 & \vline & 7 \\ 0 & 3 & 4 & -1 & \vline & -1\\ -2 & 1 & 5 & 2 & \vline & 0 \end{array}\!\right]$ 。

增廣矩陣完整的保留了線性方程組的所有資訊，其尺寸由其所描述的方程式與未知數的數目決定：增廣矩陣的每一列 (row) 對應一個方程式的係數與常數，每一行 (column) 記錄同一個未知數的係數，分隔直線的右行記錄常數。表面上，矩陣以一種極為簡潔的方式記錄了線性方程組，隱藏的數學意義是：矩陣讓我們將線性方程組視為一個完整的獨立數學物件，因此可與其他同類的物件相比較。譬如，我們可比較兩個線性方程組是否擁有相同的解。以正式的數學詞彙來講，這些同類物件之間的關係稱為等價 (equivalent)，由下面三個性質界定：

A 等價於 A；
若 B 等價於 A，則 A 等價於 B；
若 B 等價於 A 且 C 等價於 B，則 C 等價於 A。

若物件 A 等價於 B，那麼 A 和 B 必定存在某種定義明確的關係，而且經由某種運算或程序可以將 A 變換為 B，也可以將 B 變換回 A。因此，我們不禁要問：對線性方程組執行哪些運算不會改變解？

我們採用的主要代數運算是消去與代入。消去運算也可以稱為取代 (substitution)，具體地說，將第 $j$ 式取代為第 $i$ 式通乘 $k$ 與第 $j$ 式之和， $k\neq 0$ ，此運算依據的原理即為等量公理：將方程式等號兩邊同乘或同加一個非零數不會改變等式關係。取代是求解方程式的主要運算，另外還有兩個輔助運算也很管用。伸縮 (scaling) 是將某個方程式通乘一個非零數以改變方程式的係數，原理亦為等量公理，因此方程組的解維持不變；交換 (exchange) 是置換任兩個方程式的位置，目的僅為調整方程組的陣列形式，顯然此舉也不會改變解。由於增廣矩陣的一列對應線性方程組的一個方程式，我們可以直接對增廣矩陣的列執行上述三種運算，稱之為基本列運算 (elementary row operation)：

取代：將第 $i$ 列通乘 $k$ ， $k\neq 0$ ，加進第 $j$ 列。
伸縮：第 $j$ 列通乘 $k$ ， $k\neq 0$ 。
交換：置換第 $i$ 列和第 $j$ 列。

對增廣矩陣執行基本列運算顯然比起操作線性方程組方便許多，往後我們將以增廣矩陣取代線性方程組。增廣矩陣經過有限次數的基本列運算轉換為另一個增廣矩陣，我們稱這兩個增廣矩陣是列等價的 (row equivalent)。由於每個基本列運算都有反運算而且為同型運算，列等價是一種等價關係 (見“矩陣的等價關係”)。基本列運算依循等量公理確保線性方程組的解不會改變，因此兩個列等價的增廣矩陣必定有相同的解。接下來的問題是如何利用基本列運算有效地化簡增廣矩陣以達到求解的目的。

高斯消去法指出一條明確的求解途徑：執行一連串有效的基本列運算直到增廣矩陣簡化至便於求解的形式。看底下的線性方程組與其增廣矩陣：

$\begin{array}{rrrrrrr} x_1 &\!\!\! - &\!\!\! x_2 &\!\!\! + &\!\!\! x_3 &\!\!\! = &\!\!\!-2 \\ &\!\!\! &\!\!\! 2x_2 &\!\!\!- &\!\!\! 3x_3 &\!\!\! = &\!\!\!7 \\ &\!\!\! &\!\!\! &\!\!\! - &\!\!\! 12x_3 &\!\!\!= &\!\!\!12 \end{array}\mbox{~~~~~~~~} \left[\!\!\begin{array}{crrcr} 1 & -1 & 1 & \vline & -2 \\ 0 & 2 & -3 & \vline & 7 \\ 0 & 0 & -12 & \vline & 12 \end{array}\!\!\right]$

使用反向代入法 (back-substitution) 可依次解出未知數 $x_3, x_2, x_1$ ：

$\begin{aligned}\displaystyle x_3 \,&\, =\, \frac{12}{-12}\,=\,-1 \\ x_2 \,&\, =\, \frac{3x_3+7}{2}\, =\, 2 \\ x_1 \,&\, =\, x_2 - x_3 -2\, =\, 1 \end{aligned}$

這個例子提示如果增廣矩陣具有階梯形式，使用反向代入法即可逐次求得解，我們稱具此種形式的方程組為梯形陣式 (echelon form)，對應的增廣矩陣則稱為梯形矩陣。為了清楚描述梯形矩陣，下面介紹幾個相關名稱：一個列上的軸元 (pivot，也稱領先元) 是指該列由左至右最先出現的非零元，包含軸元的列稱為軸列，包含軸元的行稱為軸行。零列是指所有的元皆為零的列，零行是所有的元皆為零的行。梯形矩陣的形式具有兩個性質：(e1) 零列置於矩陣最底下。(e2) 每列軸元的行位置位於其上方各列軸元的右側。如下例：

$\left[\!\!\begin{array}{ccccc} \blacksquare & \square & \square & \square & \square \\ 0 & 0 & \blacksquare & \square & \square \\ 0 & 0 & 0 & \blacksquare & \square \\ 0 & 0 & 0 & 0 & 0 \end{array}\!\!\right],~~ \left[\!\!\begin{array}{ccccccc} 0 & \blacksquare & \square & \square & \square & \square & \square \\ 0 & 0 & \blacksquare & \square & \square & \square & \square \\ 0 & 0 & 0 & 0 & \blacksquare & \square & \square \\ 0 & 0 & 0 & 0 & 0 & \blacksquare & \square \end{array}\!\!\right]$ ，

其中軸元 (以 $\blacksquare$ 表示) 不為零，軸列中排在軸元之後的元 (以 $\square$ 表示) 可以是任意數。

從性質 (e1) 和 (e2) 推知軸元左方與其下的每個元皆為零，如果將目光聚集於所有的零元，可清楚看出矩陣的階梯形式。高斯消去法的目標是運用基本列運算將增廣矩陣化簡為列等價的梯形矩陣。實際作法利用軸元以消去其下方的所有元，這解釋了何以軸元不得為零。我們用一個例子來說明高斯消去法的運算過程，下面的增廣矩陣已將分隔直線除去：

$\left[\!\begin{array}{rrrrr} 0 & 2 & -4 & 1 & -6 \\ -1 & 0 & -5 & 1 & -4 \\ 1 & 2 & 1 & 0 & -2 \\ 2 & -4 & 18 & -7 & 14 \end{array}\!\right]$ 。

這是一個 $4\times 5$ 階增廣矩陣，包含 4 個列與 5 個行，其中 $(i,j)$ 元位於第 $i$ 列與第 $j$ 行。給定矩陣的 $(1,1)$ 元為零，佔據了軸元的位置，因此交換第一列與第二列 (也可選擇第三或四列)，得到第一個軸元 $-1$ ，如下：

$\left[\!\begin{array}{rrrrr} -1 & 0 & -5 & 1 & -4 \\ 0 & 2 & -4 & 1 & -6 \\ 1 & 2 & 1 & 0 & -2 \\ 2 & -4 & 18 & -7 & 14 \end{array}\!\right]$ 。

接著執行兩次取代運算設法讓 $(1,1)$ 元底下的所有元皆為零：第一列通乘 1 加進第三列，第一列通乘 2 加進第四列，得到

$\left[\!\begin{array}{rrrrr} -1 & 0 & -5 & 1 & -4 \\ 0 & 2 & -4 & 1 & -6 \\ 0 & 2 & -4 & 1 & -6 \\ 0 & -4 & 8 & -5 & 6 \end{array}\!\right]$ 。

再對第二列重複上述步驟。第二個軸元為 2，執行兩次取代運算以消滅 $(2,2)$ 元之下的所有元：第二列通乘 $-1$ 加進第三列，第二列通乘 2 加進第四列，就有

$\left[\!\begin{array}{rrrrr} -1 & 0 & -5 & 1 & -4 \\ 0 & 2 & -4 & 1 & -6 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -3 & -6 \end{array}\!\right]$ 。

我們發現第三列為零列，該方程式的係數全被消去，一個方程式憑空消失。為維持梯形陣式，將第三列和第四列互換，即可得到第三個軸元 $-3$ ，而最底列則為零列：

$\left[\!\begin{array}{rrrrr} -1 & 0 & -5 & 1 & -4 \\ 0 & 2 & -4 & 1 & -6 \\ 0 & 0 & 0 & -3 & -6 \\ 0 & 0 & 0 & 0 & 0 \end{array}\!\right]$ 。

至此，增廣矩陣已具備我們期待的梯形，其中第一、二、三列為軸列，而第一、二、四行為軸行。

以上消去過程顯示僅須行使取代與交換運算便可將給定的矩陣轉化成梯形，但因為消去程序可能有多種列交換方式，最後產生的梯形矩陣也因此不同。值得注意的是，不論如何進行消去程序，梯形矩陣的軸元位置總是固定的，這個現象可由觀察確認 (嚴格的證明請見“簡約列梯形式的唯一性”)。

高斯消去法得到梯形增廣矩陣後，我們的求解工作已近尾聲，接下來用反向代入法限制並解出各個未知數。針對上例梯形增廣矩陣，對應的線性方程組包含 4 個未知數，依序設為 $x_1, x_2, x_3, x_4$ ，方程組呈梯形陣式：

$\begin{array}{rrrrrrrrr} -x_1 &\!\!\! &\!\!\! &\!\!\! - &\!\!\! 5x_3 &\!\!\!+&\!\!\! x_4 &\!\!\! = &\!\!\! -4 \\ &\!\!\! &\!\!\! 2x_2 &\!\!\! - &\!\!\! 4x_3 &\!\!\! + &\!\!\! x_4&\!\!\! = &\!\!\! -6 \\ &\!\!\! &\!\!\! &\!\!\! &\!\!\! &\!\! &\!\!\! -3x_4 &\!\!\! = &\!\!\! -6 \\ &\!\!\! &\!\!\! &\!\!\! &\!\!\! &\!\! &\!\!\! 0 &\!\!\! = &\!\!\! 0. \end{array}$

梯形矩陣的另一個作用在於檢查方程組是否包含「多餘」的方程式，化簡後的第四個方程式為 $0=0$ ，這對求解不起任何作用，因此實際僅存在三個有效的方程式。每一個方程式的領先變數，即由左至右最先出現的未知數，的係數就是增廣矩陣的軸元，因此領先變數又稱為軸變數 (pivot variable)。經過移項，我們將軸變數置於等號的左邊以方便管理：

$\begin{aligned} -x_1&\,=\, 5x_3\,-\,x_4\,-\,4 \\ 2x_2&\,=\, 4x_3\,-\,x_4\,-\,6\\ -3x_4&\,=\,-6. \end{aligned}$

上面三個方程式分別鎖定了軸變數 $x_1, x_2, x_4$ ，但 $x_3$ 未受任何方程式約束，稱為自由變數 (free variable)。令 $x_3=\alpha$ ，希臘小寫字母 $\alpha$ 為實數，這種未受限的數稱做參數 (parameter)。軸變數 $x_4$ 直接由第三式決定，既然自由變數 $x_3$ 已定為 $\alpha$ ，軸變數 $x_2, x_1$ 便依序由第二式與第一式以及已確定的 $x_3$ 和 $x_4$ 所決定。線性方程組的通解 (general solutions，或稱一般解) 描述所有可能的解，表示如下：

$\begin{aligned} x_1 &=\, -5\alpha\,+\,6 \\ x_2 &=\, 2\alpha\,-\,4 \\ x_3 &=\, \alpha \\ x_4 &=\,2. \end{aligned}$

因為存在著自由變數 $x_3$ ，此方程組有無窮多組解，隨意設定參數 $\alpha$ 之值即可得到一解，稱為特解 (special solution)。不過，任意線性方程組並不總是有解，從梯形增廣矩陣亦可判斷此情形。見下例：

$\left[\!\!\begin{array}{rrrrcr} 2 & 3 & 1 & 1 &\vline& 1 \\ 0 & 0 & 1 & 3 &\vline& 4 \\ 0 & 0 & 0 & 0 &\vline& 5 \end{array}\!\!\right]$

對應的線性方程組為

$\begin{array}{rrrrrrrrr} 2x_1 &\!\!\! + &\!\!\! 3x_2 &\!\!\! + &\!\!\! x_3 &\!\!\! + &\!\!\! x_4 &\!\!\! = &\!\!\! 1 \\ &\!\!\! &\!\!\! &\!\!\! &\!\!\! x_3 &\!\!\! + &\!\!\! 3x_4 &\!\!\! = &\!\!\! 4 \\ &\!\!\! &\!\!\! &\!\!\! &\!\!\! &\!\!\! &\!\!\! 0 &\!\!\!= &\!\!\! 5. \end{array}$

第三式 $0=5$ 顯然不合理，這等於宣告此線性方程組是不一致的，經常我們以其同義詞「無解」稱之 (見“線性方程組的幾何意義”)。

一旦高斯消去法將線性方程組轉換為列等價的梯形陣式，便可啟動求解程序，詳細過程整理於下：

首先要判斷線性方程組是否有解。檢查梯形增廣矩陣的零列，線性方程組是一致的充要條件為 $0=c$ 且 $c$ 為 $0$ 。
如果方程組是一致的，每一方程式的軸變數便由該式鎖定，其他非軸變數的未知數因不受任何方程式約束故為自由變數。若存在自由變數，則方程組有無窮多組解，否則僅存在唯一解。
方程組的通解可由反向代入法的兩個步驟確定：(a) 若存在自由變數，將自由變數分別以參數 $\alpha, \beta, \gamma,\ldots$ 表示。(b) 從最底下的方程式逐一往上，代入已解得的變數值以鎖定軸變數。

最後舉例說明如何從梯形增廣矩陣判斷解的數目。考慮

$A=\left[\!\!\begin{array}{ccccr} 2 & 0 & 1 & \vline & -1 \\ 0 & 1 & 4 & \vline & 3 \\ 0 & 0 & 0 & \vline & 3 \end{array}\!\!\right],~ B=\left[\!\!\begin{array}{ccccr} 2 & 0 & 1 & \vline & -1 \\ 0 & 1 & 4 & \vline & 3 \\ 0 & 0 & 2 & \vline & 0 \end{array}\!\!\right],~ C=\left[\!\!\begin{array}{ccccr} 2 & 0 & 1 & \vline & -1 \\ 0 & 1 & 4 & \vline & 3 \\ 0 & 0 & 0 & \vline & 0 \end{array}\!\!\right]$ 。

矩陣 $A$ 的底列為 $\begin{bmatrix} 0 & 0 & 0 & 3\end{bmatrix}$ ，因此無解。矩陣 $B$ 不含自由變數，故有唯一解。矩陣 $C$ 的底列為零列並有一個自由變數 (即 $x_3$ )，因此存在無窮多組解。

8 Responses to 高斯消去法

Watt Lin says:

05/02/2013 at 8:36 pm

請問老師：有沒有可能在 x-y 平面，或 x-y-z立體空間，採取「圖解」方式，闡述「高斯消去法」的幾何意義？
我自己思考，若是在 x-y 平面，兩條二元一次聯立方程式，可能兩條直線有一交點，或者平行無交點，或者兩線重疊。那麼，「高斯消去法」如何畫出圖形？
二維平面，我尚未想到方法，三維空間，我更難想像。

- ccjou says:
  
  05/02/2013 at 8:59 pm
  
  很多年前，我的一位同事曾經與我討論過「圖畫高斯消去法」，我記得當時好像我們認為圖形僅能呈現高斯消去法的前後結果，無法用繪圖方式演繹運算步驟。這個問題我還要再仔細想一想以確定其中的細節。
  
  - 張盛東 says:
    
    05/02/2013 at 10:32 pm
    
    老師可以看一看這篇文章。
    
    Click to access GeoGL_B.pdf
    
    - ccjou says:
      
      05/02/2013 at 10:55 pm
      
      謝謝你提供的資料。第一篇與Watt Lin提出的問題比較相關：
      
      Click to access GeoGL_A.pdf
      
      其中fig2和fig3顯示執行高斯消去法之前與之後的圖形表達。
      
- madhouse says:
  
  05/01/2023 at 4:33 pm
  
  你们的发送的文章链接好象失效无法访问了, 我的想法是:
  方程組的解是方程式各自解的交集, 一个n个未知数方程在空间上表示n-1维超平面(超表示泛化hyper-, 不是super-), 两个方程则表示两个n-1维超平面的交集, 基本交换的取代在空间的意义为两个n-1维超平面的交线在所消去的那个变量对应维度的投影, 若取代的结果有三中情况: 1. 零列中c≠0, 则两超平面互相平行, 2.零列c=0, 则两超平面重合, 3. 两超平面相交, 取代的结果就是相交线的投影. 而基本列变换中的伸缩, 交换无实质几何意义. 对于m个有n个未知数的方程进行高斯消去法的结果是求取m个超平面的交集在n-m维上的投影.
  
Watt Lin says:

05/02/2013 at 9:39 pm

若在三維空間，先消去變數x，是不是得到 y-z 平面的線？
第二步驟消去變數y，即得z軸上的點。
我說起來好像容易，想要畫圖，卻感覺困難。
也許要先拿個有解的簡單例題，若能畫出圖形去說明高斯消去法的步驟，
成功之後才推廣到三維的一般情況，例如平面重疊、不相交。

老羅 says:

11/15/2014 at 11:30 am

您好:
例子矩陣
$\begin{bmatrix} 0 & 2 & -4 & 1 & -6 \\ -1& 0 & -5 & 1&-4 \\ 1 & 2 & 1 &0 &-2 \\ 2 &-4 & 18 & -7 & 14 \end{bmatrix}$ ,
第四列第四行的數字應為-7 才對。

- ccjou says:
  
  11/16/2014 at 9:45 am
  
  謝謝指正，已修訂。

	jianglong on Strassen 演算法──分治矩陣乘法
	jianglong on Strassen 演算法──分治矩陣乘法
	xmj on 內積的定義
	Ning ChingSan on 線性代數的第一堂課──矩陣乘法的定義
	momo on 兩岸線性代數用詞參照
	訪客 on 克拉瑪公式的簡易幾何證明