Iterative Techniques

Iterative Techniques(Jacobi, Gauss-Seidel, SOR) Matrix Form 쉽게 유도하기

 

 라는 Linear Systems of Equations이 있다.

수치적으로 iteration을 수행하는 방법은 Jacobi 방법, Gauss-Seidel 방법, SOR 방법 등이 있다.

 (Jacobi Method)

 (Gauss-Seidel Method)

 (SOR Method)

 Matrix Form으로 이들을 이해해보자. 네 개의 행렬을 도입하자.

 그리고 의 관계가 성립한다. 에서 모든 것이 출발!

 

 Iteration을 행렬을 이용해서 나타내보면 꼴이 된다.

 여기서 와 에 따라 iteration 방법이 다르다.

 유도시 두 가지 Tip이 있다. 이 룰을 잘 기억해보면 유도는 쉽다!

번째 식에서 에 대한 다른 의 요소와 상수들로 나타낸 선형 시스템을 기준으로 하자.

 1- 의 업데이트 시 의 기존값을 이용하지 않으면 우변에 는 나타나지 않는다.

 2- update 이미 된 것을 이용한다면 좌변으로! update 안 된 것을 이용하면 우변으로!

(1) Jacobi Method

  모두 업데이트 안 된 값을 이용한다. , 는 우변에 나타난다. 의 업데이트 시 의 기존값을 이용하지 않으므로 우변에 는 나타나지 않는다.

(2) Gauss-Seidel 방법

 일 때는 는 업데이트 된 값을, 일 때는 업데이트 되지 않은 값을 이용한다. 즉 은 좌변에 는 우변에 나타난다. 의 업데이트 시 의 기존값을 이용하지 않으므로 우변에 는 나타나지 않는다.

(3) Successive Over-Relaxation Method(SOR)

 이 방법에서는 (1), (2)와 달리 의 업데이트 시 의 기존값도 이용하므로 가 우변에 나타나야 한다. 일 때는 는 업데이트 된 값을, 일 때는 업데이트 되지 않은 값을 이용하므로 은 좌변에 는 우변에 나타난다. relaxation factor 를 도입하여 는 배를 곱한 값을, 나머지는 배 곱해 준 값을 이용한다.

 이므로 가 된다. (3)의 설명대로 우선 우변부터 보자.

 

등식을 맞추기 위해 좌변은 다음과 같이 되어야한다.

그렇다면 로 할 수 있다.

따라서 Matrix Form(혹은 Vector Form)으로 일반화한 형태는 아래와 같다.

(1) Jacobi Method

(2) Gauss-Seidel Method

(3) SOR Method