[Week2/Day1] 선형대수 - 선형시스템의 행렬표현 및 해법

승준·2021년 4월 26일

KDT 프로그래머스 인공지능 데브코스

목록 보기

22/28

선형시스템의 행렬표현 및 해법

가장 간단한 형태의 linear system(선형 시스템) 문제를 살펴 보자.

3x = 6

즉, 가장 단순한 형태의 선형 시스템은 다음과 같다. 이 선형 시스템의 해는 뭘까?

ax = b

선형시스템의 해집합

해가 하나인 경우

$3x = 6$ 와 같은 경우 해가 한 개만 존재 한다.

해가 없는 경우

$0x = 6$ 와 같은 경우 x에 대해 만족하는 해가 존재 하지 않는다. $x = \frac{6}{0}$

해가 여려개인 경우

$0x = 0$ x에 해가 어느것이 와도 해가 되기 때문에 해가 무한개로 존재한다. $x = \frac{0}{0}$

$a = 0$ 이면 특이(Singular)하다.

ax = b의 해가 곧장 나오지 않는다. 왜냐하면 $x = \frac{b}{a}$ 일때, a가 0이 되면 식 자체가 성립하지 않기때문이다.

a의 역수(inverse)가 존재하지 않는 경우, a가 특이(singular) 하다고 한다. 왜냐하면, 모든 수 체계에서 모든 수는 역수가 존재 한다. 즉, 곱에 대한 짝이 존재 한다. 하지만, 0의 경우만 짝이 없다 그래서 특이(singular) 하다고 한다.

해가 없는 경우, 해가 여려개인 경우 모두 $a=0$ 인 경우이다.

해의 존재 여부

해가 있으면 선형시스템이 consistent 하다고 한다.

즉, Consistent(말이 된다) 라는 의미이고, 해가 하나 있는경우와 해가 여려개 있경우가 이에 속한다.
해가 없으면 선형시스템이 inconsistent 하다고 한다.

불능을 의미하고, 해가 없는 경우가 이에 속한다

예제

해가 하나인 경우(unique solution)

\begin{bmatrix} 1 & 3 \\ -2 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \end{bmatrix}

해가 없는 경우(no solution)

\begin{bmatrix}1 & 3 \\2 &6\end{bmatrix}\begin{bmatrix}x_1 \\ x_2\end{bmatrix} = \begin{bmatrix}2 \\5\end{bmatrix}

위 식을 그래프로 표현 하면 다음과 같다. 즉, 두 선형 방정식은 평행을 이루어 해가 존재 하지 않는다.

해가 여러개인 경우 (infinitely many solution)

\begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 4 \end{bmatrix}

위 식을 그래프로 표현 하면 다음과 같다. 이는 두 그래프가 겹치는 형상을 나타낸다. 즉 무수히 많은 해가 존재 하게 된다.

선형시스템의 행렬 표현

첨가행렬(augmented matrix)

계수행렬과 상수벡터를 묶어 아래와 같이 간단히 표현할 수 있다. 이렇게 표현한 행렬을 첨가행렬 (augmented matrix)이라 한다

계수 행렬(coefficient matrix)

첨가행렬의 행 연산

Row equivalent

첨가행렬에 여러 번의 기본 행 연산을 적용하여 다른 행렬로 변환할 수 있는 경우, 두 행렬은 행으로 등가(row equivalent)이다.

두 선형 시스템의 첨가행렬(augmented matrix)이 row equivalent하면 이들은 같은 해집합(solution set)을 갖는다.

첨가행렬의 행 축약(row reduction)

행(row)의 pivot (leading entry)

행에서 맨 왼쪽에 있는 0이 아닌 원소를 pivot이라고 한다 또는, 맨 앞에 있다고 해서 leading entry라고도 한다.

행 사다리꼴 행렬 (row echelon form)

다음 조건을 만족하면, 행 사다리꼴 행렬(row echelon form)이라고 한다.

모든 성분이 0인 행(row)은 맨 아래쪽에 위치

모든 행(row)의 pivot은 위쪽 행(row)보다 오른쪽 열(column)에 있다.

모든 pivot은 1이고, pivot 아래 열의 원소는 모두 0인 상태

다음 행렬은 행 사다리꼴(row echelon form) 행렬이다.

\begin{bmatrix} 1 &4 &5\\ 0 &1 &3\\ 0 &0 &1 \end{bmatrix}\ \begin{bmatrix} 1&2&3\\ 0&0&1\\ 0&0&0 \end{bmatrix} \ \begin{bmatrix} 1&2&3&4\\ 0&0&1&5\\ 0&0&0&0 \end{bmatrix}

반면, 다음 행렬은 행 사다리꼴 행렬이 아니다.

\begin{bmatrix} 2&4&5\\ 0&1&3\\ 0&0&1 \end{bmatrix}\ \begin{bmatrix} 0&0&0\\ 0&1&1 \end{bmatrix} \ \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}

첫 번째 행렬은 1행의 추축성분이 1이 아니고, 두 번째 행렬은 모든 성분이 0인 행이 그렇지 않은 행보다 위에 위치하고, 세 번째 행렬은 위쪽 행의 추축성분이 아래쪽 행의 추축성분보다 오른쪽에 있으므로, 이들 행렬은 행 사다리꼴 행렬이 아니다.

기약 행 사다리꼴 행렬(reduced row echelon from, rref)

모든 추축성분이 해당 열에서 0이 아닌 유일한 성분인 행 사다리꼴 행렬을 기약행 사다리꼴 행렬 (reduced row echelon form matrix) 또는 축약행 사다리꼴 행렬이라 한다.

pivot의 값이 1이고,
행(row) 에서 pivot이 유일한 0이 아닌 원소

다음은 기약행 사다리꼴의 예이다.

\begin{bmatrix} 1 & 0 & 0\\ 0 &1 &0\\ 0 &0 &1 \end{bmatrix}\ \begin{bmatrix} 1 &0 &0 &1\\ 0 &1 &0 &2\\ 0 &0 &1 &3 \end{bmatrix} \ \begin{bmatrix} 1 &2 &0 &0 \\ 0 &0 &0 &1\\ 0 &0 &0 &0 \end{bmatrix} \ \begin{bmatrix} 1 &2 &0 &1\\ 0 &0 &1 &1\\ 0 &0 &0 &0 \end{bmatrix}

pivot의 위 아래 성분이 모두 0이므로, 이들 행렬은 모두 기약행 사다리꼴 행렬이다

선형시스템의 해법

가우스 소거법(Gauss elimination)

row reduction을 통해 선형 시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형 하는 절차이다.

선형 시스템을 첨가행렬(augmented matrix)로 표현 한다.
기약 사다리꼴(reduced row echelon form)이 되도록 행연산
1. 0인 행은 맨 아래 행으로 이동
2. 0이 아닌 행은 pivot이 1이 되도록 행연산
3. pivot이 위 아래 원소가 0이 되로록 행연산
4. 맨 오르쪽 값을 제외하고 모든 원소가 0인 경우, 해가 없음(inconsistent) -> Stop
reduced row echelon form 행렬에서 해를 읽어냄

단일 해를 갖는 선형시스템의 경우

x + y + z = 5\\ 2x + 3y + 5z = 8\\ 4x + 5z = 2

위와 같은 식이 주어 었을 때, 다음 그림과 같이 첨가 행렬을 구한뒤 가우스 소거법을 진행 한다.

위의 경우 $x = 3, y=4, z=-1$ 의 해집합을 얻게 된다.

해가 없는 선형 시스템의 경우

위 문제의 경우 $0 = -1$ 의 해집합을 얻게 되고 해가 없게 된다. 즉 inconsistent인 선형 시스템이다.

무수히 많은 해를 갖는 선형스템의 경우

이 문제 또한, 가우스 소거법을 이용해 풀면 다음과 같다.

마지막 첨가행렬(augmented matrix)에서 1행과 2행은 다음과 같은 방정식으로 나타낼 수 있다.

3행(row)의 원소는 모두 0이기 때문에, 미지수 z의 값은 하나로 고정 되지 않는다. 즉, $z$ 에 어떤 값 $t$ 를 대입 해도 연립선형방적식의 해가 존재한다. 따라서 첫번째 행과 두번 째 행에서 얻은 방정식에 $z = t$ 를 대입 하면 다음과 같이 해를 표현 할 수 있다.

자유변수(free variable)

어떤 값이는 될 수 있는 t와 같은 변수를 자유변수라고 한다. 자유변수 $t$ 에는 어떤 값을 대입해도 해가 된다.

$t$ 에 어떤 값을 대입해도 해가 존재하기 때문에, 이 연립선형방정식에는 해가 무수히 많다. 즉, 자유 변수를 갖는 연립선형방적식의 해는 무수히 많다. 이러한 연린선형방적인은 부정(inconsistent)라고 한다.

행 축약을 통해 얻을 수 있는 것

주어진 선형 시스템을 가장 풀기 쉬운 꼴로 변형 해준다.
주어진 선형 시스템의 rank를 알려준다.
- 즉, 유요한 선형 방정식의 갯수를 알려준다.
선형 시스템이 해가 있는지(consistent) 아니면 해가 없는지 (inconsistent) 알려준다.

승준

내일을 기록하기 위해서 오늘을 기록합니다 🤗

이전 포스트