가우스-조던 소거법
행령에서 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행을 상수배를 다른 행들에 더한다.불능인 연립선형방정식에 대한 가우스-조던 소거법
$\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)