가우스 소거법(1)

이번 포스트에서는 행렬을 이용하여 선형 연립방정식을 푸는 방법인 "가우스 소거법"에 대해 공부한다.

​

1. 가우스 소거법으로 선형 연립방정식 풀기

저번 포스트에서 선형 연립방정식을 행렬로 표현하는 방법을 알아보았다. 이제 구체적으로 방정식을 풀어 보자. 2차 연립방정식으로 시작한다.

새로운 연립방정식에서 y = 1 이고 이를 첫 번째 방정식에 대입하면 x = 3 이다. 따라서 주어진 연립방정식의 해는 (3, 1)이다.

이 방법은 기존에 우리가 연립방정식을 풀 때 자주 쓰였던 방법이다. 가우스 소거법은 이러한 방법을 체계화한 것이다. 3차 연립방정식을 가우스 소거법으로 풀어 보면:

가우스 소거법은 소거를 통해 연립방정식을 풀기 쉬운 형태로 만든다. 소거법을 적용하고 난 후 새로운 연립방정식의 계수 행렬의 형태, 즉 주대각선 아래가 모두 0이고 주대각선이 0이 아닌 형태를 위삼각 행렬(upper triangle matrix)이라 부르고 이는 방정식의 풀이를 쉽게 한다. 해 벡터 (x, y, z)의 맨 뒤쪽 문자부터 차근차근 찾아간다면 방정식의 해를 찾는 것은 어렵지 않다. 이 방법을 후진대입법(back substitution) 이라고 한다.

​

또한 위삼각 행렬에서 주대각선의 성분들을 피봇(pivot) 이라 칭하는데, 정사각행렬에서 n행의 1, 2, 3... n - 1 번째 성분이 모두 0일때 n번째 성분을 나타낸다.

즉, 가우스 소거법의 목적은 n차 정방 계수행렬을 0이 아닌 n개의 피봇을 가지는 위삼각 행렬로 만드는 것이다. 행렬의 주대각선 아래 성분을 소거하기 위해 적당한 행에 적당한 상수를 곱해서, 다른 행의 성분들을 소거해 나간다. 다음은 가우스 소거법의 일반적인 방법이다. 물론 반드시 아래 순서를 따를 필요는 없다. 굳이 해 벡터의 마지막 성분부터 찾지 않아도 되며(후진대입을 반드시 할 필요는 없다) 소거 또한 다른 행을 먼저 하는 것이 편하다면 그렇게 해도 된다.

 

​

2. 소거법의 실패

위에서 소개한 방법만으로 가우스 소거법을 진행하면 종종 해를 찾지 못할 경우가 생긴다. 이는 방정식의 유일한 해가 존재하지만 일시적으로 실패하는 경우, 해가 존재하지 않거나 무수히 많은 해를 가지는 경우이다. 케이스별로 정리하면

​

case1 - 유일한 해가 존재하지만 후진대입법을 사용할수 없을 때: 행 교환

예를 들어 주어진 방정식이 모든 소거를 완료한 형태라고 하자.

위에서 소개한 방법만으로는 방정식의 해를 구할 수 없다. 첫 번째 피봇이 0이고, 따라서 위삼각 행렬을 만들 수 없고 결론적으로 후진대입법을 사용할 수 없기 때문이다. 이런 경우, 모든 소거를 완료한 후 계수 행렬과 우변 행렬의 행을 적절히 바꾸어 주면 된다. (해 벡터는 바꿀 필요 없다.)

case2 - 비가역 행렬: 해가 존재하지 않거나 무한한 해를 가질 때

방정식의 유일한 해가 존재하지 않는 경우, 계수 행렬은 행 교환 혹은 소거를 통해 위삼각 행렬을 가질 수 없다. 즉 n차 정방행렬에서 n개의 피봇을 찾을 수 없으며 이때 계수 행렬은 비가역이다.

경우에 따라 굳이 소거법을 사용하기보다는 계수 행렬의 행벡터 중 서로 종속인 것을 찾아내어 방정식의 유일한 해가 존재하지 않음을 보일 수도 있다.

여기서 가역 행렬과 비가역 행렬을 구분하는 또 다른 기준을 알 수 있다.

 

 

 

adadadad