[선형대수] 가우스 소거법
on
가우스 소거법
들어가며
임의의 원소에 대해 연산을 해도 원래 값이 바뀌지 않게 하는 원소를 그 연산에 대한 항등 원이라 한댜 실수에서 덧셈에 대한 항등원은 0, 곱셈에 대한 항등원은 1이다.
\[a + 0 = a \ (\text{덧셈에 대한 항등원 0)}\\ a \times 1 = a \ \text{(곱셈에 대한 항등원 1)}\]어떤 원소 a에 대해 연산을 하여 항등원을 만드는 원소를 그 연산에 대한 역원 이라고 한다.
\[a \times (\frac{1}{a}) = 1 \ \text{(곱셈에 대한 a의 역원} \frac{1}{a})\]가우스 소거법
Gauss elimination은 임의의 m x n 선형 시스템의 해를 구하는 가장 대표적인 방법이다.
다음 두 단계로 진행 된다.
- Forward elimination(전방 소거법): 주어진 선형 시스템을 아래로 갈수록 더 단순한 형태의 선형 방정식을 가지도록 변현한다.
- Back-subtistution(후방 대입법): 아래에서 위로 미지수를 실제값으로 대체한다.
1. Forward Elimination(전방 소거법)
forward elminiation은 주어진 선형 시스템을 아래로 갈 수록 더 단순한 형태의 선형 방정식을 가지로도록 변형하는 절차이다. 즉, 행 사다리꼴(row echelon form)을 만들도록 변형 하는 것이다.
다음 행렬은 행 사다리꼴(row echelon form) 행렬이다.
\[\begin{bmatrix} 1 &4 &5\\ 0 &1 &3\\ 0 &0 &1 \end{bmatrix}\; \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} \; = \begin{bmatrix} *\\ *\\ * \end{bmatrix} \;\]가장 마지막 행의 값을 구하면 $x_3 = *$ 라는 식을 구하게 되고 아주 간단하게 미지수를 구할 수 있게 된다. 이렇게 구한 $x_3$를 갖고 두 번째 선형 방정식 $x_2 + 3x_3$을 쉽게 구할 수 있다. 이런식으로 밑에서 부터 위로 식을 구하게 되고, 전방(왼쪽)에 최대한 많은 0을 배치하는 것을 전방 소거법이라고 한다.
Foward(전방)
- 왼쪽 $\rightarrow$ 오른쪽
- 위 $\rightarrow$ 아래
위 같은 방향을 전방이라고 정의한다.
예제1
\[\begin{matrix} 2x_1 + &2x_2 + &4x_3 &= 18\\ x_1 + &3x_2 + &2x_3 &= 13 \\ 3x_1 +& x_2 + &3x_3& = 14\\ \end{matrix}\]풀이
우선 연립선형방정식을 첨가 행렬(augmented matrix)로 표현 한다.
\[\left[ \begin{array}{ccc|c} 2& 2 &4 & 18\\ 1 & 3 &2 & 13 \\ 3& 1 &3& 14\\ \end{array} \right]\]
위 전방 소거법을 통해 얻어진 기약행 사다리꼴 행렬로 부터 해가 $x_1 = 1, x_2 =2, x_3 =3$ 임을 알 수 있다.
예제2
불능(inconsistent)인 경우의 문제를 한번 풀어 보자
\[\begin{matrix} &4x_2 + &x_3 &= 2\\ 2x_1 + &6x_2 - &2x_3 &= 3 \\ 4x_1 +& 8x_2 - &5x_3& = 4\\ \end{matrix}\]먼저 위 연립선형방정식을 첨가 행렬로 표현 한다.
\[\left[ \begin{array}{ccc|c} 0& 4 &1 & 2\\ 2 & 6 &-2 & 3 \\ 4& 8 &-5& 4\\ \end{array} \right]\]다음과 같이 forward elmination을 적용하여 row echelon form을 얻는다.
3행(row)의 성분은 모두 0이기 때문에, 미지수 $x_3$의 값은 하나로 고정되지 않는다. $x_3$에 어 떤 값 $t$를 대입해도 연립선형방정식의 해가 존재한다. 따라서 첫 번째 행과 두 번째 행 에서 얻은 방정식에 $x_3 = t$를 대입하면 다음과 같이 해를 표현할 수 있다.
\[x_1 = \frac{7}{4}t, \ x_2 = -\frac{1}{4}t + \frac{1}{2},\ x_3 = t\]$x_3$와 같이 자유변수 $t$를 갖는 연립선형방정식의 해는 무수히 많다. 이러한 연립선형방정식을 부정(inconsistent)이라고 한다.
Back-subsitution (후방대입법)
위의 예제2 에서 얻은 $x_1, x_2 , x_3$ 미지수들을 퉁해 실제값을 대체하여 선형 시스템의 해를 구할 수 있다. 1행의 식을 쓰면, $x_1 + -\frac{7}{4}x_3 = 0$ 이고. $x_3$의 값을 알아야 $x_1$의 값을 구할 수 있다. 마찬가지로 2행의 경우도, $x_2 +\frac{1}{2}x_3 = \frac{1}{2}$ 임으로 $x_3$의 값을 알아 $x_2$의 값을 구할 수 있었다. 이렇게 3행에 존재하는 $x_3$를 구해 밑에서 부터 위 행의 값들을 구해나가는 과정을 후방 대입법이라고 한다.
소거법에 쓰이는 Elementary Row Operations(EROs, 기본행연산)
다음 소거법에 활용된 세가지 기본행연산(Elementary Row Operations, 기본행연산)이다.
- Replacement(치환): $r_j \leftarrow r_j - mr_i$
- $j$ 번째 행을 기준행인 $i$ 번째 행을 $m$배하여 빼서 업데이트 한다.
- Interchange(교환): $r_j \leftrightarrow r_i$
- $j$번째 행과 $i$번째 행의 위치를 서로 바꾼다.
- Scaling(스케일링): $r_j \leftarrow sr_j$
- $j$번째 행을 s배 스케일링한다.
Foward Elmination(전방소거법)의 가치
- 주어진 선형 시스템을 가장 풀기 쉬운 꼴로 변형해준다.
- 주어진 시스템의 rank를 알려준다.
- 선형시스템이 불능인지 consistent인지 알려준다.
Upper triangluar from(상삼각형태)
전방 소거법은 EROs(기본행연산)을 활용하여 주어진 선형시스템 $Ax=b$에서 행렬 $A$를 upper triangluar form으로 만드는 작업을 수행한다. 즉, 미지수를 계산하기 가장 쉬운 형태로 만들어 준다.