[2주차 Day1] 02강: 가우스 소거법

pengu·2021년 5월 4일

배움기록 선형대수 수학

KDT 배움기록

목록 보기

3/12

노션 기록

선형시스템 $A\rm x = b$ 의 해

해가 하나인 경우(unique solution)
- $3x = 6$
- $\begin{bmatrix} 1 & 3\\ -2 & 1 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} 2\\ 3 \end{bmatrix}$
해가 없는 경우(no solution)
- $0x = 6$
- $\begin{bmatrix} 1 & 3\\ 2 & 6 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} 2\\ 5 \end{bmatrix}$
해가 여러개인 경우(infinitely many solutions)
- $0x = 0$
- $\begin{bmatrix} 1 & 3\\ 2 & 6 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} 2\\ 4 \end{bmatrix}$
$a= 0$ 이면 특이하다
- $ax=b \ (a, b\ 는 \ scalar)$ 의 해가 곧장 나오지 않는다. 왜?
- $a$ 의 역수(inverse)가 존재하지 않는 경우 $a$ 가 특이(singular)하다고 한다.
- $A$ 가 행렬인 경우 역행렬(inverse matrix)이 존재하지 않으면 $A$ 가 특이하다고 한다.
해가 있으면 선형시스템이 consistent하다고 한다.
해가 없으면 선형시스템이 inconsistent하다고 한다.

가우스 소거법(Gauss elimination)

가우스 소거법은 임의의 $m \times n$ 선형시스템의 해를 구하는 가장 대표적인 방법이다

가우스 소거법의 두 단계

가우스 소거법은 다음 두 단계로 수행된다 :

Forward elimination(전방소거법) ⭐

주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다
- 주어진 선형 시스템
  
  $\begin{bmatrix} * & * & *\\ * & * & *\\ * & * & * \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} *\\ *\\ * \end{bmatrix}$
- Forward elimination(전방소거법) 수행 후
  
  $\begin{bmatrix} * & * & *\\ 0 & * & *\\ 0 & 0 & * \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} *\\ *\\ * \end{bmatrix}$
전방소거법을 수행하면 마지막 행을 초등교과수준의 가장 단순한 선형방정식으로 만들 수 있다!
Back-substitution(후방대입법)

아래에서부터 위로 미지수를 실제값으로 대체하여 선형시스템의 해를 구한다
- Forward elimination(전방소거법) 수행 후
  
  $\begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 1\\ 5\\ 1 \end{bmatrix}$
- Back-substitution(후방대입법) 수행 후
  
  $\begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -4\\ 2\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 5\\ 1 \end{bmatrix}$
후방대입법을 수행할 때 아래에서부터 위로 풀어나가는 각 선형방정식은 초등교과수준의 방정식이다!

예제

주어진 선형 시스템

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

$\begin{aligned} &E_1:x_1 + 2x_2 + x_3 = 1\\ &E_2:x_1 + 2x_2 + 3x_3 = 3 \\ &E_3:2x_1 + 3x_2 - x_3 = -3 \end{aligned}$

전방소거법

1행 1열을 기준(pivot)으로 잡기

$E_2 \leftarrow E_2 - E_1$

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

$E_3 \leftarrow E_3 - 2E_1$

$\begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 2\\ 0 & -1 & -3 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 1\\ 2\\ -5 \end{bmatrix}$

2행 2열을 기준(pivot)으로 잡기

$E_2 \leftrightarrow E_3$

$\begin{bmatrix} 1 & 2 & 1\\ 0 & -1 & -3\\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 1\\ -5\\ 2 \end{bmatrix}$

$E_2 \leftarrow -E_2$

$\begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 3\\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 1\\ 5\\ 2 \end{bmatrix}$

3행 3열을 기준(pivot)으로 잡기

$E_3 \leftarrow {1 \over 2} E_3$

$\begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 1\\ 5\\ 1 \end{bmatrix}$

후방대입법

$x_3 = 1$

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

$x_2 = 2$

$\begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1\\ 2\\ 1 \end{bmatrix} = \begin{bmatrix} 1\\ 5\\ 1 \end{bmatrix}$

$x_1 = -4$

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

소거법에 쓰이는 기본행연산(Elementary Row Operations, EROs)

소거법에는 3가지 기본행연산이 있다.

Replacement(치환) : $\rm r_{\it j} \leftarrow \rm r_{\it j} - \it m \ \rm r_{\it i}$
- $j$ 번째 행을 기준행인 $i$ 번째 행을 $m$ 배하여 빼서 업데이트한다
Interchange(교환) : $\rm r_{\it j} \leftrightarrow \rm r_{\it i}$
- $j$ 번째 행과 $i$ 번째 행의 위치를 서로 바꾼다
Scaling(스케일링) : $\rm r_{\it j} \leftarrow \it s \ \rm r_{\it j}$
- $j$ 번째 행을 $s$ 배 스케일링한다

Forward Elimination(전방소거법)의 가치 ⭐

가우스 소거법에서 전방소거법의 가치는 다음과 같다

주어진 선형시스템을 가장 풀기 쉬운 꼴(상삼각형태)로 변형해준다
- Upper triangular form(상삼각형태)
  
  전방소거법은 EROs(기본행연산)을 활용하여 주어진 선형시스템 $A\rm x = b$ 에서 행렬 $A$ 를 upper triangular form으로 만드는 작업을 수행한다

주어진 선형시스템의 rank(랭크)를 알려준다
- rank(랭크)
  
  임의의 행렬 A가 있을 때 이 행렬의 열들로 생성될 수 있는 벡터 공간의 차원을 의미한다
  
  즉, 행렬 A의 열들 중에서 선형 독립인 열들의 최대 개수
  
  의미 있는 식이 몇 개인지 파악할 수 있다