가우스-조르당 소거법(Gauss-Jordan Elimination)

비동차 연립방정식 $A\mathbf{x}=\mathbf{b}$ 의 해는 계수 행렬 $A$의 특성에 의해 좌지우지 됩니다. 행렬 $A$의 행과 열의 개수의 대소관계라던지, $A$의 랭크 혹은 가진 $\mathrm{pivots}$ 의 개수, 정사각행렬이라면 가역성 여부 등이 해의 운명을 결정하게 됩니다. 이러한 비동차 연립방정식의 이론적 측면을 총정리하기 전에, 일단 방정식 자체를 '푸는 법'을 하나 소개하려고 합니다. 그것은 여태까지 배웠던 개념들과 소거법을 숙지하면 깨우칠 수 있는 방법입니다.

---

1. 가우스 소거법과 가우스-조르당 소거법

 

1) 뜻

 

연립방정식 $A\mathbf{x}=\mathbf{b}$ 를 첨가행렬 $\begin{bmatrix}
A \mid \mathbf{b}
\end{bmatrix}$ 로 표현했을 때, 이것을 행 사다리꼴로 변형하여 해를 구하는 방법을 '가우스 소거법(Gaussian Elimination)'이라 한다. 반면 더 나아가 첨가행렬을 기약 행 사다리꼴로 변형하여 해를 구하는 방법은 '가우스-조르당 소거법(Gauss-Jordan Elimination)'이라고 한다.

 

가우스는 워낙 희대의 천재라 유명한데, 조르당 역시 심심치 않게 여러 정리에 이름이 등장합니다. 다만, 동명이인이 있습니다. 이 정리와 관련된 인물은 독일의 빌헬름 조르당(Wilhelm Jordan)으로, 복소해석학의 조르당 보조정리(Jordan's lemma)과 군론에 큰 영향을 미친 프랑스의 카미유 조르당(Camille Jordan)과는 동명이인입니다. 앞글자만 봐도 국적을 알 수 있을 법 하군요. 조르당은 '조던' 또는 '요르당'이라고 부르기도 합니다.

 

일단 가우스 소거법과 가우스-조르당 소거법의 차이를 확실히 알아야 합니다. 가우스 소거법은 행 사다리꼴로만 변형하는데, 그러면 행렬의 형태가 상삼각행렬(Upper triangle matirx)이 됩니다. 그 다음 부터는 맨 아래 행부터 하나씩 미지수를 구한 뒤 위 행에 대입해서 푸는 방법으로 일반해를 다 구할 수 있게 됩니다. 책에 따라 이걸 'back substitution'이라 부를 때가 있습니다. 번역하기 곤란한 단어라 그대로 넣었습니다.

 

반면, 조르당은 이에 더 나아가 $\mathrm{pivots}$ 이 모두 1인 상태에서 이 $\mathrm{pivots}$들을 가진 열에서 $\mathrm{pivots}$을 제외한 성분이 모두 0이 될 때까지 기본 행 연산을 수행하여 기약 행 사다리꼴을 만들었습니다. 그렇게 되면, 첨가행렬은 $A$가 가역일 때 $\begin{bmatrix} 
A \mid I_n
\end{bmatrix}$ 에서 $\begin{bmatrix} 
I_n \mid A
\end{bmatrix}$ 으로 바뀐다는 사실을 저번 포스팅에서 소개했었습니다. 그러면 $A$의 역행렬도 구하고, 바(bar)뒤의 $\mathbf{b}$ 가 연립방정식의 해에 해당되는 열벡터로 바뀌게 됩니다.

 

 두 방법 중 무엇이 빠르고 효율적인지에 대한 질문의 답은 하나로 내리기가 곤란합니다. 장단점이 있기 때문입니다. 우선 연산량을 따지면, 당연히 기약 행 사다리꼴까지 바꿔야 하는 가우스-조르당 소거법이(당분간은 그냥 조르당 소거법으로 언급) 가우스 소거법보다 느립니다. 이것은 특히 행렬의 크기가 커질수록 두드러지게 됩니다. 반면 내가 역행렬을 구해야 하는 경우에는, 조르당 소거법이 훨씬 유리하겠지요. 행렬이 비가역인 경우에는 소거법을 진행하다 영행을 마주칠 겁니다. 그럴 땐 굳이 기약 행 사다리꼴까지 구하지 않아도 될 때가 있을 겁니다. 그럼에도 불구하고 우리는 $3\times 3$ 행렬을 주로 다루고, 역행렬을 구할 일이 많기 때문에 주로 조르당 소거법을 사용하게 될 것이라 생각하시면 됩니다.

 

 

2) 소거법을 진행할 때 참고할 점

 

소거법은 기본 행 연산을 통해 진행합니다. 다만 몇가지 고려하면 좋은 부분들이 있습니다.

 

① 영행이 있으면 가장 아래로 내리고, 미지수 계수가 0인 행일수록 아래로 내린다.

 

행렬 $\begin{pmatrix}
0 &2 &4\\ 
1 & -1&5\\
4 & 2 &3\\
\end{pmatrix}$ 에 대해 소거법을 진행할 때는, 기약 행 사다리꼴 및 행 사다리꼴의 정의에 의해서 0이 아닌 첫 성분은 위쪽에 놓인 행일수록 왼쪽에서 나와야 합니다. 그러므로 영행 자체가 존재하면 가장 아래로 내리도록 행 교환을 해야 하며, 미지수 계수가 0인 행이 존재해도 아래쪽으로 내려서 소거법을 진행해야 합니다.

 

② 선행하는 미지수부터 소거한다.

 

방정식에 미지수가 $x,y,z$ 3개가 있는 경우를 고려합니다. 기본 행 연산을 하면서 아래 행의 미지수 앞의 계수를 0이 되도록 만들어야 합니다. 이 때 $x$를 먼저 소거하고, $y,z$ 순으로 진행해야 합니다. 뜬금없이 $z$의 계수부터 0으로 만드는 것은 좋지 않습니다.

---

예제 1) 다음 연립방정식을 가우스-조르당 소거법으로 풀어라.

 

$$\left\{\begin{matrix}
x+2y+3z=14\\ 
2x+5y+6z=30\\ 
-x+2y+3z=12
\end{matrix}\right.$$

 

위 방정식을 첨가행렬 $\begin{bmatrix}
A\mid \mathbf{b}
\end{bmatrix}$ 로 생각하고 소거법을 진행합시다. 첨가행렬은

 

$$\begin{bmatrix} 
\left.\begin{matrix} 
\; 1 & 2 &3 \; \\  
\; 2 &5  &6 \; \\  
\; -1 &2  &3 \; 
\end{matrix}\right|  
& \begin{matrix}
14 \;\\ 
30 \;\\ 
12 \;
\end{matrix}  
\end{bmatrix}$$

 

이고,

 

$$R_2-2R_1\rightarrow R_2\;,\;R_1+R_3\rightarrow R_3\;\;\Rightarrow \;\;\begin{bmatrix} 
\left.\begin{matrix} 
\; 1 & 2 &3 \; \\  
\; 0 &1  &0 \; \\  
\; 0 &4  &6 \; 
\end{matrix}\right|  
& \begin{matrix}
14 \;\\ 
2 \;\\ 
26 \;
\end{matrix}  
\end{bmatrix}$$

 

$$R_3-4R_2\rightarrow R_3\;,\;\frac{1}{6}R_3\rightarrow R_3
\;\;\Rightarrow \;\;\begin{bmatrix} 
\left.\begin{matrix} 
\; 1 & 2 &3 \; \\  
\; 0 &1  &0 \; \\  
\; 0 &1  &0 \; 
\end{matrix}\right|  
& \begin{matrix}
14 \;\\ 
2 \;\\ 
3 \;
\end{matrix}  
\end{bmatrix}$$

 

여기까지 하면, 1행을 제외한 2,3행은 영행이 없으니 행렬 $A$가 가역일 것이라 예상 가능하고, 이제 1행의 2열과 3열 성분만 0으로 바꿔주는 작업을 하면 됩니다. 그를 위해선 2행과 3행을 통해 기본 행 연산을 수행해주면 됩니다.

 

$$R_1-3R_3\rightarrow R_1\;,\;R_1-2R_2\rightarrow R_1
\;\;\Rightarrow \;\;\begin{bmatrix} 
\left.\begin{matrix} 
\; 1 & 0 &0 \; \\  
\; 0 &1  &0 \; \\  
\; 0 &1  &0 \; 
\end{matrix}\right|  
& \begin{matrix}
1 \;\\ 
2 \;\\ 
3 \;
\end{matrix}  
\end{bmatrix}$$

 

기약 행 사다리꼴이 완벽하게 만들어졌고, 항등행렬이 되었으니 $A$는 가역이며 이 연립방정식의 해는 $x=1\;,\;y=2\;,\;z=3$ 입니다. 추가로 첨가행렬의 뒤쪽 $\mathbf{b}$를 항등행렬 $I_n$ 으로 놓고 같은 연산을 반복하면 $A$의 역행렬도 구할 수 있을 것입니다.