[수치해석] Gaussian elimination(가우스 소거법)

이번 포스팅에서는 선형대수방정식의 해를 구하는 방법 중 하나인

 

Gaussian elimination(가우스 소거법)에 대해 알아보겠습니다.

(출처: Chapra의 응용수치해석 3rd edition, Steven C. Chapra 저)

 Gaussian elimination(가우스 소거법)이란?

가우스 소거법은 전진소거법을 통해 미지수를 소거하고, 후진대입하는 알고리즘으로써

 

선형대수방정식을 푸는데에 가장 기본이 되는 방법입니다.

 

 Gaussian elimination 하는 방법

예를 들어 아래와 같이 3개의 미지수와 3개의 방정식이 있다고 하면

 

$$a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}=b_{1}$$

$$a_{21}x_{1}+a_{22}x_{2}+a_{23}x_{3}=b_{2}$$

$$a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}=b_{3}$$

 

대수방정식의 형태로 아래와 같은 matrix로 나타낼 수 있습니다.

 

$$\begin{bmatrix}a_{11} & a_{12} & a_{13} & : & b_{1} \\a_{21} & a_{22} & a_{23} & : & b_{2} \\ a_{31} & a_{32} & a_{33} & : & b_{3} \end{bmatrix}$$

 

여기서 전진소거법은 matrix의 하삼각행렬의 성분을 모두 0으로 만드는 작업입니다.

 

즉,

 

$$\begin{bmatrix}a_{11} & a_{12} & a_{13} & : & b_{1} \\0 & a_{22}' & a_{23}' & : & b_{2}' \\ 0 & 0 & a_{33}'' & : & b_{3}'' \end{bmatrix}$$

 

의 형태로 만드는 작업이죠.

 

이 때, 연립방정식의 해 중 하나인 $x_{3} = b_{3}''/a_{33}''$를

 

아주 간단히 구할 수 있고, 이를 2번째 식, 1번째 식에 차례로 대입하는 것을

 

후진대입법이라고 하며, 이와 같은 방식으로 모든 해를 구할 수 있습니다.

 

$$x_{3} = b_{3}''/a_{33}''$$

$$x_{2} = (b_{2}'-a_{23}'x_{3})/a_{22}'$$

$$x_{1} = (b_{1}-a_{13}x_{3}-a_{12}x_{2})/a_{11}$$

 

 주의할 점

처음 전진소거 시에 $a_{21}/a_{11}$을 첫번째 식에 곱해서 나온 결과를

 

두번째 식에 곱하게 되는데,

 

이 때 $a_{11}$이 0에 가까운 소수라면 반올림 오차에 의해 경우에 따라

 

무한대에 가까운 수가 나오기 때문에 꼭 피해줘야합니다.

 

따라서 각각의 행을 정규화하기 전에 각 피봇원소가 속한 열에서 피봇원소 아래의

 

계수들 중에서 절대값이 가장 큰 것을 찾아 그 계수가 포함된 행의 위치를 바꾼 후

 

가장 큰 원소가 피봇원소가 되도록 방정식의 순서를 조절하는 방법을

 

Pivoting(피봇팅)이라고 하며, 이 방법을 사용하면

 

나눗셈에서 0으로 나누는 것을 피할 수 있습니다.

 

 Pivoting(피봇팅) 예시

아래와 같은 연립방정식이 있다고 가정해봅시다.

 

$$0.0003x_{1}+3.0000x_{2}=2.0001$$

$$1.0000x_{1}+1.0000x_{2}=1.0000$$

 

이 때, $a_{11}=0.0003$으로 0에 가까워 피봇팅이 필요합니다. 

 

큰 피봇원소를 지닌 행을 정규화하여 식의 순서를 바꿉니다.

 

$$1.0000x_{1}+1.0000x_{2}=1.0000$$

$$0.0003x_{1}+3.0000x_{2}=2.0001$$

 

그 다음 전진소거와 후진대입을 통해 $x_{2} = 2/3$이라는 답을

 

쉽게 얻을 수 있습니다.