바나흐 고정점 정리

편집 역사 토론
수치해석 시뮬레이션 마지막 수정: 2026-08-22 04:31:05

1. 개요[편집]

바나흐 고정점 정리
Banach Fixed-Point Theorem
별칭축약사상 원리 (contraction mapping principle)
발표스테판 바나흐, 1922년
가정완비 거리공간 + 립시츠 상수 L < 1
결론고정점 존재·유일 + 기하급수적 수렴
수렴 차수선형(1차). 매 반복 오차에 L 곱

축약이면 이긴다. 문제는 대부분의 흥미로운 사상이 축약이 아니라는 것.

바나흐 고정점 정리는 완비 거리공간 위의 축약사상은 고정점을 정확히 하나 가지며, 아무 데서나 시작한 반복이 그 고정점으로 기하급수적으로 수렴한다는 정리다. 정확히 쓰면 이렇다.

(X,d)(X,d) 가 공집합이 아닌 완비 거리공간이고 T:X→XT : X \to X 가 어떤 상수 0≤L<10 \le L < 1 에 대해

d(Tx,Ty)≤L d(x,y)∀ x,y∈Xd(Tx, Ty) \le L\, d(x,y) \qquad \forall\, x,y \in X

를 만족한다고 하자(이런 TT 를 축약사상이라 한다). 그러면 TT 는 유일한 고정점 x∗x^* (Tx∗=x∗Tx^* = x^*)를 가지고, 임의의 x0∈Xx_0 \in X 에서 출발한 반복 xn+1=Txnx_{n+1} = Tx_n 이 x∗x^* 로 수렴하며, 아래에 적는 오차한계가 성립한다.

가정이 이렇게 소박한데 결론은 존재·유일·수렴·오차한계를 한꺼번에 준다. 수치해석에서 무언가를 “반복해서 푸는” 알고리즘은 대부분 이 정리의 변주이거나, 이 정리가 통하지 않아서 만들어진 우회로다.1 반복법·뉴턴-랩슨법·다중격자법·동적 계획법의 값 반복이 각자 다른 언어로 같은 이야기를 한다.

2. 증명 스케치 — 코시열을 만들어 내는 기하급수[편집]

증명이 짧고, 짧은 만큼 어디를 건드리면 무너지는지도 잘 보인다.

  1. 간격이 기하급수적으로 줄어든다. d(xn+1,xn)=d(Txn,Txn−1)≤L d(xn,xn−1)d(x_{n+1},x_n) = d(Tx_n, Tx_{n-1}) \le L\,d(x_n,x_{n-1}) 을 반복하면 d(xn+1,xn)≤Lnd(x1,x0)d(x_{n+1},x_n) \le L^n d(x_1,x_0).
  2. 코시열이다. m>nm > n 에 대해 삼각부등식으로 이어 붙이면 d(xm,xn)≤∑k=nm−1Lk d(x1,x0)≤Ln1−L d(x1,x0)d(x_m,x_n) \le \sum_{k=n}^{m-1} L^k\,d(x_1,x_0) \le \dfrac{L^n}{1-L}\,d(x_1,x_0) 이고, L<1L<1 이므로 n→∞n\to\infty 에서 0. 여기서 공비가 1 미만인 등비급수가 수렴한다는 사실 하나가 전부를 떠받친다.
  3. 완비성이 극한을 준다. 코시열이 XX 안에서 수렴한다는 보장이 완비성이다. 극한을 x∗x^* 라 하자.
  4. 극한이 고정점이다. 축약사상은 연속이므로 Tx∗=T(lim⁡xn)=lim⁡Txn=lim⁡xn+1=x∗Tx^* = T(\lim x_n) = \lim Tx_n = \lim x_{n+1} = x^*.
  5. 유일하다. 고정점이 둘이면 d(x∗,y∗)=d(Tx∗,Ty∗)≤L d(x∗,y∗)d(x^*,y^*) = d(Tx^*,Ty^*) \le L\,d(x^*,y^*) 이고 (1−L)d(x∗,y∗)≤0(1-L)d(x^*,y^*) \le 0 이므로 d=0d = 0.

가정 두 개가 각각 어디서 쓰였는지가 명확하다. 완비성이 없으면 3번이 깨진다 — X=(0,1]X = (0,1], T(x)=x/2T(x)=x/2 는 L=1/2L=1/2 인 축약이지만 고정점 0이 공간 밖에 있다. L<1L<1 을 L=1L=1 로 느슨하게 하면 1번의 등비급수가 죽는다. X=[1,∞)X=[1,\infty), T(x)=x+1/xT(x) = x + 1/x 는 모든 x≠yx\ne y 에서 ∣Tx−Ty∣<∣x−y∣|Tx-Ty| < |x-y| 를 만족하지만(엄격 축약처럼 보인다) 고정점이 없다. “상수 LL 이 하나로 잡히는가”와 “점마다 거리가 줄어드는가”는 전혀 다른 조건이다.

3. 오차한계 — 시작하기 전에 이미 안다[편집]

증명 2번 식에서 m→∞m\to\infty 를 보내면 선험(a priori) 오차한계가 그대로 떨어진다.

d(xn,x∗)  ≤  Ln1−L d(x1,x0)d(x_n, x^*) \;\le\; \frac{L^n}{1-L}\, d(x_1, x_0)

첫 한 걸음만 밟아 보면 nn 번째 오차의 상한을 미리 알 수 있다는 뜻이다. 실무에서 더 자주 쓰이는 것은 후험(a posteriori) 한계 쪽이다.

d(xn,x∗)  ≤  L1−L d(xn,xn−1)d(x_n, x^*) \;\le\; \frac{L}{1-L}\, d(x_n, x_{n-1})

이쪽은 “방금 얼마나 움직였는가”만 재면 되므로 반복 종료 조건에 바로 쓸 수 있다. 그리고 여기서 반복법 실무의 고질병 하나가 설명된다 — LL 이 0.99면 증분 d(xn,xn−1)d(x_n,x_{n-1}) 이 10−610^{-6} 이어도 실제 오차는 10−410^{-4} 수준일 수 있다. “변화량이 작다”를 “수렴했다”로 읽는 습관은 LL 이 1에 가까울 때 정확히 1/(1−L)1/(1-L) 배만큼 자신을 속인다.

수렴 차수는 선형(1차)이다. 오차가 매 반복 LL 배씩 줄어드니 유효숫자가 일정 속도로 붙는다. 뉴턴-랩슨법이 2차 수렴하는 것은 그 반복사상의 미분이 근에서 0이 되어 국소 립시츠 상수가 L→0L \to 0 으로 가기 때문이다 — 즉 뉴턴은 “점점 더 강해지는 축약”이고, 그래서 바나흐 정리는 뉴턴의 수렴을 보장하기는 해도 그 속도를 설명하지는 못한다.

4. 미분방정식의 존재·유일성[편집]

정리의 첫 대형 응용은 피카르-린델뢰프 정리다. 초기값 문제

y′(t)=f(t,y(t)),y(t0)=y0y'(t) = f(t,y(t)), \qquad y(t_0) = y_0

에서 ff 가 연속이고 yy 에 대해 립시츠 상수 LL 로 립시츠면, 어떤 구간에서 해가 존재하고 유일하다. 증명은 미분방정식을 적분방정식으로 바꾸는 데서 시작한다.

(Ty)(t)=y0+∫t0tf(s,y(s)) ds(\mathcal T y)(t) = y_0 + \int_{t_0}^{t} f\bigl(s, y(s)\bigr)\,ds

이제 해를 찾는 것은 T\mathcal T 의 고정점을 찾는 것과 같고, 무대는 연속함수 공간 C([t0−δ, t0+δ])C([t_0-\delta,\ t_0+\delta]) 에 상한노름을 준 완비 거리공간이다. 계산해 보면 ∥Ty−Tz∥∞≤δL ∥y−z∥∞\|\mathcal Ty - \mathcal Tz\|_\infty \le \delta L\,\|y-z\|_\infty 이므로 δ<1/L\delta < 1/L 로 잡으면 축약이다. 상미분방정식의 존재·유일성 정리가 사실은 고정점 정리의 따름정리인 셈이고, 그 반복 yn+1=Tyny_{n+1} = \mathcal T y_n 이 교과서의 피카르 반복이다.2

같은 논법이 음함수 정리에도 쓰인다. F(x,y)=0F(x,y)=0 을 yy 에 대해 풀고 싶을 때 y↦y−[DyF(x0,y0)]−1F(x,y)y \mapsto y - [D_yF(x_0,y_0)]^{-1}F(x,y) 라는 사상을 만들면, (x0,y0)(x_0,y_0) 근방의 작은 닫힌 공 위에서 이것이 축약이 되어 유일한 해 y(x)y(x) 를 준다. 연속법(continuation)·호길이법 같은 비선형 해석 기법이 “왜 매개변수를 조금만 움직이면 해가 따라온다고 믿어도 되는가”에 대한 근거가 이것이다.

5. 선형 반복법 — 스펙트럼 반지름이 곧 축약 상수다[편집]

Ax=bA\mathbf x = \mathbf b 를 x(k+1)=Gx(k)+c\mathbf x^{(k+1)} = G\mathbf x^{(k)} + \mathbf c 로 푸는 야코비·가우스-자이델·SOR은 정확히 아핀 사상의 고정점 반복이다. 어떤 노름에서 ∥G∥<1\|G\| < 1 이면 축약이고, 바나흐 정리가 수렴과 오차한계를 준다.

여기서 미묘한 점이 있다. 교과서가 말하는 수렴 조건은 노름이 아니라 스펙트럼 반지름 ρ(G)<1\rho(G) < 1 이다. 둘을 잇는 것이 다음 사실이다 — 임의의 ε>0\varepsilon>0 에 대해 ∥G∥≤ρ(G)+ε\|G\| \le \rho(G)+\varepsilon 인 유도 노름이 존재한다. 그러므로 "ρ(G)<1\rho(G)<1"과 “어떤 노름에서 GG 가 축약사상”은 완전히 같은 말이고, 스펙트럼 반지름 조건은 바나흐 정리를 쓰기 좋게 번역한 것에 지나지 않는다. 다만 “어떤 노름에서”가 함정이다. 그 노름이 우리가 잔차를 재는 노름과 다르면, 수렴은 보장되지만 초반 수십~수백 반복 동안 잔차가 올라가는 과도 성장(transient growth)이 일어난다. GG 가 비정규(non-normal) 행렬일 때 흔한 일이며, 의사스펙트럼이 다루는 현상이 정확히 이것이다. 잔차 그래프가 잠깐 치솟는다고 발산으로 단정하지 말라는 실무 조언의 이론적 근거다. 자세한 수렴 조건은 반복법 참고.

6. 축약이 깨지는 자리 — 강성 문제와 뉴턴[편집]

암시적 시간적분이 이 정리의 한계를 가장 아프게 보여 준다. 후진 오일러법

yn+1=yn+h f(tn+1,yn+1)\mathbf y_{n+1} = \mathbf y_n + h\,\mathbf f(t_{n+1}, \mathbf y_{n+1})

는 매 스텝 비선형 방정식을 풀어야 한다. 가장 순진한 방법은 우변을 그대로 반복하는 것(y(k+1)=yn+hf(tn+1,y(k))\mathbf y^{(k+1)} = \mathbf y_n + h\mathbf f(t_{n+1},\mathbf y^{(k)}), 함수 반복)인데, 이 사상의 립시츠 상수는 hLhL 이다. 따라서 축약 조건은

h<1Lh < \frac{1}{L}

이고, 여기서 LL 은 f\mathbf f 가 y\mathbf y 에 대해 갖는 립시츠 상수(대략 야코비안의 크기)다. 강성 방정식에서는 LL 이 가장 빠른 (그리고 관심 없는) 시간 규모의 역수라, 이 조건이 명시적 방법의 안정성 제한과 사실상 같아진다. 암시적 도식을 쓴 이유가 바로 그 제한에서 벗어나려는 것이었는데, 내부 반복을 함수 반복으로 하는 순간 제한이 뒷문으로 되돌아온다. 그래서 강성 문제의 표준은 뉴턴 반복이다.

(I−h ∂f∂y)Δy=− r(y(k))\Bigl(\mathbf I - h\,\frac{\partial \mathbf f}{\partial \mathbf y}\Bigr)\Delta \mathbf y = -\,\mathbf r(\mathbf y^{(k)})

야코비안을 명시적으로 다뤄서, 축약 상수가 hLhL 이 아니라 “야코비안 근사의 오차”에 비례하도록 바꾼 것이다. 야코비안을 몇 스텝 얼려 쓰는 단순화 뉴턴(simplified Newton)이 여전히 수렴하는 것도 그 축약 상수가 여전히 1보다 작기 때문이다. 강성 ODE 솔버가 예외 없이 야코비안을 요구하는 이유는 “정확도” 때문이 아니라 “고정점 반복이 축약이 되게 만들기 위해서”다. 미분대수방정식에서 이 사정은 더 극단적이 된다.

7. 수렴 논증의 공용어[편집]

큰 시뮬레이션 알고리즘들의 수렴 증명이 결국 “축약 상수를 하나 찾았다”로 끝난다.

  • 다중격자법. 2격자 반복 연산자의 노름을 평활화 성질과 근사 성질로 나누어 각각 잡으면, 격자 간격 hh 에 무관한 축약 상수가 나온다. 다중격자의 자랑인 ”O(N)O(N) 복잡도”는 사실 ”LL 이 hh 에 의존하지 않는다”의 다른 말이다.
  • 영역 분할법. 부분영역을 번갈아 푸는 교대 슈바르츠법은 인터페이스 데이터에 대한 고정점 반복이고, 축약 상수는 겹침 폭과 부분영역 개수에 의존한다. 전달 조건을 바꿔 그 축약 상수 자체를 최소화하도록 설계한 것이 최적화 슈바르츠 방법이다.
  • 값 반복. 마르코프 결정 과정에서 벨만 최적 연산자는 상한노름에 대해 ∥TV−TW∥∞≤γ ∥V−W∥∞\|\mathcal T V - \mathcal T W\|_\infty \le \gamma\,\|V - W\|_\infty 를 만족하는 γ\gamma-축약이다. 그래서 최적 가치함수가 유일하게 존재하고, 값 반복의 오차는 위의 선험 한계를 그대로 물려받아 ∥Vn−V∗∥∞≤γn∥V1−V0∥∞/(1−γ)\|V_n - V^*\|_\infty \le \gamma^n\|V_1-V_0\|_\infty/(1-\gamma) 로 줄어든다. 할인율 γ\gamma 가 1에 가까울수록 1/(1−γ)1/(1-\gamma) 가 폭발한다는 것이 강화 학습에서 장기 과제가 어려운 이유의 절반이다.3 해밀턴-야코비-벨만 방정식의 연속시간 판에서도 같은 구조가 반복된다.

8. 축약이 아니면 어떻게 되나[편집]

L=1L = 1 인 비확장 사상(nonexpansive map)에서는 이야기가 통째로 달라진다. 고정점이 아예 없을 수도 있고(R\mathbb R 위의 T(x)=x+1T(x)=x+1), 있어도 반복이 수렴하지 않을 수 있다(T(x)=−xT(x)=-x 는 고정점 0을 갖지만 xnx_n 은 부호만 바꾸며 진동한다). 그래도 완전히 손을 놓는 것은 아니다.

  • 존재성. 브라우더-괴데-커크 정리에 의해, 힐베르트 공간의 유계 닫힌 볼록집합을 자기 자신으로 보내는 비확장 사상은 고정점을 갖는다. 유한차원의 브라우어 고정점 정리를 무한차원으로 끌어올린 결과다.
  • 수렴. 순수 반복 대신 크라스노셀스키-만 반복 xn+1=(1−αn) xn+αn Txnx_{n+1} = (1-\alpha_n)\,x_n + \alpha_n\,T x_n 처럼 이전 값과 평균을 내면 진동이 죽는다. ∑αn(1−αn)=∞\sum \alpha_n(1-\alpha_n) = \infty 조건에서 힐베르트 공간의 고정점으로 약수렴한다.

이 평균화가 현대 볼록 최적화 알고리즘의 뼈대다. 사영·근접(proximal) 연산자는 비확장을 넘어 견고 비확장(firmly nonexpansive)이고, 이들을 조합한 근접 경사법·더글러스-래치포드·ADMM은 전부 “평균화된 비확장 사상의 반복”으로 통일해 분석된다(볼록 최적화 참고). 대가는 속도다 — 축약이면 기하급수적으로 수렴하지만, 비확장에서는 대개 O(1/n)O(1/n) 급의 열화된 속도밖에 얻지 못한다. 축약이면 이기고, 비확장이면 겨우 비긴다.

반대편 극단도 있다. 사상이 거리를 오히려 늘리는 확대(expanding) 사상이면 고정점은 있어도 불안정해 반복이 그것을 향해 가지 않고, 그러면서도 유계 영역 안에 갇혀 있으면 카오스 이론의 영역이 된다. 텐트 사상처럼 기울기 절댓값이 1보다 큰 조각별 선형 사상이 대표적이며, 바나흐 정리의 부등식 방향이 뒤집힌 자리에서 수렴 대신 랴푸노프 지수가 나온다. 같은 반복 xn+1=Txnx_{n+1}=Tx_n 을 놓고 한쪽 끝에는 수치해석이, 다른 끝에는 카오스가 있는 셈이다.4

9. 관련 문서[편집]

10. Footnotes[편집]

  1. 농담 반 진담 반으로, 수치해석 알고리즘 설계의 절반은 “이 문제를 어떤 축약사상의 고정점으로 쓸 것인가”이고 나머지 절반은 “그 축약 상수를 어떻게 1에서 멀리 떼어놓을 것인가”다. 전처리기·다중격자·완화계수 튜닝이 전부 후자에 속한다. ↩

  2. 축약이 되도록 구간을 δ<1/L\delta < 1/L 로 줄여야 한다는 점 때문에 이 증명은 국소적 존재성만 준다. 비엘레츠키 노름 ∥y∥∗=sup⁡te−2L∣t−t0∣∣y(t)∣\|y\|_* = \sup_t e^{-2L|t-t_0|}|y(t)| 라는 가중 노름을 쓰면 구간을 줄이지 않고도 축약을 만들 수 있다 — 같은 공간에 노름만 바꿔 끼워 정리를 더 세게 뽑아내는, 함수해석의 전형적인 잔기술이다. ↩

  3. 그래서 γ=0.999\gamma = 0.999 같은 설정은 “먼 미래까지 본다”는 뜻이기도 하지만 “수렴 보장이 사실상 없다”는 뜻이기도 하다. 논문에서 할인율만 슬쩍 올려 성능이 좋아졌다고 하면, 반복 횟수를 얼마나 늘렸는지부터 확인하는 것이 예의다. ↩

  4. 로지스틱 사상은 매개변수를 키우면 축약 → 주기배가 → 카오스로 넘어가는데, 그 배가 지점의 간격 비가 파이겐바움 상수다. 바나흐 정리가 커버하는 영역은 그 긴 여정의 맨 처음 구간뿐인 셈이다. ↩