Iterative methods : Jacobi, GS, SOR

• Iterative methods
  • Convergence
• Richardson method
  • Convergence
• Jacobi method
• Gauss-Seidel Method
• SOR (Successive OverRelaxation)

Iterative methods

수치선형대수 수업에서 배운 내용을 조금 정리해 보려고 한다. 구체적으로, 행렬 $A$와 벡터 $b$에 대해, $Ax = b$를 푸는 여러 방법들 중 iterative methods를 몇 포스팅에 걸쳐 다루어 본다.

우선, 행렬 $A$ 의 inverse를 구하기가 쉽다면 $x = A^{-1} b$ 를 계산하면 간단하다. 당연히 이상한 방법을 필요로 하는 이유는 이 inverse를 구하기가 어렵기 때문이다. 어렵다는 것은 두 가지 의미가 있는데…

1. Numerically unstable 해서 수치 오차가 우려되는 경우
2. Complexity 관점에서, 계산 시간이 큰 경우 두 경우 모두 “계산이 어렵다” 라는 말로 퉁치기로 하자.

한번에 정확히 $x = A^{-1} b$를 구하는 대신, 임의의 $x_0$에서 시작해서, $x_i$들의 sequence가 $x$로 수렴하게 하려고 한다. 이때 $x_{i+1}$ 은 $x_i$ 및 그 이전 항들을 이용하여 귀납적으로 연산할 수 있어야 하고, 각 step은 계산이 쉬워야 할 것이다.

어떤 행렬 $Q$에 대해, $A = Q - (Q - A)$ 로 쓰면, $Ax = b$의 해 $x$는 $Qx = (Q - A) x + b$ 를 만족해야 할 것이다. 따라서, $Qx_k = (Q - A)x_{k-1} + b$ 를 우리의 iteration으로 쓸 것이다.

또한, $A = L + D + U$ 를, $L$을 diagonal 아래의 (strictly) lower triangular한 행렬로, $U$를 그 반대의 upper triangluar 행렬로, $D$를 $A$의 diagonal로 잡기로 한다.

이번 포스팅에서는 가급적 증명들을 생략하고 method들에 대해서만 간략히 살펴보고, 증명은 나중에 여력이 되면 쓸 예정이다.

Convergence

위 iteration이 올바른 답을 낸다는 사실은 상당히 nontrivial하다. 우선 $x_k = Q^{-1}((Q-A)x_{k-1} + b) = f(x_{k-1})$ 이라고 쓰면, 우리의 목표는 $f$의 fixed point를 찾는 것임을 알 수 있다. 이 iteration은 사실 이러한 $f$에 대해 FPI (Fixed Point Iteration) 을 수행하는 과정으로 이해할 수 있다. FPI가 언제 어떻게 수렴하는지를 이해하는 것은 쉽지 않은데, $f$가 Lipschitz continuous w/ $L < 1$ 임을 보이거나, 훨씬 더 어려운 수학적 내용들을 공부해야 한다. 작년에 최적화 이론 수업에서 이러한 수렴 정리들을 배웠는데, Averaged operator에 대한 수렴정리가 상당히 어렵지만 재밌었던 기억이 있다. 직접 링크를 거는 것이 적절한지 모르겠는데, Ernest K. Ryu 교수님의 최적화 이론 수업 자료가 웹사이트에 공개되어 있으므로 찾아보면 (해석개론 정도의 해석학 지식 배경 위에서) 이해할 수 있을 것 같다. (Monotone Operators and Base Splitting Schemes 의 Theorem 1 부분을 확인하면 된다)

Richardson method

Richardson method는 $Q = \frac{1}{w}I$ 를 쓰는 방법이다. 즉, $x_k = (I - wA) x_{k-1} + wb$ 를 생각할 것이다. $I - wA$를 한번 구한 다음부터는 계속 행렬-벡터 곱셈만 반복해도 되므로, 각 step이 $O(n^2)$이고, $I - wA$를 한번 구하는데 $O(n^2)$ 이 들게 되므로 iteration 횟수 $m$에 대해 $O(n^2 m)$ 시간에 연산할 수 있다.

Convergence

$x_* - x_i$ 를 직접 계산하면, $(I - wA)x_* + wb - (I - wA)x_{i-1} - wb$ 가 되고, 이를 반복적으로 적용하면 다음 식을 얻는다. \(x_* - x_k = (I - wA)^k (x_* - x_0)\) 편의상, $x_0$ 을 영벡터로 놓으면, 우리는 다음과 같은 식을 얻는다. \(\norm{x_* - x_k} = \norm{(I - wA)^k x_*} \leq \norm{I - wA}^k \norm{x_*}\) 이제 $\norm{I - wA}$ 부분을 evaluate 해야 함을 알 수 있고, 선형대수의 지식을 잘 써서 계산해 보면 수렴 속도는 $\lambda_n / \lambda_1$, 즉 가장 큰 eigenvalue와 가장 작은 eigenvalue의 비에 의존함을 파악할 수 있다.

Jacobi method

Gauss-Seidel Method

SOR (Successive OverRelaxation)