[응용선형대수] Gauss elimination 가우스 소거법

앞의 글에서 linear equation에 대해서 보았고 해에 대한 3가지 경우를 살펴보았습니다.

 

복잡한 고차방정식에서도 해가 없는지, 무수히 많은지, unique solution이 존재하는지를 알고 싶을 수 있습니다.

이 때는 gauss elimination을 통해 확인해볼 수 있습니다.

 

gauss elimination은 중학교 때 했던 소거법과 거의 비슷하다고 생각합니다.

 

$\left\{\begin{matrix}x_{1}+3x_{2}-2x_{3}+0x_{4}=3\\ 2x_{1}+6x_{2}-2x_{3}+4x_{4}=18\\0x_{1}+x_{2}+x_{3}+3x_{4}=10\end{matrix}\right.$

 

다음과 같은 equation이 있다고 할 때, 이를 아래와 같은 형태로 표현하겠습니다.

 

$\begin{bmatrix}\left.\begin{matrix}1 & 3 & -2 & 0\\2 & 6 & -2 & 4\\0 & 1 & 1 & 3\end{matrix}\right| \begin{matrix}3\\ 18\\ 10\end{matrix}\end{bmatrix}$

 

문자를 제외하고 계수와 상수만 적은 것입니다. 이제 각 row를 특정 수를 곱해서 row들끼리 빼고 더함으로써 행렬의 우측 아래가 0이 되도록, 즉 triangular form이 되도록 바꾸겠습니다.

 

step1)

첫 번째 row에 2를 곱해서 두 번째 row를 뺍니다.

 

$\begin{bmatrix}\left.\begin{matrix}1 & 3 & -2 & 0\\0 & 0 & 2 & 4\\0 & 1 & 1 & 3\end{matrix}\right| \begin{matrix}3\\ 12\\ 10\end{matrix}\end{bmatrix}$

 

step2)

두 번째 row는 각 계수를 2로 나눌 수 있으므로 나눠줍니다. 세 번째 row를 두 번째 row로 옮기고 자동으로 두 번째 row는 세 번째 row에 들어갑니다.

 

$\begin{bmatrix}\left.\begin{matrix}1^{*} & 3 & -2 & 0\\0 & 1^{*} & 1 & 3\\0 & 0 & 1^{*} & 2\end{matrix}\right| \begin{matrix}3\\ 10\\ 6\end{matrix}\end{bmatrix}$

 

이 형태를 보면 행렬의 우측 아래가 모두 0이므로 triangular form이 되고, 이를 row-echelon form(행사다리꼴 행렬)이라고 합니다. pivot(별표시 해놓은 숫자들) 아래가 다 0이고 각 row의 pivot이 위의 row보다 뒤에 있는 경우입니다.

 

여기에서 더 계산을 수행할 수도 있습니다.

 

step3)

pivot이 모두 1이고, pivot 위아래의 element가 모두 0이 되도록 바꿉니다. 세 번째 row를 이용해 두 번째 row의 세 번째 element를 0으로 만들고, 세 번째와 두 번째 row를 이용해 첫 번째 row의 두 번째, 세 번째 element를 0으로 만들어주면 됩니다.

 

$\begin{bmatrix}\left.\begin{matrix}1 & 0 & 0 & 1\\0 & 1 & 0 & 1\\0 & 0 & 1 & 2\end{matrix}\right| \begin{matrix}3\\ 4\\ 6\end{matrix}\end{bmatrix}$

 

여기서 주목할 부분은 다른 column은 pivot을 제외하고 다 0으로 만들 수 있지만 마지막 column은 0이 아니라는 점입니다. 분명 미지수는 4개인데 식은 3개이기 때문에 발생하는 문제입니다. 충분한 식이 존재하지 않는 것입니다.

이렇게 pivot은 1이고 그 위아래는 0인 형태를 reduced (row) echelon form이라고 합니다.

 

마지막 형태를 가지고 matrix에서 equation으로 다시 바꾸면,

 

$\left\{\begin{matrix}x_{1}+x_{4}=3\\ x_{2}+x_{4}=4\\ x_{3}+2x_{4}=6\end{matrix}\right. \rightarrow \begin{matrix}x_{1}=3-x_{4}\\ x_{2}=4-x_{4}\\ x_{3}=6-2x_{4}\\ x_{4}=x_{4}\end{matrix}\rightarrow x=\begin{bmatrix}3\\ 4\\ 6\\ 0\end{bmatrix}+x_{4}\begin{bmatrix}-1\\ -1\\ -2\\ 1\end{bmatrix}$

 

여기서 $x_{4}$값에 따라서 무수히 해가 많음을 알 수 있습니다.

 

마지막으로 위의 gauss elimination에서 가능한 operation은 3개입니다.\

1) row에 상수 c를 곱하는 것 $r_{i}\rightarrow c r_{i}$

2) 두 row의 위치를 바꾸는 것 $r_{i}\rightleftharpoons r_{j}$

3) 한 row에 다른 row의 상수곱을 더하는 것 $r_{i}\rightarrow r_{i}+cr_{j}$

 

이 operation을 이용해 위와 같이 gauss elimination(가우스 소거법)을 진행하시면 됩니다.

 

---