[04/26] 인공지능 수학 - 가우스 소거법

아주 간단한 형태의 선형시스템의 독특한 경우

 

ex 1) 해가 없는 경우 (no solution)

 

0x = 6

 

ex 2) 해가 여러 개인 경우 (infinitely many solutions)

 

0x = 0

 

• a = 0이면 특이하다.
  • ax = b의 해가 곧장 나오지 않는다.
  • a의 역수(inverse)가 존재하지 않는 경우, a가 특이(singular)하다고 한다.
• 해가 있으면 선형시스템이 consistent하다고 한다.
• 해가 없으면 선형시스템이 inconsistent하다고 한다.

 

선형 시스템 Ax = b의 경우

 

ex 1) 해가 하나인 경우 (unique solution)

 

x + 3y = 2

-2x + y = 3

 

=> x = -1, y = 1

 

ex 2) 해가 없는 경우 (no solution)

 

x + 3y = 2

2x + 6y = 5

 

=> 미지수 계수 행렬의 역행렬이 존재하지 않는 singular 행렬이다.

 

ex 3) 해가 여러 개인 경우 (infinitely solutions)

 

x + 3y = 2

2x + 6y = 4

 

=> 위의 케이스처럼 역행렬이 존재하지 않는 singular 행렬이다.

 

• A의 역행렬(inverse matrix)이 존재하지 않는 경우, A가 특이(singualr)하다고 하다.
• 해가 있으면 선형시스템이 consistent하다고 한다.
• 해가 없으면 선형시스템이 inconsistent하다고 한다.

---

가우스 소거법

 

Gauss elimination이란? 임의의 m x n 선형시스템의 해를 구하는 가장 대표적 방법

 

가우스 소거법의 두 단계

 

1.  Forward elimination(전방소거법) : 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다.
2. back-substitution(후방대입법) : 아래에서부터 위로 미지술르 실제값으로 대체한다.

 

ex )

 

주어진 선형시스템

 

| 1 2  1 | | x |    |  1 |

| 1 2  3 | | y | = |  3 |

| 2 3 -1 | | z |    | -3 |

 

x + 2y + z = 1 ---- E₁

x + 2y + 3z = 3 ---- E₂

2x + 3y -z = -3 ---- E₃

 

Forward Elimination(전방소거법) 수행 후

 

| 1 2 1 | | x |    | 1 |

| 0 1 3 | | y | = | 5 |

| 0 0 1 | | z |    | 1 |

 

E₂ <- E₂ - E₁

 

  x + 2y + z = 1

- x + 2y + 3z = 3

=> 2z = 2

 

E₃ <- E₃ - 2E₁

 

  2x + 3y - z = -3

- 2x + 4y + 2z = 6

=> - y - 3z = -5

 

E₂ <-> E₃

 

x + 2y + z = 1 ---- E₁

    - y - 3z = -5 ---- E₂

            2z = 2 ---- E₃

 

E₂ <- -E₂

 

y + 3z = 5 

 

E₃ <- 1/2 E₃

 

z = 1

 

Forward elimination 정리하면...

 

• 1행 1열을 기준(pivot)으로 잡기
• r₂ <- r₂ - r₁
• r₃ <- r₃ - 2r₁
• 2행 2열을 기준(pivot)으로 잡기
• r₂ <-> r₃
• r₂ <-  - r₂
• 3행 3열 기준(pivot)으로 잡기
• r₃ <- 1/2 r₃

 

 

Back-substitution(후방대치법) 수행 후

 

1)

z = 1

 

2)

y + 3z = 5

y + 3 = 5

∴ y = 2

 

3) 

x + 2y + z = 1

x + 4 + 1 = 1

∴ x = -4

 

말그대로 뒤에서부터 대치해가며 미지수의 값을 풀어가는 굉장히 쉬운 방법

---

소거법에 쓰이는 Elementary Row Operations (EROs, 기본행연산)

 

• Replacement(치환)
  • ex) r₂ <- r₂ - mr₁
  • 1번째 행을 기준행인 1번째 행을 m배해서 빼서 업데이트한다.
• Interchange(교환)
  • ex) r₂ <-> r₃
  • 2번째 행과 3번째 행의 위치를 서로 바꾼다.
• Scaling(스케일링)
  • ex) r₂ <- sr₂
  • 2번째 행을 s배 스케일링한다. 

---

★ 전방소거법의 가치

 

• 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변행해준다.
  • Upper triangular form(상삼각형태)
  • | * * * | | x |    | * |
    | 0 * * | | y | = | * |
    | 0 0 * | | z |   | * |
• 주어진 선형시스템의 rank(랭크)를 알려준다.
  • 의미 있는 식의 갯수를 rank라고 생각하면 된다.
• 선형시스템이 해가 있는지(consistent) 아니면 해가 없는지(inconsistent) 알려준다.