리처드슨 반복

오류 제보
수치해석 마지막 수정: 2026-11-01 04:34:52
○ 공개 검수 대기 AI 보조 작성 표시 기준 보기
상위 문서: 반복법

1. 개요

리처드슨 반복
Richardson iteration
갱신xk+1=xk+ω (b−Axk)x_{k+1}=x_k+\omega\,(b-Ax_k)
오차 전파ek+1=(I−ωA) eke_{k+1}=(I-\omega A)\,e_k
수렴 (SPD)0<ω<2/λmax⁡0<\omega<2/\lambda_{\max}
최적 ω\omega2/(λmin⁡+λmax⁡)2/(\lambda_{\min}+\lambda_{\max})
최적 수렴률(κ−1)/(κ+1)(\kappa-1)/(\kappa+1)
다른 이름고정 보폭 경사하강, 의사시간 전진, 랜드웨버(정규방정식판)
제안L. F. 리처드슨 (1911)

잔차를 보고, 그만큼 고친다. 반복법은 전부 여기서 시작한다.

리처드슨 반복(Richardson iteration)은 선형계 Ax=bAx=b 를 풀 때 현재 잔차 rk=b−Axkr_k=b-Ax_k 에 상수 ω\omega 를 곱해 해에 더하는 가장 단순한 정상 반복법이다.

xk+1=xk+ω (b−Axk)x_{k+1}=x_k+\omega\,(b-Ax_k)

행렬-벡터 곱 하나와 벡터 덧셈 하나뿐이라 구현은 한 줄이다. 그런데 이 한 줄이 놀랄 만큼 많은 이름으로 다시 나타난다. 이차 함수에 대한 고정 보폭 경사하강법, 정상 상태를 구하려고 du/dt=b−Audu/dt=b-Au 를 명시적 오일러로 굴리는 의사시간 전진, 정규방정식에 적용한 랜드웨버 반복이 모두 리처드슨 반복이다. 전처리기 MM 을 붙인 xk+1=xk+M−1(b−Axk)x_{k+1}=x_k+M^{-1}(b-Ax_k) 까지 넓히면 야코비(M=DM=D)·가우스-자이델(M=D+LM=D+L)도 이 틀에 들어간다 — 반복법의 모든 정상 반복이 “전처리된 리처드슨”이다.

이름은 영국 기상학자 루이스 프라이 리처드슨에서 왔다. 1911년 석조 댐의 응력을 유한차분으로 계산한 논문에서, 손계산으로 연립방정식을 반복해 풀며 이 방법을 썼다.1 같은 사람이 만든 리처드슨 외삽법과는 다른 방법이다(그 논문 하나에 두 아이디어가 다 들어 있다).

2. 수렴 — 고유값 하나하나의 문제

오차 ek=xk−x∗e_k=x_k-x^* 는 ek+1=(I−ωA)eke_{k+1}=(I-\omega A)e_k 로 전파된다. 반복행렬 T=I−ωAT=I-\omega A 의 고유값은 1−ωλi1-\omega\lambda_i 이므로, 노이만 급수·스펙트럼 반지름의 일반론대로

수렴  ⟺  max⁡i∣1−ωλi∣<1.\text{수렴}\iff \max_i\lvert1-\omega\lambda_i\rvert<1.

AA 가 대칭 양정치(SPD) 이고 고유값이 [λmin⁡,λmax⁡][\lambda_{\min},\lambda_{\max}] 에 있으면, 이 조건은 0<ω<2/λmax⁡0<\omega<2/\lambda_{\max} 다. 수렴률을 최소화하려면 양 끝의 ∣1−ωλ∣\lvert1-\omega\lambda\rvert 를 같게 맞추면 되고,

ω∗=2λmin⁡+λmax⁡,ρ(T)=κ−1κ+1,κ=λmax⁡λmin⁡.\omega^*=\frac{2}{\lambda_{\min}+\lambda_{\max}},\qquad \rho(T)=\frac{\kappa-1}{\kappa+1},\quad \kappa=\frac{\lambda_{\max}}{\lambda_{\min}}.

κ\kappa 가 크면 ρ≈1−2/κ\rho\approx1-2/\kappa 라서 오차를 10−610^{-6} 배 줄이는 데 약 6.9κ6.9\kappa 번이 든다. 반복 횟수가 조건수에 정비례한다는 것이 리처드슨의 한계다.

1차원 푸아송 행렬 tridiag(−1,2,−1)\mathrm{tridiag}(-1,2,-1), n=100n=100 으로 재 보면 κ≈4134\kappa\approx4134 이고,

방법잔차 10−610^{-6} 까지 반복 수
리처드슨, 최적 고정 ω\omega (이론 예측)약 28 550
리처드슨, 최적 고정 ω\omega (측정)28 348
체비쇼프 가속 (이론 상한)약 470
켤레기울기법 (측정, b=1b=\mathbf 1)50

이다. 켤레기울기법이 50 번에 끝나는 건 b=1b=\mathbf 1 이 대칭이라 고유벡터 절반만 들어 있어, 정확한 산술에서 50 단계면 끝나기 때문이다. 고정 ω\omega 는 모든 고유 성분을 같은 다항식 1−ωλ1-\omega\lambda 로만 깎으니 이런 구조를 전혀 활용하지 못한다.

비대칭 행렬은 사정이 다르다. 고유값이 모두 복소평면의 오른쪽 반평면에 있으면 충분히 작은 ω\omega 로 수렴하지만, 허수축 양쪽에 걸쳐 있으면 어떤 실수 ω\omega 도 수렴시키지 못한다. 원점 중심 원판이 모든 1−ωλi1-\omega\lambda_i 를 담을 수 없기 때문이다. 이게 GMRES 같은 크리로프 방법이 필요한 이유 중 하나다.

3. 체비쇼프 가속 — 원래 리처드슨이 한 것

사실 리처드슨의 원래 아이디어는 고정 ω\omega 가 아니라 스텝마다 다른 ωk\omega_k 였다. kk 스텝 뒤의 오차는

ek=∏j=1k(I−ωjA) e0=pk(A) e0,pk(0)=1e_k=\prod_{j=1}^{k}(I-\omega_jA)\,e_0=p_k(A)\,e_0,\qquad p_k(0)=1

이므로, [λmin⁡,λmax⁡][\lambda_{\min},\lambda_{\max}] 위에서 ∣pk∣\lvert p_k\rvert 의 최댓값이 가장 작은 다항식을 고르면 된다. 답은 이동·정규화한 체비쇼프 다항식이고, 1/ωj1/\omega_j 를 그 근에 두면

∥ek∥≤2(κ−1κ+1)k∥e0∥\lVert e_k\rVert\le 2\left(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\right)^{k}\lVert e_0\rVert

로 반복 수가 κ\sqrt\kappa 에 비례하게 줄어든다. 위 표의 470 이 이것이다.

함정은 순서다. ωj\omega_j 를 근의 크기 순서대로 쓰면, 큰 ω\omega 를 연속으로 쓰는 중간 구간에서 오차가 일시적으로 엄청나게 커지고 반올림 오차가 증폭된다. 영(Young, 1954)이 이 불안정성을 분석했고, 이후 근을 섞어 쓰는 순서 기법들이 나왔다. 실무에서는 3항 점화식으로 같은 다항식을 안정적으로 만드는 체비쇼프 준반복(semi-iterative method)을 쓴다. 고유값 범위 [λmin⁡,λmax⁡][\lambda_{\min},\lambda_{\max}] 를 알아야 한다는 점이 켤레기울기법 대비 약점이지만, 내적이 없어서 전역 통신이 필요 없다 — 대규모 병렬에서 이게 다시 장점이 된다. 다항식 전처리와 다중격자 평활기에서 살아남은 이유다.

4. 다른 얼굴들

경사하강법. f(x)=12x⊤Ax−b⊤xf(x)=\tfrac12x^\top Ax-b^\top x 의 기울기가 Ax−bAx-b 이므로 보폭 η\eta 의 경사하강은 ω=η\omega=\eta 인 리처드슨이다. 최적 보폭 2/(L+μ)2/(L+\mu), 수렴률 (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) 이라는 최적화 교과서의 결과가 위 식과 글자까지 같다. 폴랴크의 헤비볼(모멘텀) 방법을 이차 함수에 쓰면 2차 정상 반복이 되고, 최적 계수에서 κ\sqrt\kappa 수렴률을 얻는다 — 체비쇼프 준반복의 정상 극한이다.

의사시간 전진. 정상 해를 찾으려고 du/dτ=b−Audu/d\tau=b-Au 를 Δτ\Delta\tau 로 명시적 전진하면 ω=Δτ\omega=\Delta\tau 인 리처드슨이다. 수렴 조건 ω<2/λmax⁡\omega<2/\lambda_{\max} 는 명시적 스킴의 안정성 한계(CFL 류 조건)와 같은 식이다. 압축성 CFD 의 국소 시간 전진(셀마다 다른 Δτ\Delta\tau)은 대각 전처리된 리처드슨이고, 여기에 다중격자를 얹는 것이 고전적인 정상 해법이다.

다중격자 평활기. ω\omega 를 1/λmax⁡1/\lambda_{\max} 근처로 잡은 리처드슨은 고주파 오차를 빠르게, 저주파 오차를 거의 안 깎는다. 수렴 방법으로는 최악이지만 평활기로는 딱 맞다. 1차원 푸아송에서 가중 야코비 ωJ=2/3\omega_J=2/3 (리처드슨으로는 ω=1/3\omega=1/3) 은 고주파 성분을 매 스텝 1/31/3 이하로 줄인다. 남은 저주파는 다중격자법의 거친 격자가 처리한다.

랜드웨버 반복. 불량조건 문제 Ax≈bAx\approx b 에 정규방정식 A⊤Ax=A⊤bA^\top Ax=A^\top b 의 리처드슨, 즉 xk+1=xk+ωA⊤(b−Axk)x_{k+1}=x_k+\omega A^\top(b-Ax_k) 를 쓴 것(0<ω<2/σmax⁡20<\omega<2/\sigma_{\max}^2). 큰 특이값 성분부터 수렴하고 작은 특이값(잡음 증폭 성분)은 늦게 들어오므로, 반복을 일찍 멈추는 것 자체가 정규화가 된다. 반복 수가 티호노프 정규화의 1/λ1/\lambda 역할을 하는 “준수렴” 현상으로, 너무 오래 돌리면 오히려 해가 나빠진다.2

반복 개선. 저정밀 LU 인수 L^U^\hat L\hat U 로 x←x+(L^U^)−1(b−Ax)x\leftarrow x+(\hat L\hat U)^{-1}(b-Ax) 를 하는 혼합 정밀도 반복 개선도 M=L^U^M=\hat L\hat U 인 전처리 리처드슨이다. 수렴 조건 ρ(I−M−1A)<1\rho(I-M^{-1}A)<1 이 대략 “저정밀 단위반올림 × 조건수 < 1” 로 번역된다.3

5. 관련 문서

6. Footnotes

  1. 리처드슨은 이 계산을 “계산원”들에게 나눠 맡겼고, 계산 속도에 따라 품삯을 줬다고 한다. 나중에 그가 상상한 “6만 4천 명이 극장에 모여 날씨를 계산하는 공장”은 병렬 컴퓨팅의 원조 망상으로 자주 인용된다. ↩

  2. 딥러닝의 조기 종료(early stopping)가 정규화처럼 동작하는 이유도 같은 수학이다. 경사하강은 큰 특이값 방향부터 맞추니, 일찍 멈추면 작은 방향(대개 잡음)을 아직 안 배운 상태다. 70년 묵은 랜드웨버가 최신 논문에 자꾸 소환되는 이유. ↩

  3. 반복 개선은 “LU 를 다시 할 돈은 없지만 잔차는 계산할 수 있는” 사람을 위한 방법이다. 반정밀도로 인수분해하고 배정밀도로 잔차를 구하는 GPU 해법들이 이걸로 배정밀도 정확도를 뽑는다. ↩

검증 자료

이 문서의 주요 출처

  1. L. F. Richardson (1911), The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam, Phil. Trans. R. Soc. A 210, 307-357
  2. D. M. Young (1954), On Richardson's method for solving linear systems with positive definite matrices, Journal of Mathematics and Physics 32, 243-255
  3. L. Landweber (1951), An iteration formula for Fredholm integral equations of the first kind, American Journal of Mathematics 73(3), 615-624
  4. Y. Saad (2003), Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM (Ch. 4, 12)
  5. A. Greenbaum (1997), Iterative Methods for Solving Linear Systems, SIAM
이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

의견을 반영할게요. 감사합니다.

다음으로 읽기 크리로프 부분공간법 약 5분 더 탐색 →