[AI] 가우스 소거법 기본

가우스 소거법에서 알아봅시다.

종류

1. forward elimination(전방소거법)

   아래로 내려가면서 값을 0으로 변경해 줍니다.

2. back substitution(후방대입법)

   아래에서 위로 올라가면서 미지수(x) 값들을 대입하면서 계산합니다.

Forward elimination의 역할

• 주어진 선형시스템을 풀기쉬운(보기쉬운) 형태로 바꿔줍니다.(Upper triangular form(상삼각형태))

  [*  *  *] [x1]  [*]
  [0  *  *] [x2]  [*]
  [0  0  *] [x3]    [*]

• 주어진 선형시스템의 rank(랭크)를 알려줍니다.

  의미있는 식(선형독립)의 갯수를 구하는 알고리즘으로 작동할 수 있습니다. (선형독립, 선형종속)

  # 주어진 식
  [1  3] [x1]  [2]
  [-2 1] [x2]  [3]
  ----------------
  # forward eleimination
  [1  3] [x1]  [2]
  [0  1] [x2]  [7]   // rank = 2

  # 주어진 식
  [1  3] [x1]  [2]
  [2  6] [x2]  [4]
  ----------------
  # forward eleimination
  [1  3] [x1]  [2]
  [0  0] [x2]  [0]   // rank = 1

• 선형시스템이 해가 있는지(consistent) 없는지(inconsistent) 알려준다.

  해가 있는 선형시스템(consistent linear system): 해가 무수히 많음.

  # 주어진 식
  [1  3] [x1]  [2]
  [2  6] [x2]  [4]
  ----------------
  # forward eleimination
  [1  3] [x1]  [2]
  [0  0] [x2]  [0]   // rank = 1

  해가 없는 선형시스템(inconsistent linear system)

  # 주어진 식
  [1  3] [x1]  [2]
  [2  6] [x2]  [4]
  ----------------
  # forward eleimination
  [1  3] [x1]  [2]
  [0  0] [x2]  [1]   // 행렬의 rank = 1,  전체 시스템으로 보면 rank = 2

예시

아래와 같은 선형시스템이 주어 졌을 때 가우스 소거법으로 계산을 해보겠습니다.

r1. [1  2  1] [x1]        [1]
r2. [1  2  3]    [x2]    =    [3]
r3. [2  3 -1]    [x3]     [-3]

전방소거법

r1을 기준으로 전방 소거법을 계산해 줍니다. r2`의 첫번째 행을 0으로 만들어 주기 위해선 아래와 같은 식이 필요합니다.

1. r2' 구하기

r2' <- r2 - r1

  r2.  [1  2  3]    [x2]        [3]
- r1.  [1  2  1]  [x1]        [1]
-----------------------------
= r2`. [0  0  2]    [x2]        [2]

r1.  [1  2  1] [x1]      [1]
r2`. [0  0  2] [x2]    = [2]
r3.  [2  3 -1] [x3]     [-3]

이렇게 r2`의 값을 구해줍니다.

2. r3' 구하기

r3' <- r3 - 2r1

  r3.  [2  3 -1] [x3] [-3]
- 2r1. [2  4  2] [x1]    [2]
-----------------------------
= r3`. [0 -1 -3] [x3] [-5]

r1.  [1  2  1] [x1]      [1]
r2`. [0  0  2] [x2]    = [2]
r3`. [0 -1 -3] [x3]  [-5]

3. 보기 쉽게 수정하기

• 가우스 소거법에서 forward로 가려는 곳에 0이 아닌 숫자가 존재하면 행의 순서를 변경해 줍니다.

r1.  [1  2  1] [x1]       [1]
r2`. [0 -1 -3] [x2] = [-5]
r3`. [0  0  2] [x3]       [2]

• 가우스 소거법에서 기준값은 1로 하는것이 좋습니다.

r1.  [1  2  1] [x1]      [1]
r2`. [0  1  3] [x2]   [5]
r3`. [0  0  2] [x3]      [2]

result

따라서 궁극적으로 아래와 같은 값을 구할 수 있습니다.

r1.  [1  2  1] [x1]      [1]
r2`. [0  1  3] [x2]   [5]
r3`. [0  0  1] [x3]      [1]

또한 전부 0인 식이 없기 때문에 rank 가 3이라는 것을 알 수 있습니다.

위의 식에 후방대입법으로 계산을 하여 미지수를 구해 보겠습니다.

후방대입법

r1.  [1  2  1] [x1]      [1]
r2`. [0  1  3] [x2]   [5]
r3`. [0  0  1] [x3]      [1]

1. x3의 값 구하기

r3: 0 + 0 + x3 = 1

r1.  [1  2  1] [x1]      [1]
r2`. [0  1  3] [x2]   [5]
r3`. [0  0  1] [1]      [1]

2. x2의 값 구하기

r2: 0 + x2 + 3 = 5

r1.  [1  2  1] [x1]      [1]
r2`. [0  1  3] [2]  = [5]
r3`. [0  0  1] [1]      [1]

3. x1의 값 구하기

r1: x1 + 4 + 1 = 1

r1.  [1  2  1] [-4]      [1]
r2`. [0  1  3] [2]  = [5]
r3`. [0  0  1] [1]      [1]

result

r1. [1  2  1] [x1]        [1]
r2. [1  2  3]    [x2]    =    [3]
r3. [2  3 -1]    [x3]     [-3]

따라서 주어진 선형시스템의 해는 아래와 같습니다.

x1 = -4
x2 = 2
x3 = 1

기본행연산 (EROs)

소거법에 쓰인 기본행 연산.

• Replacement 치환: rj <- rj - mri

  j행번째 행을 기준행인 i번째 행을 m배하여 빼서 업데이트 한다.

• Interchange 교환: rj <-> ri

  j번재 행과 i번째 행의 위치를 서로 바꾼다.

• Scaling 스케일링: rj <- srj

  j 번째 행을 s배 스케일링 한다.

이렇게 가우스 소거법의 기본을 정리해 보았습니다. 학창시절 조금 더 열심히 공부할껄 그랬습니다. ㅎㅎ

긴 글 읽어주셔서 감사합니다.

References

국민대학교 Mathematic Fundamentals for Artificial Intelligence 강의 중 가우스 소거법을 참고하였습니다.