선형대수학 – 가우스-조단(Gauss-Jordan) 소거법

가우스-조던 소거법

행령에서 x의 해를 구하는 데 Ax = b에 대한 행 연산을 통해 해 x를 구하는 방법을 보면.

Ax = b 에서 행렬 A가 단위 행렬 I라면 해는 x = b임을 알 수 있다.

이러한 행렬을 다음과 같은 절차로 기약행 사다리꼴 형태로 변환을 하기 위해서 가우스-조던 소거법을 사용할 수 있다.

즉 가우스 조던 소거법은 기약행 사다리꼴을 만드는 체계화된 절차이다. (*기약행 사다리콜 행렬 : 모든 추축성분이 해당 열에서 0이 아닌 유일한 성분인 행 사다릴꼴 행렬을 기약행 사다리꼴 행렬 또는 축약행 사다리꼴 행렬이라 한다.)

$\begin{bmatrix}
1 \ 0 \ 0 \\
0 \ 1 \ 0 \\
0 \ 0 \ 1
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
-2 \\
4
\end{bmatrix}$

이 행렬방정식을 연립선형방정식 형태로 전개하면, $x_{1} = 3, x_{2} = -2, x_{3} = 4$와 같이 각 미지수 값이 결정된다.

좌변의 행렬 A를 단위행렬 I로 만들 수 있다면, 이 행렬방정식의 해를 바로 구할 수 있다.

$\begin{bmatrix}
1 \quad \ \  2 \quad \ \ 1 \\
2 \quad \ \ 3 \quad \ \ 1 \\
3 \ -2 \ -3
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
4 \\
-1
\end{bmatrix}$

1행에 -2를 곱하여 2행에 더한다.

$\begin{bmatrix}
1 \quad \ \  2 \quad \ \ 1 \\
0 \ -1 \ -1 \\
3 \ -2 \ -3
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
-2 \\
-1
\end{bmatrix}$

1행에 -3을 곱하여 3행에 더한다.

$\begin{bmatrix}
1 \quad \ \  2 \quad \ \ 1 \\
0 \ -1 \ -1 \\
0 \ -8 \ -6
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
-2 \\
-10
\end{bmatrix}$

2행에 -1을 곱한다.

$\begin{bmatrix}
1 \quad \ \ 2\quad \ \ 1 \\
0 \quad \ \ 1 \quad \ \  1 \\
0 \ -8 \ -6
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
2 \\
-10
\end{bmatrix}$

2향애 8을 곱하여 3행에 더한다.

$\begin{bmatrix}
1 \quad \ \ 2 \quad \ \ 1 \\
0 \quad \ \ 1 \quad \ \  1 \\
0 \quad \ \ 0 \quad \ \ 2
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
3 \\
2 \\
6
\end{bmatrix}$

2행에 -2를 곱하여 1행에 더한다.

$\begin{bmatrix}
1 \quad \ \ 0 \ \ -1 \\
0 \quad \ \ 1 \quad \ \  1 \\
0 \quad \ \ 0 \quad \ \ 2
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
-1 \\
2 \\
6
\end{bmatrix}$

3행에 $\dfrac{1}{2}$를 곱한다.

$\begin{bmatrix}
1 \quad \ \ 0 \ \ -1 \\
0 \quad \ \ 1 \quad \ \  1 \\
0 \quad \ \ 0 \quad \ \ 1
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
-1 \\
2 \\
3
\end{bmatrix}$

3행을 1행에 더한다

$\begin{bmatrix}
1 \quad \ \ 0 \quad \ \ 0 \\
0 \quad \ \ 1 \quad \ \  1 \\
0 \quad \ \ 0 \quad \ \ 1
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
2 \\
2 \\
3
\end{bmatrix}$

3행에 -1을 곱하여 2행에 더한다.

$\begin{bmatrix}
1 \quad \ \ 0 \quad \ \ 0 \\
0 \quad \ \ 1 \quad \ \  0 \\
0 \quad \ \ 0 \quad \ \ 1
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
x_{2} \\
x_{3} \\
\end{bmatrix} =
\begin{bmatrix}
2 \\
-1 \\
3
\end{bmatrix}$

따라서 해는 $x_{1} = 2, x_{2} = -1, x_{3} = 3$

가우스 – 조단 소거법으로 해를 구하는 과정

[1단계] 연립선형방정식을 첨가행렬로 변환한다.

[2단계] 첫 번째 행부터 마지막 행까지 [3단계] 부터 [5단계]의 과정을 반복해서 수행한다. 이때 현재 고려하는 행 번호를 i라고 하자

[3단계] i열부터 마지막 열까지, 위쪽 행의 추축성분이 아래쪽 행의 추축성분과 같은 위치에 있거나 왼쪽에 있도록 행을 교환한다.

[4단계] i행을 추축성분이 j열에 있다면, i행을 (i,j) 성분의 값으로 나누어 추축성분의 값이 1이 되도록 만든다.

[5 단계] 이 추축성분을 제외한 j열의 모든 성분이 0이 되도록 i행을 상수배를 다른 행들에 더한다.

[6단계] 계수행렬 부분에 모든 성분이 0인 행이 있고, 이행에 대응하는 ‘|’ 이후의 값이 0 이 아니면, ‘해가 없다(불능이다)’ 라고 판정한다.

[7단계] 0이 아닌 성분이 포함된 행의 개수가 미지수의 개수보다 적다면, ‘무수히 많은 해가 존재한다(부정이다)’라고 판정한다.

[8단계] [6단계] 와 [7단계]에 해당하지 않는 경우라면, 기약행 사다리꼴 행렬에서 해를 읽는다.

불능인 연립선형방정식에 대한 가우스-조던 소거법

$\begin{bmatrix}
1 & -3 & -6 & | & 2 \\
3 & -8 & -17 & | & -1 \\
1 & -4 & -7 & | & 10
\end{bmatrix}$

($R_{2} \leftarrow -3R_{1} + R_{2}$)

$\begin{bmatrix}
1 & -3 & -6 & | & 2 \\
0 & 1 & 1 & | & -7 \\
1 & -4 & -7 & | & 10
\end{bmatrix}$

($R_{3} \leftarrow -R_{1} + R_{3}$)

$\begin{bmatrix}
1 & -3 & -6 & | & 2 \\
0 & 1 & 1 & | & -7 \\
1 & -1 & -1 & | & 8
\end{bmatrix}$

($R_{3} \leftarrow R_{2} + R_{3}$)

$\begin{bmatrix}
1 & -3 & -6 & | & 2 \\
0 & 1 & 1 & | & -7 \\
0 & 0 & 0 & | & 1
\end{bmatrix}$

마지막 행렬의 3행은 $0x_{1} + 0x_{2} + 0x_{3} = 1$ 로 해는 존재하지 않는다. 즉 이 연립 방정식은 불능이다.

부정인 연립선형방정식의 풀이법

$\begin{bmatrix}
0 & 4 & 1 & | & 2 \\
2 & 6 & -2 & | & 3 \\
4 & 8 & -5 & | & 4
\end{bmatrix}$

($R_{1} \leftrightarrow R_{2} $)

$\begin{bmatrix}
2 & 6 & -2 & | & 3 \\
0 & 4 & 1 & | & 2 \\
4 & 8 & -5 & | & 4
\end{bmatrix}$

($R_{1} \leftarrow \dfrac{1}{2}R_{1} $)

$\begin{bmatrix}
1 & 3 & -1 & | & \dfrac{3}{2} \\
0 & 4 & 1 & | & 2 \\
4 & 8 & -5 & | & 4
\end{bmatrix}$

($R_{3} \leftarrow -4R_{1} + R_{3} $)

$\begin{bmatrix}
1 & 3 & -1 & | & \dfrac{3}{2} \\
0 & 4 & 1 & | & 2 \\
0 & -4 & -1 & | & -2
\end{bmatrix}$

($R_{2} \leftarrow \dfrac{1}{4}R_{2} $)

$\begin{bmatrix}
1 & 3 & -1 & | & \dfrac{3}{2} \\
0 & 1 & \dfrac{1}{4} & | & \dfrac{1}{2} \\
0 & -4 & -1 & | & -2
\end{bmatrix}$

($R_{1} \leftarrow -3R_{2}+R_{1} $)
($R_{3} \leftarrow 4R_{2}+R_{3} $)

$\begin{bmatrix}
1 & 0 & -\dfrac{7}{4} & | & 0 \\
0 & 1 & \dfrac{1}{4} & | & \dfrac{1}{2} \\
0 & 0 & 0 & | & 0
\end{bmatrix}$

3행의 성분은 모두 0이기 때문에, 미지수 $x_{3}$의 값은 하나로 고정되지 않는다. x_{3}에 어떤 값 t를 대입해도 연깁선형방정식의 해가 존재한다.

$x_{1} – \dfrac{7}{4}x_{3} = 0 \rightarrow x_{1} = \dfrac{7}{4}x_{3}$

$x_{2} – \dfrac{1}{4}x_{3} = \dfrac{1}{2} \rightarrow x_{2} = -\dfrac{1}{4}x_{3} + \dfrac{1}{2}$

$x_{3} = t$를 대입하면

$x_{1} – \dfrac{7}{4}t, x_{2} = -\dfrac{1}{4}t + {1}{2}, x_{3} =t$ 이 때 어떤 값이 든 될 수 있는 t와 같은 변수를 자유변수(fre variable)라고 한다.

$t = 4 \Rightarrow (x_{1},x_{2},x_{3}) = (7, -\dfrac{1}{2}, 4)$

$t = -2 \Rightarrow (x_{1},x_{2},x_{3}) = (\dfrac{7}{2}, 1, -2)$

t에 어떤 값을 대입해도 해가 존재하기 때문에 이 연립선형방정식의 해는 무수히 많다. 이러한 연립선형방정식을 부정이라고 한다.

python code

import numpy as np

a = np.zeros((2,3)) # 2*3 영행렬
b = np.ones((2,2)) # 모든 성분이 1인 2*2 행렬
c = np.full((3,2),3) # 모든 성분이 3인 3*2 행렬
d = np.eye(2) # 2*2 단위 행렬

가우스 조던 소거법

import numpy as np

#행렬 A를 출력하는 함수
def pprint(msg, A):
    print("---", msg, "---")
    (n,m) A.shape
    for i in range(0,n):
        line = ""
        for j in range(0,m):
            line += "{0:.2f}".format(A[i,j])+"\t"
            if j == n-1:
                line += "| "
        print(line)
    print("")

#가우스-조단 조거법을 수행하는 함수
def gauss(A):
    (n,m) = A.shape

    for i in range(0, n):
        # i번째 열에서 절댓값이 최대인 성분의 행 선택
        maxEl = abs(A[i,i])
        maxRow = i
        for k in range(i+1, n):
            if abs(A[k,i]) > maxEl:
                maxEl = abs(A[k,i])
                maxRow = k
        #현재 i번째 행과 최댓값을 갖는 행 maxRow 의 교환
        for k in range(i,m):
            tmp = A[maxRow,k]
            A[maxRow,k] = A[i,k]
            A[i,k] = tmp

        #추축 성분을 1로 만들기
        piv = A[i,i]
        for k in  range(i,m):
            A[i,k] = A[i,k]/piv

        #현재 i번째 열의 i번째 행을 제외한 모두 성분을 0으로 만들기
        for k range(0,n):
            if k != i:
                c = A[k,i]/A[i,i]
                for j in range(i,m):
                    if i == j:
                        A[k,j] = 0
                    else:
                        A[k,j] = A[k,j] - c *  A[i,i]
        pprint(str(i+1)+"번째 반복",A)

    x = np.zeros(n)
    for i in range(0,n):
        x[i] = A[i,n]
    return x

A = np.array([[2.,2.,4.,18.],[1.,3.,2.,13.],[3.,1.,3.,14.]])
pprint("주어진 문제",A)
x = gauss(A)

(n,m) = A.shape
line = "해:\t"
for i in range(0,n):
    line += "{0:.2f}".format(x[i]) + "\t"
print(line)