2.2.2 연립일차방식의 해법(정칙인 경우) - 가우스 요르단 소거법

블록 행렬 표기만으로 연립 일차방정식을 풀다 <- 가우스 요르단 소거법 

 

블록 행렬로 표기하여 연립 일차방정식 $A\mathbf {x} = \mathbf {y}$를 풀었지만, 도중에 값이 경신된 부분은

 

$\begin {pmatrix}  
* &  *&  *& \mid  *\\   
* &  *&  *& \mid *\\   
*& *&  *& \mid *  
\end {pmatrix}\begin {pmatrix}   
x_{1}\\ x_{2}  
\\x_{3}   
\\ - \\-1   
\end {pmatrix} = \begin {pmatrix}  
0\\0   
\\ 0  
\end {pmatrix}$

 

* 부분 뿐입니다. 다른 부분은 처음부터 끝까지 같습니다.

 

그렇다면 일부러 쓰지 않아도 풀 수 있으므로 갱신하는 부분만 끄집어낸 

 

$(A | \mathbf{y})=\begin {pmatrix}   
2 &  3  &3 &\mid  9\\    
3 &  4&  2& \mid 9\\    
-2& -2&  3& \mid 2   
\end {pmatrix}$

 

을 변형해가는 방법이 연립일차방정식의 '손 계산 방법'입니다.

 

이때 변형해가는 방법은

 

어느 행을 c배 한다.

 

어느 행을 c배하여 다른 행에 더한다

 

입니다(c는 0이 아닌 수). 목표는 A였던 부분을 단위행렬 $I$로 만드는 것입니다. 그렇게 되면 $\mathbf {y}$였던 부분이 해가 됩니다.

 

지금부터는 조금 다른 순서인 가우스 요르단(Gauss-Jordan) 소거법을 이용해서 풀어보겠습니다(어떤 순서라도 $I$에 도달하면 성공입니다).

 

$(A \mid \mathbf{y})$    (2.13)

 

$=\begin {pmatrix}   
2 &  3  &3 &\mid  9\\
- & - & - & \mid - \\     
3 &  4&  2& \mid 9\\
- & - & - & \mid - \\    
-2& -2&  3& \mid 2   
\end {pmatrix}$     (2.14)   

1행을 1/2배하여 선두에 1을 만든다.    

$-> \begin {pmatrix}   
1 &  \frac{3}{2}  &\frac {3}{2} &\mid  \frac {9}{2}\\
- & - & - & \mid - \\     
3 &  4&  2& \mid 9\\   
- & - & - & \mid - \\    
-2& -2&  3& \mid 2     
\end {pmatrix}$     (2.15)

 

1행을 (-3)배하여 2행에 더해 선두를 0으로 만든다.

1행을 2배하여 3행에 더해 선두를 0으로 만든다.

이것으로 1열을 완성한다.

 

$-> \begin {pmatrix}   
1 &  \frac{3}{2}  &\frac {3}{2} &\mid  \frac {9}{2}\\
- & - & - & \mid - \\     
0 &  -\frac{1}{2}&  -\frac {5}{2}& \mid -\frac {9}{2}\\
- & - & - & \mid - \\    
0& 1&  6& \mid 11   
\end {pmatrix}$     (2.16)

 

2행을 (-2)배하여 2열(대각 성분)에 1을 만든다.

$-> \begin {pmatrix}   
1 &  \frac{3}{2}  &\frac {3}{2} &\mid  \frac {9}{2}\\
- & - & - & \mid - \\     
0 &  1&  5& \mid 9\\
- & - & - & \mid - \\    
0& 1&  6& \mid 11   
\end {pmatrix}$     (2.17)

 

2행을 (-3/2)배하여 1행에 더해 2열을 0으로 만든다.

2행을 (-1)배하여 3행에 더해 2열을 0으로 만든다.

이것으로 2열도 완성된다.

$-> \begin {pmatrix}   
1 &  0  &-6 &\mid  9\\
- & - & - & \mid - \\     
0 &  1&  5& \mid 9\\
- & - & - & \mid - \\    
0& 0&  1& \mid 2   
\end {pmatrix}$   (2.18)  

 

운좋게도 3행은 이대로 3열(대각 성분)이 1

3행을 6배하여 1행에 더해 3열을 0으로 만든다.

3행을 (-5)배하여 2행에 더해 3열을 0으로 만든다.

 

$-> \begin {pmatrix}   
1 &  0  &0 &\mid  3\\
- & - & - & \mid - \\     
0 &  1&  0& \mid -1\\
- & - & - & \mid - \\    
0& 0&  1& \mid 2  
\end {pmatrix}$     (2.19)

 

이것으로 3열도 완성

 

이렇게 $\mathbf{x} = (3, -1, 2)^{T}$를 구했습니다.

 

이 방법만으로는 통하지 않는 경우도 있습니다.

 

대각 성분을 1로 하려고 했더니 해당 부분이 0인 경우입니다.

 

이러한 경우 세 번째 방법인 피보팅(pivoting)을 사용합니다.

 

▶ 어느 행과 다른 행을 바꿔 넣는다(pivoting)

 

예를 들어

 

$=\begin {pmatrix}    
0 &  1  &6 &\mid  11\\ 
- & - & - & \mid - \\      
3 &  4&  2& \mid 9\\ 
- & - & - & \mid - \\     
-2& -2&  3& \mid 2    
\end {pmatrix} \rightarrow \begin {pmatrix}    
3 &  4  &2 &\mid  9\\ 
- & - & - & \mid - \\      
0 &  1&  6& \mid 11\\ 
- & - & - & \mid - \\     
-2& -2&  3& \mid 2    
\end {pmatrix}$ 1행과 2행을 바꾼다.

 

와 같이 0이 아닌 것을 가져와'1행에 1/3을 곱하여 대각 성분에 1을 만든다'라는 형태 입니다. 어떤 방법인지 원래 모습으로 쓰면

 

$=\begin {pmatrix}    
0 &  1  &6 &\mid  11\\ 
- & - & - & \mid - \\      
3 &  4&  2& \mid 9\\ 
- & - & - & \mid - \\     
-2& -2&  3& \mid 2    
\end {pmatrix}\begin {pmatrix}    
x_{1}\\ x_{2}   
\\x_{3}    
\\ - \\-1    
\end {pmatrix} = \begin {pmatrix}   
0\\0    
\\ 0   
\end {pmatrix}

 \rightarrow \begin {pmatrix}    
3 &  4  &2 &\mid  9\\ 
- & - & - & \mid - \\      
0 &  1&  6& \mid 11\\ 
- & - & - & \mid - \\     
-2& -2&  3& \mid 2    
\end {pmatrix}\begin {pmatrix}    
x_{1}\\ x_{2}   
\\x_{3}    
\\ - \\-1    
\end {pmatrix} = \begin {pmatrix}   
0\\0    
\\ 0   
\end {pmatrix}$

 

즉 연립 일차방정식

 

$x_{2} + 6x_{3} = 11$ 

 

$3x_{1} + 4x_{2} + 2x_{3} = 9$ 

 

$-2x_{1} - 2x_{2} +3x_{3} = 2$

 

의 1식과 2식의 순서를 바꿔서 

 

$3x_{1} + 4x_{2} + 2x_{3} = 9$ 

$x_{2} + 6x_{3} = 11$ 

$-2x_{1} - 2x_{2} +3x_{3} = 2$

 

로 고쳐 쓴 것뿐입니다. 바꾼다고 해서 답이 바뀌지는 않습니다.

 

정리하겠습니다.

 

기본 순서는 다음을 반복하는 것으로 1열씩 정리해갑니다.

 

$\begin {pmatrix}
1 & 0 &0 &* &* & *& |& *\\ 
0 & 1 &0 &* &* & *& |& *\\
0 & 0 &1 &* &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &\bigstar  &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &* &* & *& |& *\\
0 & 0 &0 &* &* & *& |& *\\
0 & 0 &0 &* &* & *& |& *\\
\end {pmatrix}$ 대각 성분 ★이 1이 되도록 이 행을 ★로 나눈다.

 

$\begin {pmatrix}
1 & 0 &0 &\square   &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 1 &0 &\square &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &1 &\square &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &1  &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &\square &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &\square &* & *& |& *\\
- & - &- &- &- & -& |& -\\ 
0 & 0 &0 &\square &* & *& |& *\\
\end {pmatrix}$ 비 대각 성분 □가 0이 되도록 좀 전의 행의 □배를 각 행에서 뺀다. 

 

단, 만약 ★이 0이 되었다면 다음과 같이 피보팅 한다.

 

$\begin {pmatrix} 
1 & 0 &0 &*   &* & *& |& *\\ 
0 & 1 &0 &* &* & *& |& *\\  
0 & 0 &1 &*&* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &0  &* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
\end {pmatrix}$ ▲에서 0이 아닌 것을 찾아 행을 바꾼다.

 

$\begin {pmatrix} 
1 & 0 &0 &*   &* & *& |& *\\ 
0 & 1 &0 &* &* & *& |& *\\  
0 & 0 &1 &*&* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
- & - &- &- &- & -& |& -\\  
0 & 0 &0 &0  &* & *& |& *\\ 
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
0 & 0 &0 &\blacktriangle &* & *& |& *\\ 
\end {pmatrix}$ 나머지는 기본 순서로 돌아간다.

 

$\mid$의 왼쪽 행렬 부분이 전부 정리되면 $\mid$의 우측 벡터 부분에 해가 나타납니다.

 

피보팅을 사용해도 막히는 경우는 ▲가 모두 0이었다는 이야기입니다.

 

그런 A는 '납작하게 누르는' 사상이고 애초에 $A^{-1}$이 존재하지 않습니다. 

 

변수 소거법이 시간이 적게 들지만 가우스 요르단 소거법은 단순하고 알기 쉬워 작은 행렬을 손으로 계산할 때 시간에서 손해를 볼 정도는 아니므로 알아두시길 바랍니다.

 

다음 시간에는 역행렬의 계산을 해보겠습니다. 감사합니다.