선형대수학 – 가우스-조단(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)

 

 

 

 

“선형대수학 – 가우스-조단(Gauss-Jordan) 소거법”의 11개의 댓글

  1. Hello! Quick question that’s completely off topic. Do you know how
    to make your site mobile friendly? My web site looks weird when viewing from my
    iphone 4. I’m trying to find a theme or plugin that might be able to fix this problem.

    If you have any recommendations, please share. Cheers!

답글 남기기