연립 일차 방정식의 해
Chapter 3 : Solving Systems of Linear Equations
Edited by / 장성준 (junnei) 
-
목차
연립 일차 방정식은 $Ax = b$ 로 행렬의 형태로 나타낼 수 있다고 Chapter 1 에서 확인했고,
Chapter 2 에서는 행렬의 덧셈과 곱셈에 대한 기본적인 행렬 연산에 대해서 알아보았다.
이번 페이지에서는, 연립 일차 방정식의 해를 구하기 위해 행렬의 성질을 이용하는 방법에 대해 알아볼 것이다.
특수해와 일반해(Particular and General Solution)
다음과 같은 연립 일차 방정식과 함께 자세히 알아보도록 하자.
\[\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{bmatrix} = \begin{bmatrix} 42 \\ 8 \end{bmatrix} .\]위의 방정식은 2개의 방정식과 4개의 미지수로 이루어진 연립 방정식이다.
일반적으로 방정식의 개수보다 미지수의 개수가 많은 상황에서는 방정식의 해가 하나로 특정되지 않는다.
즉, 해의 개수가 무한하기 때문에(infinitely many solution) 모든 해를 표현할 수 있는 일반해를 찾을 필요성이 있다.
위의 방정식은 직관적으로 다음의 해를 도출해낼 수 있는 쉬운 방정식이다.
\[b = \begin{bmatrix} 42 \\ 8 \end{bmatrix} = 42 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 8 \begin{bmatrix} 0 \\ 1 \end{bmatrix} + 0 \begin{bmatrix} 8 \\ 2 \end{bmatrix} + 0 \begin{bmatrix} -4 \\ 12 \end{bmatrix}.\] \[\therefore \; \boldsymbol{x} = \begin{bmatrix} 42 & 8 & 0 & 0 \end{bmatrix}^{T}\]방정식의 해를 구하는 과정에서 위에서의 $\boldsymbol{x} = \begin{bmatrix}42 & 8 & 0 & 0\end{bmatrix}^{T}$ 와 같이 특정되는 해를 특수해라고 한다.
여기에서 알아두어야 할 점은, 특수해는 방정식의 모든 해가 아니라는 점이다.
그렇기 때문에, 온전한 풀이를 위해서는 특수해로부터 일반해를 구하는 과정이 필수적이다.
일반해를 어떻게 구하는지 바로 알아보도록 하자.
먼저, 열들을 더하거나 빼서 $Ax = 0$ 이 되도록 하는 조합을 찾을 것이다.
그리고 이미 $Ax = b$ 를 만족하는 특수해를 찾았으므로, 양변에 $Ax = 0$ 를 더해서 일반해를 구할 것이다.
이 때 $Ax = 0$ 를 만족하는 $x$ 를 Homogeneous Solution 이라고 하고, kernel 혹은 null space 에서의 basis of solution 이라 부른다.
처음의 식으로부터 일반해를 구하는 과정을 다음 예시를 통해 자세히 알아보자.
예시
\[\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{bmatrix} = \begin{bmatrix} 42 \\ 8 \end{bmatrix} .\] \[먼저, \; 세번째 \; 열을 \; 첫번째와 \; 두번째 \; 열을 \; 이용해 \; 다음과 \; 같은 \; 식을 \; 만들 \; 수 \; 있다.\] \[\begin{align} \begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} &= \begin{bmatrix} 8 \\ 2 \end{bmatrix} \\ \begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} 8 \\ 2 \\ 0 \\ 0 \end{bmatrix} &=8 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \\ 1 \end{bmatrix} \end{align} \Rightarrow \begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} 8 \\ 2 \\ -1 \\ 0 \end{bmatrix} =Ax=0.\]정리
일반적인 접근방법(general approach)을 정리하면 아래와 같이 3단계로 나타낼 수 있다.
$Ax=b$ 의 특수해 찾기
$Ax=0$ 의 모든 해 찾기
위의 과정에서 $1$ 과 $2$ 의 해를 결합하여 일반해 만들기
위의 예제는 간단하게 주어져서 쉽게 해를 구할 수 있었지만, 일반적인 방정식들은 이렇게 단순하게 않다.
다행히도, 우리는 가우시안 소거법(Gaussian eliminateion)을 사용하여 방정식을 간단하게 표현할 수 있다.
앞으로도 대부분의 풀이에 가우시안 소거법을 활용할 것이고, 덕분에 어려운 형태의 방정식도 풀 수 있을 것이다.
가우시안 소거법(Gaussian eliminateion)은 복잡한 방정식을 간단한 형태로 바꾸어주는 기본 선형 방정식으로,
정확히 말하자면, 첨가 행렬(Augmented matrix)를 행 사다리꼴(row-echelon form)로 바꾸어주는 알고리즘이다.
행렬을 간단하게 표현하는데 아래에서 설명할 기본 행 연산을 이용하므로 기본 행 연산을 먼저 알아보도록 하자.
기본 행 연산(Elementary Transformations)
먼저, 선형 방정식을 푸는 데 핵심적인 역할을 하는 개념으로 기본 행 연산(elementary transformation)이 있다.
기본 행 연산은 방정식을 조금 더 간단하게 바꾸어주는 역할을 하고, 다음과 같은 방법들이 있다.
-
두 행을 교환하기 (행렬에서의 행은 방정식을 나타냄)
-
행에 상수 $\lambda \in \mathbb{R}$ 를 곱하기
-
서로 다른 두 행을 더하기
기본 행 연산을 통해 행렬을 행 사다리꼴(row-echelon form)로 바꾸면 해를 쉽게 구할 수 있다.
자세한 내용은 다음 예시 2.6 를 통해 같이 살펴보자.
예시 2.6
$a \in \mathbb{R}$ 에 대해 다음과 같은 방정식이 있다.
\[\begin{align} \begin{matrix} −2x_1 \\ 4x_1 \\ x_1 \\ x_1 \end{matrix} \begin{matrix} + \\ - \\ - \\ - \end{matrix} \begin{matrix} 4x_2 \\ 8x_2 \\ 2x_2 \\ 2x_2 \end{matrix} \begin{matrix} − \\ + \\ + \\ \\ \end{matrix} \begin{matrix} 2x_3 \\ 3x_3 \\ x_3 \\ \\ \end{matrix} \begin{matrix} − \\ - \\ - \\ - \end{matrix} \begin{matrix} x_4 \\ 3x_4 \\ x_4 \\ 3x_4 \end{matrix} \begin{matrix} + \\ + \\ + \\ + \end{matrix} \begin{matrix} 4x_5 \\ x_5 \\ x_5 \\ 4x_5 \end{matrix} \begin{matrix} = \\ = \\ = \\ = \end{matrix} \begin{matrix} −3 \\ 2 \\ 0 \\ a \end{matrix} \end{align}\]간단하게 행렬식으로 표현하면 $Ax = b$ 를 $(A \mid b)$ 의 형식으로 표현할 수 있고,
이 때 $(A \mid b)$ 를 첨가 행렬(augmented matrix) 이라고 한다.
아래는 첨가 행렬에 기본 행 연산을 적용하여 해를 구하는 과정이다.
\[\begin{align} i) \qquad &\begin{bmatrix} \left. \begin{matrix} -2 & 4 & -2 & -1 & 4 \\ 4 & -8 & 3 & -3 & 1 \\ 1 & -2 & 1 & -1 & 1 \\ 1 & -2 & 0 & -3 & 4 \end{matrix} \right\rvert & \begin{matrix} -3 \\ 2 \\ 0 \\ a \end{matrix} \end{bmatrix} \begin{matrix} Swap\;with\;R_3 \\ \\ Swap\;with\;R_1 \\ \\ \end{matrix} \\\\ ii) \qquad &\begin{bmatrix} \left. \begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 4 & -8 & 3 & -3 & 1 \\ -2 & 4 & -2 & -1 & 4 \\ 1 & -2 & 0 & -3 & 4 \end{matrix} \right\rvert & \begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \end{bmatrix} \begin{matrix} \\ -4R_1\\ +2R_1 \\ -R_1 \end{matrix} \\\\ iii) \qquad &\begin{bmatrix} \left. \begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & -3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & -1 & -2 & 3 \end{matrix} \right\rvert & \begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \end{bmatrix} \begin{matrix} \\ \\ \\ -R_2-R_3 \end{matrix} \\\\ iv) \qquad &\begin{bmatrix} \left. \begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & -3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} \right\rvert \begin{matrix} 0 \\ 2 \\ -3 \\ a+1 \end{matrix} \end{bmatrix} \begin{matrix} \\ \cdot (-1) \\ \cdot (-\frac{1}{3}) \\ \\ \end{matrix} \\\\ v) \qquad &\begin{bmatrix} \left. \begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} \right\rvert \begin{matrix} 0 \\ -2 \\ 1 \\ a+1 \end{matrix} \end{bmatrix} \begin{matrix} \\ \\ \\ \\ \end{matrix} \end{align}\] \[\Leftrightarrow particular \; solution \; : \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 2\\0\\-1\\1\\0 \end{bmatrix} , \quad a = 1\] \[\Leftrightarrow general \; solution \; : \left \{ \boldsymbol{x} \in \mathbb{R}^{5} : \boldsymbol{x} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} + \lambda_{1} \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_{2} \begin{bmatrix} 2 \\ 0 \\ -1 \\ 2 \\ 1 \end{bmatrix} , \lambda_{1}, \lambda_{2} \in \mathbb{R} \right \}\]행 사다리꼴
위의 과정에서 $v)$ 에서 행 사다리꼴이 완성된 것을 확인할 수 있고, 이 행렬은 항상 계단 구도를 가진다.
\[v) \qquad \begin{bmatrix} \left. \begin{matrix} \boldsymbol{1} & \color{blue}{-2} & 1 & -1 & 1 \\ 0 & 0 & \boldsymbol{1} & -1 & 3 \\ 0 & 0 & 0 & \boldsymbol{1} & -2 \\ 0 & 0 & 0 & 0 & \color{blue}{0} \end{matrix} \right\rvert \begin{matrix} 0 \\ -2 \\ 1 \\ a+1 \end{matrix} \end{bmatrix}\]행 사다리꼴의 각 행에서 0이 아닌 첫번째 요소를 피벗(pivot)이라고 하며 피벗은 1의 값을 가지도록 한다.
그리고 $v)$ 의 마지막 행과 같이 피벗이 존재하지 않는 열, 즉 모든 요소가 0인 열은 가장 아래에 위치하도록 한다.
행 사다리꼴은 아래와 같은 특징을 가진다.
-
피벗을 가지는 $x$ 값을 basic variable 이라고 하며, 이 값을 가진 열을 pivot column 이라고 한다.
-
반대로, 피벗이 존재하지 않는 열을 free column이라고 하며, 이에 대응하는 $x$ 값을 free variable 이라고 한다.
-
위의 예제에서 $x1, x3, x4$ 는 basic variables, $ x2 , x5$ 는 free variables 이다.
가우스 조르단 소거법과 Minus-1 트릭
{ :.no_toc }