고정점(Fixed point)

계산기에 아무 수나 넣고 cos 버튼(라디안⁠, radian⁠)을 거듭 누르면, 수가 0.7390851…에 모여 더는 변하지 않습니다. 이 수는 cos x = x를 만족합니다. 이처럼 함수⁠(function)⁠ f가 제자리로 보내는 점, 곧 $f(x^*) = x^*$인 점 $x^*$를 f의 고정점이라 합니다. 같은 규칙을 되풀이하는 수열 $x_{n+1} = f(x_n)$이 어떤 수로 다가간다면 그 수는 반드시 고정점입니다. 수열이 $x^*$로 수렴⁠(convergence)⁠하고 f가 연속이면, 식의 양쪽에서 극한⁠(limit)⁠을 취해 $x^* = f(x^*)$를 얻기 때문입니다.

되풀이를 눈으로 보는 방법이 거미줄 그림입니다. 곡선 y = f(x)와 대각선 y = x를 함께 그리고, 가로축의 $x_0$에서 세로로 곡선까지 올라가면 높이가 $x_1 = f(x_0)$입니다. 그 높이 그대로 가로로 대각선까지 가면 가로 좌표가 $x_1$이 되니, 다시 세로로 곡선까지 올라가 $x_2$를 얻습니다. 곡선과 대각선이 만나는 곳이 고정점입니다. 함수: . 노란 점을 끌어 출발점을 바꾸고, 되풀이 횟수를 늘려 보세요: n = .

오른쪽 그림은 고정점까지의 거리 $|x_n - x^*|$를 로그 눈금(10⁻³, 10⁻⁶, …)으로 그린 것이고, 점선은 기울기⁠(slope)⁠가 $\log_{10}|f'(x^*)|$인 직선입니다.

왜 어떤 고정점은 끌어당기고 어떤 고정점은 밀어낼까요? 고정점 가까이에서 곡선은 국소 선형성⁠(local linearity)⁠에 따라 기울기가 $f'(x^*)$인 직선과 거의 같습니다. 그래서 $x_{n+1} - x^* = f(x_n) - f(x^*) \approx f'(x^*)\,(x_n - x^*)$, 곧 고정점까지의 거리가 한 걸음마다 대략 $|f'(x^*)|$배가 됩니다. 이 값이 1보다 작으면 거리가 등비수열⁠(geometric progression)⁠처럼 줄어 고정점이 끌어당기고(안정), 1보다 크면 거리가 불어나 밀어냅니다(불안정). 기울기가 음수이면 차이의 부호가 번갈아 바뀌어 거미줄이 네모난 나선으로 감기고, 양수이면 계단처럼 한쪽에서 다가갑니다. cos x에서는 $f'(x^*) = -\sin x^* \approx -0.674$이니 걸음마다 거리가 약 2/3로 줄며 나선을 그리고, 오른쪽 그림의 점들이 점선을 따라 곧게 내려갑니다. 1 + 1/x의 고정점은 황금비⁠(golden ratio)⁠ φ이고 $f'(\varphi) = -1/\varphi^2 \approx -0.382$입니다. 1에서 출발하면 2, 3/2, 5/3, 8/5, …가 나오는데, 이것은 피보나치 수열⁠(Fibonacci sequence)⁠의 이웃한 두 항의 비이자 φ의 연분수⁠(continued fraction)⁠ 근사입니다.

$|f'(x^*)| = 1$이면 이 어림으로는 판정이 안 됩니다. sin x의 고정점 0이 그런 경우로, 수열이 0으로 가기는 하지만 거리가 대략 $\sqrt{3/n}$로 아주 느리게 줄어듭니다. 반대로 $f'(x^*) = 0$이면 다음 걸음의 거리가 지금 거리의 제곱에 비례해서, 거리가 충분히 작아진 뒤에는 맞는 자릿수가 걸음마다 대략 두 배로 늘어납니다. x²의 고정점 0이 그렇고(1에서는 f′ = 2라 밀어냅니다), 뉴턴 방법⁠(Newton's method)⁠이 빠른 이유도 이것입니다. 뉴턴 방법은 $N(x) = x - g(x)/g'(x)$를 되풀이해 N의 고정점, 곧 g의 근을 찾는데, g의 근에서($g' \ne 0$인 단순근이라면) $N' = 0$이 되도록 만들어져 있습니다. (x + 2/x)/2가 x² − 2 = 0에 쓴 뉴턴 방법입니다.

고정점이 있는지, 하나뿐인지, 되풀이로 찾아지는지를 한꺼번에 보장하는 정리가 있습니다. 1922년 폴란드의 스테판 바나흐가 증명한 축약 사상⁠(contraction mapping)⁠ 정리입니다. 어떤 두 점 사이의 거리도 k배(k < 1) 이하로 줄이는 함수를 축약 사상이라 합니다. 구멍이 없는 공간(실수⁠(real number)⁠처럼 완비된 공간)을 자기 자신으로 보내는 축약 사상에는 고정점이 정확히 하나 있고, 어디서 출발해도 되풀이가 그리로 수렴하며, n걸음 뒤의 거리는 처음의 $k^n$배 이하입니다. 우리나라 지도를 우리나라 땅 위 어딘가에 펼쳐 놓으면, 지도 위의 점 가운데 정확히 하나는 자기가 가리키는 바로 그 땅 위에 놓인다는 것이 이 정리의 예입니다. 지도가 땅보다 작으니 '땅의 한 점을 지도 위의 그 점이 놓인 자리로 보내는' 사상은 축약입니다. 1890년 에밀 피카르는 미분방정식⁠(differential equation)⁠의 해를 적분⁠(integral)⁠ 방정식의 고정점으로 보고 되풀이로 다가가 해가 있음을 보였는데, 이 방법을 바나흐의 정리로 다시 읽으면, 방정식의 오른쪽이 너무 가파르지 않은(립시츠 조건⁠, Lipschitz condition⁠) 경우 짧은 시간 구간에서 해가 하나뿐이라는 것까지 한 번에 나옵니다.

되풀이로는 찾지 못해도 고정점이 반드시 있다고 말해 주는 정리도 있습니다. 구간 [0, 1]을 자기 자신으로 보내는 연속함수를 아무렇게나 그려 보세요. 곡선이 대각선을 피하게 만들 수 있을까요?

이유는 중간값 정리⁠(intermediate value theorem)⁠입니다. g(x) = f(x) − x로 두면, f의 값이 [0, 1] 안에 있으니 g(0) = f(0) ≥ 0이고 g(1) = f(1) − 1 ≤ 0입니다. 연속함수 g가 0 이상에서 0 이하로 가려면 그 사이 어딘가에서 0을 지나야 하고, 그 점이 고정점입니다. 이것을 원판, 공, 그리고 일반 차원으로 넓힌 것이 브라우어르 고정점 정리입니다. 닫힌 원판(또는 공)을 자기 자신 안으로 보내는 연속 사상에는 고정점이 적어도 하나 있다. 커피잔을 휘저은 뒤에도(찢거나 튀기지 않고 연속으로 섞었다면) 처음과 같은 자리에 있는 커피 알갱이가 적어도 하나 있다는 식으로 흔히 설명합니다. 3차원의 경우는 1904년 라트비아의 피어스 볼이, 일반 차원은 1910년 프랑스의 자크 아다마르와 1912년 브라우어르가 증명했습니다. 이 정리는 고정점이 있다는 것만 말하고 어디 있는지는 알려 주지 않는 비구성적 증명의 대표이고, 브라우어르는 나중에 직관주의자로서 이런 증명을 받아들이지 않았습니다(수학 기초론 논쟁⁠, debate on the foundations of mathematics⁠). 원판을 원둘레로 바꾸면 정리는 거짓입니다. 원을 조금 돌리는 사상에는 고정점이 없습니다. 속이 꽉 찼는지, 구멍이 뚫렸는지가 결과를 가르는 이런 성질을 다루는 분야가 위상수학⁠(topology)⁠입니다.

고정점은 여러 분야에서 '평형'이라는 이름으로 나타납니다. 페이지랭크⁠(PageRank)⁠의 중요도 벡터⁠(vector)⁠는 '링크를 따라 중요도를 나눠 주는 규칙'을 적용해도 변하지 않는 고정점이고, 0.85를 곱하는 감쇠 때문에 이 규칙은 축약이 되어 되풀이 계산으로 빨리 구해집니다. 강화 학습⁠(reinforcement learning)⁠의 가치 함수도 같은 모양입니다. 벨먼 방정식의 오른쪽을 적용하는 연산은 할인율⁠(discount factor)⁠ γ가 1보다 작으면 축약이라, 되풀이하면 하나뿐인 고정점, 곧 참 가치로 수렴합니다. 마르코프 연쇄⁠(Markov chain)⁠의 정상 분포⁠(stationary distribution)⁠와 고윳값이 1인 고유벡터⁠(eigenvector)⁠도 고정점입니다. 1950년 미국의 수학자 존 내시는, 모든 참가자가 다른 참가자들의 전략에 대해 가장 좋은 대응을 하고 있어 아무도 혼자 전략을 바꿀 이유가 없는 상태(내시 균형⁠, Nash equilibrium⁠)가, 확률⁠(probability)⁠을 섞는 전략까지 허용하면 참가자와 전략이 유한한 모든 게임에 있음을 가쿠타니 고정점 정리⁠(Kakutani fixed-point theorem)⁠로 증명했고, 이듬해 브라우어르 고정점 정리⁠(Brouwer fixed-point theorem)⁠로 다시 증명했습니다. 그보다 앞선 1937년 폰 노이만도 경제 성장 모형에서 브라우어르 정리를 넓힌 고정점 정리⁠(fixed-point theorem)⁠를 썼습니다. 논리에서는 괴델의 '나는 증명할 수 없다'는 문장(불완전성 정리⁠, incompleteness theorem⁠)이 '증명할 수 없다'는 성질의 고정점을 만드는 대각선 보조정리⁠(diagonal lemma)⁠로 얻어지고, 람다 계산⁠(lambda calculus)⁠의 Y 조합자⁠(Y combinator)⁠는 어떤 함수에든 고정점을 만들어 주어 재귀⁠(recursion)⁠를 가능하게 합니다. 변수에 타입⁠(type)⁠을 붙인 단순 타입 람다 계산⁠(simply typed lambda calculus)⁠에서는 모든 계산이 반드시 끝납니다. 그 대가로 Y 조합자에는 타입을 붙일 수 없어서, 이런 식의 무제한 재귀는 쓸 수 없습니다.

이어지는 곳. 고정점 근처에서 무슨 일이 일어나는지는 동역학계⁠(dynamical system)⁠의 첫 질문입니다. 고정점의 기울기가 −1을 지나며 안정성⁠(stability)⁠을 잃으면 두 값을 오가는 주기⁠(period)⁠ 2 궤도⁠(orbit)⁠가 태어나고(로지스틱 사상⁠(logistic map)⁠, 분기⁠(bifurcation)⁠), 이런 일이 거듭되면 혼돈⁠(chaos)⁠에 이릅니다. 끌어당기는 고정점은 가장 단순한 끌개⁠(attractor)⁠이고, 훨씬 복잡한 끌개의 예가 로렌츠 끌개⁠(Lorenz attractor)⁠입니다. 연속 시간의 흐름에서는 고정점을 평형점⁠(equilibrium)⁠이라 부르며, 선형 미분방정식⁠(linear differential equation)⁠의 고윳값이 그 안정성을 정합니다. 최솟값을 찾는 경사 하강법⁠(gradient descent)⁠도 기울기가 0인 곳을 고정점으로 삼는 되풀이입니다. 복소평면⁠(complex plane)⁠에서 되풀이의 고정점과 주기점을 따라가면 망델브로 집합⁠(Mandelbrot set)⁠이 나오고, 자기 자신을 가리키는 구조로서의 고정점은 자기 참조⁠(self-reference)⁠와 대각선에서 이어집니다. 거리 대신 '정보의 순서'를 쓰는 고정점도 있습니다. 영역 이론⁠(domain theory)⁠은 재귀로 정의한 프로그램의 뜻을 '아직 모름' ⊥에서 시작한 되풀이 $\bot, F(\bot), F(F(\bot)), \dots$의 상한⁠(upper bound)⁠, 곧 가장 작은 고정점으로 정합니다. 같은 생각을 타입에 쓰면, 목록이나 나무처럼 자기 자신으로 정의되는 타입이 방정식 $X\cong F(X)$의 가장 작은 해로 나오고, 이것이 시작 대수입니다. 모든 부분집합⁠(subset)⁠에 상한과 하한⁠(lower bound)⁠이 있는 순서(완비 격자⁠, complete lattice⁠)에서는 순서를 지키는 함수마다 가장 작은 고정점이 있습니다(크나스터–타르스키 정리). 갈루아 연결⁠(Galois connection)⁠을 한 바퀴 돌아 얻는 닫힘 연산⁠(closure operator)⁠도 이런 함수이고, 그 고정점이 연결의 '닫힌 원소⁠(closed element)⁠'들입니다.