선형대수 note 2: Elimination with Matrices

가우스 소거법 (Gauss Elimination1) 은 A\mathbf{x} = \mathbf{b} 형식의 선형계 (Linear System) 를 푸는 알고리즘이다.

  1. i 번째 행에서 0 이 아닌 pivot 을 찾는다. pivot 이 0 이라면 아래 행과 교환한다.2
    • 더 이상 교환할 행이 없다면 중단 (i 가 마지막 행이었다면 success, 아니라면 failed)
  2. pivot 을 기준으로 그 아래 행에서 i 번째 행의 상수배 한 것을 빼서 성분을 0 으로 만든다.
  3. 마지막 행까지 반복
  4. 1. 로 돌아가 다음 열의 i+1 번째 행에 대해서 수행

ex)

    \[A = \begin{bmatrix} \fbox{1} & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 2 \end{bmatrix} \xrightarrow{E_{21}} \begin{bmatrix} \fbox{1} & 2 & 1 \\ 0 & \fbox{2} & -2 \\ 0 & 4 & 2 \end{bmatrix} \xrightarrow{E_{32}} \begin{bmatrix} \fbox{1} & 2 & 1 \\ 0 & \fbox{2} & -2 \\ 0 & 0 & \fbox{5} \end{bmatrix} = U\]

E_{21} 는 첫번째 행에 3 배를 하여 두번째 행에서 빼는 연산이다. (연산의 결과로 A_{21} 성분이 0 이 되었다)
E_{32} 는 두번째 행에 2 배를 하여 세번째 행에서 빼는 연산이다. (연산의 결과로 A_{32} 성분이 0 이 되었다)

가우스 소거 후 상삼각 행렬이 되었다면, 후진 대입 (Back substitution) 으로 해를 구할 수 있다.

가우스 소거는 기본 행 연산 (Elementary row operation) 으로 이루어 진다. 이것은 우변의 \mathbf{b} 에도 동시에 적용되므로 연립방정식의 해를 유지한다. 기본행 연산은 아래의 3 가지 연산으로 이루어져 있다.

  1. 행을 교환한다
  2. 행에 상수를 곱한다.
  3. 행에 상수배를 하여 다른 행에 더한다.

이것은 A 의 좌변에 행렬을 곱하는 것으로 표현할 수 있다. 이 행렬을 기본 행렬 (Elementary Matrix) 라고 부른다.

ex)

    \[E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} ,\quad E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}\]

가우스 소거 후 결과 행렬 U 는 상삼각 행렬 (upper triangular matrix) 이 된다.

ex)

    \[E_{32} E_{21} A = E A = U\]

반대로 U 에서 A 로 변환하는 과정에 대해서 생각해 보자. 이것은 각 기본 행렬의 역 (Inverse) 을 적용하는 것과 같다.

    \[\begin{aligned} U &= E_{32} E_{21} A \\ E^{-1}_{21} E^{-1}_{32} U &= A \end{aligned}\]

각 기본 행렬의 역행렬은 elimination 하기 위해 pivot 행에 곱했던 상수에 부호만 반대로 바뀐것이 된다.

ex)

    \[E^{-1}_{21} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} ,\quad E^{-1}_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}\]

    \[E^{-1} = E^{-1}_{21} E^{-1}_{32} =  \begin{bmatrix} 1 & 0 & 0 \\ \fbox{3} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \fbox{2} & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ \fbox{3} & 1 & 0 \\ 0 & \fbox{2} & 1 \end{bmatrix}\]

공교롭게도 E^{-1} 의 하삼각 부분에는 각 elimination 행렬들의 multiplier 가 그대로 들어간다.3

다음은 C++ 로 만든 가우스 소거 함수다. (공개 수학 라이브러리 Eigen 을 사용)


선형대수 note 목록

  1. 미지수를 앞에서 부터 없애버리므로 Forward elimination 이라고도 부른다.
  2. 실제로 컴퓨터로 계산할 때 너무 작은 수로 나누면 수치적으로 불안정하게 된다. 따라서 pivot 이 0 이 아니더라도 가장 큰 수를 pivot 으로 삼기 위해 행을 교환하는데 이를 row pivoting 또는 partial pivoting 이라고 부른다.
  3. 이 내용은 나중에 LU 분해와 이어진다.

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *