선형방정식의 반복해법 Iterative Methods for Solving Linear Systems

Ax=b 에서 A의 대각 행렬에 0이 포함되어 있지 않은 경우, 해 x를 계산하는 방법에는 크게 직접법(direct method)와 반복법(iterative method)이 있다. 전자는 단 한번의 행렬 계산으로 정확한 해를 구하는 반면, 후자는 행렬 계산을 반복하여 근사해(approximate solution)를 구하는 것이다. 행렬의 크기가 작다면 전자가 효과적이지만 행렬의 크기가 커지면 후자가 효과적이다.

 

직접법의 가장 대표적인 방법으로 가우스 소거법(Gauss elimination method)을 들 수가 있다면, 반복법으로는 야코비 기법(Jacobi iteration method)을 들 수 있다.

 

 

 

Jacobi Iteration

---

 

야코비 방법은 두 가지의 가정으로부터 출발한다. (1) 해당 방정식이 유일한 해(unique solution)를 갖고 있으며, (2) 계수 행렬(coefficient matrix) A의 대각 성분이 0을 갖고 있지 않다는 것이다.

 

이 기법의 기본개념은 행렬 A를 대각 성분 D와 그 나머지 R로 분해하여 Dx^k+1 = b-Rx^k 형태의 반복식으로 전환하여 해 x를 반복계산을 통해 구하는 것이다. 반복계산은 초기에 x를 임의의 값으로 추정하여 반복식의 우변에 대입하여 좌변의 x를 구하고, 이 값을 다시 반복식의 우변에 대입하여 새로운 x를 구하는 반복과정을 수행한다. 반복계산은 x가 원하는 허용오차(allowable error) 범위에 들어오게 되면 멈추게 된다.

 

 

 

 

식을 각 변수에 대하여 정리한 다음, 초기임의값(initial approximation)을 추정하여 각 식에 대입하면 각 변수는 결과값을 새로 얻게 된다. 이 값들을 반복적으로 대입하면(iteration) 해가 특정 값에 수렴(converge)하게 된다.

야코비 기법은 가장 기본적인 반복법으로써, 반복계산의 회수를 줄여 신속하게 계산하기 위해 여러 가지 유형의 변형된 반복법들이 소개되어 있다. 가장 대표적인 변형된 반복법으로 가우스-자이델법(Gauss-Seidel Method)이 있다.

 

 

 

Gauss-Seidel Method

---

 

야코비 기법은 n번째 추정(n^th approximation)에서 얻어진 각 x_i의 값이 (n+1)번째 추정을 하기 전까지 그대로 저장되어 있다. 그러나 가우스-자이델 기법의 경우에는 새로운 x_i가 얻어지자마자 다음 변수에 대한 계산에 새로 얻어진 값을 넣어 계산한다. 결과적으로, 해의 수렴 속도가 더 빨라지게 된다.

그러나 위의 두 가지 방법이 어느 방정식에나 사용될 수 있는 것은 아니다. Divergence가 0인(수렴하는) 방정식에만 사용이 가능하다. 계수 행렬 A가 대각선 지배 행렬(strictly diagonally dominant matrix)일 때에만 위 두가지 방법에서 수렴해가 나온다. 즉, 계수 행렬의 대각 성분의 절대값이 같은 행의 모든 성분의 절대값의 합보다 클 때만 수렴한다.

 

Definition of Strictly Diagonally Dominant Matrix

An (nxn) matrix A is strictly diagonally dominant if the absolute value of each entry on the main diagonal is greater than the sum of the absolute values of the other entries in the same row. That is,

 

 

위에 따라서 선형연립방정식에서 계수 행렬이 대각선 지배 행렬일 경우 어떠한 초기값에 대해서도 야코비와 가우스-자이델법으로 수렴해를 구할 수 있다는 아래의 theorem이 정리된다. 그러나 이는 충분조건이지 필요조건이 아니다. 반드시 대각선 지배 행렬이 아니어도 특정 초기값에 대하여 수렴해가 나올 수 있다.

 

 

Convergence of the Jacobi and Gauss-Seidel Methods

 

If A is strictly diagonally dominant, then the system of linear equations given by Ax=b has a unique solution to which the Jacobi method and the Gauss-Seidel method will converge for any initial approximation.

 

 

http://college.cengage.com/mathematics/larson/elementary_linear/5e/students/ch08-10/chap_10_2.pdf