高斯消去法

    \[\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 = 22x = -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}有倍數關係,那麼3z4z也可以透過倍數關係求得解,但也有可能沒有解,使得這些方程式其實處於solvable或者unsolvable,所以才稱為free variable。

Scientia

我是Scientia,研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Hardware Security以及Anomaly Detection.

Related Posts

Vectors

在整個線性代數中,最基本的單位就是一個向量,假設一個擁有兩個值的向量像是

    \[V = \begin{bmatrix}v_{1} \\ v_{2} \end{bmatrix}\]

向量加法假設另一組向量w一樣包含於兩個值$w = \begin{bmatr…

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

群之可解性

群之可解性

威脅情報指標 Indicators of compromise (IoC)

威脅情報指標 Indicators of compromise (IoC)

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page

群

NP-Completeness

NP-Completeness

異常檢測的問題分類

異常檢測的問題分類