Systems of Linear Equations
연립일차(선형)방정식(Systems of linear equations)는 선형대수학의 중심이 되는 파트입니다. 많은 문제들은 연립선형방정식으로 공식화될 수 있고, 선형대수학은 이 문제를 풀 수 있는 방법을 제공합니다.
예제를 통해 살펴보도록 하겠습니다.
Example 2.1
A 회사가 $N_1, \dotsc, N_n$ 제품을 생산하는데, 각 제품을 생산할 때 $R_1, \dotsc, R_m$ 의 리소스가 필요합니다. 여기서 $a_{ij}$는 $N_j$ 라는 제품 하나를 생산하기 위해서 필요한 $R_i$ 리소스 하나를 표현합니다 ($i = 1, \dotsc, m$ and $j = 1, \dotsc, n$).
목적은 총 $b_i$ 만큼의 $R_i$ 리소스를 사용할 수 있을 때, 남는 자원없이 최대로 생산할 수 있는 수를 찾는 것입니다. 각 제품들의 갯수를 $x_1, \dotsc, x_n$ 라고 한다면, 리소스 $R_i$ 는 아래 식의 합만큼 필요합니다.
\[a_{i1}x_1 + \cdots + a_{in}x_n \tag{2.2}\]따라서, 최적의 제품 계획 $(x_1, \dotsc, x_n) \in \mathbb{R}^n$ 은 다음의 연립방정식을 만족해야 합니다.
\[\begin{align*} a_{11}x_1 + \cdots &+ a_{1n}x_n = b_1 \\ &\vdots \\ a_{m1}x_1 + \cdots &+ a_{mn}x_n = b_m \end{align*} \tag{2.3}\]여기서 $a_{ij} \in \mathbb{R}$ and $b_i \in \mathbb{R}$.
식 (2.3)은 연립선형방정식의 general form이고, $x_1, \dotsc, x_n$ 은 이 방정식에서 미지(unknown)의 값입니다. 식 (2.3)을 만족하는 모든 n-튜플 $(x_1, \dotsc, x_n) \in \mathbb{R}^n$ 은 이 연립선형방정식의 해 입니다.
Example 2.2
\[\begin{matrix} x_1 &+ &x_2 &+ &x_3 &= &3 &\quad (1)\\ x_1 &- &x_2 &+ &2x_3 &= &2 &\quad(2) \\ 2x_1 & & &+ &3x_3 &= &1 &\quad(3) \end{matrix} \tag{2.4}\]위의 연립선형방정식은 해가 없습니다.
\[\begin{matrix} x_1 &+ &x_2 &+ &x_3 &= &3 &\quad(1) \\ x_1 &- &x_2 &+ &2x_3 &= &2 &\quad(2) \\ & &x_2 &+ &x_3 &= &2 &\quad(3) \end{matrix} \tag{2.5}\]
처음 두 방정식을 더하면 $2x_1 + 3x_3 + 5$ 가 되고, 이 결과는 (3) 방정식과 모순입니다.이 번에는 위 식을 살펴보겠습니다. (1), (3) 방정식으로부터 $x_1 = 1$ 임을 알 수 있습니다. 그리고 (1) + (2) = $2x_1 + 3x_3 = 5$ 이고, $x_1 = 1$ 이기 때문에 $x_3 = 1$ 이라는 것도 알 수 있습니다. 마지막으로 (3) 방정식을 통해 $x_2 = 1$ 이라는 것도 알 수 있습니다. 따라서, (1, 1, 1)만 연립선형방정식의 해가 될 수 있습니다.
\[\begin{matrix} x_1 &+ &x_2 &+ &x_3 &= &3 &\quad(1) \\ x_1 &- &x_2 &+ &2x_3 &= &2 &\quad(2) \\ 2x_1& & &+ &3x_3 &= &5 &\quad(3) \end{matrix} \tag{2.6}\]
마지막으로 아래의 연립선형방정식을 살펴보겠습니다. 위 연립방정식에서 (3) 방정식만 변경되었습니다.(1) + (2) = (3) 이므로, 세 번째 방정식을 생략할 수 있습니다(redundancy). (1)과 (2)로부터, $2x_1 = 5 - 3x_3$ , $2x_2 = 1 + x_3$ 을 얻을 수 있으며, $x_3 = a \in \mathbb{R}$ 이라고 정의한다면, 이 연립선형방정식의 해는 다음을 만족하는 triplet이 됩니다.
\[\left( \frac{5}{2} - \frac{3}{2}a, \frac{1}{2} + \frac{1}{2}a, a \right) \tag{2.7}\]즉, 무한히 많은 솔루션들이 있는 솔루션 집합을 얻게 됩니다.
일반적으로 실수 값에 대한 연립선형방정식에서 우리는 하나도 없거나, 오직 하나이거나, 무한히 많은 해를 얻습니다. 선형 회귀(Linear Regression, Ch9)에서는 Example 2.1과 같이 해를 구할 수 없는 연립선형방정식을 해결합니다.
간단하게 기하학적 해석으로 선형연립방정식을 살펴보겠습니다.
두 개의 변수 $x_1, x_2$ 에 대한 연립선형방정식에서 각 선형방정식은 $x_1x_2$ 평면의 직선을 정의합니다. 선형연립방정식의 해는 모든 방정식을 동시에 만족해야 하므로, 이 연립방정식의 해는 정의되는 선의 교집합입니다. 이때 가능한 교집합은 직선(두 선형방정식이 동일한 직선을 정의할 때), 점, 또는 공집합(평행할 때)이 될 수 있습니다.
위 그림은 아래의 시스템을 보여주고 있습니다.
\[\begin{align*} 4x_1 &+ 4x_2 = 5 \\ 2x_1 &- 4x_2 = 1 \end{align*} \tag{2.8}\]여기서 해의 공간은 $(x_1, x_2) = (1, \frac{1}{4})$ 인 점입니다.
이와 비슷하게 3개의 변수에서, 각각의 선형방정식은 3차원 공간의 평면을 결정합니다. 즉, 이 평면들을 교차했을 때, 즉, 동시에 모든 선형방정식을 만족할 때 평면(plane), 직선(line), 점(point), 또는 공집합을 가능한 해의 교집합으로 얻을 수 있습니다.
연립선형방정식을 조금 더 체계적으로 접근하기 위해서 식 (2.3)에서 계수 $a_{ij}$ 를 벡터로 표현하고 이러한 벡터들을 모아서 행렬로 표현합니다. 따라서, 식 (2.3)을 다음과 같은 형태로 표현합니다.
\[x_1 \begin{bmatrix} a_{11} \\ \vdots \\ a_{m1} \end{bmatrix} + x_2 \begin{bmatrix} a_{12} \\ \vdots \\ a_{m2} \end{bmatrix} + \cdots + x_n \begin{bmatrix} a_{1n} \\ \vdots \\ a_{mn} \end{bmatrix} = \begin{bmatrix} b_{1} \\ \vdots \\ b_{m} \end{bmatrix} \tag{2.9}\] \[\rightleftharpoons \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{m1} & \cdots & a_{mn} \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ \vdots \\ b_m \end{bmatrix} \tag{2.10}\]