23. 연립 일차 방정식과 가우스 소거법

23.1. Linear Systems of Equations.

 

 다음 연립방정식이 있다고 합시다.

$\begin {cases} a_{11} x_1 + \cdots + a_{1n} x_n = b_1 \\ a_{21} x_1 + \cdots + a_{2n} x_n = b_2 \\ \cdots \\ a_{m1} x_1 + \cdots + a_{mn} x_n = b_m \end {cases}$     (1)

 이제 이 연립방정식을 matrix를 이용하여 $\mathbf{Ax} = \mathbf {b}$와 같이 나타내 봅시다.

$\mathbf {A} = [a_{ij}] = \begin {bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end {bmatrix}$, $\mathbf{x} = \begin{bmatrix} x_{1} \\ \vdots \\ x_n\end{bmatrix}$, $\mathbf{b} = \begin{bmatrix} b_1 \\ \vdots \\ b_n \end{bmatrix}$      (2)

 이제 $\mathbf {A}$에 column vector $\mathbf {b}$를 추가하여 만든 matrix를 $\tilde {\mathbf {A}}$라 하고 그 matrix는 다음과 같습니다.

$\tilde{\mathbf{A}} = \begin {bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end {bmatrix}$     (3)

 (3)의 $\tilde {\mathbf {A}}$와 같은 matrix를 Augmented matrix라고 합니다. Gauss Elimination을 이용하여 연립방정식을 풀기 위해 위와 같은 연립방정식을 Augmented matrix로 만드는 과정이 필요합니다.

 

 

23.2. Gauss Elimination.

 

 예제를 통해 풀어봅시다. 다음과 같은 연립방정식이 있다고 합시다.

$\begin {cases} x_1 - x_2 + x_3 = 0 \\ -x_1 + x_2 + x_3 = 0 \\ 10x_2 + 25x_3 = 90 \\ 20x_1 + 10x_2 = 80 \end {cases}$     (4)

 (4)를 먼저 (3)의 $\tilde {\mathbf {A}}$처럼 나타내어 봅시다.

$\tilde{\mathbf{A}} = \begin {bmatrix} 1 & -1 & 1 & 0 \\ -1 & 1 & -1 & 0 \\ 0 & 10 & 25 & 90 \\ 20 & 10 & 0 & 80 \end {bmatrix}$     (5)

 $x_1$을 소거합니다. 이는 (5)의 1st row voctor를 제외한 모든 1st column을 0으로 만들면 됩니다. 2nd row에 1st row를 더하면 되고, 4th row는 1st row에 -20을 곱해주고 더하면 됩니다.

$\begin {bmatrix} 1 & -1 & 1 & 0 \\ 0&0&0&0 \\ 0 & 10&25&90 \\ 0&30&-20&80\end{bmatrix}$     (6)

 보기 편하도록 row 배열을 바꿉시다.

$\begin{bmatrix} 1 & -1 & 1 & 0 \\ 0 & 10&25&90 \\ 0&30&-20&80  \\ 0&0&0&0\end {bmatrix}$     (7)

 이제 $x_2$를 소거합니다. 2nd row에 -3을 곱한 뒤 3rd row에 더해줍니다.

$\begin {bmatrix} 1 & -1 & 1 & 0 \\ 0 & 10&25&90 \\ 0&0&-95&-190 \\ 0&0&0&0\end {bmatrix}$     (8)

 (8)을 다시 연립방정식으로 나타내 봅시다. row 순서를 반대로 합니다.

$\begin {cases} -95x_3 = -190 \\ 10x_2 +15x_3 = 90 \\ x_1 - x_2 + x_3 = 0 \end {cases}$      (9)

 (9)의 위 식부터 차례대로 풀면 각각의 변수의 해를 구할 수 있습니다.

$\therefore x_3 = 2 , x_2 = 4, x_1=2$

 이와 같은 방법으로 연립방정식을 Augmented matrix로 나타내어 각 변수를 소거시켜서 계산하는 방법을 Gauss Elimination이라고 합니다. 사실 중학생 때 독립변수가 2개인 연립방정식을 푸는데 이와 같은 방법을 사용하였었죠. 그 방법의 연 장판이라고 보시면 이해가 쉽습니다.

 

 

23.3. Elementary Row Operations. Row-Equivalant Systems.

 

 23.2에서 Gauss Elimination을 이용하여 풀었을 때 보았듯, Augmented matrix를 다음 세 가지 같은 연산을 하여도 연립방정식의 해를 변화시키지 않습니다.

 1. 2개의 row를 바꿀 수 있습니다.

 2. 어떤 한 개의 row에 임의의 상수를 곱하여 다른 row에 더하여 계산할 수 있습니다.

 3. 0이 아닌 임의의 상수를 곱할 수 있습니다.

 연립방정식 형태로 계산할 때도 위와 같은 세 가지 연산을 사용할 수 있습니다.

 

 

23.4. Gauss Elimination: the Three Possible Cases of Systems.

 

 23.4.1. Many Solutions Exist.

  연립방정식을 Augmented matrix로 나타내어 다음과 같다고 합시다.

$\begin {bmatrix} 3.0 & 2.0 & 2.0 & -5.0 &|&8.0 \\ 0.6& 1.5&1.5&-5.4&|&2.7 \\ 1.2&-0.3&-0.3&2.4&|&2.1 \end {bmatrix}$      (10)

  (10)의 $x_1$을 소거시킵니다. 1st row에 -0.2를 곱하여 2nd row에 더합니다.

$\begin{bmatrix} 3.0 & 2.0 & 2.0 & -5.0 &|&8.0 \\ 0&1.1&1.1&-4.4&|&1.1 \\ 0&-1.1&-1.1&1.4&|&-1.1 \end{bmatrix}$     (11)

  (11)의 $x_2$를 소거시킵니다. 2nd row를 3rd row에 더합니다.

$\begin{bmatrix} 3.0 & 2.0 & 2.0 & -5.0 &|&8.0 \\ 0&1.1&1.1&-4.4&|&1.1 \\ 0&0&0&0&|&0 \end{bmatrix}$     (12)

  (12)의 결과로 다음과 같은 해를 얻게 됩니다.

$\begin {cases} x_2 = 1-x_3+4x_4 \\ x_1 = 2-x_4 \end {cases}$

  이 같은 경우에는 $x_3$,$x_4$를 확정할 수 없기 때문에, 무한한 해를 얻게 됩니다.

 

 23.4.2. No Solution Exist.

  연립방정식을 Augmented matrix로 나타내어 다음과 같다고 합시다.

$\begin {bmatrix} 3& 2&1&|&3\\2&1&1&|&0\\6&2&4&|&6\end {bmatrix}$     (13)

  (13)의 $x_1$을 소거시킵니다. 1st row에 $-\frac {2}{3}$을 곱하여 2nd row에 더합니다. 그리고 1st row에 -2를 곱하여 3rd row에 더하면 다음과 같습니다.

$\begin {bmatrix} 3& 2&1&|&3\\0&\frac{1}{3}&\frac{1}{3}&|&-2\\0&-2&2&|&0\end{bmatrix}$     (14)

  (14)의 $x_2$를 소거시킵니다. 2nd row에 -6을 곱하여 3rd row에 더합니다.

$\begin{bmatrix} 3& 2&1&|&3\\0&\frac {1}{3}&\frac {1}{3}&|&-2\\0&0&0&|&12\end {bmatrix}$     (15)

  (15)에서 $0 = 12$라는 식을 얻었습니다. 이를 만족시키는 해는 없기 때문에 주어진 연립방정식을 만족시키는 해는 존재하지 않습니다.

 

 23.4.1과 23.4.2의 결과에 따라 Gauss Elimination으로 풀었을 때 1) 1개의 해를 가지는 경우, 2) 무한한 해를 가지는 경우, 3)해가 존재하지 않는 경우와 같이 오직 3가지 경우만 존재합니다.

 

 이번 포스팅은 여기서 마치겠습니다. 다음 포스팅에서는 Vector Space에 대하여 다룰 예정입니다.