Gauss-Jordan Elimination

선형 시스템을 푸는 3가지 대수적 연산(algebraic operations)은 아래와 같다.

 

1) 0이 아닌 상수를 행(row)에 곱한다.

2) 두 개의 행의 위치를 교환한다.

3) 하나의 행에 상수배를 곱한 것을 다른 행에 더한다.

 

위의 3가지 연산을 elementary row operations(기본 행 연산)이라고 부른다. 아래 예시를 살펴보며 제대로 이해해보자.

 

우선 아래와 같은 선형 시스템이 있다.

 

$x + y + 2z = 9$

$2x + 4y - 3z = 1$

$3x + 6y - 5z = 0$

 

이를 증강행렬로 표현하면 아래와 같다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
2 & 4 & -3 & 1 \\
3 & 6 & -5 & 0 \\
\end{bmatrix}

이제 여기에 우리가 중학교 때부터 지겹게 해왔던 연립방정식을 푸는 것과 동일한 방식으로 각각의 $x, y, z$를 구할 것이다.

 

1. 우선 첫 번째 행에 -2를 곱한 값을 두 번째 행에 더해준다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
0 & 2 & -7 & -17 \\
3 & 6 & -5 & 0 \\
\end{bmatrix}

2. 마찬가지로 첫 번째 행에 -3을 곱한 값을 3번째 행에 더해준다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
0 & 2 & -7 & -17 \\
0 & 3 & -11 & -27 \\
\end{bmatrix}

3. 다음으로 두 번째 행에 $\frac{1}{2}$을 곱해준다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
0 & 1 & -\frac{7}{2} & -\frac{17}{2} \\
0 & 3 & -11 & -27 \\
\end{bmatrix}

4. 두 번째 행에 -3을 곱한 값을 세 번째 행에 더해준다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
0 & 1 & -\frac{7}{2} & -\frac{17}{2} \\
0 & 0 & -\frac{1}{2} & -\frac{3}{2} \\
\end{bmatrix}

5. 세 번째 행에 -2를 곱해준다.

\begin{bmatrix}
1 & 1 & 2 & 9 \\
0 & 1 & -\frac{7}{2} & -\frac{17}{2} \\
0 & 0 & 1 & 3 \\
\end{bmatrix}

6. 두 번째 행에 -1을 곱한 값을 첫번째 행에 더한다.

\begin{bmatrix}
1 & 0 & \frac{11}{2} & \frac{35}{2} \\
0 & 1 & -\frac{7}{2} & -\frac{17}{2} \\
0 & 0 & 1 & 3 \\
\end{bmatrix}

7. 마지막으로 세번째 행에 $-\frac{11}{2}$를 곱한 값을 첫 번째 행에 더하고, $-\frac{7}{2}$를 곱한 값을 두 번째 행에 더한다.

\begin{bmatrix}
1 & 0 & 0 & 1 \\
0 & 1 & 0 & 2 \\
0 & 0 & 1 & 3 \\
\end{bmatrix}

 

이렇게 하여 $x = 1, y = 2, z = 3$의 unique solution을 얻을 수 있었다. 특히 아래 1-3을 만족하는 행렬을 row echelon form(ref), 1-4를 모두 만족하는 행렬을 reduced row echelon form(rref)이라고 한다.

 

1. 어떤 행의 모든 요소(entries)가 0이 아니면(not all-zero), 그 때 첫 번째 nonzero 숫자는 1이다. 이를 leading 1이라고 한다.

2. 행의 모든 요소가 0인 행들은 행렬의 가장 아래에 위치한다.

3. not all-zero인 두 연속적인 행이 있을 때, leading 1의 위치는 위의 행이 아래의 행보다 먼저(왼쪽에) 위치한다.

4. leading 1을 포함하는 각각의 열(column)은 leading 1을 제외한 모든 요소가 0이다.

 

위와 같이 증강 행렬에 3가지 기본 행 연산을 통하여 ref를 얻는 과정을 가우스 소거법(Gaussian Elimination)이라고 하며, ref에서 각 행의 leading 1의 위쪽을 0으로 만들어 rref까지 얻으면 이를 가우스-조던 소거법(Gauss-Jordan Elimination)이라고 한다.

 

가우스-조던 소거법의 일반화된 방법은 아래와 같다.

 

1. Not all-zero인 leftmost column(0이 아닌 값이 존재하는 행들 중 가장 왼쪽에 entry가 위치하는 행)의 위치를 찾는다.

2. 필요하다면, 행렬의 가장 위쪽 행(top row)과 1에서 찾은 leftmost column의 위치를 교환한다.

3. 가장 위쪽 행의 leftmost column의 entry의 값이 $a$라면, leading 1으로 만들어주기 위해 $\frac{1}{a}$로 해당 행을 나누어준다.

4. top row에 적절한 값을 곱한 값을 다른 행에 더하여 leading 1의 아래의 entries를 0으로 만든다.

5. 이제 top row를 제외한 부분행렬(submatrix)에 1-4의 과정을 ref가 될 때 까지 반복한다.

6. last nonzero row의 leading 1의 위쪽에 있는 entries의 값을 0으로 만들기 위해 적절한 값을 곱하여 더해준다. 이렇게 하면 rref가 만들어 진다.

 

우리가 어떤 증강 행렬을 rref로 변형한다면, 한 눈에 해당 선형 시스템의 해를 구하거나 해가 없다는 것을 알 수 있기 때문에 rref로 변환하는 과정이 필요하다. 

 

References

1. Elementary linear algebra 12th editon, Howard Anton, Anton Kaul