가우스 소거법

가우스 소거법 m by n 선형시스템의 해를 구하는 대표적인 방법이다.

해가 나오는 경우는 세 가지가 있다.
$ax = b$

해가 하나인 경우

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

일반적인 경우로 하나의 해가 나온다.

해가 없는 경우

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

두 직선이 평행한 경우로 해가 없다.

해가 여러 개인 경우

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

두 직선이 같은 경우로 해가 무수히 많다.

가우스소거법을 사용하면 직선을 그리지 않고 해를 알 수 있다.
가우스소거법은 두 과정을 거쳐 진행된다.

1. 전방소거법(Forward Elimiation)
   선형시스템을 아래로 갈수록 점차 더 단순한 형태의 선형방정식을 가지도록 변형하는 절차

$\begin{vmatrix} a & b & c \\ d & e & f \\ g & h & i\end{vmatrix}\begin{vmatrix} x_1 \\ x_2 \\ x_3\end{vmatrix}=\begin{vmatrix} n \\ m \\ l\end{vmatrix} \to \begin{vmatrix} 1 & b' & c' \\ 0 & 1 & f' \\ 0 & 0 & 1\end{vmatrix}\begin{vmatrix} x_1 \\ x_2 \\ x_3\end{vmatrix}=\begin{vmatrix} n' \\ m' \\ l'\end{vmatrix}$

선형방정식 $E_1, E2, E3$ 를 연산하여 오른쪽과 같은 상삼각행렬로 만들어준다.

연산은 다음과 같다.

1. 치환(Replacement)
   $E_j \gets E_j -mE_i$
   $E_1$과 $E_2$를 치환하면 $E_1 = E_1 - (a-1)/d \,E_2$
   $E_1$의 a를 1로 만들 수 있다.

2. 교환(Interchange)
   $E_j \leftrightarrow E_i$
   $E_j$와 $E_i$의 위치를 바꿔준다.

3. 스케일링(Scailing)
   $E_j \gets sE_j$
   $E_j$에 s를 곱해 치환, 교환을 쉽게 하기 위해 스케일링해준다.

2. 후방대입법(Back Substitution)
   전방소거법으로 구한 상삼각행렬의 선형방정식을 아래에서 위로 풀어나가며 선형시스템의 해를 구하는 절차
   $\begin{vmatrix} 1 & b' & c' \\ 0 & 1 & f' \\ 0 & 0 & 1\end{vmatrix}\begin{vmatrix} x_1 \\ x_2 \\ x_3\end{vmatrix}=\begin{vmatrix} n' \\ m' \\ l'\end{vmatrix} \to \begin{vmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{vmatrix}\begin{vmatrix} x_1 \\ x_2 \\ x_3\end{vmatrix}=\begin{vmatrix} n'' \\ m'' \\ l''\end{vmatrix}$

전방소거법보다 간단한 방법으로 아래 선형방정식을 스케일링하여 바로 위의 선형방정식을 치환하여 주대각 성분이 모두 1인 대각행렬을 만든다.