Lecture Notes - Gauss Elimination

가우스 소거법

선형시스템의 해를 구하는 방법

---

가장 단순한 형태의 선형시스템은 아래와 같다. 이 선형시스템의 해는 무엇인가?

$$ ax = b $$ 

해가 하나인 경우 

$$ 3x=6 $$

 

해가 없는 경우 

$$ 0x =y $$

 

해가 여러개인 경우

$$ 0x = 0 $$

 

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

 

 

$$ Ax = b $$

 

가우스 소거법 (Gauss elimination)

• 가우스 소거법은 임의의 m x n 선형시스템의 해를 구하는 대표적인 방법이다.
• 아래 두단계로 수행된다.

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

 

가우스 소거법 실제로 해보기

 

 $$ \begin{bmatrix}
        1 & 2 & 1\\
        1 & 2 & 3\\
        2 & 3 & -1\\
       \end{bmatrix}
       \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} =
       \begin{bmatrix}1 \\3 \\-3 \end{bmatrix} $$

 

1. 1행 1열을 기준으로 잡기
2. r2 ← r2 - r1
3. r3 ← r3 - 2r1
4. 2행 2열을 기준으로 잡기
5. r2 ↔ r3
6. r2 ← −r2
7. 3행 3열을 기준(pivot)으로 잡기
8. r3 ← 1/2 r3

 

가우스 소거법에서 전방소거법은
주어진 선형 시스템의 rank를 알려주고, 선형시스템이 해가 있는지 아니면 없는지 알려준다.