高斯消去法 (Gaussian Elimination)
本系列文章內容參考自經典教材 Elementary Linear Algebra (Pearson New International Edition)。本文對應章節:Ch1-4 Gaussian Elimination。
高斯消去法 (Gaussian Elimination)
什麼是高斯消去法?
高斯消去法 (Gaussian Elimination) 是一種系統性的演算法,用於將任意矩陣轉換成簡化列梯形式 (Reduced Row Echelon Form, RREF)。
在上一篇中,我們學到了 REF 和 RREF 的定義,但沒有詳細說明「如何」將矩陣轉換成這些形式。高斯消去法就是這個「如何」的答案——它提供了一套明確的步驟,讓我們可以機械化地完成這個轉換。
演算法概覽
高斯消去法分為兩個階段:
| 階段 | 名稱 | 目標 | 步驟 |
|---|
| Forward Pass | 前向消去 | 將矩陣化為 REF | Step 1-4 |
| Backward Pass | 後向消去 | 將 REF 化為 RREF | Step 5-6 |

Forward Pass:前向消去 (Step 1-4)
Step 1:找出 Pivot Column 與 Pivot Position
從矩陣的最左邊開始,找出第一個非全零的 column,這個 column 稱為 Pivot Column(主元行)。
在這個 pivot column 中,第一列的位置稱為 Pivot Position(主元位置)。
[A∣b]=0000162−10−41−6−53521165−17
在這個例子中,第一個 column 全為 0,所以第二個 column 是 pivot column,而位置 (1,2) 是 pivot position。
Step 2:Row Interchange(列交換)
如果 pivot position 的元素是 0,則在 pivot column 中選擇一個非零元素所在的列,與第一列交換,使得 pivot position 變成非零。
0000162−10−41−6−53521165−17R1↔R2000106−1201−4−63−551216−157
Step 3:消去 Pivot 下方的元素
將 pivot position 所在列的適當倍數,加到下方的每一列,使得 pivot position 下方的所有元素都變成 0。
000106−1201−4−63−551216−157R3−6R1000100−1261−4−123−5−131210−1513
Step 4:遞迴處理子矩陣
忽略包含 pivot position 的那一列,對剩餘的子矩陣重複 Step 1-4。
000100−1261−4−123−5−131210−1513
對子矩陣繼續執行 Step 1-4,直到處理完所有列,最終得到 REF:
000100−1201−403−52124−15−2(REF)
Backward Pass:後向消去 (Step 5-6)
Step 5:正規化並消去 Pivot 上方的元素
從最後一個 pivot(最下方的非零列)開始:
- 若 leading entry 不是 1,則將該列縮放使其變成 1
- 將該列 的適當倍數加到上方的每一列,使得 pivot position 上方的所有元素都變成 0
000100−1201−403-52124−15−221R3000100−1201−403-51122−15−1
R1−3R3,R2+5R3000100−1201−40001−512220−1
Step 6:繼續處理上一個 Pivot
對上一個 pivot 重複 Step 5,直到處理完第一列為止。
21R2000100-1101−20001−56220−1R1+R2000100010−1−2000116220−1
最終得到 RREF。
Pivot 相關術語
在高斯消去法中,有幾個重要的術語需要釐清:
| 術語 | 定義 |
|---|
| Pivot Position | RREF 中 leading entry(領導元素)所在的位置 |
| Pivot | 位於 pivot position 的元素(在 RREF 中必為 1) |
| Pivot Column | 包含 pivot position 的 column |
10002000