[수치해석] 가우스-자이델(Gauss-Seidel) 법

이번 포스팅에서는 선형대수방정식을 푸는 반복법 중 하나인

 

가우스-자이델(Gauss-seidel)법에 대해 알아보겠습니다.

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

 가우스-자이델(Gauss-Seidel)법

가우스-자이델 기법은 선형대수방정식을 푸는 반복법 중의 하나로,

 

제법 보편적으로 사용되는 방법입니다.

 

이 방법은 해를 구하기 위해 미지수 $x$을 가정해야 하며,

 

이를 연립방정식을 구성하는 각각 다른 방정식에 대입시켜

 

해를 수렴시켜가는 방법입니다.

 

초기값은 흔히 0으로 많이 시작합니다.

 

아래와 같이 주어지는 방정식이 있다고 해보죠.

 

$$[A]\left\{x\right\}=\left\{b\right\}$$

 

만약 이 방정식이 3x3라면, 각 해를 구하기 위해 식을 아래와 같이 변형할 수 있습니다.

 

$$x^{j}_{1}=\frac{b_{1}-a_{12}x_{2}^{j-1}-a_{13}x_{3}^{j-1}}{a_{11}}$$

$$x^{j}_{2}=\frac{b_{2}-a_{21}x_{1}^{j-1}-a_{23}x_{3}^{j-1}}{a_{22}}$$

$$x^{j}_{3}=\frac{b_{3}-a_{31}x_{1}^{j-1}-a_{32}x_{2}^{j-1}}{a_{33}}$$

 

즉, 구하고자 하는 해를 좌항에 두고 나머지를 모두 우항으로 옮긴 형태입니다.

 

이때 $j$는 반복횟수입니다.

 가우스-자이델(Gauss-Seidel)법 예제

아래와 같은 연립방정식을 풀어보죠.

 

$$3x_{1}-0.1x_{2}-0.2x_{3}=7.85$$

$$0.1x_{1}+7x_{2}-0.3x_{3}=-19.3$$

$$0.3x_{1}-0.2x_{2}+10x_{3}=71.4$$

 

참고로 위 방정식의 해는 각각 $x_{1} = 3, x_{2} = -2.5, x_{3} = 7$입니다.

 

각 해를 구하기 위해 식을 정리해봅시다.

 

$$x_{1}=\frac{7.85+0.1x_{2}+0.2x_{3}}{3} \tag{1}$$

$$x_{2}=\frac{-19.3-0.1x_{1}+0.3x_{3}}{7} \tag{2}$$

$$x_{3}=\frac{71.4-0.3x_{1}+0.2x_{2}}{10} \tag{3}$$

 

여기서 $x_{2}, x_{3}$의 초기값을 각각 0으로 가정하고 식 (1)을 풀어보죠.

 

1회 반복

 

$$x_{1}=\frac{7.85+0.1(0)+0.2(0)}{3}=2.6167$$

 

여기서 계산된 $x_{1}$의 초기값과 $x_{3}=0$을 식(2)에 대입합니다.

 

$$x_{2}=\frac{-19.3-0.1(2.6167)+0.3(0)}{7}=-2.7945$$

 

다시 여기서 계산된 $x_{1}, x_{2}$의 값을 식(3)에 대입합니다.

 

$$x_{3}=\frac{71.4-0.3(2.6167)+0.2(-2.7945)}{10}=7.0056$$

 

이렇게 1회차 반복이 완료됩니다.

 

2회 반복

 

1회차에 계산된 값이 있으니 다시 식 (1)에 대입하여 계산합니다.

 

$$x_{1}=\frac{7.85+0.1(-2.7945)+0.2(7.0056)}{3}=2.9906$$

 

$$x_{2}=\frac{-19.3-0.1(2.9906)+0.3(7.0056)}{7}=-2.4996$$

 

$$x_{3}=\frac{71.4-0.3(2.9906)+0.2(-2.4996)}{10}=7.0002$$

 

2회만 반복했을 뿐인데도 정해에 제법 가까워 졌습니다.

 

위와 같은 반복으로 허용오차 이내에 진입하게 되면

 

반복을 종료하고 그 결과를 해로 결정하는 방법이 Gauss-Seidel법입니다.

 

 

여기까지 Gauss-Seidel법에 대해 알아보았습니다.