[선형대수학] 가우스 소거법 (Gaussian elimination)

❗본 포스팅은 한양대학교 이상화 교수님의 '선형대수' 강의를 기반으로 개인적인 정리 목적 하에 재구성하여 작성된 글입니다.

 

Row Form vs Column Form

$$ x+2y=3\\ 4x+5y=6 $$

위와 같은 연립일차 방정식이 있을 때 고등학교에서 배웠던 방법은 소거할 항의 계수를 맞춘 뒤 소거하는 방법을 통해서 해를 구할 수 있었다. 예시의 경우 첫 번째 식에 4를 곱하고 빼서 x를 소거하고, 구한 y와 x를 구할 수 있다.

 

위의 연립일차방정식은 아래의 행렬로 표현할 수 있고,

$$ \begin{bmatrix}1 & 2 \\4 & 5 \\\end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 3 \\ 6 \\ \end{bmatrix} $$

x, y 행렬만 남기고 전부 오른쪽으로 이항하면 x와 y의 값에 대해 빠르게 구할 수 있게 된다.

$$ \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 4 & 5 \\ \end{bmatrix}^{-1} \begin{bmatrix} 3 \\ 6 \\ \end{bmatrix} = \begin{bmatrix} -1 \\ 2 \\ \end{bmatrix} $$

이렇게 구한 값의 의미에 대해서 생각해보자.

직선에 대한 연립방정식을 푼다는 것은 두 직선의 교점을 구하는 것라는 사실은 이미 알고 있을 것이다.

그런데 linear combination으로 접근해 보면 아래와 같이 표현할 수 있다.

$$ \begin{bmatrix}1 & 2 \\4 & 5 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} = x \begin{bmatrix} 1 \\ 4 \\ \end{bmatrix} + y \begin{bmatrix} 2 \\ 5 \\ \end{bmatrix} = \begin{bmatrix} 3 \\ 6 \\ \end{bmatrix} $$

이것의 의미는  $\begin{bmatrix}1 \\4 \\\end{bmatrix}$벡터를 x배, $\begin{bmatrix}2 \\5 \\\end{bmatrix}$벡터를 y배해서 $\begin{bmatrix}3 \\6 \\\end{bmatrix}$벡터를 구한다는 의미다.

정리하면

Row form(도형 혹은 직선의 형태)에서는 교점이라는 기하학적 의미를,

Column form(행렬)에서는 열 벡터의 선형 결합이라는 의미를 갖는다.

 

Singular case

특이 케이스를 의미한다. 해가 하나만 나오지 않고 아래의 두 가지 경우일 때를 의미한다.

 

• 해를 구할 수 없는 경우
• 해가 무수히 많은 경우

그러면 Row Form에서는 선 또는 평면이 평행한 경우 → 해를 구할 수 없는 경우

또는 아예 겹치는 경우 → 해가 무수히 많은 경우가 된다.

 

반면 column form에서 생각해 보자면 두 개의 칼럼 벡터의 방향이 평행한 경우 → 해가 없는 경우

또는 모두 같은 평면 상에 있는 3개의 벡터가 있는데 다른 공간의 벡터를 만드려고 하면? → 해가 없는 경우이다.

그러면 같은 공간의 벡터를 만드려고 하면? → 두 개의 벡터만을 이용해 모두 표현이 가능해지기 때문에 이런 경우 조합이 무수히 많아지게 되는 것이다.

 

 

가우스 소거법 (Gaussian elimination)

가우스 소거법(Gaussian Elimination)은 연립 일차 방정식 시스템을 푸는 알고리즘이다.

$$ 2u + v + w = 5 \\ 4u - 6v \space\space \space\space\space= -2 \\ -2u + 7v + 2w = 9 $$

 

 

가우스 소거법의 방법

 

• 하나의 pivot을 중심으로 그 아래의 요소는 모두 0으로 만드는 것이 목적이고, 다음 pivot으로 이동해 가면서 더 이상 소거할 항이 없을 때까지 진행한다.
• 예를 들어 위의 예시의 경우 첫 번째 행은 고정해둔 상태이고, 첫번째 pivot을 중심으로 그 아래 요소들을 모두 0으로 만드는 것이 목적이다.
• 두 번째 행 첫번째 요소를 0으로 → 첫번째 행에 -2를 곱하고 두번째 행을 더하면 두번째 행에 대한 계산은 완료된다.
• 세 번째 행 첫번째 요소를 0으로 → 첫번째 행과 세번째 행을 더하면 세번째 행에 대한 계산도 완료된다.
• 위의 과정처럼 두 번째 pivot을 중심으로 또 계산해 주면서 더 이상 소거할 항이 없을 때까지 진행하면 오른쪽 위쪽만 non-zero의 값이 남게 되는데, 우리는 그것을 upper triangular martix(U)라고 부른다.

 

가우스 소거법에서 유의할 점

 

pivot에 해당하는 숫자가 0이 나오면 가우스 소거법을 멈추고 연립방정식의 순서를 바꾸면 된다. 우리는 이것을 pivoting이라고 한다.

예를 들어 아래의 예시가 있을 때 가우스 소거법을 하면 다음과 같이 나온다. 이때는 pivoting을 이용해서 2번째와 3번째 식을 바꾸면 가우스 소거법을 할 수 있다.

그러나 아래와 같은 예시는 pivoting으로 해결되지 않는다. 그러면 이 경우에는 a, b, c에 따라 무수히 많은 값이 있을 수 있다.