Skip to main content
Secologies

高斯消去法

•5 min•1,245 words
矩陣線性代數高斯消去法

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

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

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

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

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

整個聯立方程系統變成

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

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

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

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

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

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

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

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

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

[24−2∣249−3∣8−2−37∣10]\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 4 & 9 & -3 & | & 8 \\ -2 & -3 & 7 & | & 10\end{bmatrix}

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

[24−2∣2011∣4015∣12]\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 0 & 1 & 1 & | & 4 \\ 0 & 1 & 5 & | & 12\end{bmatrix}

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

[24−2∣2011∣4004∣8]\begin{bmatrix}2 & 4 & -2 & | & 2 \\ 0 & 1 & 1 & | & 4 \\ 0 & 0 & 4 & | & 8\end{bmatrix}

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

[A∣b]\begin{bmatrix}A | b\end{bmatrix}

又或者

[U∣c]\begin{bmatrix} U | c\end{bmatrix}

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

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

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

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

[111∣225∣468∣]\begin{bmatrix}1 & 1 & 1 & | & \\ 2 & 2 & 5 & | & \\ 4 & 6 & 8& | & \end{bmatrix}

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

[111∣003∣024∣]\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 0 & 3 & | & \\ 0 & 2 & 4& | & \end{bmatrix}

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

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

[111∣024∣003∣]\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 2 & 4& | & \\ 0 & 0 & 3 & | \end{bmatrix}

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

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

[111∣225∣448∣]\begin{bmatrix}1 & 1 & 1 & | & \\ 2 & 2 & 5& | & \\ 4 & 4 & 8 & | \end{bmatrix}

做高斯消去後

[111∣003∣004∣]\begin{bmatrix}1 & 1 & 1 & | & \\ 0 & 0 & 3& | & \\ 0 & 0 & 4 & | \end{bmatrix}

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

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

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