1차 연립방정식과 가우스 소거법(Gauss Elimination)

이번 포스팅에서는 Singular Case에 대해 알아보고 저번 포스팅에서 소개했었던 가우스 소거법의 구체적인 절차(방법)에 대해서 소개하려고 한다. 목차는 다음과 같다.

 

1. Singular Case란?

2. Gauss Elimination(가우스 소거법) 절차

1. Singular Case란?

우선 정의부터 하자면 Singular Case란 Unique한 해를 가지지 않을 때를 말하며 두 가지의 Case가 존재한다.

 

• No solution : 해가 존재하지 않아서 해결책이 없는 경우이다.

• Infinite solution : 해가 무수히 많아서 해결책이 무한한 개수인 경우이다.

다음 그림을 보면서 row form(도형, 직선)일 때와 Column form(벡터)일 때 두 가지 예시를 나누어서 살펴보자.

 

Singular Case란, 해가 없거나 해가 무수히 많을 때를 말한다.

< row form (도형, 직선)일 경우 >

• No solution : 서로 평행할 때

• Infinite solution : 서로 겹칠(Overlap) 때

< Column form (벡터)일 경우 > 

• No solution : 서로 벡터가 평행할 때

• Infinite solution : 같은 평면상의 a라는 벡터를 구할 때

Column form(벡터)일 경우 텍스트상으로 이해가 되지 않는다면 위 필기의 벡터에 관한 그림을 보면서 이해해보자.

 

2. Gauss Elimination(가우스 소거법)

다음은 가우스 소거법에 대한 구체적인 방법이다. 연립방정식이든 행렬이든 어떤 형태로 나타낼 때는 "계수가 0이 아닌 변수를 가장 먼저(왼쪽)에 두고 계산을 해야한다" 는 점이 중요하다. 

 

가우스 소거법의 구체적인 절차

가우스 소거법으로 문제를 해결하기 위해서는 또 하나의 조건이 필요한데, 이른바 'Pivot'이라는 특정 변수(그림 속에서는 u, v, w)의 계수가 non-zero(0이 아닌)이어야 한다는 것이다. 위 그림의 파란색 동그라미로 쳐진 부분을 보면 변수를 순차적으로 u -> v -> w 로 하나씩 소거할 때마다 모든 pivot이 0이 되서는 안된다. 

 

이를 행렬로 표현하면 밑의 그림과 같이 되며, 모든 pivots들이 0이 되지 않아야 하고 대각선의 pivots들 기준으로 왼쪽 아래는 모두 0, 오른쪽 위는 0이 아니어야 한다. 우리는 이러한 행렬형태를 'Upper Triangular 행렬'이라고 부르기도 한다.

 

그렇다면 pivots 중에 하나라도 '0'의 값이 있을 때는 어떻게 할까? 이 때는 가우스 소거법 계산을 멈추고, 연립방정식의 나열 순서를 바꾸어 주어야 한다. 이를 Breakdown이라고 부르기도 하며 pivot을 만들어준다는 의미에서 pivoting이라고도 부른다. 밑의 그림을 보면서 이해해보자.

 

Pivot에 0이 있을 때는 어떻게 해야할까?

 

두 번째 예시로 만약 pivoting이 불가할 경우 에는 어떻게 할까? 밑의 예시문제를 보자.

 

Pivoting이 불가능하면 어떻게 해야할까?

결론적으로 unique한 해를 계산할 수는 없다. 위의 예시문제처럼 w에 관해 두가지의 식 'b-2a/3', 'c-4a/4' 두 개로 나오게 된다. 우리는 여기서 두 가지의 가정을 하고 각각의 가정에 대한 결과를 확인할 수 있다.

 

-  "b-2a/3 = c-4a/4" 라는 가정을 하게 되면, 해가 무수히 많아지게 된다.

-  "b-2a/3 ≠ c-4a/4" 라는 가정을 하게 되면, 해가 존재하지 않게 된다.

 

우리는 현실에서 마주하는 문제들은 보통 unique한 해를 갖는 것이 아닌 해가 무수히 많아지는 경우를 맞닥뜨리게 된다. 이는 우리가 선형대수학을 배움으로써 무수히 많은 해 중 적당한 기준을 설정하고 가장 적합한 해(Optimization)를 찾을 수 있는 것이다.