[인공지능 수학 - 선형대수]2강 : 가우스 소거법
가우스 소거법
선형시스템의 해(Solution of a Linear System)
가장 간단한 형태의 linear system(선형 시스템) 문제를 다시 살펴보자.
$3x = 6$
이 선형시스템의 해(solution)는…
$ax = b$(단, a와 b는 스칼라, 즉 숫자)
보통 이런식으로 풀 것이다.
$x = b/a$
간단해보이지만, 어떤 수를 나눈다는것은 프로그래밍적으로 봤을때 위험한 행동이다. 만약 a가 0이된다면 어떻게 할 것인가?
사실 초등 교과과정에서 배운 선형시스템의 해 조차도 간단하지 않다.
해가 하나인 경우(unique solution)
$3x = 6$
$x = 2$
-> consistent
해가 없는 경우(no solution)
$0x = 6$
-> inconsistent
해가 여러개인 경우(infinitely many solution)
$0x = 0$
-> consistent
$ax=b$ 에서…
- $a=0$ 이면 특이하다.
- $ax=b$의 해가 곧장 나오지 않는다.
- a의 역수가 존재하지 않는 경우, a가 특이(singular)하다고 한다.
- 해가 있으면 선형시스템이 consistent하다고 한다.
- 해가 없으면 선형시스템이 inconsistent하다고 한다.
linear system(선형시스템) Ax=b 역시 마찬가지이다.
해가 하나인 경우(unique solution)
$
\begin{bmatrix}
1 & 3\cr
-2 & 1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
2\cr
3
\end{bmatrix}
$
$x_1 = -1$, $x_2 = 1$이 해가 된다.
-> consistent
해가 없는 경우(no solution)
$
\begin{bmatrix}
1 & 3\cr
2 & 6
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
2\cr
5
\end{bmatrix}
$
-> inconsistent
해가 여러개인 경우(infinitely many solution)
$
\begin{bmatrix}
1 & 3\cr
2 & 6
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
2\cr
4
\end{bmatrix}
$
-> consistent
$Ax=b$에서…
$A = 0$이면 특이하다- A의 역행렬(inverse matrix)가 존재하지 않는 경우, A가 특이(singular)하다고 한다.
- 해가 있으면 선형시스템이 consistent하다고 한다.
- 해가 있으면 선형시스템이 consistent하다고 한다.
Gauss elimination(가우스 소거법)
Gauss elimination은 임의의 m*n 선형시스템의 해를 구하는 가장 대표적인 방법이다.
Gauss elimination은 다음의 두 단계로 수행된다.
- Forward elimination(전방소거법): 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다.
- back-substitution(후방대입법) : 아래에서부터 위로 미지수를 실제값으로 대체한다.
1번을 깊게 이해해야 한다! 전방소거법이 제일 중요하다.
Gauss elimination(가우스 소거법): 1) Forward Elimination(전방소거법)
forward elimination은 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형하는 절차이다.
주어진 선형시스템
$
\begin{bmatrix}
1 & 2 & 1\cr
1 & 2 & 3\cr
2 & 3 & -1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
3\cr
-3
\end{bmatrix}
$
$Ax = b$에서, 행렬 A는 대부분 0이 아닌 숫자들로 꽉 차있게 주어진다.
Forward elimination(전방소거법) 수행 후
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 1 & 3\cr
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
5\cr
1
\end{bmatrix}
$
$Ax = b$에서, 행렬 A부분이 소거(elimination)에 의해서, 많은 부분들이 0으로 바뀌게 된다.
맨 마지막줄, 즉 위에서는 3행이 굉장히 단순해진다.
$0x_1 + 0x_2 + x_3 = 1$
$x_3 = 1$
이를 통해 다른 방정식에 대입하여 하나씩 해를 구해나갈 수 있다.
즉, 전방 소거법이란, 전방에 대해 모든 방향에서 0을 최대한 많이 만들어내는 것이다.
0을 많이 만들어내서 행렬에서 숫자가 있는 부분을 역삼각형 모양으로 만들면, 마지막 행을 초등학교 수준의 방정식으로 만들어낼 수 있다.
Gauss elimination(가우스 소거법): 2) Back-substitution(후방대입법)
이제 back-substitution을 이용해 아래에서부터 위로 미지수를 실제값으로 대체하여 선형시스템의 해(solution)을 구할 수 있다.
Forward elimination(전방소거법) 수행 후
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 1 & 3\cr
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
5\cr
1
\end{bmatrix}
$
Back-substitution(후방대치법) 수행 후
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 1 & 3\cr
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
-4\cr
2\cr
1
\end{bmatrix}
=
\begin{bmatrix}
1\cr
5\cr
1
\end{bmatrix}
$
Gauss elimination(가우스 소거법) 실제로 해보기
$
\begin{bmatrix}
1 & 2 & 1\cr
1 & 2 & 3\cr
2 & 3 & -1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
3\cr
-3
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$x_1 + 2x_2 + 3x_3 = 3$ — E2
$2x_1 + 3x_2 - x_3 = 3$ — E3
일때, 다음과 같이 가우스 소거법에 의해 E2의 $x_1$부터 0으로 만든다.
E2 <- E2 - E1
위의 연산을 중학생처럼 수식계산을 하지 말고! 스마트하게 행렬 계산으로 한다. [1 2 1]과 [1 2 3]을 뺄셈 연산 하고, [1]과 [3]을 뺄셈 연산 하면, 다음과 같이 된다.
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 0 & 2\cr
2 & 3 & -1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
2\cr
-3
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$2x_3 = 2$ — E2
$2x_1 + 3x_2 - x_3 = 3$ — E3
이제 E3에 가우스 소거법을 적용하자.
E3 <- E3 - 2*E1
결과는 다음과 같다.
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 0 & 2\cr
0 & -1 & -3
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_2\cr
x_3
\end{bmatrix}
=
\begin{bmatrix}
1\cr
2\cr
-5
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$2x_3 = 2$ — E2
$-x_2 - 3x_3 = -5$ — E3
이제 행렬의 모양을 역삼각형으로 만들어주기 위해, E2와 E3의 위치를 바꾼다!
E2 <-> E3
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & -1 & -3\cr
0 & 0 & 2
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_3\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
1\cr
-5\cr
2
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$-x_2 - 3x_3 = -5$ — E3
$2x_3 = 2$ — E2
이제 E3의 $-x_2$가 기준이 되는데, 가우스 소거법에서는 기준을 만들 때 기준을 1로 만드는 것을 좋아하기 때문에 다음과 같은 작업을 해준다.
E2 <- -E2
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 1 & 3\cr
0 & 0 & 2
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_3\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
1\cr
5\cr
2
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$x_2 + 3x_3 = 5$ — E3
$2x_3 = 2$ — E2
이제 E2의 $2x_3$가 기준이 되는데, 가우스 소거법에서는 기준을 만들 때 기준을 1로 만드는 것을 좋아하기 때문에 다음과 같은 작업을 해준다.
E3 <- 1/2E3
$
\begin{bmatrix}
1 & 2 & 1\cr
0 & 1 & 3\cr
0 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
x_1\cr
x_3\cr
x_2
\end{bmatrix}
=
\begin{bmatrix}
1\cr
5\cr
1
\end{bmatrix}
$
$x_1 + 2x_2 + x_3 = 1$ — E1
$x_2 + 3x_3 = 5$ — E3
$x_3 = 1$ — E2
이제 forward elimination은 끝! 이제 후방대치법을 이용해서 하나하나 값을 대입해가기만 하면 된다.
정리
정리해 보면 forward elimination은 아래의 절차로 수행되었다.
- 1행 1열을 기준(pivot)으로 잡기
- $r_2$ <- $r_2 - r_1$
- $r_3$ <- $r_3 - 2r_1$
- 2행 2열을 기준(pivot)으로 잡기
- $r_2$ <-> $r_3$
- $r_2$ <- $-r_2$
- 3행 3열을 기준(pivot)으로 잡기
- $r_3$ <- $1/2r_3$
이렇게 정리해서 보니 알고리즘으로 코드화가 가능해보인다.
소거법에 쓰이는 Elementary Row Operations (EROs, 기본행연산)
다음은 소거법에 활용된 세가지 기본행연산(elementary row operations, EROs) 이다.
- Replacement(치환) : $r_j$ <- $r_j - mr_i$
- j번째 행을 기준행인 i번째 행을 m배하여 빼서 업데이트한다.
- Interchange(교환) : $r_j$ <-> $r_i$
- j번째 행과 i번째 행의 위치를 서로 바꾼다.
- Scaling(스케일링) : $r_j$ <- $sr_j$
- j번째 행을 s배 스케일링한다.
[중요] Forward Elimination(전방소거법)의 가치
Gauss elimination에서 forward elimination의 가치는 다음과 같다.
- 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변형해 준다.
- 주어진 선형시스템의 rank(랭크)를 알려준다.
- 랭크는 얼마나 어려운지이다.
- rank = 2 : 선형시스템에서 실제로 의미가 있는 식이 2개. 전방소거법을 수행했을 때 A행렬의 행이 0만으로 채워지지 않는 식이 2개.
- rank = 1 : 선형시스템에서 실제로 의미가 있는 식이 1개. 전방소거법을 수행했을 때 A행렬의 행이 0만으로 채워지지 않는 식이 1개.
- 선형시스탬이 해가 있는지(consistent)아니면 해가 없는지(inconsistent) 알려준다.
Upper triangular form(상삼각형태)
Forward elimination(전방소거법)은 EROs(기본행연산)을 활용하여 주어진 선형시스템 $Ax = b$에서 행렬 A를 upper triangular form으로 만드는 작업을 수행한다.