반복법

수치해석 시뮬레이션 마지막 수정: 2026-07-08 04:35:10

1. 개요[편집]

정확한 답을 한 번에 구할 수 없다면, 대충 찍고 계속 고쳐나가면 되잖아? 수렴은 신에게 맡긴다.

반복법(iterative methods)은 선형 연립방정식 $A\mathbf{x} = \mathbf{b}$ 를 직접 풀지 않고, 초기 추측값 $\mathbf{x}^{(0)}$ 에서 출발해 점점 참해에 가까워지는 근사해 수열 $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \dots$ 를 만들어가는 수치해법이다. 가우스 소거법이나 LU 분해 같은 직접법(direct method)이 유한 번의 연산으로 정확한 답을 뱉는 것과 대조적으로, 반복법은 원하는 정밀도에 도달할 때까지 같은 갱신 공식을 계속 돌린다.

왜 이런 귀찮은 짓을 하냐고? 희소행렬이 답이다. 전산유체역학이나 구조해석에서 나오는 계수행렬은 미지수가 수백만 개인데도 대부분의 성분이 0인 희소행렬이다. 직접법을 쓰면 채움현상으로 메모리가 폭발하지만, 반복법은 행렬-벡터 곱만 반복하면 되므로 희소성을 고스란히 살릴 수 있다.¹ 대규모 시뮬레이션의 선형 솔버가 거의 다 반복법인 이유다.

2. 기본 아이디어[편집]

계수행렬을 $A = M - N$ 처럼 두 부분으로 쪼개는(splitting) 것에서 출발한다. 그러면 $A\mathbf{x} = \mathbf{b}$ 는 다음 고정점 반복(fixed-point iteration) 형태가 된다.

M\mathbf{x}^{(k+1)} = N\mathbf{x}^{(k)} + \mathbf{b}

핵심은 $M$ 을 풀기 쉬운 행렬로 고르는 것이다. $M$ 이 대각행렬이거나 삼각행렬이면 매 반복에서 $\mathbf{x}^{(k+1)}$ 을 싸게 구할 수 있다. 어떻게 쪼개느냐에 따라 야코비, 가우스-자이델, SOR로 갈린다. $A = D + L + U$ ( $D$ 는 대각, $L$ 은 엄격 하삼각, $U$ 는 엄격 상삼각)로 분해해두면 이야기가 깔끔해진다.

3. 야코비 · 가우스-자이델 · SOR[편집]

야코비법(Jacobi method)은 $M = D$ 로 잡는다. 즉 대각 성분만 남겨서 나눈다.

x_i^{(k+1)} = \frac{1}{a_{ii}}\left( b_i - \sum_{j \ne i} a_{ij}\, x_j^{(k)} \right)

모든 성분이 오직 이전 단계 값 $\mathbf{x}^{(k)}$ 만 참조하므로 계산이 완전히 독립적이다. 덕분에 병렬 컴퓨팅과 GPU 컴퓨팅에 궁합이 환상적이다. 단점은 수렴이 굼뜨다는 것.

가우스-자이델법(Gauss-Seidel method)은 $M = D + L$ 로 잡는다. 방금 갱신한 최신 값을 즉시 써먹는 것이 핵심이다.

x_i^{(k+1)} = \frac{1}{a_{ii}}\left( b_i - \sum_{j<i} a_{ij}\, x_j^{(k+1)} - \sum_{j>i} a_{ij}\, x_j^{(k)} \right)

같은 반복 안에서 이미 고친 값을 재활용하니 야코비보다 대략 두 배 빨리 수렴한다. 대신 순차 의존성이 생겨서 순수 병렬화는 까다롭다(적-흑 순서화 등으로 우회).

SOR(Successive Over-Relaxation, 축차 과완화법)은 가우스-자이델에 완화 계수 $\omega$ 를 얹어 갱신을 과하게 밀어붙인다.

x_i^{(k+1)} = (1-\omega)\, x_i^{(k)} + \omega\, x_i^{(\text{GS})}

$\omega = 1$ 이면 그냥 가우스-자이델이고, $1 < \omega < 2$ 면 과완화(over-relaxation)로 수렴이 극적으로 빨라진다. 문제는 최적 $\omega$ 가 행렬에 따라 다르다는 것. 잘 고르면 수렴 차수 자체가 개선되지만, 대충 찍으면 오히려 느려지거나 발산한다.²

4. 수렴 조건과 스펙트럴 반지름[편집]

반복법이 수렴하느냐 마느냐는 반복행렬(iteration matrix) $G = M^{-1}N$ 의 성질로 결정된다. 오차 $\mathbf{e}^{(k)} = \mathbf{x}^{(k)} - \mathbf{x}^*$ 는 다음을 만족한다.

\mathbf{e}^{(k+1)} = G\, \mathbf{e}^{(k)} \quad\Longrightarrow\quad \mathbf{e}^{(k)} = G^k\, \mathbf{e}^{(0)}

이 오차가 0으로 사라지려면 $G^k \to 0$ 이어야 하고, 이것의 필요충분조건은 $G$ 의 스펙트럴 반지름(spectral radius)이 1보다 작은 것이다.

\rho(G) = \max_i |\lambda_i(G)| < 1

즉 반복행렬의 고유값 중 절댓값이 가장 큰 놈이 1 미만이면 무조건 수렴한다. 그리고 $\rho(G)$ 가 작을수록 빨리 수렴한다. $\rho$ 가 0.99쯤 되면 수렴은 하는데 하세월이라 커피가 아니라 퇴근을 부른다. 실용적인 충분조건으로는 계수행렬 $A$ 가 엄격 대각 우세(strictly diagonally dominant)하면 야코비와 가우스-자이델이 모두 수렴한다는 정리가 유명하다.³

5. 반복법의 현재 위치[편집]

야코비·가우스-자이델·SOR 같은 고전적 정지 반복법(stationary iterative methods)은 오늘날 단독 선형 솔버로는 거의 쓰이지 않는다. 수렴이 너무 느려서다. 대신 이들은 크리로프 부분공간법(CG, GMRES 등)의 전처리기로, 혹은 다중격자법의 평활자(smoother)로 조연을 맡으며 화려하게 부활했다.

특히 다중격자법에서 가우스-자이델은 고주파 오차를 매끈하게 지워주는 평활자로 제격이라, 현대 대규모 전산유체역학 솔버의 심장부에서 여전히 돌아가고 있다. 즉 고전 반복법은 은퇴한 게 아니라, 더 똑똑한 알고리즘의 부품으로 재취업한 셈이다.

6. 관련 문서[편집]

반복법은 행렬 $A$ 를 통째로 저장할 필요조차 없다. 행렬-벡터 곱 $A\mathbf{v}$ 를 계산하는 함수만 있으면 된다. 이걸 행렬 없는(matrix-free) 방법이라 부르며, 초대규모 문제에서 메모리를 아끼는 비장의 카드다. ↩
최적 완화 계수 $\omega_{\text{opt}}$ 를 이론적으로 구하는 공식이 특정 행렬 클래스에는 존재하지만, 일반 행렬에서는 그냥 몇 개 찍어보고 제일 빠른 걸 고르는 게 현실이다. 학문의 세계에도 결국 노가다는 있다. ↩
“대각 우세”는 각 행에서 대각 성분의 절댓값이 나머지 성분들의 절댓값 합보다 큰 상태다. 물리적으로는 각 격자점이 자기 자신에게 가장 강하게 연결된 얌전한 시스템이라는 뜻. 다행히 잘 만든 이산화는 대체로 이 조건을 만족한다. ↩

반복법