도입 및 소개

Gaussian Elimination이란?

이번 포스트에서는 Gaussian Elimination (가우스 소거법)에 대해서 소개하고자 한다.

사실 Gaussian Elimination 의 본질은 매우 간단하다. 중학교/고등학교에서 배웠던 연립방정식의 해를 구하고자 할 때 우리는 변수를 소거할 수 있도록 주어진 방정식에 적당한 수를 곱한뒤 빼서 값을 구하지 않는가?

가우스 소거법은 이런 과정을 행렬과 벡터로 나타내는 $Ax=b$ 꼴에서 진행하는 것이다. 

Gaussian Elimination의 목표

선형방정식 $Ax = b$에서 행렬 $A$를 Upper triangular form(상삼각행렬)꼴로 정리하는 것

Upper triangular나 Lower triangular 형태로 행렬을 정리하게 되면, 반드시 하나의 행에서는 1개의 변수만을 갖는 방정식(ex. $2x = 1$)이 존재하게 된다.

그 방정식을 이용하여 변수 하나의 값을 알게되면, 차례대로 구한 변수의 값만을 다른 방정식에 대입해가면서 모든 변수를 간단한 대입연산 만으로도 구할 수 있다는 이점이 존재하기 때문에 Gaussian Elimination을 진행하는 것이다.

*Upper triangular : 대각선상을 기준으로, 대각선상과 그 오른쪽 윗부분에만 0이아닌 값이 존재하는 행렬
(↔ Lower triangular)

왼쪽 : Upper triangular, 오른쪽 : Lower triangular

Gaussian Elimination Process

Row Operation (행연산)

• Augmented matrix Form
  • Gaussian Elimination를 쉽게 진행하기 위해 고안한 행렬의 표현 방법.
  • 행렬과 벡터 표현으로 나타내는 $Ax=b$를 $[A|b]$ 형태의 행렬로 나타낸다.
  • 변수들의 집합벡터인 $x$는 미지수로 이루어져있기 때문에 계산에 영향을 주지 않아서 생략하고 Augmented matrix로 표현할 수 있다.

• Row Operation의 3가지 방법
  • Subtracting a multiple of a row from another row (어떤 행에 상수배를 취한 행을 다른 행으로부터 빼낸다.)
    → 특정 변수를 소거
    (주로 이 과정에서 당하는 행에는 수를 곱하지 않는다.)
  • Exchanging rows (행의 순서를 바꾼다.)
    → 나열된 방정식의 순서를 바꿈
  • Scaling a row with nonzero scalar (행을 0이 아닌 스칼라 값으로 scaling하여 계수를 간단하게 표현한다.)

이처럼 행 연산은 기존 방정식을 변화시키지 않고, 방정식의 표현만 변화시키기 때문에 행연산을 수행하기 전후의 방정식은 변하지 않는다. 

연산과정 예시

주어진 연립방정식

1. $Ax = b$ 꼴로 표현

   $\begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}=\begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix}$

2. Augmented matrix Form*으로 표현

   $\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \\ \end{array} \right]$

3. 첫번째 행의 첫번째 요소 $2$로 아래 행의 요소를 소거
   $\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ \color{blue}0 & 1 & 1 & 4 \\ \color{blue}0 & 1 & 5 & 12 \\ \end{array} \right]$

• 두번째 행에는 첫번째 행에 2를 곱한 값을 빼주어서 소거를 진행한다.
  $(2) - 2 \times (1)$
• 세번째 행에는 첫번째 행을 더해주어 소거를 진행한다.
  $(3) + (1)$

4. 두번째 행의 두번째 요소 $1$로 세번째 행의 두번째 요소를 소거 한다.
   $(3) - (2)$
   $\left[ \begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & \color{blue}0 & 4 & 8 \\ \end{array} \right]$

가우스 소거를 이용하여 얻은 방정식의 해

Breakdown; 소거법의 붕괴

더 이상 소거를 진행할 수 없는 상황을 만났을 때

Temporary Breakdown

• 아래행의 요소에는 값이 남아있는데, 윗행의 요소가 $0$이 되어 윗행을 이용하여 아래행을 소거할 수 없는 상황
• 소거하고자하는 요소와 동일한 열에 $0$ 이 아닌 다른값을 가지고 있는 행과 행교환 해주어 문제를 해결한다.

Permanent Breakdown

• Temporary Breakdown상황이 발생했을 때, 교체가능한 행이 없는 경우
  (소거하려는 요소와 동일한 열의 모든 요소가 $0$ 이 된 상황)
• 일단 그 다음 열의 요소로 소거를 진행한다.
• 그렇게 만들어지는 결과행렬은 $0$ 으로만 이루어진 행을 무조건 가지게 된다.
  • $[0 0 ... 0 | 0]$
    → 해가 무수히 많다.
  • $[0 0 ... 0 | c]$ ($c$는 상수)
    → 모순. 따라서 해가 없다.

Pivots and Multipliers

Row Echelon Form

가우스 소거법을 끝낸 결과로 나타난 upper triangular matrix를 지칭하는 말

• $0$ 으로만 이루어진 행은 존재하지 않거나, 아래부터 위치한다. (2)
• $k+1$ 번째 행에 처음으로 나타나는 $0$ 이 아닌 값은, 바로 위의 행($k$ 행)보다 오른쪽에 위치한다. (1, 2, 3)

pivot

Row Echelon Form에서 각 행에 대하여 첫번째로 나타나는 0이 아닌 값.

• n개의 미지수로 이루어진 n개의 방정식이 주어진 연립방정식에서 만약 피봇의 개수가 n개라면, 해당 방정식의 해는 항상 존재하며 유일하다.
• 위를 행렬 표현으로 바꾸면, $n\times n$ 행렬 $A$를 Gaussian Elimination한 결과로 얻어진 pivot의 개수가 n개라면, 벡터 $x$의 요소들(미지수 해)은 유일하게 존재한다.

따라서 행렬에 있어서 pivot이 굉장히 중요한 역할을 하게 된다.

multiplier

행에 어떤 값을 곱해 다른행의 요소를 소거할 때, 해당 행에 곱해주는 값

multiplier = 소거하려는 요소의  값 / pivot 을 이용하여 구할 수 있다.

위 예시에서 multiplier는 2이다.

• $l_{21}$ = 소거할 값 / pivot = 4 / 2 = 2
• *$l_{21}$ : $A$의 $(2,1)$ 요소를 지우기 위해 사용하는 multiplier.

GE를 이용한 행렬의 분해

LU Factorization

(이때 L은 low triangular matrix, U는 upper triangular matrix를 의미한다.)

LU Factorization을 사용하는 이유

• $A=LU$로 분해할 수 있다면, $Ax=b$ 방정식을 쉽게 해결할 수 있다.
  • $A = LU$를 $Ax = b$에 적용하면, $LUx = b$
  • $Ux$를 $y$라는 새로운 벡터로 가정하면, $Ly = b$
• 따라서 Ax=b라는 방정식을 간단한 형태의 두 방정식으로 바꿔 표현할 수 있다.
  • $Ux=y$
  • $Ly=b$
• upper triangular matrix와 low triangular matrix로 표현된 방정식을 해결하는 것은 간단하기에 (단순대입), 쉽게 방정식을 사용할 수 있다.

• 실제 상황에서는 행렬 A는 변하지 않는데 결과벡터인 b가 계속해서 변화하는 경우, 변화하는 각각의 경우마다 모두 가우스 소거법을 적용하는 것 보다는 LU로 표현하여 계산하는 것이 더 간단하다.

LU Factorization 적용방법

기본 아이디어는 $Ax=b$로 표현된 방정식의 양변에 어떤 행렬을 곱해야 가우스 소거가 완료된 표현으로 변하는가? 이다.
→ GE 과정을 하나의 행렬곱으로 표현하고자 한다.

• 가우스 소거를 마친 행렬 $A$는 Upper triangular matrix이므로 $U$로 표기한다.
• 아이디어를 표현하여 어떤 행렬 $E$를 $A$에 곱하여 $U$를 만들 수 있다고 가정하자.
  (행렬 $E$를 곱한것만으로도 GE를 수행한 것과 동일한 행렬을 얻음)
  • $EA = U$
• 양변에 $E$의 역행렬을 곱하면, $A = E^{-1}U$로 표현된다.
• 이때 $E$의 역행렬은 Low triangular matix ($L$)로 나타낼 수 있다. *예시 참고
  $A = LU$

실제 LU Factorization 적용예시
LU Factorization을 적용할 행렬 $A$

1. $A$의 $(2,1)$요소를 지우기 위해 사용하는 행렬 $E_{21}$.

   $l_{21} = 2$
   $E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ \color{blue}-2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

   $E$는 곱하더라도 요소에 변화가 없는 항등행렬을 base로 활용하고 지우고자하는 요소의 위치에 (- multipler) 를 대입한 행렬으로 표현할 수 있다.

2. $A$의 $(3,1)$요소를 지우기 위해 사용하는 행렬 $E_{31}$.

   $l_{31} = -1$
   $E_{31} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \color{blue}1 & 0 & 1 \end{bmatrix}$

3. $A$의 $(3,2)$요소를 지우기 위해 사용하는 행렬 $E_{32}$.

   $l_{32} = 1$
   $E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \color{blue}-1 & 1 \end{bmatrix}$

4. 각 단계에 사용되는 행렬 E들과 행렬 A를 모두 차례대로 곱하면 실제 Gauss Elimination을 진행한 것과 동일한 Upper triangular matrix를 얻을 수 있다.

   $E_{32}E_{31}E_{21}A = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix} = U$

5. 이후 행렬 E들의 곱의 역행렬을 계산하면 Low triangular matrix가 되며, 최종적으로는 A = LU라는 행렬을 얻을 수 있다.

LDU Factorization

• $U$를 대각행렬인 $D$를 이용하여 다시 표현하여 분리시킨 것
• $A = LDU$

실제 LDU Factorization 적용예시