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

Written by metterian
on 

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

가장 간단한 형태의 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$인 경우이다.

해의 존재 여부

예제

해가 하나인 경우(unique solution)

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

image-20210426163347329

해가 없는 경우(no solution)

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

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

image-20210426163023695

해가 여러개인 경우 (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}\]

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

image-20210426163304906

선형시스템의 행렬 표현

\[\begin{align*} x_1 - 2x_2 + x_3 &= 0\\ 2x_2 - 8x_3 &= 8 \\ -4x_1 + 5x_2 + 9x_3 &= -9 \end{align*}\]

첨가행렬(augmented matrix)

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

image-20210426174910314

계수 행렬(coefficient matrix)

image-20210426163905905

첨가행렬의 행 연산

Row equivalent

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

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

image-20210426164639051

첨가행렬의 행 축약(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}\quad \begin{bmatrix} 1&2&3\\ 0&0&1\\ 0&0&0 \end{bmatrix} \quad \begin{bmatrix} 1&2&3&4\\ 0&0&1&5\\ 0&0&0&0 \end{bmatrix} \quad\]

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

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

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


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

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

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

\[\begin{bmatrix} 1 & 0 & 0\\ 0 &1 &0\\ 0 &0 &1 \end{bmatrix}\quad \begin{bmatrix} 1 &0 &0 &1\\ 0 &1 &0 &2\\ 0 &0 &1 &3 \end{bmatrix} \quad \begin{bmatrix} 1 &2 &0 &0 \\ 0 &0 &0 &1\\ 0 &0 &0 &0 \end{bmatrix} \quad \begin{bmatrix} 1 &2 &0 &1\\ 0 &0 &1 &1\\ 0 &0 &0 &0 \end{bmatrix}\]

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


선형시스템의 해법

가우스 소거법(Gauss elimination)

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

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

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

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

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

image-20210426173126584

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

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

image-20210426175645988

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

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

equation (1)

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

image-20210426175935417

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

equation (3)

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

equation (2)

자유변수(free variable)

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

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


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