가우스 소거법

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

선형대수학에서, 가우스 소거법(Gauß消去法, 영어: Gaussian elimination)은 연립일차방정식을 풀이하는 알고리즘이다. 풀이 과정에서, 일부 미지수가 차츰 소거되어 결국 남은 미지수에 대한 선형 결합으로 표현되면서 풀이가 완성된다. 가우스 소거법은 보통 행렬을 사용하며, 계수 행렬을 그와 풀이가 같은 더 간단한 행렬로 변환하여 풀이를 완성한다. 가우스 소거법은 행렬식역행렬의 계산에도 응용된다.

정의[편집]

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

여기서

은 주어진 행렬이고,

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

기본행연산[편집]

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

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

일차연립방정식의 풀이[편집]

행렬 에 대하여, 이라고 하면, 번째 행의 선행 계수(先行係數, 영어: leading coefficient)라고 한다. 선행 계수는 존재하지 않을 수 있다.

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

  • 만약 이라면, 모든 에 대하여 이다.
  • 만약 이며 가 존재한다면, 이다.

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

  • 은 행사다리꼴행렬이다.
  • 가 존재한다면, 이며, 모든 에 대하여 이다.

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

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

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

가우스 소거법[편집]

가우스 소거법 행렬 을 기본행연산을 가하여 행사다리꼴행렬로 만드는 알고리즘이며, 다음과 같다. 먼저 첫번째 행을 다음과 같이 처리한다.

  1. 선행 계수가 위치하는 가장 작은 열수 을 찾는다.
  2. 이라면, 첫번째 행을 인 어떤 번째 행과 치환한다.
  3. 모든 번째 행에 첫번째 행의 배를 더해, 밑의 항들을 0으로 만든다.

그 뒤, 두번째 행을 다음과 같이 처리한다.

  1. 어떤 번째 행의 선행 계수가 위치하는 가장 작은 열수 을 찾는다.
  2. 이라면, 두번째 행을 인 어떤 번째 행과 치환한다.
  3. 모든 번째 행에 두번째 행의 배를 더해, 밑의 항들을 0으로 만든다.

일반적으로, 번째 행은 다음과 같이 처리한다.

  1. 어떤 번째 행의 선행 계수가 위치하는 가장 작은 열수 을 찾는다.
  2. 이라면, 번째 행을 인 어떤 번째 행과 치환한다.
  3. 모든 번째 행에 번째 행의 배를 더해, 밑의 항들을 0으로 만든다.

만약 항상 를 찾을 수 있다면, 모든 번째 행에 대하여 순차적으로 위와 같이 처리한다. 만약 어떤 가 존재하지 않는다면, 거기서 멈춘다.

기약행사다리꼴행렬을 원한다면, 찾았던 모든 에 대하여 순차적으로 다음과 같은 단계를 추가로 거친다.

  1. 번째 행에 를 곱해, 를 1로 만든다.
  2. 모든 번째 행에 번째 행의 배를 더해, 위의 항들을 0으로 만든다.

성질[편집]

기본행연산[편집]

세 가지 기본행연산은 모두 가역 연산이다.

  • 행의 치환의 역연산은, 자기 자신이다.
  • 행의 상수곱의 역연산은, 그 행에 그 상수의 역수를 곱하는 것이다.
  • 어떤 행에 다른 행의 배수를 더하는 것의 역연산은, 더하는 대신 빼는 것이다.

두 연립일차방정식의 첨가 행렬이 하나에 기본행연산을 가하여 다른 하나를 얻을 수 있다면, 행동치라라고 한다. 첨가 행렬이 행동치라면, 연립방정식의 풀이는 서로 같다.

기본 행렬단위 행렬에 기본행연산을 한 번 가하여 얻는 행렬이다. 이에 따라, 세 가지 기본행연산은 기본 행렬 곱셈과 대응한다.

행사다리꼴행렬[편집]

가우스 소거법 알고리즘에서 알 수 있듯, 모든 연립일차방정식의 첨가 행렬은 그와 같은 해를 갖는 행사다리꼴행렬 및 기약행사다리꼴행렬로 변환할 수 있다. 따라서, 연립일차방정식의 풀이는 행사다리꼴행렬 및 기약행사다리꼴에 대한 풀이로 귀결된다.

행사다리꼴행렬 에 대한 연립일차방정식 에 대하여, 다음 두 조건이 서로 동치이다.

  • 해가 존재한다.
  • 선행 계수가 없으나, "상수항"(즉 열의 항)이 0이 아닌 행이 존재하지 않는다.

또한, 에 대하여, 다음 세 조건이 서로 동치이다.

  • 해가 유일하다.
  • "0행"(즉 선행 계수가 없는 행)이 아닌 행이 정확히 개이다.

행렬식의 계산[편집]

가우스 소거법을 사용하여 정사각 행렬행렬식을 계산할 수 있다. 이는 행렬 에 대하여, 다음 사실들이 성립하기 때문이다.

  • 기본행연산을 가하면, 행렬식은 "상수배" 변화한다. 즉,
    • 행을 치환하면, 행렬식은 -1배가 된다.
    • 행에 상수곱을 하면, 행렬식은 그 상수의 역수배가 된다.
    • 어떤 행에 다른 어떤 행의 상수배를 더하면, 행렬식은 변하지 않는다.
  • 가우스 소거법을 사용하여, 을 행사다리꼴행렬로 변환할 수 있다. 특히, 정사각행렬이므로, 이는 0행(즉 모든 항이 0인 행)을 갖거나, 상삼각 행렬이다.
  • 0행을 갖는 정사각행렬의 행렬식은 0이다.
  • 상삼각 행렬의 행렬식은 모든 대각항의 곱이다.

역행렬의 계산[편집]

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

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

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

[편집]

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

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

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

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

그렇다면 다음과 같다.

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

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

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

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

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

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

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

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

역행렬의 계산[편집]

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

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

따라서 은 다음과 같다.

바깥 고리[편집]