2. 선형 방정식의 소거법 (Elimination Method of Linear Equations)

선형 시스템에서는 다음과 같은 3가지 방법을 통해 방정식을 원래의 식과 동치인 선형 방정식으로 변환할 수 있다.

1. 한 방정식에 0이 아닌 상수를 곱한다.
2. 방정식의 위치를 바꾼다.
3. 한 방정식에 0이 아닌 상수를 곱하여 다른 방정식에 더한다.

이를 활용하여 선형 시스템의 해를 구하는 방법으로 소거법이 있는데, 크게 가우스 소거법과 가우스-조단 소거법이 있다.

둘은 대체로 유사하나 가우스 소거법은 행사다리꼴행렬에서 대입법을 통해 해를 구하고, 가우스-조단 소거법은 기약행사다리꼴행렬을 이용해 해를 구하는 차이가 있다.

가우스 소거법^{Gaussian Elimination}

가우스 소거법은 대각 원소를 기준으로 아래가 모두 0인 행사다리꼴행렬^{Row Echelon Form:REF}을 이용해 연립선형방정식의 해를 구하는 방법이다.

$$ 3x_1 + 2x_2 -x_3 = 5\\
x_1-3x_2+4x_3 = -9\\
2x_1-x_2+x_3 = 2 $$

우선, 위 연립 방정식을 첨가 행렬^{Augmented Matrix}로 바꿔준다.

$$\left[ \begin{matrix} 3 & 2 & -1 \\ 1 & -3 & 4 \\ 2 & -1 & 1 \\ \end{matrix} \left| \, \begin{matrix} 5 \\ -9 \\ 2 \\ \end{matrix} \right. \right]$$

적절한 변환을 통해 맨 위의 식을 $x_1$의 계수가 1이 되도록 해준다. 위 연립 방정식에서는, 식 (2)와 식 (1)의 위치를 바꿔주면 된다.

$$\left[ \begin{matrix} 1 & -3 & 4 \\ 3 & 2 & -1 \\ 2 & -1 & 1 \\ \end{matrix} \left| \, \begin{matrix} -9 \\ 5 \\ 2 \\ \end{matrix} \right. \right]$$

식 (1)을 이용해 식 (2)와 식 (3)의 $x_1$을 소거해준다. (계수를 0으로 만든다.)

$$\left[ \begin{matrix} 1 & -3 & 4 \\ 0 & 11 & -13 \\ 0 & 5 & -7 \\ \end{matrix} \left| \, \begin{matrix} -9 \\ 32 \\ 20 \\ \end{matrix} \right. \right]$$

식 (3)과 식 (2)의 위치를 바꾸고, 식 (2)의 $x_2$의 계수를 1로 맞춰준다.

$$\left[ \begin{matrix} 1 & -3 & 4 \\ 0 & 1 & -\frac{7}{5} \\ 0 & 11 & -13 \\ \end{matrix} \left| \, \begin{matrix} -9 \\ 4 \\ 32 \\ \end{matrix} \right. \right]$$

식 (2)를 활용해 식 (3)의 $x_2$을 소거해주고, $x_3$의 계수를 1로 맞춘다..

$$\left[ \begin{matrix} 1 & -3 & 4 \\ 0 & 1 & -\frac{7}{5} \\ 0 & 0 & 1 \\ \end{matrix} \left| \, \begin{matrix} -9 \\ 4 \\ -5 \\ \end{matrix} \right. \right]$$

이제 행사다리꼴행렬을 얻었다.

이제 $x_3=-5$가 나왔으니, 이를 식 (2)에 대입하여 $x_2$를 구하고, 이를 다시 식(1)에 대입하여 $x_1$을 구할 수 있다.

$$x_2-\frac{7}{5}(-5) = 4 \\
x_2 = 4-7 = -3 $$

$$ x_1 - 3(-3) + 4(-5) = -9 \\
x_1 = -9 -9 +20 = 2 $$

$$ x_1 = 2, x_2 = -3, x_3 = -5 $$

가우스-조단 소거법^{Gauss Jordan Elimination}

가우스 소거법에서 더 나아가, 기약행사다리꼴행렬^{Reduced Row Echelon Form:RREF}을 사용하는 가우스-조단 소거법이 있다. 가우스 소거법의 행사다리꼴행렬에서 이어진다.

$$\left[ \begin{matrix} 1 & -3 & 4 \\ 0 & 1 & -\frac{7}{5} \\ 0 & 0 & 1 \\ \end{matrix} \left| \, \begin{matrix} -9 \\ 4 \\ -5 \\ \end{matrix} \right. \right]$$

식(3)을 이용해, 식 (2)와 식 (1)의 $x_3$을 소거한다.

$$\left[ \begin{matrix} 1 & -3 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \left| \, \begin{matrix} 11 \\ -3 \\ -5 \\ \end{matrix} \right. \right]$$

그 다음, 식 (2)를 이용해 식(1)의 $x_2$를 소거한다.

$$\left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \left| \, \begin{matrix} 2 \\ -3 \\ -5 \\ \end{matrix} \right. \right]$$

기약행사다리꼴행렬을 얻었다. 각 식이 하나의 $x$의 값을 나타내어, 해를 알 수 있다.