Gauss Elimination(가우스 소거법)은 선형 연립 방정식을 푸는 데 사용되는 방법 중 하나로, 행렬의 연산을 통해 계수 행렬을 삼각행렬(upper triangular matrix)로 만들어 원하는 해를 구하는 과정이다.
삼각행렬 중 대각선에 위치한 것은 pivot으로 0이 되면 안된다.
uvw로 설명을 하겠다
(1) 2u + v + w = 5
(2) 4u - 6v = -2
(3) -2u + 7v +2w = 9
여기서 가우스 소거법의 첫번째 조건은 변수의 계수가 0이 아닌 것을 첫번째로 소거하는 것이다.
또한, 기준이 되는 첫번째 식은 모든 변수가 존재해야 한다.
(1) 2u + v + w = 5 이것을 기준으로 두자.
기준이 되는 식으로 (2), (3)번 식의 변수를 하나식 소거한다.
(2)의 u를 소거하기 위해서는 (1)에 -2를 곱해야 한다.
(3)의 u를 소거하기 위해서는 그냥 더하면 된다.
(2) = {(2) -2(1)} == -8v -2w = -12
(3) = {(3) + (1)} == 8v +3w = 14
이제 (2)번 식으로 (3)번식의 변수 v를 제거하면 된다.
(2) = {(2) + (3)} == w = 2
이걸 정리하면 다음과 같다.
1)
(1) 2u + v + w = 5
(2) 4u - 6v = -2
(3) -2u + 7v +2w = 9
2)
(1) 2u + v + w = 5
(2) -8v -2w = -12
(3) 8v +3w = 14
3)
(1) 2u + v + w = 5
(2) -8v -2w = -12
(3) w = 2
이렇게 나온 w의 값으로 (2) > (1) 식에 역치환을 하는 방법으로 v, u의 값을 구하면 된다.
이것을 백터로 표현하면 다음과 같다.
| 2 1 1 : 5 |
| 4 -6 0 : -2 |
| -2 7 2 : 9 |
| 2 1 1 : 5 |
| 0 -8 -2 : -12 |
| 0 8 3 : 14 |
| 2 1 1 : 5 |
| 0 -8 -2 : -12 |
| 0 0 1 : 2 |
이렇게 마지막 행렬의 대각선은 pivot으로 존재하고, pivot을 기준으로 위쪽은 모두 채워져서 삼각형의 모양을 하고 있다.
이것을 Upper Triangle이라고 한다.
그런데 pivot이 0인 경우가 있다. 이런 경우 연립 방정식의 순서를 바꿔서 해결하는 경우가 있다.
(1) u + v + w = a
(2) 2u + 2v + 5w = b
(3) 4u + 6v + 8w = c
이 식을 가우스 소거법으로 제거하면 다음과 같이 나오게 된다.
(1) u + v + w = a
(2) 3w = b - 2a
(3) 2v + 4w = c - 4a
이때, 그냥 (2)번 식과 (3)번 식의 순서만 바꿔주면 된다. 이 과정으로 pivot을 만든다는 뜻으로 pivoting이라고 한다.
그런데 연립방정식의 순서를 바꿔도 해결이 안되는 경우가 있다.
(1) u + v + w = a
(2) 2u + 2v + 5w = b
(3) 4u + 4v + 8w = c
이러면 다음과 같이 나온다
(1) u + v + w = a
(2) 3w = b - 2a
(3) 4w = c - 4a
이럴때는 그냥 w를 구하면 된다.
w = (b - 2a) / 3 = (c - 4a) / 4일때 두개가 같으면 해가 무수히 많은 경우고, 두개가 일치하지 않으면 해가 없는 경우다.