高斯消去法

$\begin{cases}2x + 4y - 2z = 2 \\ 4x + 9y - 3z = 8 \\ -2x - 3y + 7z = 10\end{cases}$

為了解決上述的聯立方程系統，使用高斯消去法減少不同variable的係數來求出我們需要的結果，要做的其實就只是把不同的方程式互相加減，通常把該項variable稱作pivot，接著把pivot的方程式乘上某個數扣掉剩餘的其他方程式，首先把第一項乘上 $(-2)$ 加到第二項，

$((-2) \times (2x + 4y - 2z = 2)) + (4x +9y - 3z = 8)$

使得第一項方程式變成 $-4x-8y+4z = -4$ ，將其加到第二項方程式後，該項變成 $y + z = 4$

而針對第三項方程式讓第一項方程式乘上 $(-1)$ 加上去，變成 $y + 5z = 12$

整個聯立方程系統變成

$\begin{cases}2x+4y-2z = 2 \\ y+z = 4 \\ y+5y = 12\end{cases}$

這樣就讓 $x$ 係數只剩下一組，該組就稱作pivot，接著選擇另一組pivot，我們選擇第二個方程式的 $y$ 作為pivot，所以將其乘上 $(-1)$ 加到第三項方程式，

$(-1)(y+z = 4) + (y+5z) = 12$

第三項方程式變成 $4z = 8$ ，所以經由第二次的計算現在方程式變成

$\begin{cases}2x+4y-2z = 2 \\ y + z = 4 \\ 4z = 8\end{cases}$

明顯的可以直接算出 $z = 2$ ，在往上計算 $y+2 = 4$ 求得 $y = 2$ ，在知道了 $y$ 以及 $z$ 最後在往上一層算 $2x+8-4 = 2$ ， $2x = -2$ ，最終可以知道 $x = -1$ ，所以找出了一組解

$x = -1, y = 2, z = 2$

這種往上計算的方法稱作backward substitution。

而在線性代數當中，經常是把聯立方程系統透過矩陣的方法來表示，使用矩陣運算的方法會比較快速

$\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 4 & 9 & -3 & | & 8 \\ -2 & -3 & 7 & | & 10\end{bmatrix}$

做法其實也跟上面的流程差不多，一樣先選擇2當作pivot，然後消去底下的數字，

$\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 0 & 1 & 1 & | & 4 \\ 0 & 1 & 5 & | & 12\end{bmatrix}$

同樣的第二次計算第二個pivot，

$\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 0 & 1 & 1 & | & 4 \\ 0 & 0 & 4 & | & 8\end{bmatrix}$

可以明顯觀察到這組聯立方程系統變成了上三角矩陣，在上面一般方法計算的時候其實也有呈現出上三角矩陣的樣子，但現在會更明顯，而通常會表示成

$\begin{bmatrix}A | b\end{bmatrix}$

又或者

$\begin{bmatrix} U | c\end{bmatrix}$

其中 $U$ 是upper-triangular matrix(上三角矩陣)，而 $c$ 則為一個常數結果，將原本的問題 $Ax = b$ 置換成 $Ux = c$ 來解決 $n$ 個variables

而我們可以思考一下，在什麼情況下上面的方法會錯誤？

為了求出那些未知的解，pivots不能是 $0$

讓我們來考慮一個例子，什麼時候在計算時會出錯？

$\begin{bmatrix}1 & 1 & 1 & | & \\ 2 & 2 & 5 & | & \\ 4 & 6 & 8& | & \end{bmatrix}$

一樣計算高斯消去法變成下列

$\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 0 & 3 & | & \\ 0 & 2 & 4& | & \end{bmatrix}$

而當我們想要去找第二個pivot的時候卻是 $0$ ，這時候我們可以怎麼做？

觀察一下其實下一個方程式在 $y$ 的pivot是有值的，所以在高斯消去法當中其中一點很重要的是其實我們可以交換一下不同方程式的位置，像這裡我們把下一行方程式往上移變成

$\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 2 & 4& | & \\ 0 & 0 & 3 & | \end{bmatrix}$

有時候就是必須得交換row，同時將這樣的例子稱作nonsingular case

然而有些時候是行不同的，像下面的例子：

$\begin{bmatrix}1 & 1 & 1 & | & \\ 2 & 2 & 5& | & \\ 4 & 4 & 8 & | \end{bmatrix}$

做高斯消去後

$\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 0 & 3& | & \\ 0 & 0 & 4 & | \end{bmatrix}$

讓我們轉換成聯立方程式來看會比較清楚

$\begin{cases}x+y+z = C_{1} \\ 3z = C_{2} \\ 4z = C_{3}\end{cases}$

很明顯的可以看到這真的沒辦法找到 $y$ 的pivot了，這樣就無法繼續做消去法，這樣的情況稱作singular case， $z$ 這樣的情況稱作free variable，存在不同的解可以達成，但這樣要取決於 $C_{2}$ 跟 $C_{3}$ 之間的關係，如果 $C_{2}$ 跟 $C_{3}$ 有倍數關係，那麼 $3z$ 跟 $4z$ 也可以透過倍數關係求得解，但也有可能沒有解，使得這些方程式其實處於solvable或者unsolvable，所以才稱為free variable。