[선형대수] 연립 선형 방정식
연립 선형 방정식 (System of Linear Equations)
연립 선형 방정식 (연립 일차 방정식)은 아래와 같이 행렬로 표현할 수 있다.
\[\begin{cases} x_1+x_2+x_3=3\\x_1-x_2+2x_2=2\\2x_1+x_3=1 \end{cases} ~\to~ \begin{bmatrix}1&1&1\\1&-1&2\\2&0&1\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} =\begin{bmatrix}3\\2\\1\end{bmatrix}\]이때 변수 벡터 $\mathbf{x}$를 $\mid$ (bar)로 표현해서, 하나의 행렬로 나타낸 것을 첨가 행렬 (Augmented Matrix)이라고 부른다.
\[\begin{bmatrix}1&1&1\\1&-1&2\\2&0&1\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} =\begin{bmatrix}3\\2\\1\end{bmatrix} ~\to~ \begin{bmatrix}\begin{array}{ccc|c} 1&1&1&3\\1&-1&2&2\\2&0&1&1 \end{array}\end{bmatrix}\]연립 선형 방정식을 푸는 방법에는 크게 3가지가 있다.
- 가우스 소거법 (Gauss Elimination)
- 크래머의 법칙 (Cramer’s Rule)
- LU 분해 (LU Decomposition)
연립 선형 방정식이 가질 수 있는 세 가지 해의 형태
연립 선형 방정식이 가질 수 있는 해의 종류에는 세 가지가 있다.
1. 해가 유일함 (Unique solution)
단 하나의 해만 존재하는 경우이다.
\[\begin{bmatrix}\begin{array}{ccc|c} 1&0&0&1\\0&1&0&2\\0&0&1&3 \end{array}\end{bmatrix} ~\to~ \mathbf{x}=\begin{bmatrix}1\\2\\3\end{bmatrix}\]기하학적으로는, 예를 들어 2차원 공간에서 두 직선이 오직 한 점에서만 만나는 상황으로 이해할 수 있다.
2. 해가 무수히 많음 (Infinitely many solutions)
해가 하나가 아니라 여러 개인 경우이다.
이러한 상황은 주로 Under-determined System (방정식의 개수 < 미지수의 개수)에서 발생한다.
이러한 시스템은 자유 변수 (Free variable)를 포함하게 된다.
자유 변수는 어떤 값을 대입해도 방정식이 성립하는 변수로, 자유 변수가 존재한다면 그 변수에 따라 해가 무한히 많이 생기게 된다.
위에서 변수 $x_3$에 따라 해가 결정되며, 이때 $x_3$를 자유 변수라고 부른다.
기하학적으로는, 예를 들어 2차원 공간에서 두 직선이 같은 직선을 나타내는 상황으로 이해할 수 있다.
3. 해가 없음 (No solution)
해가 없는 경우로, 연립 방정식에 모순이 있어 어떤 값을 대입해도 모든 방정식을 동시에 만족시킬 수 없는 상황이다.
이러한 상황은 주로 Over-determined System (방정식의 개수 > 미지수의 개수)에서 발생한다.
\[\begin{bmatrix}\begin{array}{ccc|c} 1&0&1&3\\0&1&2&2\\0&0&1&1 \end{array}\end{bmatrix}\]기하학적으로는, 예를 들어 2차원 공간에서 두 직선이 평행한 상황으로 이해할 수 있다.
Over-determined System은 우리가 흔히 보는 선형 회귀 그림처럼, 미지수는 $x,y$ 축 2개이지만 데이터 샘플이 매우 많은 경우로 생각할 수 있다.
이러한 경우에는 해를 구할 수 없지만, 최소 제곱법 (Least Square Method)으로 해를 근사할 수 있다.
연립 방정식의 해가 존재할 조건
선형 연립 방정식 $A\mathbf{x}=\mathbf{b}$의 해가 존재할 조건은 여러 관점에서 설명할 수 있다.
1. Rank 관점
행렬 $A$의 Rank와 첨가 행렬 $[A\mid \mathbf{b}]$의 Rank가 같아야 해가 존재한다.
\[\text{rank}(A)=\text{rank}(A\mid \mathbf{b})\]즉, 가우스 소거법을 이용해 REF 형태로 만들었을 때 아래 형태의 행이 존재하면 안된다.
\[\begin{bmatrix}\begin{array}{cccc|c}0&0&\cdots&0&c\end{array}\end{bmatrix}~,~(c\neq0)\]변수의 개수를 $n$이라고 할 때, 아래의 경우로 나눌 수 있다.
- 해가 유일함: $\text{rank}(A)=\text{rank}(A\mid \mathbf{b})=n$
- 해가 무수히 많음: $\text{rank}(A)=\text{rank}(A\mid \mathbf{b})<n$
- 해가 없음: $\text{rank}(A)<\text{rank}(A\mid \mathbf{b})$
Example: 연립 방정식의 해 판별
\[[A\mid \mathbf{b}]=\begin{bmatrix}\begin{array}{ccc|c}1&0&0&1\\0&1&0&2\\0&0&1&3\end{array}\end{bmatrix}~,~[B\mid \mathbf{b}]=\begin{bmatrix}\begin{array}{ccc|c}1&0&0&1\\0&1&0&2\\0&1&0&2\end{array}\end{bmatrix}~,~[C\mid \mathbf{b}]=\begin{bmatrix}\begin{array}{ccc|c}1&0&0&1\\0&1&0&2\\0&1&0&3\end{array}\end{bmatrix}\]$[A\mid \mathbf{b}]$는 $\text{rank}(A)=\text{rank}(A\mid \mathbf{b})=3$이므로 유일한 해를 가진다.
$[B\mid \mathbf{b}]$는 $\text{rank}(B)=\text{rank}(B\mid \mathbf{b})=2<3$이므로 해가 무수히 많이 존재한다.
$[C\mid \mathbf{b}]$는 $\text{rank}(C)<\text{rank}(C\mid \mathbf{b})$이므로 해가 존재하지 않는다.
2. 벡터 공간 관점
벡터 $\mathbf{b}$가 행렬 $A$의 열공간에 포함되어야 한다.
\[\mathbf{b}\in C(A)\]즉, 행렬 $A$의 열벡터의 선형 결합으로 span되는 공간에 $\mathbf{b}$가 존재해야 한다.
$A$가 정사각 행렬인 경우
정사각 행렬 $A$가 가역 행렬이라면, 어떤 $\mathbf{b}$에 대해서도 항상 유일한 해가 존재한다.
\[\mathbf{x}=A^{-1}\mathbf{b}\]즉, $\text{det}(A)=0$일때 $A\mathbf{x}=\mathbf{b}$는 유일한 해를 가진다.
가우스 소거법 (Gauss Elimination)
연립 선형 방정식을 풀기 위해, 기본 행 연산을 수행하여 첨가 행렬을 Reduced REF로 변형하는 알고리즘이다.
기본 행 연산은 아래와 같으며, 이는 우리가 평소에 연립 방정식을 풀 때 하는 방식과 동일하다.
- 행 교환 $(R_i\leftrightarrow R_j)$: 두 행의 위치를 바꾼다.
- 행 상수배 $(R_i\to cR_i~,~c\neq0)$: 하나의 행 전체에 0이 아닌 상수를 곱한다.
- 행 덧셈 $(R_i\to R_i+cR_j)$: 한 행에 상수배를 한 뒤, 그 결과를 다른 행에 더한다.
Example: 연립 방정식을 RREF로 변환
\[\begin{bmatrix}\begin{array}{ccc|c}1&1&1&6\\2&3&1&14\\1&-1&2&2\end{array}\end{bmatrix}\]위의 방정식을 Reduced REF로 변환하는 과정은 다음과 같다.
\[\begin{bmatrix}\begin{array}{ccc|c}1&1&1&6\\0&1&-1&2\\1&-1&2&2\end{array}\end{bmatrix}\]
- $R_2\rightarrow R_2-2R_1$
\[\begin{bmatrix}\begin{array}{ccc|c}1&1&1&6\\0&1&-1&2\\0&-2&1&-4\end{array}\end{bmatrix}\]
- $R_3\rightarrow R_3-R_1$
\[\begin{bmatrix}\begin{array}{ccc|c}1&1&1&6\\0&1&-1&2\\0&0&-1&0\end{array}\end{bmatrix}\]
- $R_3\rightarrow R_3+2R_1$
행 사다리꼴 (Row Echelon Form)
REF (Row Echelon Form)는 가우스 소거법을 통해 만들어지는 형태로, 이 형태는 다음과 같은 특징을 가진다.
모든 원소가 0인 행은 행렬의 가장 아래쪽에 위치한다.
\[\begin{bmatrix} 1&2&3&4\\0&4&5&6\\0&0&1&7\\ \color{blue}{0}&\color{blue}{0}&\color{blue}{0}&\color{blue}{0} \end{bmatrix}\]0이 아닌 원소를 포함하는 행의 경우, 그 행의 첫 번째 0이 아닌 원소인 Leading entry는 그 위 행의 첫 번째 0이 아닌 원소보다 더 오른쪽에 위치한다.
\[\begin{bmatrix} \color{blue}{1}&2&3&4\\0&\color{blue}{4}&5&6\\0&0&\color{blue}{1}&7\\ 0&0&0&0 \end{bmatrix}\]각 행의 첫 번째 0이 아닌 원소인 Pivot 아래에 있는 모든 원소는 0이다.
\[\begin{bmatrix} 1&2&3&4\\\color{red}{0}&1&5&6\\\color{red}{0}&\color{blue}{0}&1&7\\ \color{red}{0}&\color{blue}{0}&\color{magenta}{0}&0 \end{bmatrix}\]
RREF (Reduced REF)는 REF에서 한 단계 더 나아간 형태로, 가우스 소거법의 최종 목표 형태이다. RREF는 REF의 모든 규칙을 만족하면서 다음의 두 가지 추가 규칙을 따른다.
모든 피벗은 1이어야 한다.
\[\begin{bmatrix} \color{blue}{1}&0&0&4\\0&\color{blue}{1}&0&6\\0&0&\color{blue}{1}&7\\ 0&0&0&0 \end{bmatrix}\]피벗을 포함하는 열에서 피벗을 제외한 나머지 모든 원소는 0이어야 한다.
\[\begin{bmatrix} 1&\color{blue}{0}&\color{magenta}{0}&4\\\color{red}{0}&1&\color{magenta}{0}&6\\\color{red}{0}&\color{blue}{0}&1&7\\ \color{red}{0}&\color{blue}{0}&\color{magenta}{0}&0 \end{bmatrix}\]
연립 선형 방정식 풀기
연립방정식 $A\mathbf{x}=\mathbf{b}$의 일반해(General solution)는 특수해(Particular solution)와 동차해(Homogeneous solution)의 합으로 표현될 수 있다.
\[\mathbf{x}=\mathbf{x}_p+\mathbf{x}_h\]- 특수해: $A\mathbf{x}=\mathbf{b}$를 만족하는 하나의 특정한 해
- 동차해: 동차방정식 (Homogeneous Equation) $A\mathbf{x}=\mathbf{0}$를 만족하는 모든 해들의 집합
동차해를 특수해에 더해도 $A\mathbf{x}=A(\mathbf{x}_p+\mathbf{x}_h)=A\mathbf{x}_p+A\mathbf{x}_h=\mathbf{b}+\mathbf{0}=\mathbf{b}$이기 때문에 방정식의 결과는 변하지 않는다.
$A\mathbf{x}=\mathbf{0}$에서 $\mathbf{x}=\mathbf{0}$은 항상 해가 되기 때문에 자명해(Trivial solution)라고 부르며, 그 외의 해는 비자명해(Non-Trivial soltuion)라고 부른다.
$A\mathbf{x}=\mathbf{0}$에서 행렬 $A$가 Invertible하다면, 해는 영벡터밖에 없다.
\[A\mathbf{x}=\mathbf{0}~\to~A^{-1}A\mathbf{x}=A^{-1}\mathbf{0}~\to~\mathbf{x}=\mathbf{0}\]이것은 변환 후 원점에 도달하는 유일한 벡터는 변환 전에도 원점이었다는 것을 뜻한다.
즉, 역행렬이 존재한다는 것은 행렬 변환이 공간을 찌그러뜨리지 않고 원래 상태를 유지한다는 것을 의미한다.
Example: 연립 방정식 풀기
\[\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}\]1. Solve Non-Homogeneous Equation
\[\begin{bmatrix}\begin{array}{cccc|c}1&0&8&-4&42\\0&1&2&12&8\end{array}\end{bmatrix}\]
- 첨가 행렬로 변환 후 가우스 소거법 수행
\[x_3=0,~x_4=0\]
- 자유 변수들을 원하는 값으로 설정
\[x_2+2x_3+12x_4=8~\to~x_2=8\] \[x_1+8x_3-4x_4=42~\to~x_1=42\]
- 피벗 변수 (Pivot variable)들을 구함
특수해를 구함
\[\mathbf{x}_p=\begin{bmatrix}42\\8\\0\\0\end{bmatrix}\]2. Solve Homogeneous Equation
\[\begin{bmatrix}\begin{array}{cccc|c}1&0&8&-4&0\\0&1&2&12&0\end{array}\end{bmatrix}\]
- 동차 방정식에 대해 가우스 소거법 수행
Pivot column이 아닌 열에 대한 미지수를 자유 변수로 표현
\[x_2=-2x_3-12x_4\] \[x_1=-8x_3+4x_4\]동차해를 구함
\[\mathbf{x}_h=x_3\begin{bmatrix}-8\\-2\\1\\0\end{bmatrix}+x_4\begin{bmatrix}4\\-12\\0\\1\end{bmatrix}\]3. Find General solution
\[\mathbf{x}=\mathbf{x}_p+\mathbf{x}_h=\begin{bmatrix}42\\8\\0\\0\end{bmatrix}+x_3\begin{bmatrix}-8\\-2\\1\\0\end{bmatrix}+x_4\begin{bmatrix}4\\-12\\0\\1\end{bmatrix}\]
왜 일반해를 특수해 + 동차해 형태로 표현할까?
단순히 모든 해를 나열하는 것보다, ‘특수해 + 동차해’로 표현하는 것이 더 효율적이기 때문이다.
특수해는 $A\mathbf{x}=\mathbf{b}$를 만족하는 모든 해 중 하나를 고른 것이다.
즉, 해공간(Solution space) 위의 하나의 벡터인 것이다.
동차해는 $A\mathbf{x}=\mathbf{0}$을 만족하는 모든 벡터를 모은 것이다. 즉, Null Space이다.
영공간을 직선이라고 가정할 때, $\mathbf{x}_p+\mathbf{x}_h$는 직선을 정답을 위치한 공간으로 평행이동하는 것으로 볼 수 있다.
예를 들어, $x+y=1$을 가정해보자.
이 방정식에서 특수해는 $\mathbf{x}_p=(0,1)$, 동차해는 $\mathbf{x}_h=(t,-t)$로 구할 수 있고, 그에 따른 일반해는 아래와 같다.
\[\mathbf{x}=\begin{bmatrix}0\\1\end{bmatrix} +t\begin{bmatrix}1\\-1\end{bmatrix}\]이는 기하학적으로 $y=-x$를 $y$축 방향으로 $1$만큼 평행이동한다는 의미이다.
즉, 기준점 하나 (특수해)와 방향 (동차해)만으로 $x+y=1$의 모든 해를 표현할 수 있다.
- 빨간색 직선은 $x+y=1$ 즉, 해공간을 나타낸다.
- 파란색 직선은 $x+y=0$ 즉, 영공간인 동차해 $\mathbf{x}_h$를 나타낸다.
- 초록색 벡터는 특수해 $\mathbf{x}_p$를 나타낸다.