가우스 소거법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

가우스 소거법(Gauß消去法, 영어: Gaussian elimination, 약자 GE)은 선형대수학에서 일차연립방정식을 풀기 위한 알고리즘이다. 한 방정식을 첫 변수에 대해 푼 다음, 이 식을 나머지 방정식에 넣어 연립 선형방정식을 푸는 방식이다. 위의 결과는 방정식과 변수의 개수가 원래 연립방정식보다 하나 적은 새로운 연립방정식이 된다. 같은 과정을 2번째 변수에 적용하고, 방정식이 하나만 남을 때까지 다른 변수들에 이 과정을 되풀이한다. 하나 남은 방정식에서는 마지막 변수만 미지변수이다. 이 방정식의 해로 바로 앞에서 얻은 미지수가 2개인 방정식의 해를 구한다. 이 과정은 모든 미지수의 값을 구할 때까지 계속된다.

정의[편집]

어떤 에 대하여, 다음과 같은 꼴의, 개의 미지수에 대한 m개의 방정식으로 구성된 일차연립방정식이 주어졌다고 하자.

여기서

은 주어진 행렬이고,

개의 미지수를 포함하는 열벡터이다. 즉, 이는 풀어서 쓰면 다음과 같다.

보통, 유일한 해를 가진 일차 연립 방정식의 경우 방정식의 수는 미지수의 수와 같으며, 즉 이다. 그러나 해가 유일하지 못한 경우나, 해가 없는 경우, 방정식이 중복되는 경우 등에서는 일 수 있다.

기본 행 연산[편집]

이 경우, 이 연립 방정식에 다음과 같은 세 가지 연산을 가할 수 있다. 이들을 기본 행 연산(基本行演算, 영어: elementary row operation)이라고 한다.

  • (행의 치환) 번째 행과 번째 행을 서로 바꾼다.
  • (행의 상수곱) 번째 행을 0이 아닌 임의의 상수 으로 곱한다.
  • (행의 합) 임의의 상수 에 대하여, 번째 행의 배를 번째 행에 더한다.

사다리꼴 행렬[편집]

가우스 소거법의 기본적인 목표는 행렬을 기본 행 연산을 적용하여 사다리꼴 행렬(사다리꼴行列, 영어: échelon matrix)로 만드는 것이다. 행렬 이 다음 조건을 만족시키면, 사다리꼴 행렬이라고 한다.

  • 만약 이라면, 모든 에 대하여 이다.
  • 이라고 하면, 번째 행의 선행계수(영어: leading coefficient)라고 한다. 만약 라면, 이다.

행렬 이 다음 조건을 만족시키면, 기약행 사다리꼴 행렬(旣約行사다리꼴行列, 영어: reduced-row échelon matrix)이라고 한다.

  • 은 사다리꼴이다.
  • 번째 행의 선행계수라고 하자. 그렇다면 이며, 모든 에 대하여 이다.

즉, 사다리꼴 행렬은 행렬의 원소들이 대략 위에는 사다리꼴, 밑에는 0인 형태의 행렬이다. 기약행 사다리꼴 조건은 사다리꼴 조건보다 더 강한 조건이다.

예를 들어, 다음과 같은 행렬은 사다리꼴 행렬이다.

다음과 같은 행렬은 기약행 사다리꼴 행렬이다.

가우스 소거법 알고리즘[편집]

가우스 소거법 행렬 을 기본 행 연산을 가하여 사다리꼴로 만드는 알고리즘이며, 대략 다음과 같다. 각 행에 대하여, 첫 번째 행부터 각각 사다리꼴로 놓을 수 있다. 즉, 번째 행을 처리한다고 하자.

  1. 우선 선행계수가 번째 열에 위치해 있지만 이라면, 선행계수가 0이지 않게 하기 위해 그 밑에 있는 다른 열과 치환한다.
  2. 그 뒤, 번째 행의 밑에 있는 다른 모든 행의 원소들을 번째 행의 배수를 더해 0으로 만든다.
  3. 만약 기약행 사다리꼴을 원한다면, 다음과 같은 두 단계를 추가로 거친다.
    1. 번째 행 자체를, 로 놓기 위해 상수로 곱한다.
    2. 또한, 번째 행 위에 있는 다른 행들 또한 번째 행의 배수를 더해 0으로 만든다.

이는 의사코드로는 다음과 같다. 의 각 열벡터들을 이라고 쓰자.

for :
(번째 행의 선행계수의 위치. 만약 이러한 이 없다면, 알고리즘을 종료시킨다.)
(이며 인 임의의 행이라고 하자)
(번째 행과 번째 행을 치환)
(*)
for :
(번째 행에 번째 행의 배를 더한다)
(*) for :
(번째 행에 번째 행의 배를 더한다)

의사코드는 행렬을 기약행 사다리꼴로 만든다. 만약 기약행 사다리꼴 대신 그냥 사다리꼴로 족하다면, 앞에 (*)이 붙은 단계들은 생략할 수 있다.

역행렬의 계산[편집]

가우스 소거법을 사용하여 정사각행렬역행렬을 계산할 수 있다. 행렬 의 역행렬을 계산하려면, 단위행렬을 추가하여, 행렬로 만든다.

이 행렬에 기본 행 연산을 가하여

로 만든다면, 행렬 과 같다.

[편집]

해가 유일한 연립 선형 방정식[편집]

다음과 같은 선형 방정식이 주어졌다고 하자.

첫 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본 행 연산을 가한다.

  1. 첫째 식의 -2배를 둘째 식에 더한다
  2. 첫째 식의 1배를 셋째 식에 더한다.

그렇다면 다음과 같다.

두 번째 열을 사다리꼴로 놓기 위해, 다음과 같은 기본 행 연산을 가한다.

  • 둘째 식의 1배를 셋째 식에 더한다. 그러면 다음과 같다.

이제 행렬이 사다리꼴이 되었다. 그렇다면, 이제 미지수들을 가장 밑의 행으로부터 순서대로 대입하여 계산할 수 있다.

해가 유일하지 않거나 없는 연립 선형 방정식[편집]

정칙(Nonsingular) 행렬일 경우의 예

(식 2와 3을 바꾸어 해결한다)

비정칙(Singular) 행렬일 경우의 예

(해가 없는 경우도 있다.)

역행렬의 계산[편집]

다음과 같은 행렬 의 역행렬을 계산한다고 하자.

기본 행 연산을 가하면, 다음과 같다.

따라서 은 다음과 같다.

바깥 고리[편집]