[선형대수학] 7. 가우스-사이델 방법 (Gauss-Seidel method)

2011. 01. 14

우리가 지금까지 연립방정식을 해를 적은 공간으로 보다 빠르게 구하기 위하여
연립방정식의 해를 구하는 다양한 방법들을 공부 했었다.
한번 기억을 가다 듬어 보자

LU분해법, 두리틀분해, 콜레스키 분해 등등   "분해법" 대해서 공부하였다.
가우스 소거법, 가우스 조르단 소거법 등등   "소거법" 대해서 공부하였다.

하지만 이런 소거법과 분해법을 이용하기 위해서는 다양한 제약사항이 따르곤 했다.




그렇다면 이런 제약사항에 관여하지 않아서
소거법을 이용할 수 없다면 우리는 어떻게 연립방정식을 풀어야 할가?

그 대안으로는 조사법 & 반복법 학습 등이 있다.
가우스와 루트비히 폰 사이델이라는 사람은 이미 소거법의 대안으로 을
가우스-사이델 방법이라는 것을 내 놓아 우리를 편하게 해준다.

우리가 이번시간에 배울 내용은 그 가우스-사이델 방법에 대해서 알아 볼것이다.





그럼 그 가우스-사이델 방법은 어떤 것인가요?

가우스-사이델 방법은
반복법(Iterative method) + 근사법(approximate method)를 접목시킨것이다.

쉽게 이해하기 위해서는 패턴인식에서 기대치 최대화(EM) 알고리즘을 생각하면 쉽게 떠오를 것이다.
이 과정 역시

(첫째) 초기값을 설정해주고

(둘째) 이 초기값을 대입하여 새로운 연립방정식을 만들어 내고

(셋째) 둘째 과정을 지속적으로 반복하다 보면 어느 일정한 값에 수렴하게 되고

(넷째) 마지막으로 그 수렴값을 해로 인정하는 것이다.

어떻게 이해가 되셨습니까?




나는 EM알고리즘을 알지도 못한데다가 위의 글도 이해가 안가요 예를 들어 설명해주세요 !

예를 들어 설명해 보겠다.
다음과 같은 연립방정식이 있다.

이 연립방정식을 직접 풀어본다면

X1 = 3
X2 = -2.5
X3 = 7

이 바로 나온다.
하지만 미지수의 수치가 천문학 수치에 소수점까지 있다면 우린 쉽게 구하기는 어렵다.
그래서 보다 빠르게 접근하기 위하여 가우스-사이델 방식을 이용할 것이다.

가우스 사이델 방식을 이용하기 위하여

(첫째) 초기값을 설정

 초기값을 X2=X3=0 으로 설정 할 것이다.
여기서 초기값 설정은 굳이 0으로 안하고 자유롭게 설정해도 된다.
(하지만 이것은 알아야 한다 이 초기값에 따라 해가 빠르게 나올수 있고 늦게 나올 수 있다.)
여기서는 X2 와 X3의 초기값을 0으로 설정해놓았다.

(둘째) 초기값을 토대로 연립방정식을 풀어본다.

X2와 X3의 값을 알고 있으니 이 수식에 대입하여 연립방정식을 풀어본다.

1) X1의 값을 구해보니 2.616667이 나왔다.

2) X2 값을 구해보니 -2.794524 가 나왔다.

3) X3 값을 구해보니 7.005610가 나왔다.

(셋째) 수렴할 때 까지 반복한다.

1) 첫번째
 X2 와 X3 의 값을 각각 0으로 설정 했었다.

2) 두번째 
  X2와 X3의 값을 위 식에서 나온 -2.794524 와 7.005610 으로 설정한다.
.
.
.
N-1) N-1번째
  X2와 X3 의 값이  - 2.455532 와  7.00000119

N) N번째
  X2와 X3 의 값이  - 2.455555 와  7.00000112
.
.
.

(넷째)수렴값을 해로 인정

 급격하게 변하다가 일정 수치로 수렴하는 구간이 있다.
이를 답으로 설정


 

아 이제 이해가 가네요 ^^ 그런데 만약 수렴을 안하는 경우는 어떻하나요?

그래서 이를 개선하기 위하여 이완법을 만들어 놓았다.

가우스 사이델법을 약간 수렴성 향상을 위하여 만들어 놓은것으로
가중평균값이라는 것을 사용한다.

여기서 가중치 λ를 임의로 설정한다 0<  λ < 2의 구간을 두어서

if(λ = 1) 
    수정되지 않는다.

else if (0<λ<1)
   하 이완법

else 즉(1<λ<2)
   상 이완법

방식으로 한다. (상이완법, 하이완법에 나중에 ^^;;)



아 그럼 이런 반복법에는 가우스 - 사이델 방법밖에 없나요?

가우스-사이델 방식 뿐만 아니라 자코비(Jacobi) 반복법도 있습니다.
가우스 사이델 방법과 다른 점을 자코비 방식은 다음을 위해 저장을 해둠으로써 더 유용한 경우도 있습니다.
하지만 일반적으로 가우스-사이델 방식을 많이 사용합니다.




이제 내용과 의미를 아셨다면 실전에 사용할 수 있도록 코딩 들어가셔야죠 ^^

도움이 되셨다면 리플 부탁드립니다 !
리플 하나가 큰 힘이 된답니다 ^^