1차 연립방정식과 가우소 소거법

Gaussian Elimination

지금으로부터 약 240여 년 전, 독일 출생의 한 유치원 생은 등차 수열의 합을 정확히 이해하고 공식을 만들어낸다. 그가 바로 Gauss(가우스)라는 저명한 과학자이다. 이 분은 어떤 operation(셈)을 수행하는데 있어, 어떻게 하면 더욱 효율적으로 해결하는지에 대한 생각을 많이 하신 분이며… 그냥 천재다. 그로 인해 물리학, 역학, 미분기하학 등 많은 분야에서 그의 이름을 찾아볼 수 있다.

그럼 1차 연립방정식에서 그의 방법이 어떻게 적용되는지 살펴보자.

다음과 같은 1차 연립방정식이 있다. \(\begin{aligned} \begin{cases} 2u\ +\ v\ +\ w =\ 5\\ 4u\ -\ 6v\ \ \ \ \ \ \ \ = -2\\ -2u\ +\ 7v\ +\ 2w =\ 9 \end{cases} \end{aligned}\) 이를 가우스 소거법을 이용해서 연립방정식을 해결해보자.

하나의 행 방정식을 기준으로 방정식의 변수를 하나씩 제거해 나가는 것이다.

이처럼 맨 마지막 행의 변수를 하나로 만들어 위쪽으로 대입해가며 해를 찾는 과정을 “back substitution”이라고 한다.

주의할 점이 있는데, 기준이 되는 행의 맨 앞의 element를 pivot이라고 한다. 이때 pivot의 해당하는 값이 non-zero가 되어야 한다. 각 행의 pivot element가 non-zero가 될 때, Gaussian Elimination은 unique solution을 구할 수 있다.

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

노란색 형광펜에 해당하는 원소들이 pivot element이고 빨간색 행렬이 의미하는 것은 삼각행렬(Upper triangular), 줄여서 U라고 한다.

Breakdown

만약 운이 나빠서, pivot element에 0이 나타나서 가우스 소거법을 할 수 없는 상황이라고 해보자. 그럴 때는 다음과 같은 방법이 있다.

• when a zero appears in a pivot position
• G.E has to stop
• the order of equation has to be changed

방정식의 행의 순서를 바꾸면 된다는 것.

Ex 2)를 보면 w 값이 다음과 같다. \(\begin{aligned} w = \frac{b-2a} {3} \Leftrightarrow \frac {c-4a} {4}=w \end{aligned}\) a, b, c를 모르는 상황이기 때문에 세 변수에 따라서 solution의 상황이 달라질 것이다. 해가 무수히 많거나, 만약 w가 같지 않다면 세 평면의 방정식이 만나지 않는다 (해가 없다).

이처럼 행렬로써 방정식이나 함수를 표현하면 보다 더 수월하게 unique solution을 찾을 수 있다. 그것을 배우는 학문이 바로 *Linear Algebra이다.