고정점 반복

오류 제보
수치해석 마지막 수정: 2026-10-19 04:11:38
○ 공개 검수 대기 AI 보조 작성 표시 기준 보기

1. 개요

고정점 반복
Fixed-Point Iteration
푸는 것x = g(x) (또는 f(x) = 0 을 그렇게 고쳐 쓴 것)
반복xk+1 = g(xk)
국소 수렴 조건|g′(x*)| < 1 (다변수: 야코비안의 스펙트럼 반지름 < 1)
수렴 차수보통 1차 (비율 |g′(x*)|), g′(x*) = 0 이면 2차 이상
다른 이름피카르 반복, 연속 대입법, 단순 반복

식을 x=g(x)x = g(x) 꼴로 바꿔 놓고, 오른쪽에 넣고 왼쪽에서 꺼내기를 무한 반복한다. 이게 전부다. 그리고 수치해석에서 제일 많이 돌아가는 루프다.

고정점 반복(fixed-point iteration)은 방정식을 x=g(x)x = g(x) 꼴로 바꾼 뒤, 초기값 x0x_0 에서 xk+1=g(xk)x_{k+1} = g(x_k) 를 반복해 gg 의 고정점 x∗=g(x∗)x^* = g(x^*) 에 다가가는 방법이다. 미분방정식 쪽에서는 피카르 반복(Picard iteration), 선형대수 쪽에서는 반복법의 야코비·가우스-자이델, 양자화학에서는 SCF 루프, 연성 해석에서는 분할 반복이라는 이름으로 똑같은 구조가 계속 나온다.

이론적 뼈대는 바나흐 고정점 정리가 다 갖고 있다 — gg 가 축약이면 유일한 고정점이 있고 반복은 기하급수로 수렴한다. 이 문서는 그 정리를 다시 증명하지 않고 실무 쪽 질문만 다룬다. 같은 방정식에서 gg 를 어떻게 고르느냐에 따라 수렴·진동·발산이 갈리는 이유, 수렴 속도를 g′(x∗)g'(x^*) 하나로 읽는 법, 이완 계수로 반복을 길들이는 법, 그리고 다변수·실전 루프에서 이것이 어떤 얼굴로 나타나는지다.

2. 같은 방정식, 다른 g — 수렴은 고쳐 쓰는 법이 정한다

f(x)=x2−2=0f(x) = x^2 - 2 = 0 의 근 2\sqrt2 를 찾는다고 하자. 이걸 x=g(x)x = g(x) 로 고쳐 쓰는 방법은 무수히 많고, 고르는 순간 운명이 정해진다. 초기값 x0=1x_0 = 1 로 배정밀도에서 돌린 결과다.

g(x)g(x)g′(2)g'(\sqrt2)결과
2/x2/x−1-12,1,2,1,…2, 1, 2, 1, \dots 영원히 2-주기
x−(x2−2)x - (x^2-2)1−22≈−1.831-2\sqrt2 \approx -1.832,0,2,0,…2, 0, 2, 0, \dots 수렴 실패
x−(x2−2)/4x - (x^2-2)/41−2/2≈0.291-\sqrt2/2 \approx 0.2923회 만에 10−1210^{-12}
x−(x2−2)/(22)x - (x^2-2)/(2\sqrt2)004회
12(x+2/x)\tfrac12(x + 2/x)005회 (뉴턴-랩슨법 그 자체)

첫 줄이 교훈적이다. 2/x2/x 는 고정점이 정확히 2\sqrt2 인데도 ∣g′∣=1|g'| = 1 이라 한 발짝도 다가가지 않는다. 둘째 줄은 ∣g′∣>1|g'| > 1 이라 고정점이 밀어내는 점이 된다. 근이 존재하는지와 반복이 그 근을 찾는지는 완전히 다른 질문이다.

넷째 줄은 반칙이다 — 답 2\sqrt2 를 미리 알아야 기울기를 정확히 0 으로 맞출 수 있다. 그런데 그 “반칙”을 매 반복 현재 위치에서 근사적으로 하면 바로 다섯째 줄, 뉴턴법이 된다. 뉴턴법은 g(x)=x−f(x)/f′(x)g(x) = x - f(x)/f'(x) 로 고른 고정점 반복이고, 단순근에서 g′(x∗)=0g'(x^*) = 0 이 되도록 설계된 gg 다.1

3. 수렴 속도는 g′(x*) 가 말한다

gg 가 고정점 근처에서 매끄러우면 테일러 전개로

ek+1=xk+1−x∗=g(xk)−g(x∗)=g′(x∗) ek+12g′′(ξ) ek2e_{k+1} = x_{k+1} - x^* = g(x_k) - g(x^*) = g'(x^*)\,e_k + \tfrac12 g''(\xi)\,e_k^2

이니, 근 근처에서 오차는 매 반복 g′(x∗)g'(x^*) 배가 된다. 여기서 읽을 수 있는 게 셋이다.

  • 수렴 여부: ∣g′(x∗)∣<1|g'(x^*)| < 1 이면 충분히 가까운 초기값에서 수렴한다(국소 수렴). >1> 1 이면 고정점이 반발점이라 정확히 그 위에서 출발하지 않는 한 떠난다.
  • 속도: 오차를 10 배 줄이는 데 대략 −1/log⁡10∣g′(x∗)∣-1/\log_{10}|g'(x^*)| 회가 든다. ∣g′∣=0.9|g'| = 0.9 면 22회, 0.990.99 면 229회. 1 에 가까운 비율은 “수렴은 하는데 퇴근을 못 하는” 영역이다.
  • 모양: g′(x∗)<0g'(x^*) < 0 이면 오차 부호가 매번 바뀌어 근 주위를 지그재그로 감고 들어가고, >0> 0 이면 한쪽에서 단조롭게 다가간다.

g′(x∗)=0g'(x^*) = 0 이면 1차 항이 사라져 2차 수렴이 되고, g′′g'' 까지 0 이면 3차가 된다. 일반적으로 처음으로 0 이 아닌 도함수의 차수가 수렴 차수다. 이 관점이 뉴턴·핼리 같은 고차 방법을 한 줄로 분류하는 공용어다.

3.1. 검산 — 오메가 상수

x=e−xx = e^{-x} 의 고정점은 오메가 상수 Ω=W(1)≈0.5671432904\Omega = W(1) \approx 0.5671432904 다(람베르트 W). g′(x)=−e−xg'(x) = -e^{-x} 이므로 g′(Ω)=−Ω≈−0.567g'(\Omega) = -\Omega \approx -0.567. 예측: 부호가 번갈아 바뀌면서 매 반복 오차가 약 0.57 배.

x0=1x_0 = 1 에서 실측한 오차 ek=xk−Ωe_k = x_k - \Omega:

kk123456
eke_k−0.1993-0.1993+0.1251+0.1251−0.0667-0.0667+0.0391+0.0391−0.0217-0.0217+0.0125+0.0125
ek/ek−1e_k/e_{k-1}—−0.628-0.628−0.533-0.533−0.586-0.586−0.556-0.556−0.573-0.573

비율이 −0.567-0.567 주위로 모인다. 10−1010^{-10} 까지는 39회가 걸렸다. −1/log⁡100.567≈4.06-1/\log_{10}0.567 \approx 4.06 회/자릿수 × 약 9.6 자릿수(초기 오차 0.43 → 10−1010^{-10}) ≈ 39 회와 맞는다.

4. 이완 — 반복을 길들이는 가장 싼 장치

원래 반복에 현재 값을 섞는다.

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

이 새 반복의 사상 gω(x)=(1−ω)x+ωg(x)g_\omega(x) = (1-\omega)x + \omega g(x) 는 고정점이 그대로이고 기울기만 gω′(x∗)=1−ω (1−g′(x∗))g_\omega'(x^*) = 1 - \omega\,(1 - g'(x^*)) 로 바뀐다. 따라서

ωopt=11−g′(x∗)\omega_{\text{opt}} = \frac{1}{1 - g'(x^*)}

로 잡으면 기울기가 0 이 된다. g′(x∗)<0g'(x^*) < 0 인 지그재그 반복은 ω<1\omega < 1 로 감쇠(under-relaxation)해야 하고, 0<g′(x∗)<10 < g'(x^*) < 1 인 느린 단조 반복은 ω>1\omega > 1 로 가속(over-relaxation)할 수 있다. 반복법의 SOR 이 바로 후자를 선형계에 적용한 것이다.

오메가 상수 예에서 ωopt=1/(1+Ω)≈0.638\omega_{\text{opt}} = 1/(1+\Omega) \approx 0.638 이다. 같은 x0=1x_0 = 1, 같은 허용오차 10−1010^{-10} 으로 실측한 반복 수:

ω\omega1 (원래)0.50.60.6380.70.8
반복 수391594916

물론 ωopt\omega_{\text{opt}} 를 정확히 알려면 g′(x∗)g'(x^*) 를 알아야 하니 실전에서는 추정한다. 연속한 세 반복값으로 그 기울기를 매번 추정하는 것이 아이켄 델타제곱법·스테펜센 방법이고, 분할 연성 해석에서 쓰는 “아이켄 동적 이완”이 같은 발상의 벡터판이다. 과거 여러 개의 잔차로 최소제곱 조합을 만들면 앤더슨 가속이 된다.

이완의 또 다른 쓸모는 비축약 사상을 수렴시키는 것이다. gg 가 비확대(nonexpansive, 립시츠 상수 1)일 뿐이라 바나흐 정리가 안 먹힐 때도, 평균 반복 xk+1=(1−ω)xk+ωg(xk)x_{k+1} = (1-\omega)x_k + \omega g(x_k) (0<ω<10<\omega<1)은 힐베르트 공간 등에서 고정점으로 (약)수렴한다는 것이 크라스노셀스키-만 반복의 정리다. 위 표의 g(x)=2/xg(x) = 2/x 가 바로 그런 예로, ω=1/2\omega = 1/2 를 넣으면 12(x+2/x)\tfrac12(x + 2/x) — 뉴턴법이 튀어나온다.

5. 다변수 — 스펙트럼 반지름의 영역

x∈Rn\mathbf{x} \in \mathbb{R}^n, xk+1=G(xk)\mathbf{x}_{k+1} = G(\mathbf{x}_k) 에서는 g′g' 자리를 야코비안 G′(x∗)G'(\mathbf{x}^*) 가 차지한다. 오스트롭스키 정리: GG 가 고정점에서 미분 가능하고 스펙트럼 반지름 ρ(G′(x∗))<1\rho(G'(\mathbf{x}^*)) < 1 이면 x∗\mathbf{x}^* 는 끌개(point of attraction)다. 수렴 비율은 대략 ρ\rho 다.

여기서 스칼라에는 없던 함정이 둘 생긴다.

  1. 노름이 1 보다 커도 수렴할 수 있다. ∥G′∥>1\|G'\| > 1 인데 ρ<1\rho < 1 이면 결국 수렴하지만, 비정규(non-normal) 야코비안이면 처음 수십 반복 동안 오차가 크게 불어났다가 줄어든다. 로그에서 잔차가 튀어 오르는 걸 보고 발산이라 판정해 끄면 억울하다.
  2. 고유모드별로 운명이 갈린다. 대부분의 모드는 0.3 배씩 줄어드는데 한 모드만 0.999 배면 그 모드 하나가 전체 반복 수를 정한다. 유한요소 분할 연성에서 가장 낮은 모드, SCF 에서 긴 파장의 전하 출렁임(charge sloshing)이 대표적인 범인이다.

선형 고정점 반복 xk+1=Bxk+c\mathbf{x}_{k+1} = B\mathbf{x}_k + \mathbf{c} 가 반복법의 야코비·가우스-자이델이다. 거기서는 G′=BG' = B 가 상수라 ρ(B)<1\rho(B) < 1 이 국소가 아니라 전역 수렴 조건이 된다.

6. 실전의 고정점 루프들

  • 피카르 선형화 — 비선형 PDE 의 계수를 직전 반복값으로 얼린다. 나비에-스토크스 방정식의 대류항 (u⋅∇)u(\mathbf{u}\cdot\nabla)\mathbf{u} 를 (uk⋅∇)uk+1(\mathbf{u}_k\cdot\nabla)\mathbf{u}_{k+1} 로 두는 식이다. 수렴 반경이 넓어 초기값에 관대한 대신 1차 수렴이라, 흔히 피카르 몇 번으로 끌고 간 뒤 뉴턴-크리로프법으로 갈아탄다. SIMPLE 알고리즘의 외부 반복과 압력·속도 이완 계수(0.3, 0.7 같은 국룰 값)도 이 계보다.
  • SCF — 하트리-폭 방법·밀도범함수이론에서 밀도 → 퍼텐셜 → 새 밀도의 사상을 반복한다. 그대로 돌리면 진동·발산이 흔해서 선형 혼합(= 위의 이완), DIIS·펄레이 혼합(= 앤더슨 가속의 사촌)이 기본 장착이다.
  • 분할 연성 — 유체-구조 연성에서 유체 솔버와 구조 솔버를 번갈아 부르는 것이 경계 변위에 대한 고정점 반복이다. 구조가 가볍고 유체가 무거울수록 ∣g′∣|g'| 가 1 을 넘어 발산하는 “부가질량 불안정”이 유명하고, 아이켄 이완이 표준 처방이다.
  • 음함수 시간 적분 — 후진 오일러 yn+1=yn+hf(yn+1)y_{n+1} = y_n + h f(y_{n+1}) 를 고정점 반복으로 풀면 축약 조건이 h L<1h\,L < 1 (LL 은 ff 의 립시츠 상수)이 되어, 강성 방정식에서는 음함수 방법을 쓰는 의미가 사라진다. 그래서 강성 솔버는 고정점이 아니라 뉴턴 반복을 쓴다(이 논리는 바나흐 고정점 정리 쪽에 자세하다).

7. 멈추는 법과 함정

  • 정지 기준. ∣xk+1−xk∣|x_{k+1} - x_k| 가 작다고 오차가 작은 게 아니다. 비율 q=∣g′∣q = |g'| 이 1 에 가까우면 실제 오차는 대략 q1−q∣xk+1−xk∣\frac{q}{1-q}|x_{k+1}-x_k| 로, q=0.99q = 0.99 면 증분의 99 배다. 증분 비율로 qq 를 추정해 이 보정을 곱하는 게 정직한 정지 기준이다.2
  • 주기와 카오스. ∣g′(x∗)∣>1|g'(x^*)| > 1 이 된 뒤에도 반복이 무한대로 날아가지 않고 2-주기, 4-주기… 로 갇히는 경우가 있다. 로지스틱 사상이 바로 이 고정점 반복이고, 매개변수를 올리면 분기 이론의 주기 배가를 거쳐 카오스 이론으로 들어간다. 잔차가 일정한 패턴으로 오르내리면 “거의 수렴”이 아니라 주기 궤도일 수 있다.
  • 여러 고정점. gg 의 고정점이 여럿이면 어느 것에 끌리는지는 초기값이 정한다. 끌림 영역의 경계가 프랙탈일 수도 있다.
  • 이분법과 비교. 1차 수렴이라는 점은 이분법과 같지만, 이분법은 비율 0.5 를 보장하고 고정점 반복은 ∣g′∣|g'| 에 맡긴다. 대신 고정점 반복은 차원을 가리지 않는다 — 이분법은 1차원 밖으로 나갈 수 없다.3

8. 관련 문서

9. Footnotes

  1. 그래서 “뉴턴법 vs 고정점 반복”이라는 비교는 엄밀히는 “잘 고른 gg vs 대충 고른 gg“다. 뉴턴은 경쟁자가 아니라 이 집안의 장남이다. ↩

  2. 바나흐 정리의 후험 오차한계 ∥xk−x∗∥≤q1−q∥xk−xk−1∥\|x_k - x^*\| \le \frac{q}{1-q}\|x_k - x_{k-1}\| 그대로다. 로그에 “증분 10−610^{-6}, 수렴!”이라고 찍어 놓고 실제 오차는 10−410^{-4} 인 코드는 생각보다 흔하다. 문제는 그 코드가 대개 내 코드라는 것. ↩

  3. 다변수에서 이분법의 정신을 이으려는 시도(단체 분할, 위상수학적 차수 이용)가 있긴 하지만, 실무 솔버 로그에서 보게 될 일은 없다. 다차원에서는 결국 고정점과 뉴턴의 세계다. ↩

검증 자료

이 문서의 주요 출처

  1. J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (SIAM Classics, 2000; 원판 1970) — 10.1.3 Ostrowski 정리
  2. Wikipedia, Fixed-point iteration (수렴 조건·이완·예제)
  3. Wikipedia, Krasnosel'skii–Mann iteration (평균 반복)
  4. Wikipedia, Banach fixed-point theorem (축약 사상과 선험·후험 오차한계)
이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

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

다음으로 읽기 뉴턴-랩슨법 약 5분 더 탐색 →