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}$이 존재하지 않습니다. 

 

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

 

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