가우스소거법(Gaussian Elimination)과 LU분해(LU Decomposition)

가우스 소거법 - Gaussian Elimination

가우스소거법은 연립방정식의 해를 구하는 방법 중 하나다.

각 행의 pivot을 사용해 Upper Triangular Matirx를 만드는 과정이라고 생각하면 된다.

 

예시를 따라가며 가우스소거법의 연산방법을 익혀보자.

아래 연립일차방정식의 해 u, v, w를 구하는 것이 목적이다.

$$\begin{cases} 2u+v+w = 5\\ 4u-6v = -2 \\ -2u+7v+2w = 9 \end{cases}$$

 

이를 행렬로 표현하면 다음과 같다.

$$\left[ \begin{matrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \\ \end{matrix} \right] \left[ \begin{matrix} u \\ v \\ w \\ \end{matrix} \right] = \left[ \begin{matrix} 5 \\ -2 \\ 9 \\ \end{matrix} \right]$$

미지수를 생략하여 좀 더 간단하게 표현하면 다음과 같이 나타낼 수 있다.

 

$$\left[ \begin{matrix} 2&1&1&5 \\ 4&-6&0&-2 \\ -2&7&2&9 \\ \end{matrix}\right]$$

 

 

첫번째 행의 첫번째 열 요소, 두번째 행의 두번째 열 요소, 세번째 행의 세번째 열 요소,,,,(대각선으로)

를 각 행의 pivot이라고 한다.

 

가우스소거법은 각 행을 더하고 빼면서, pivot을 기준으로 pivot 아래에 있는 요소들을 모두 0으로 만들어주는 과정을 의미한다.

먼저 1행의 pivot인 2를 기준으로, 첫번째 pivot 아래를 모두0으로 만들어 보자.

$$\left[ \begin{matrix} 2&1&1&5 \\ 4&-6&0&-2 \\ -2&7&2&9 \\ \end{matrix}\right] → \left[ \begin{matrix} 2&1&1&5 \\ 0&-8&-2&-12 \\ 0&8&3&14 \\ \end{matrix}\right]$$

이 과정에서 2행과 3행에 각각 연산된 것은 다음과 같이 나타낼 수 있다.

$$l_{2}' = l_{2}-2*l_{1}$$

$$l_{3}' = l_{3}-(-1*l_{1})$$

 

이어서 두번째 pivot(2행의 pivot -8)을 기준으로, 그 아래를 모두 0으로 만들어 보자. 이때는 2행과 3행을 계산하면 되겠다.

$$\left[ \begin{matrix} 2&1&1&5 \\ 0&-8&-2&-12 \\ 0&8&3&14 \\ \end{matrix}\right] → \left[ \begin{matrix} 2&1&1&5 \\ 0&-8&-2&-12 \\ 0&0&1&2 \\ \end{matrix}\right]$$

이 과정에서 3행에 연산된 것은 다음과 같이 나타낼 수 있다.

$$l_{3}'' = l_{3}'-(-2*l_{2}')$$

 

pivot 아래가 모두 0인 형태가 되었으므로 가우스소거법을 종료하면 된다.

$$\left[ \begin{matrix} 2&1&1 \\ 0&-8&-2 \\ 0&0&1 \\ \end{matrix}\right]$$

이때, 이렇게 pivot 아래가 모두 0이고, 그 위는 0이 아닌 행렬을 Upper Triangular Matirx (U)라고 한다.

 

이 U를 아까의 연립방정식 형태로 변환하면 다음과 같다.

$$\begin{cases} 2u+v+w = 5\\ 0u-8v-2w = -12 \\ 0u+0v+1w = 2 \end{cases}$$

해를 구하기 쉬운 형태가 되었다. 이를 올라가면서 변수를 하나씩 구하고, 구한 변수를 위의 식에 대입하는 Back-Substitution 방식으로 모든 해를 구하면 된다.

 

이러한 가우스 소거법을 통해, 행렬 A에 관한 식을 행렬 U에 관한 식으로 변형시킬 수 있음을 알 수 있다.

$$A·x = b → U·x = c$$

 

---

가우스 소거법에서 LU 분해법까지 (LU Decomposition)

가우스 소거법이 행렬 A를 U로 변환하는 과정을 의미했다면, LU 분해법은 행렬 A를 L(Lower Triangular Matrix) 과 U(Upper Triangular Matrix) 행렬의 곱으로 분해해내는 것을 의미한다.

 

$$A \;=\;L\;·\;U$$

그 분해과정을, 가우스 소거법을 행렬의 곱으로 나타내보면서 알아보자.

 

위에서 사용한 예시를 그대로 쓰자.

 

$$A = \left[ \begin{matrix} 2&1&1&5 \\ 4&-6&0&-2 \\ -2&7&2&9 \\ \end{matrix}\right]→ \left[ \begin{matrix} 2&1&1&5 \\ 0&-8&-2&-12 \\ 0&8&3&14 \\ \end{matrix}\right]→ \left[ \begin{matrix} 2&1&1&5 \\ 0&-8&-2&-12 \\ 0&0&1&2 \\ \end{matrix}\right] = U$$

 

A가 U로 변환되는 과정에서 사용된 연산은 아래와 같다.

$$l_{2}' = l_{2}-2*l_{1}\;,\;\;so\;\;-l_{21}=-2$$

$$l_{3}' = l_{3}-(-1*l_{1})\;,\;\;so\;\;-l_{31}=1$$

$$l_{3}'' = l_{3}'-(-2*l_{2}')\;,\;\;so\;\;-l_{32}=2$$

 

위의 연산을 행렬의 곱으로 표현하면 다음과 같다.

$$E_{21} = \left[\begin{matrix}1&0&0 \\ -l_{21} = -2&1&0 \\ 0&0&1\\ \end{matrix}\right],\;E_{31} = \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ -l_{31} = 1&0&1\\ \end{matrix}\right],\;E_{32} = \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ 0&-l_{32} = 2&1\\ \end{matrix}\right]$$

 

$$E = E_{32}·E_{31}·E_{21} = \left[ \begin{matrix} 1&0&0 \\ -l_{21} = -2&1&0 \\ (-l_{21})(-l_{32})-l_{31} = -5&-l_{32} = 2&1 \\ \end{matrix}\right]$$

 

$$E·A = E_{32}·E_{31}·E_{21}·A = U = \left[ \begin{matrix} 2&1&1 \\ 0&-8&-2 \\ 0&0&1 \\ \end{matrix}\right]$$

이때 E21, E31, E32를 Elementary Matrix라고 하며, 각각은 뒤의 행을 기준으로 앞의 행을 '가우스소거' 해주는 역할을 한다.

가령 아래의 식은 A 행렬의 1행을 기준으로 2행을 가우스소거해주는 과정을 의미하는 것이다.

$$E_{21}·A$$

 

 

 

이제껏 elementary matrix를 활용해 A 행렬을 U 꼴로 바꾸는 가우스소거법을 행렬의 곱으로 나타내었다.

$$E·A = U$$

이를 이용해 우리가 도달해야 하는 결론은 아래와 같음을 상기하자.

$$A = L·U$$

 

 

E의 inverse matrix가 L(Lower Triangular Matrix)꼴이라면, 아래의 과정을 통해 LU분해에 다다를 수 있울 것이다.

$$E^{-1} = L$$

$$E^{1}·E·A = E^{1}·U$$

$$A = L·U$$

즉, 양변에 E의 역행렬을 곱해주면 A가 LU로 분해되는 것을 확인할 수 있을 것이다.

이 과정을 행렬로 표현해보자.

 

$$E_{21}^{-1} = \left[\begin{matrix}1&0&0 \\ 2&1&0 \\ 0&0&1\\ \end{matrix}\right],\;E_{31}^{-1} = \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ -1&0&1\\ \end{matrix}\right],\;E_{32}^{-1} = \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ 0&-2&1\\ \end{matrix}\right]$$

각 elementary matrix의 역행렬은 행렬의 0이 아닌 요소에 -를 붙인 꼴과 같다.

 

$$\left[ \begin{matrix} 1&0&0 \\ -2&1&0 \\ -5&2&1 \\ \end{matrix}\right]_{E} \left[ \begin{matrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \\ \end{matrix}\right]_{A}\;=\;\left[ \begin{matrix} 2&1&1 \\ 0&-8&-2 \\ 0&0&1 \\ \end{matrix}\right]_{U}$$

위의 식 양변에 E의 역행렬을 곱해주면,

 

$$E^{-1}·E(A)·A\;=\; E^{-1}·U$$

$$I·A\;=\; E^{-1}·U$$

$$I·A\;=\; (E_{32}·E_{31}·E_{21})^{-1}·U$$

$$I·A\;=\; (E_{21}^{-1}·E_{31}^{-1}·E_{32}^{-1})·U$$

 

$$E_{21}^{-1}·E_{31}^{-1}·E_{32}^{-1} = \left[\begin{matrix}1&0&0 \\ 2&1&0 \\ 0&0&1\\ \end{matrix}\right] \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ -1&0&1\\ \end{matrix}\right] \left[\begin{matrix}1&0&0 \\ 0&1&0 \\ 0&-2&1\\ \end{matrix}\right] = \left[\begin{matrix}1&0&0 \\ 2&1&0 \\ -1&-2&1\\ \end{matrix}\right]$$

E의 역행렬이 Lower Triangular Matrix 꼴임을 알 수 있다! 따라서,

 

$$\left[ \begin{matrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \\ \end{matrix}\right]_{A}\;=\;\left[\begin{matrix}1&0&0 \\ 2&1&0 \\ -1&-2&1\\ \end{matrix}\right]_{L} \left[ \begin{matrix} 2&1&1 \\ 0&-8&-2 \\ 0&0&1 \\ \end{matrix}\right]_{U}$$

$$A = L·U$$

 

 

---

Pivoting 과 Permutation Matrix - 행의 순서 바꾸기

 

원활하게 가우스소거법이 이루어진다면 좋겠지만, 그렇지 않은 경우도 있다.

연산과정에서 pivot이 0이 되어버릴 때가 그렇다.

$$\left[ \begin{matrix} 1&1&1&-1 \\ 2&2&5&2 \\ 4&6&8&3 \\ \end{matrix}\right] → \left[ \begin{matrix} 1&1&1&-1 \\ 0&0&3&4 \\ 0&2&4&7 \\ \end{matrix}\right]$$

2행의 pivot이 0이 되어버리면서 가우스소거법이 더이상 불가능해졌다.

 

이때는 행의 순서를 바꾸는 pivoting을 실행함으로써 가우스소거법을 계속 진행할 수 있다.

$$\left[ \begin{matrix} 1&1&1&-1 \\ 0&2&4&7 \\ 0&0&3&4 \\ \end{matrix} \right]$$

2행과 3행의 순서가 바뀐 것을 확인하자.

 

Permutation Matrix를 사용하면 pivoting의 과정 또한 행렬의 곱으로 나타낼 수 있다.

 

아래 Permutation Matrix는 행렬의 i열과 j열을 바꾸어주는 역할을 한다.

$$P_{ij} = \left[\begin{matrix}1&0&0&...&0 \\0&1&0&...&0\\0&0&1&...&0\\0&0&0&...p_{ij}=1&0\\0&0&0&p_{ji}=1...&0\\ \end{matrix}\right]$$

Identity Matrix와 유사하게 생겼으나, pivoting 하려는 행들에 한해, P[j][i]와 P[i][j]가 1인 행렬이다.

 

예를 들어보자.

$$P^{12} = \left[\begin{matrix}0&1\\1&0\\ \end{matrix}\right]_{2*2}$$

$$P^{34} = \left[\begin{matrix}1&0&0&0\\0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ \end{matrix}\right]_{4*4}$$

 

가령 P12 * A를 하게 될 경우, 결과로서 나오는 행렬은 A행렬의 첫번째 행과 두 번째 행을 바꿔준(swap) 행렬의 꼴인 것이다.

 

 

정리하자면, A 행렬에 Elementary Matrix를 곱하고, 필요에 따라 중간중간에 Permutation Matrix를 곱하는 과정을 반복하는 행위가, 결국 가우스소거법을 행렬의 곱으로 표현한 것이라는 결론이 난다. 

예를 들어보자.

$$P_{23}·E_{31}·E_{21}·A$$

위 행렬의 곱을 "A행렬의 2행을 1행 pivot을 이용해 소거해주고, 3행을 1행 pivot을 이용해 소거해준 후 2행과 3행의 위치를 바꿔주는 연산이다." 라고 해석할 수 있다는 것이 핵심이다.

 

---

 

Singular Case in Gaussina Elimination

가우스소거법으로 계산했으나 해가 없거나 무수히 많은 singular case가 나올 수도 있다.

가우스 소거법의 결과가 Upper Triangular Matrix가 아닌 경우가 그 case이다.

$$\begin{cases} u+v+w = a \\ 2u+2v+5w = b \\ 4u+4v+8w = c \end{cases}$$

위 연립일차방정식은 가우스소거법으로 pivot 아래를 0으로 만드는 과정을 거쳤을 때 다음과 같은 형태를 띤다.

$$\left[ \begin{matrix} 1&1&1&a \\ 0&0&3&b-2a \\ 0&0&4&c-4a \end{matrix}\right]$$

$$w_{1} = {b-2a \over 3}\;,\;w_{2} = {c-4a\over 4}$$

 

(1) w1과 w2가 일치할 때
w에 해당하는 해는 존재함을 알 수 있다. 단, 알 수 있는 범위는 u+v = a-w 까지로 제한되며, u와 v 각각은 알 수 없다.
식을 만족하는 모든 집합이 답이 되는 것이다. (Infinitely many solution)

(2) w1과 w2가 일치하지 않을 때
해가 존재하지 않는 경우다. (No Solution)