가우스 소거법

가우스 소거법은 크게 두 단계로 나뉘게 된다.
첫번째는 forward elimination, 두번째는 back-subtitution인데, 두번째의 경우 초등교과 수준의 연산이 이루어지기 때문에, 첫번째를 집중적으로 봐야한다.

forward elimination

정의는 주어진 선형시스템을 아래로 갈 수록 더 단순한 형태의 선형 방정식을 가지도록 변형하는 것이다.

즉 주어진 선형 시스템을 대수로 표현하였을 때, 아래로 갈수록 선형 행렬이 "Upper triangular form" 으로 바뀌는 것이다.

Upper Triangular form 이란?

다음과 같은 방식으로 점점 A 즉 coefficent(계수)를 아래로 갈 수 록 하나씩 제거하여 0으로 만드는 것이다.

가우스 소거법은 첫번째 방정식을 기준으로 먼저 아래의 첫번째 column의 값들을 1로 만드려고 하고, 이후 방정식을 바꾸거나 해서 두번째 값이 있는 방정식으로 바꾸어, 다음 기준으로 만들고 하는 과정을 반복한다.

이렇게 바꾸는 연산은 총 3가지이다.

• replacement
• interchange
• scaling

replacement는 rj = rj - m*ri 형식 처럼 기준 값을 배수로 취하여 항을 소거하는 형식이고,

interchange는 삼각형을 만들기 위해 서로의 row(식)을 바꾸는 것을 의미한다.

scaling은 자신을 기준에 맞게 배수를 취하여 바꾸는 것을 의미한다. rj = mrj

forward의 장점

장점은 정리하면 3가지로 나뉜다.

• 가장 풀기 쉬운 "Upper Triangular form"으로 만들어 준다는 점.
• 주어진 선형시스템의 rank(얼마나 복잡한지 안한지)를 알려준다.
• 선형시스템에 해가 있는지 없는지 알려준다.

첫번째는 위에서 언급했지만 두번째 같은 경우 예시를 들어보겠다.

[[1,3],
 [2,1]] * [x1, x2] = [2, 3] # rank = 2
 
 [[1,3],
 [2,6]] * [x1, x2] = [2, 4] # rank = 1

즉 의미있는 식의 개수를 말한다. 의미있는 식이 많을 수록 해의 값을 구하기 쉬울 것이다.

세번째의 예시는 다음과 같다.

[[1,3],
 [0,0]] * [x1, x2] = [2, 0] # consistent
 
 [[1,3],
 [0,0]] * [x1, x2] = [2, 1] # inconsistent

즉, 해당 값이 분명 말이 안되는 값임에도 식이 나와있다면 이는 해가 없는(inconsistent) 값이다. 이를 판별해 주는 기능도 한다.

LU 분해에 대해서는 다음에 정리하겠다.