[Linear Algebra] Gaussian Elimination(가우스 소거법)

Gaussian Elimination(가우스 소거법)

많이 사용되는 기본적인 파트이므로 꼼꼼히 보자.

사다리꼴 (Echelon Forms)

이전 챕터 예제에서 x, y, z의 solution을 구할 때 위와 같은 형태로 만들어 구했던 것을 기억할 것이다. 이러한 형태를 가지기 위해서는 다음 4가지 성질을 만족해야 한다.

1. 만약 행이 모두 0이 아닌 경우, 그 행에서 첫 번째로 0이 아닌 수는 1이어야 합니다. 이를 선도 1 (leading 1)이라고 부릅니다.
2. 모든 요소가 0인 행이 있으면, 그것들은 행렬의 맨 밑으로 내려가야 한다.
3. 모두 0이 아닌 두 연속된 행에서, 하위 행의 선도 1(leading 1)은 상위 행의 선도 1보다 오른쪽에 있어야 한다.
4. 선도 1이 포함된 각 열은 그 열의 다른 모든 요소가 0이어야 한다.

여기서 1, 2, 3번을 만족한다면 행사다리꼴(Row Echelon Form)이고, 1,2,3,4번 모두를 만족한다면 기약 행사다리꼴(Reduced Row Echelon Form)이 된다.

예시: 기약 행사다리꼴



예시: 기약 행사다리꼴이 아닌 행사다리꼴

참고 | 모든 행렬은 유일한 기약 행사다리꼴을 갖지만, 행사다리꼴은 유일하게 갖지 않습니다. 기본 행연산의 순서가 다르면 다른 행사다리꼴이 나오게 됩니다.

예시: 유일한 해를 갖는 경우

예시: 세 미지수가 존재하는 선형 시스템

(a) : 마지막 행은 떠한 x, y, z에 대해서도 성립하지 않는다.

참고 | 이처럼 0 0 0 ,... , 0, 0, x 같이 마지막만 값이 있는 경우의 행을 peculiar row라고 한다.

(b) : 첨가행렬의 마지막 행이 0x+0y+0z=0으로 생략이 가능합니다. 따라서 두 개의 식으로 표현되는데, 이때 선도 1에 해당하는 변숫값들(여기선 x와 y)은 선도변수(leading variable)이라고 하고, 나머지 변수(여기선 z)들은 자유변수(free variable)이라고 합니다. 여기선 자유변수가 1개 있기 때문에 일반해는 직선의 형태를 가지게 됩니다. (자유변수 z를 매개변수로 취급하여 임의의 값 t로 설정하여 x와 y를 구할 수 있습니다.)

(c) : 첨가행렬 중 0 0 0 0이 2개가 존재하여, x-5y+z=4 식만 남게되는데 이때 선도 1에 해당하는 x를 제외하고는 모두 자유변수가 됩니다. 자유변수가 2개이기 때문에 일반해는 평면의 형태를 가지게 됩니다.

참고 | 일반해(general solution)

선형 시스템이 무수히 많은 해를 가질 때, 매개변수에 숫자를 넣어 해를 얻을 수 있는 매개변수 방정식들의 집합을 그 선형방정식의 일반해(general solution)라고 합니다. 

Elimination Methods(소거법)

가우스-요르단(Gauss-Jordan) 소거법 이라 불리는 방법에 대해 알아본다.

첨가행렬로부터 기약 행사다리꼴을 구하면 쉽게 해를 구할 수 있는 것을 확인했다. 이제 임의의 행렬을 기약 행사다리꼴로 만들기 위한 소거법(elimination)을 단계별로 살펴보자

1. 0이 아닌 원소가 있는 가장 왼쪽의 열에서 계산을 시작

2. 필요하다면, 1단계에서 찾은 열의 가장 윗수가 영이 아니도록 첫째 행과 다른 행을 바꾼다.

3. 1단계에서 찾은 열의 가장 윗수가 a이면 1/a를 곱하여 1로 바꾼다.

4. 1행에 적당한 수를 곱하여 아래 행들에게 더하여 선도 1의 아래 원소들이 모두 0이 되도록 한다.

5. 행렬의 1행은 두고 나머지 부분행렬에 대해서 다시 1단계부터 진행하여 행사다리 꼴이 될 때까지 반복합니다.

6. 추가적으로 기약 행사다리꼴이 되기 위해서는 마지막 0이 아닌 행부터 시작하여 위로 올라가면서 선도 1의 위를 0으로 만들기 위한 적당한 수를 곱하여 위의 행에 더해준다.

이렇게 기약 행사다리꼴로 만드는 알고리즘을 가우스-요르단 소거법(= 가우스 조던 소거법, Gauss-Jordan elimination)이라고 한다.

선도 1 아랫부분을 모두 0으로 하는 것을 전진 단계(forward phase,1~5단계), 선도 1 윗부분을 모두 0으로 하는 것을 후진 단계(backward phase, 6단계)라고 합니다. 만약 forward 단계만 진행한다면 기약 행사다리꼴이 아닌 행사다리꼴이 만들어지는데 이렇게 forward 단계만 진행하면 가우스 요르단 소거법이 아닌 가우스 소거법(Gaussian elimination)이라고 합니다.

예시: 가우스-요르단 소거법

Homogeneous Linear Systems(동차 선형 시스템)

상수항이 모두 0이면 이를 Homogeneous라고 부른다.

이럴 경우는 모든 연립방정식이 x1=0, x2=0, ... , xn=0을 해로 갖는다. 이 해를 자명해(trivial solution)라고 한다.

Homogeneous System은 늘 자명해를 갖기 때문에 해에 대해서는 '자명해만 있다'  또는 '자명해 외에 무수히 많은 해가 있다(비자명해(nontrivial solution)가 존재하는 경우)' 이 두 가지 가능성밖에 없다. (즉, 해가 없는 경우가 없음. peculiar row가 존재할 가능성이 없기 때문)

예시: 미지수가 두 개인 경우

Homogeneous System이 항상 비자명해를 갖는 경우가 있는데 이는 방정식보다 미지수의 개수가 더 많은 경우입니다.

예시: 항상 비자명해를 갖는 경우

미지수는 6개인데, 방정식이 4개이다. 위 동차 방정식을 기약 행사다리꼴로 나타내면?

선도 변수(leading variable)은 x1, x3, x6이며 나머지는 자유 변수가 된다.
최종적으로 선도 변수에 대해 식을 정리하면 다음과 같다.

x2, x4, x5에 따라 해가 달라지기 때문에 이럴 경우는 항상 비자명해를 가지게 된다. 즉, 동차 방정식인데 선도변수에 의해 정리했을 경우 자유변수가 존재한다면 항상 비자명해가 존재하게 됩니다. (자명해는 x2 = x4 = x5 = 0일 때이고, 이외의 모든 경우는 비자명해입니다.)

Free Variables in Homogeneous Linear Systems (동차 선형 시스템에서 자유 변수)

위 예시에서 우리는 두 가지 중요한 포인트를 확인할 수 있다.

1. 기본 행 연산은 행렬에서 0으로 구성된 열을 변경하지 않으므로 동차 선형 시스템의 기약 행사다리꼴의 마지막 열이 0이다. 이는 기약 행사다리꼴 형태에 해당하는 선형 시스템이 원래 시스템과 마찬가지로 동차임을 의미한다.
   
2. 우리는 동차 선형 시스템에서 0으로 구성된 행을 무시했다. 따라서 동차 선형 시스템의 기약 행사다리꼴에 0으로 구성된 행이 있는지 여부에 따라, 이 기약 행사다리꼴에 해당하는 선형 시스템은 원래 시스템과 동일한 수의 방정식을 가지거나 더 적을 수 있습니다.

이제 일반적인 동차 선형 시스템이 n개의 미지수를 가지고 있다고 가정하고, 그 기약 행사다리꼴 형태가 r개의 0이 아닌 행을 가지고 있다고 가정해 봅시다. 각 0이 아닌 행에는 선도 1이 포함되므로, 각 선도 1은 선도 변수에 해당합니다. 따라서, 축소 행 사다리꼴 형태의 확대 행렬에 해당하는 동차 시스템은 r개의 선도 변수를 가지며, n - r 개의 자유 변수를 가져야 합니다. 따라서 이 시스템은 다음과 같은 형태입니다.

(Σ()는 자유 변수를 포함하는 합)

정리1: 동차 시스템을 위한 자유 변수 정리
동차 방정식이 n개의 미지수를 갖고, 그것의 첨가행렬의 기약 행사다리꼴이 r개의 0이 아닌 행을 갖는다면, 이 연립방정식은 n-r개의 자유변수를 갖게 된다. 즉, n-r>=1일 경우 비자명해가 반드시 존재한다.
(동차 연립일차방정식에서 n-r>=1 일 경우 무수히 많은 해를 갖는다.)

정리2
방정식보다 더 많은 미지수를 가진 동차 선형 시스템은 무한히 많은 해를 갖는다.

가우스 소거법(Gaussian Elimination)과 역대입법(back-substitution)

지금까지 봤던 예시처럼 작은 선형 시스템은 가우스-요르단 소거법을 이용해 손으로 풀 수 있지만, 큰 선형 시스템의 경우에는 가우스 소거법으로 행사다리꼴을 만든 뒤에 역대입법(back-substitution)이라 불리는 과정을 사용하는 것이 낫다.

예시: 역대입법을 이용하여 방정식 풀기
가우스 소거법을 이용해 첨가행렬의 행사라디꼴을 구한다.

이제 역대입법을 적용해보자.

1. 선도변수에 대하여 방정식을 풉니다.

2. 밑의 방정식부터 시작하여, 연속적으로 각 방정식을 위의 방정식에 대입하여 위로 갑니다.
   • 먼저 x6을 두 번째 방정식에 대입합니다. (첫 번째 방정식은 x6에 관한 값이 없으므로 pass 된 것)
     
   • 다음으로 두번째 방정식을 첫 번째 방정식에 대입하여 다음값을 얻습니다.
     
3. 남은 자유변수에(만약 존재한다면) 임의의 값을 대입하면 일반해가 구해집니다

가우스 소거법 + 역대입법 은 가우스-요르단 소거법과 비슷하지만, backward 단계가 없고 밑에 방정식부터 위의 방정식들에 대입하는 방식으로 바꾼 방법으로 볼 수 있다.

예제: 해의 존재성과 유일성
행렬 (a), (b), (c)가 존재한다.

Solution (a)
마지막 행 0x1 + 0x2 + 0x3 + 0x4 = 1에서 시스템이 inconsistent 함을 확인할 수 있다.

Solution (b)
마지막 행 0x1 + 0x2 + 0x3 + 0x4 = 0은 해 집합에 영향을 미치지 않는다. 그 위에 있는 3개 행을 보면 x1, x2, x3는 선도 변수, x4는 자유 변수이다/ 따라서 시스템은 무한히 많은 해를 가져야 한다.

Solution (c)
마지막 행 x4 = 0에서 x4의 값을 얻고 이를 3 번째 행에 대입하면 x3 = 9를 얻게 된다. 각 행에서 얻은 값을 계속 해서 위 행에 대입하면 x1의 고유한 값ㅇ을 얻을 수 있다. 따라서 이 시스템은 유일한 해를 갖는다.

사다리꼴 형태에 대한 몇 가지 사실

사실 위에서 이미 한 번 정리한 내용이긴 한데 책에서 또 나와서 책 내용을 한 번 더 정리해봤습니다.

행 사다리꼴 형태와 기약 행 사다리꼴 형태에 대해 알아야 할 세 가지 중요한 사실이 있습니다. 다만, 여기서는 증명하지 않습니다:

1. 모든 행렬은 기약 축소된 행 사다리꼴 형태를 갖는다. 즉, 가우스-요르단 소거법이나 다른 일련의 기본 행 연산을 사용하더라도 동일한 기약 행 사다리꼴 형태가 결과로 나온다.
2. 행 사다리꼴 형태는 고유하지 않다; 즉, 기본 행 연산의 다른 순서는 다른 행 사다리꼴 형태로 이어질 수 있다.
3. 행 사다리꼴 형태가 고유하지 않더라도, 기약 행사다리꼴 형태와 모든 행렬의 행 사다리꼴 형태는 동일한 수의 영(0) 행을 가지며, 선도 1은 항상 동일한 위치에 나타난다. 이를 A의 피벗 위치(pivot positions)라 하며, A의 행렬에서 선도 1을 포함하는 열을 피벗 열(pivot columns)이라 하고, 선행 1을 포함하는 행을 피벗 행(pivot rows)이라 한다. 피벗 위치의 비영(0이 아닌) 것들의 엔트리를 A의 피벗(pivot)이라 한다.

선도 1이 [1행 1열], [2행 3열], [3행 5열]에 나타나고, 이러한 위치들이 A의 피벗 위치이다. 피벗 위치에 있는 0이 아닌 숫자들이 A의 피벗이다.

반올림 오차와 불안정성

수학적 이론과 실제 구현 사이에는 차이가 있는 경우가 많습니다. 가우스-요르단 소거법과 가우스 소거법이 좋은 예입니다. 문제는 컴퓨터가 일반적으로 수를 근사적으로 처리함으로써 반올림 오차를 유발한다는 것입니다. 따라서 주의하지 않으면 연속 계산이 답을 쓸모없게 만들 정도로 저하될 수 있습니다. 이런 경우에 해당하는 알고리즘을 불안정하다고 합니다. 반올림 오차와 불안정성을 최소화하기 위한 다양한 기법이 있습니다. 예를 들어, 큰 선형 시스템의 경우 가우스-요르단 소거법이 가우스 소거법보다 약 50% 더 많은 연산을 포함하므로, 대부분의 컴퓨터 알고리즘은 후자 방법에 기반합니다. 이 문제 중 일부는 9장에서 다룰 예정입니다.

정리