高斯消去法

**高斯消去法**（英語：Gaussian Elimination）是線性代數中的一個演算法，可以把矩陣轉化為行階梯形矩陣。高斯消去法可用來為線性方程組求解，求出矩陣的秩，以及求出可逆方陣的逆矩陣。

## 歷史

該方法以數學家卡爾・高斯命名，但最早出現於中國古籍《九章算術》，成書於約公元前 150 年。

## 例子

高斯消去法可用來找出下列方程組的解或其解的限制： $\left\{{\begin{matrix}2x+y-z=8\quad (L_{1})\\-3x-y+2z=-11\quad (L_{2})\\-2x+y+2z=-3\quad (L_{3})\\\end{matrix}}\right.$

這個演算法的原理是：

首先，要將 $L_{1}$ 以下的等式中的 $x$ 消除，然後再將 $L_{2}$ 以下的等式中的 $y$ 消除。這樣可使整個方程組變成一個三角形似的格式。之後再將已得出的答案一個個地代入已被簡化的等式中的未知數中，就可求出其餘的答案了。

在剛才的例子中，我們將 ${\frac {3}{2}}L_{1}$ 和 $L_{2}$ 相加，就可以將 $L_{2}$ 中的 $x$ 消除了。然後再將 $L_{1}$ 和 $L_{3}$ 相加，就可以將 $L_{3}$ 中的 $x$ 消除。

我們可以這樣寫：

　
: $L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}$

　
: $L_{3}+L_{1}\rightarrow L_{3}$

結果就是：

　
: $2x+y-z=8\,$

　
: ${\frac {1}{2}}y+{\frac {1}{2}}z=1\,$

　
: $2y+z=5\,$

現在將 $-4L_{2}$ 和 $L_{3}$ 相加，就可將 $L_{3}$ 中的 $y$ 消除：

　
: $L_{3}+-4L_{2}\rightarrow L_{3}$

其結果是：

　
: $2x+y-z=8\,$

　
: ${\frac {1}{2}}y+{\frac {1}{2}}z=1\,$

　
: $-z=1\,$

這樣就完成了整個演算法的初步，一個三角形的格式（指：變數的格式而言，上例中的變數各為 3,2,1 個）出現了。

第二步，就是由尾至頭地將已知的答案代入其他等式中的未知數。第一個答案就是：

　
: $z=-1\quad (L_{3})$

然後就可以將 $z$ 代入 $L_{2}$ 中，立即就可得出第二個答案：

　
: $y=3\quad (L_{2})$

之後，將 $z$ 和 $y$ 代入 $L_{1}$ 之中，最後一個答案就出來了：

　
: $x=2\quad (L_{1})$

就是這樣，這個方程組就被高斯消去法解決了。

這種演算法可以用來解決所有線性方程組。即使一個方程組不能被化為一個三角形的格式，高斯消去法仍可找出它的解。例如，如果在第一步化簡後， $L_{2}$ 及 $L_{3}$ 中沒有出現任何 $y$ ，沒有三角形的格式，照著高斯消去法而產生的格式仍是一個列階梯形矩陣。這情況之下，這個方程組會有超過一個解，當中會有至少一個變數作為答案。每當變數被鎖定，就會出現一個解。

通常人或電腦在應用高斯消去法的時候，不會直接寫出方程組的等式來消去未知數，反而會使用矩陣來計算。以下就是使用矩陣來計算的例子：

　
: $\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

跟著以上的方法來運算，這個矩陣可以轉變為以下的樣子：

　
: $\left[{\begin{array}{ccc|c}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$

這矩陣叫做「列階梯形矩陣」。

最後，可以利用同樣的演算法產生以下的矩陣，便可把所得出的解或其限制簡明地表示出來：

　
: $\left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

最後這矩陣叫做「簡化列階梯形矩陣」，亦是高斯 - 約旦消去法指定的步驟。

## 其他應用

### 找出逆矩陣

高斯消去法可以用來找出一個可逆矩陣的逆矩陣。設 $A$ 為一個 $n\times n$ 的矩陣，其逆矩陣可被兩個分塊矩陣表示出來。將一個 $n\times n$ 單位矩陣放在 $A$ 的右手邊，形成一個 $n\times 2n$ 的分塊矩陣 $B=[A,I]$ 。經過高斯消去法的計算程式後，矩陣 $B$ 的左手邊會變成一個單位矩陣 $I$ ，而逆矩陣 $A^{-1}$ 會出現在 $B$ 的右手邊。

假如高斯消去法不能將 $A$ 化為三角形的格式，那就代表 $A$ 是一個不可逆的矩陣。

應用上，高斯消去法極少被用來求出逆矩陣。高斯消去法通常只為線性方程組求解。

### 計出秩和基底的基本演算法

高斯消去法可應用在任何 $m\times n$ 的矩陣 $A$ 。在不可減去某數的情況下，我們都只有跳到下一行。以一個 $6\times 9$ 的矩陣作例，它可能可以變化為一個列階梯形矩陣：

　
: ${\begin{bmatrix}1&*&0&0&*&*&0&*&0\\0&0&1&0&*&*&0&*&0\\0&0&0&1&*&*&0&*&0\\0&0&0&0&0&0&1&*&0\\0&0&0&0&0&0&0&0&1\\0&0&0&0&0&0&0&0&0\end{bmatrix}}$

而矩陣中的 \* 是一些數字。這個列階梯形矩陣 $T$ 會有一些關於 $A$ 的資訊：

 * $A$ 的秩是 5，因為 $T$ 有 5 行非 0 的行；
* $A$ 的列空間 Col (A)，將以 $A$ 的第 1、3、4、7 和 9 列為基底，就是那些在矩陣 $T$ 之中擁有軸元的行；
* 矩陣中的 \* 表示了 $A$ 的該行如何寫為上述基底的線性組合。

## 分析

高斯消去法的演算法複雜度是 O (_n_3)；這就是說，如果係數矩陣的是 _n_ × _n_，那麼高斯消去法所需要的計算量大約與 _n_3 成比例。

高斯消去法可以用在電腦中來解決數千條等式及未知數。不過，如果有過百萬條等式時，這個演算法會十分費時。一些極大的方程組通常會用疊代法來解決。亦有一些方法特地用來解決一些有特別排列的係數的方程組。

高斯消去法可用在任何域中。

高斯消去法對於一些矩陣來說是穩定的。對於普遍的矩陣來說，高斯消去法在應用上通常也是穩定的，不過亦有例外。

## 虛擬碼

高斯消去法的其中一種虛擬碼：

這個演算法和之前談到的有點不同，它由絕對值最大的部分開始做起，這樣可以改善演算法的穩定性。本演算法由左至右地計算，每作出以下三個步驟，才跳到下一行和下一列：

1. 定出每行的絕對值最大的一個非 0 的數，將第一列的值與該列交換，使得第一列擁有這一行的最大值；
2. 將第一行的數字除以該數，使得該列的第一個數成為 1；
3. 對每一列減去第一列乘以每一列的第一個數，使得每一列的第一個數變為 0。

所有步驟完成後，這個矩陣會變成一個列階梯形矩陣，再用代入法就可以求解該方程組。

 
隨著多核處理器的日益普及，現在的程式設計師可以利用執行緒級並列高斯消去演算法來提高計算的速度。記憶體共享模式（而不是訊息交換模式）的虛擬碼如下所示：

## 參考文獻

* Atkinson, Kendall A. _An Introduction to Numerical Analysis_, 第二版，John Wiley & Sons, New York, 1989 年 ISBN 978-0-471-50023-0
* Golub, Gene H., and Van Loan, Charles F. _Matrix computations_, 第三版，Johns Hopkins, Baltimore, 1996 年 ISBN 978-0-8018-5414-9
* Lipschutz, Seymour, and Lipson, Mark. _Schaum's Outlines: Linear Algebra_, Tata McGraw-hill edition.Delhi 2001 年，第 69-80 頁

## 參見

* 高斯－約當消去法
* 列階梯形矩陣
* 線性方程組求解
* 四元玉鑒

## 外部連結

* 高斯消去法 （頁面存檔備份，存於網際網路檔案館）
* java applet 高斯消去法，只能取自然數。
* matlab octave 的高斯約當消去法
* python 語言的高斯消去法 （頁面存檔備份，存於網際網路檔案館）
* 中國大百科智慧型藏 - 消去法