高斯消去法 (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(主元位置)。
在這個例子中,第一個 column 全為 ,所以第二個 column 是 pivot column,而位置 是 pivot position。
Step 2:Row Interchange(列交換)
如果 pivot position 的元素是 ,則在 pivot column 中選擇一個非零元素所在的列,與第一列交換,使得 pivot position 變成非零。
Step 3:消去 Pivot 下方的元素
將 pivot position 所在列的適當倍數,加到下方的每一列,使得 pivot position 下方的所有元素都變成 。