고정점 반복(Fixed-Point Iteration) 기초
기본 아이디어
비선형 방정식 근사를 위한 여러 기법 중에서 고정점 반복(Fixed-Point Iteration)은 가장 단순한 형태로 이해할 수 있는 방법이다. 어떤 비선형 방정식이 $f(x)=0$과 같을 때, 이를 $x = g(x)$의 형태로 변형함으로써,
과 같은 단순 반복을 수행하여 해를 찾고자 한다. 여기에서 $x_{n+1}$은 $(n+1)$번째 근사해이며, $g(x)$는 적절히 정의된 반복 함수이다. 만일 이 반복이 수렴한다면,
인 어떤 극한점 $p$가 존재하여, 결과적으로 $p = g(p)$를 만족한다. 이 $p$가 우리가 찾고자 하는 $f(x)=0$의 해가 된다.
고정점 형태로의 변형
일반적으로 $f(x) = 0$을 $x = g(x)$ 형태로 바꾸는 방법은 여러 가지가 있다. 하나의 전형적인 예로 $f(x)$가 다음과 같이 주어졌다고 가정한다.
라면, 이를
로 만들어 $g(x) = h(x)$로 설정할 수 있다. 혹은
와 같은 형태로 재구성함으로써, 원하는 조건을 만족하는 $g(x)$를 찾을 수 있다. 결국 $x = g(x)$를 만족하는 해가 우리가 원하는 근사 해가 된다.
수렴 조건
고정점 반복을 통해 수렴을 보장받기 위해서는 보통 국소적(Local) 수렴 조건을 확인한다. 특히 $p$가 $x = g(x)$의 고정점이고, $g'(p)$가 존재한다고 할 때,
이면 $p$ 근방에서 $x_{n+1} = g(x_n)$ 반복이 수렴한다는 유명한 이론적 결과가 있다. 이를 점근적 수렴 비율(Asymptotic Convergence Rate) 관점으로 보면, $|g'(p)|$가 작을수록 더 빠르게 수렴한다. 반대로 $|g'(p)| \ge 1$이면 수렴을 담보할 수 없다.
고정점 반복의 구체적 절차
초기값 $x_0$가 주어졌다고 할 때, 다음의 반복 과정을 거친다.
이제 $|g'(p)| < 1$이라는 조건 하에서는 $n \to \infty$로 갈 때 $x_n \to p$가 성립한다. 여기서 $p$는 $x = g(x)$에 대한 고정점이자, 원래 방정식 $f(x) = 0$의 해를 만족한다.
수렴 오차 분석
$x_n$이 고정점 $p$에 근접해 있다고 가정하고, $x_n = p + e_n$으로 표현할 수 있다. 여기서 $e_n$은 $n$번째 반복에서의 오차이다. $n+1$번째 반복에서의 값은
가 된다. 테일러 전개를 이용하면
와 같이 표현 가능하다(적당한 $\xi$가 존재한다고 가정). $p = g(p)$임을 이용하면
즉, $e_{n+1} = g'(p)e_n + \frac{g''(\xi)}{2} e_n^2$라 할 수 있다. 만일 $|g'(p)| < 1$이면 $e_n$이 충분히 작을수록 $|e_{n+1}| \approx |g'(p)||e_n|$이 되므로 선형 수렴(linear convergence)이 일어난다. 또한 $g'(p) = 0$이라면 $|e_{n+1}|$가 $O(e_n^2)$로 줄어드는 이른바 이차 수렴(quadratic convergence)이 일어날 수도 있다.
반복 함수의 선택 기준
고정점 반복에 있어 가장 중요한 문제 중 하나는 $g(x)$를 어떻게 정의하느냐이다. 동일한 방정식 $f(x) = 0$을 서로 다른 형태로 $x = g(x)$로 표현할 수 있기 때문에, $|g'(x)|$가 1보다 훨씬 작아지는 영역을 찾아 적절히 고정점 식을 설정하는 것이 바람직하다. 예를 들어, 다음과 같은 서로 다른 형태가 가능하다.
이면, 이를 $x = \sqrt[3]{x+1}$로 설정할 수도 있고, $x = 1 + x^3$ 형태 등으로도 재배열할 수 있다. 그러나 모든 형태가 동일한 수렴 특성을 갖지는 않으며, 어떤 형태는 수렴이 잘 되지만 다른 형태는 발산할 수도 있다.
안정 영역 시각화
고정점 반복에서는 시각적 방법을 활용하면 이해하기 수월하다. $y = x$와 $y = g(x)$의 교점이 고정점이 된다. 교점 부근에서 $|g'(p)|$이 1보다 작은지를 확인하면, 반복 궤적이 점차 이 교점으로 모이는지 아니면 이탈하는지를 가늠할 수 있다.
위 그림은 단순히 $x_0$에서 시작해 $g$를 반복 적용하여 $p$에 도달하는 과정을 도식화한 것이다. 실제로는 $x_0$가 $p$ 근방에 위치해야만, 그리고 $|g'(p)| < 1$이 성립해야만 수렴이 보장된다.
적용 예시 구상
하나의 간단한 예로 다음 비선형 방정식을 살펴볼 수 있다.
이때 해는 $\sqrt{2}$와 $-\sqrt{2}$ 두 개이지만, 특정 초기값을 선택한 뒤 양의 해 $\sqrt{2}$에 수렴하는 고정점 반복을 시도하려면 예컨대
등의 다양한 방식으로 $x=g(x)$ 형태를 유도할 수 있다. 이 중에서 어떤 형태가 선호되는지는 $g'(x)$의 크기에 달려 있다.
복잡도와 한계
고정점 반복 방법의 가장 큰 장점은 구현이 간단하다는 것이다. 그러나 실제 문제에서 항상 $|g'(p)|<1$을 만족하도록 $g(x)$를 정의하기가 쉽지 않다. 특히, $f(x)=0$ 문제를 단순히 임의로 $x=g(x)$로 바꾼다고 해서 안정적으로 수렴한다는 보장은 없다. 또한 다변수(여러 개의 미지수가 존재하는) 상황에서 고정점 반복을 적용하려면 $\mathbf{x} = \mathbf{g}(\mathbf{x})$ 형태로 확장해야 하며, 이때는 야코비 행렬의 스펙트럼 반경(Spectral Radius) 조건 $\rho(\mathbf{g}'(\mathbf{p}))<1$ 등을 확인해야 한다.
다변수 확장
고정점 반복은 단일 변수에 국한되지 않고 다변수 함수에도 적용할 수 있다. 예를 들어, $\mathbf{x}\in\mathbb{R}^n$에 대해 $\mathbf{f}(\mathbf{x})=\mathbf{0}$을 풀고자 할 때,
와 같은 고정점 형태로 변형하면,
를 반복함으로써 해에 접근할 수 있다. 이때 수렴을 보장받기 위한 국소 조건은,
이다. 여기서 $\mathbf{g}'(\mathbf{p})$는 $\mathbf{g}$의 야코비 행렬(Jacobian matrix)을 $p$에서 평가한 것이며, $\rho(\cdot)$는 행렬의 스펙트럼 반경(spectral radius)을 의미한다. 즉,
이고, $\Lambda$는 $\mathbf{g}'(\mathbf{p})$의 고유값 집합이다. 만약 이 스펙트럼 반경이 1보다 작다면, 고정점 반복은 $p$ 근방에서 국소적으로 수렴한다.
다중근에 대한 고찰
비선형 방정식이 $p$에서 중근(multiple root)을 갖는다면, 즉 $f(p)=0$이면서 $f'(p)=0$인 경우가 발생한다면, 고정점 반복은 일반적인 단순근(simple root)에 대한 경우보다 수렴 속도가 크게 저하될 수 있다. 예를 들어 단일 변수에서 $x=g(x)$ 형태를 만들 때,
이 동시에 성립한다면, 초기값 선택에 따라 수렴 오차가 느리게 줄어들거나 아예 수렴하지 않을 수도 있다. 따라서 이런 상황에서는 고정점 반복 외에 다른 방법(예: 뉴턴 방법, 혹은 변형된 반복법)을 고려하기도 한다.
적응적 방법
고정점 반복에서 가장 중요한 것은 $g(x)$의 적절한 선택이다. 그러나 실제로는 문제의 구조가 복잡하여 $g'(x)$를 직접 살펴보고 수렴 범위를 사전에 예측하기 어려운 경우가 많다. 이런 경우,
$g(x)$를 여러 형태로 시도하고, 경험적으로 수렴 여부 및 수렴 속도를 점검한다.
$g(x)$를 정의한 뒤, 추가적인 댐핑(damping) 요인을 적용하여 $x_{n+1} = \alpha , g(x_n) + (1-\alpha)x_n$와 같이 가중 평균을 쓴다. 등의 방식으로 안정성을 강화할 수 있다. 여기서 $\alpha$는 $0 < \alpha \le 1$ 범위에서 고정 혹은 적응적으로 조정한다. 이를 통해 $|g'(p)|$가 크더라도 $\alpha$를 충분히 작게 잡으면 효과적인 수렴을 기대할 수 있다.
수치 예시 (Python)
간단한 예시로 다음 방정식을 해석해 보자.
이는 $x = \cos x$와 동일하므로, $g(x) = \cos x$로 설정할 수 있다. 이 경우,
초기값을 적당히 선택하면 수렴 여부를 확인할 수 있다. 파이썬으로 간단히 시뮬레이션해 볼 수 있다.
여기서는 $g'(x) = -\sin x$이므로, 실제 해인 $p \approx 0.739085\cdots$에서 $|-\sin p| < 1$임을 확인할 수 있다. 따라서 적당한 초기값을 주면 문제없이 수렴한다.
반복횟수와 정밀도
실제로 고정점 반복을 구현할 때, 언제 반복을 중단해야 할지 결정하는 기준 역시 중요하다. 일반적으로는 $|x_{n+1} - x_n| < \text{(tolerance)}$ 같은 절대 오차 기준이나, 혹은 $|f(x_n)|<\text{(tolerance)}$ 같은 함수값 기준을 활용할 수 있다. 초기값이 좋다면 매우 적은 반복 횟수로도 수렴이 가능하지만, 반대로 초기값이 불량하거나 $|g'(x)| \approx 1$인 구간에 머물면 수렴 속도가 크게 늦어진다.
잔차(Residual) 기반 진단
실제 계산에서는 반복이 진행될 때마다 $f(x_n)$의 크기를 동시에 살펴보기도 한다. $x_n$이 충분히 $p$에 근접하면, $f(x_n)$ 역시 거의 0에 가깝게 떨어진다. 이때 $x_{n+1} = g(x_n)$ 자체를 확인하는 것만으로는 부족하므로, 필요 시
의 변화를 추적하여 반복 종료 시점을 결정하는 것이 바람직하다. 고정점 반복에서 $|g'(p)|$가 1과 멀리 떨어져 있지 않으면, $|x_{n+1} - x_n|$는 작아져도 정작 $f(x_n)$가 상대적으로 크게 남을 수도 있기 때문이다.
고정점 반복의 이론적 기반: Banach 고정점 정리
고정점 반복법의 가장 중요한 이론적 근거 중 하나는 완비(metric complete) 공간에서의 Banach 고정점 정리(Banach Fixed-Point Theorem)이다. 이를 간단히 요약하면, 어떤 폐집합 내에서 국소적 혹은 전역적으로 Lipschitz 상수 $q<1$을 만족하는 축약(contraction) 사상이 존재한다면, 그 사상에는 유일한 고정점이 존재하고 반복을 통해 수렴한다는 것이다. 구체적으로 단일 변수 혹은 다변수 모두에 대해, $g$가 축약 사상이라면
이 성립하고, $g$의 이미지가 존재 구간(또는 영역) 안에 완전히 포함된다면 고정점 $p$는 유일하며
반복으로 $\mathbf{x}_n \to p$가 보장된다. 이때 $q<1$ 조건이 $|g'(p)|<1$ (또는 다변수의 경우 스펙트럼 반경이 1보다 작음)과 연결된다.
고정점 반복과 사상(contraction)의 관계
$|g'(p)| < 1$이라고 해서 $g$가 반드시 전체 구간에서 축약 사상이 된다는 뜻은 아니다. 하지만 $p$ 근방에서
이면, 국소적으로 축약 성질이 일시적으로 만족되어 국소 수렴이 가능하다. 반면 $g$가 전역 축약 사상이라면, 초기값을 어떻게 잡아도 전역적으로 수렴하게 된다. 실제 함수에서는 전역 축약 사상을 만족하는 $g$를 구성하기가 쉽지 않을 때가 많다.
축약 상수와 수렴 속도
$|g'(p)|$가 작을수록, 혹은 다변수에서 $\rho(\mathbf{g}'(\mathbf{p}))$가 작을수록 수렴 속도가 빨라진다. 구체적으로 선형 수렴 단계에서
형태로 오차가 기하급수적으로 감소한다. $q$가 1에 근접하면 수렴 속도가 매우 느려지며, $q$가 0에 가까우면 반복 횟수가 훨씬 적게 들어 빠르게 수렴한다. 실제 계산에서 $g'(x)$가 0에 가까운 형태를 인위적으로 만들면 이차 수렴(quadratic convergence)이나 초월적(초선형) 수렴 등이 일어날 수도 있다.
실용적 전처리 기법
고정점 반복에서 $g$의 적절한 선택이 어렵거나, 단순히 $f(x)=0$ 문제를 $x=g(x)$ 형태로 직접 바꾸기가 까다로운 경우, 사전에 다른 변환이나 전처리를 적용할 수 있다. 예를 들어, $f(x)$가 특정 다항식일 때 적절한 변수 치환을 미리 해두거나, 혹은 $f(x)$를 분해하여 일부를 다른 항으로 이끌어냄으로써 $g'(x)$의 크기를 줄이는 전략을 쓴다. 다변수 방정식에서도, $\mathbf{M}^{-1} \mathbf{f}(\mathbf{x})$ 형태로 선형 연산자를 곱해 준 뒤 $\mathbf{x} = \mathbf{x} - \mathbf{M}^{-1}\mathbf{f}(\mathbf{x})$ 같은 식으로 구성하여 고정점 반복을 유도하기도 한다. (이는 뉴턴 방법과도 관련이 있다.)
가이 스라이델(Gauss-Seidel) 등 선형계 해법과의 유사성
선형계 $\mathbf{A}\mathbf{x}=\mathbf{b}$를 푸는 데 자주 쓰이는 Jacobi 반복, Gauss-Seidel 반복, Successive Over Relaxation(SOR) 등도 결국은 고정점 반복의 한 형태로 볼 수 있다. 예를 들어, Gauss-Seidel 방법은 다음과 같이 쓸 수 있다.
단, 이때 $\mathbf{G}'(\mathbf{x})$가 특정 조건을 만족해야 수렴이 보장되는 것처럼, 선형계 반복법에서도 $|\mathbf{I} - \mathbf{M}^{-1}\mathbf{A}| < 1$ 같은 조건이 등장한다. 즉, 선형 반복 해법들도 고정점 반복 이론의 부분 집합으로 설명 가능하다.
초기값 선택의 중요성
고정점 반복은 보통 국소 수렴 성질을 가진다. 즉, 초기값이 고정점 $p$ 근처에 있어야만 수렴이 이루어진다. 초기값이 너무 멀리 있으면 $|g'(x)|$가 1 이상인 구간으로 벗어나 발산해 버리는 상황이 생긴다. 이에 따라 다음과 같은 전략이 유용하다. 먼저 브래킷(Bracket) 기법 등으로 해가 있을 법한 구간을 추정한 뒤, 그 구간 안에서 적당히 $x_0$를 고르고 반복을 시작한다. 혹은 여러 개의 초기값을 분산적으로 배치해 보고, 어느 지점에서 수렴이 시작되는지를 확인해 가며 선택을 조정하기도 한다.
고차 근사와 리처드슨 가속(Richardson Extrapolation)
선형 수렴을 가속하기 위해, 고정점 반복 중간 단계에서 발생하는 값들을 후처리(Post-processing)하여 오차를 줄이는 기술도 있다. 예컨대 리처드슨 가속은 $x_{n}$, $x_{n+1}$, $x_{n+2}$ 세 지점의 정보를 적절히 결합하여 오차 항을 상쇄하는 방식을 쓴다. 다만, 이 기법이 안정적으로 작동하려면 $x_n$이 어느 정도 수렴 영역에 들어가 있어야 하며, 수렴 양상이 거의 선형이어야 한다. 이런 가속 기법을 잘 쓰면, 실제 반복 횟수는 동일하더라도 유효 자릿수를 더 빠르게 확보할 수 있다.
고정점 반복과 뉴턴 방법의 비교
뉴턴 방법(Newton's Method)은 $f'(x)$가 존재한다는 가정하에
형태로 이차 수렴을 달성하는 강력한 방법이다. 이를 고정점 반복으로 해석하면,
라는 형태, 즉
가 된다. 당연히 고정점 반복 이론을 적용할 수 있고, $|g'(p)|<1$이 성립하면 국소적으로 매우 빠른 수렴을 얻는다. 그러나 뉴턴 방법은 $f'(x)$를 구해야 하며, 적절한 초기값 선택이 더욱 까다로울 수 있다는 단점이 있다. 고정점 반복은 $f'(x)$ 계산이 필요 없어 구현이 더 단순하지만, 그에 상응하여 수렴 속도가 더 느릴 가능성이 높다.
혼합 접근
어떤 상황에서는 고정점 반복과 뉴턴 방법, 혹은 이외의 다른 알고리즘을 절충하여 사용하는 것이 유리하다. 예컨대 초기에 $f'(x)$가 충분히 간단히 주어지지 않거나, 혹은 $x$가 아직 해에 가깝지 않아 뉴턴 방법의 수렴이 보장되지 않을 때는, 먼저 간단한 고정점 반복으로 해 근처까지 접근한다. 그리고 어느 정도 근방에 도달했다고 판단되면 뉴턴 방법으로 전환하여 빠르게 수렴률을 끌어올리는 방법도 쓸 수 있다.
복소 영역에서의 고정점 반복
복소 변수를 다루는 경우에도 고정점 반복은 동일한 형태로 적용할 수 있다. $f(z)=0$, $z\in\mathbb{C}$ 문제를 $z=g(z)$ 형태로 전환하고, $|g'(p)|<1$ (복소 미분 가능 시) 조건이 성립하면 국소적으로 수렴한다. 뉴턴 프랙탈(Newton Fractal)이 복소 평면에서의 뉴턴 방법 수렴을 시각적으로 보여 주는 예시인 것처럼, 복소 고정점 반복의 수렴/발산 영역도 매우 다채로운 패턴을 형성할 수 있다. 이 분야는 순수수학적으로도 연구 대상이 된다.
계산 비용과 스토리지
고정점 반복은 각 단계에서 $g(x_n)$만 계산하면 되므로, 대체로 매우 적은 계산량과 메모리를 소모한다. 그러나 수렴률이 느릴 수 있으므로, 원하는 정밀도를 달성하기까지 많은 반복이 필요할 때가 있다. 반면에 뉴턴 방법 등은 각 단계마다 미분 연산 혹은 야코비 행렬 계산 등 부가적인 비용을 요구하지만, 반복 횟수 자체는 적을 수 있다. 따라서 실제 응용에서는 두 방법의 장단점을 고려해 문제 규모나 정밀도 요구사항, 구현상의 편의 등을 종합적으로 판단해 선택하게 된다.
추가적 가속 기법: Steffensen 방법
고정점 반복에서는 특정 조건에서 수렴 속도를 인위적으로 가속하기 위해 Steffensen 방법(Steffensen's Method)을 적용할 수 있다. 뉴턴 방법이 $f'(x)$를 필요로 하는 반면, Steffensen 방법은 고정점 반복에서 얻어지는 함수값만으로 이차 수렴(quadratic convergence)에 가까운 효과를 낼 수 있는 특징이 있다. 기본적인 형태는 다음과 같이 요약된다. 단순 고정점 반복
과정에서 $x_n$, $g(x_n)$, $g(g(x_n))$를 이용해 다음을 계산한다.
이는 사실 Aitken $\Delta^2$ 공식을 고정점 반복에 적용한 것이다. 이렇게 하면 $g'(p)$가 0이 아닐 때도 단순 고정점 반복보다 빠른 수렴을 유도할 수 있다. 물론 분모가 0에 가까워지는 경우가 발생하면 수치적 안정성 문제가 커지므로, 실제 구현 시에는 각 단계에서 분모가 너무 작아지지 않는지 점검하는 절차가 필요하다.
비선형 연산방정식과의 연관성
고정점 반복 이론은 (유한 차원) 연립방정식뿐 아니라, 더 일반적인 무한 차원 방정식, 예컨대 편미분방정식의 약화(Weak) 형태를 해석하는 문제에서도 적용될 수 있다. 예를 들어, 어떤 편미분방정식을 적절히 재구성하여 유한요소(FEM) 기반 근사 해석을 할 때, 반복적으로 해를 갱신하는 방식이 결국 $u = \mathbf{G}(u)$ 형태의 고정점 해석으로 귀결되기도 한다. 이때 Banach 고정점 정리를 이용해 국소(또는 전역) 수렴을 증명하거나, 반복 과정에서 필요한 사상의 축약 성질을 검증하는 작업이 중요하다.
브로이어(Brouwer) 고정점 정리와의 구분
고정점 문제 하면 고등수학(위상수학)에서 등장하는 브로이어(Brouwer) 고정점 정리를 쉽게 연상할 수 있다. 브로이어 정리는 유계 폐볼록체(Convex Compact Set) 위에서 정의된 연속 매핑에는 반드시 고정점이 존재한다는 추상적 내용을 다룬다. 하지만 수치해석에서 말하는 고정점 반복이나 Banach 고정점 정리는 수렴 과정을 명확히 제공한다는 점에서 다르다. 브로이어 고정점 정리는 존재성(existence)만 보장해 줄 뿐, 어떤 방식으로 그 점에 접근할지에 대한 수렴 알고리즘을 직접적으로 제시하지는 않는다.
에이트켄(Aitken) $\Delta^2$ 공식의 일반화
Steffensen 방법의 기반이 되는 에이트켄(Aitken) 가속은, 일반적인 스칼라 수열 ${x_n}$에 대해 오차 감소를 가속하는 기법이다. 이를 고정점 반복 수열 $x_n = g(x_{n-1})$에 적용해 얻어진 것이 Steffensen 방법이다. 실제로 Steffensen 방법은 뉴턴 방법이나 할선(Secant) 방법처럼 명시적인 도함수를 구하지 않고도 빠른 수렴을 얻을 수 있는 유용한 수단이다. 다만, 구현을 위해서는 각 반복마다 $g$를 최소 두 번 더 평가해야 하므로, $g$ 평가 비용이 큰 문제에서는 효율성을 면밀히 따져야 한다.
멀티 격자(Multigrid) 구조와의 연관
편미분 방정식을 반복적으로 해석할 때 자주 사용되는 멀티 격자(Multigrid) 기법 역시 고정점 반복의 아이디어를 포함하고 있다. 대략적인 해를 빠르게 구한 뒤(저해상도 격자), 그 해를 더 높은 해상도 격자로 전달하여 보정하는 절차를 반복하게 되는데, 그 과정 자체가 일종의 고정점 연산을 여러 스케일(Scale)에서 수행하는 셈이다. 멀티 격자 기법은 선형 혹은 비선형 시스템 모두에 응용 가능하며, 대규모 문제에서도 수렴 속도를 획기적으로 향상시킨다.
준뉴턴(Quasi-Newton) 계열과 고정점 반복
준뉴턴(Quasi-Newton) 알고리즘은 뉴턴 방법처럼 미분(야코비 행렬)을 직접 구하지 않고, 반복 중에 근사행렬을 갱신해 가며 해를 찾는 방법이다. 이 역시
형태의 고정점 반복으로 해석할 수 있다. 여기서 $\mathbf{B}$는 $\mathbf{f}'(\mathbf{x})$를 근사하는 행렬이다. 대표적으로 BFGS, DFP, SR1 등의 스키마가 있으며, 각각 행렬 갱신 방식이 다르다. 이처럼 준뉴턴 계열은 미분을 직접 계산하기 번거로운 문제에서, 고정점 반복의 일반화를 통해 고급 수렴률을 얻고자 하는 아이디어의 연장선으로 이해할 수 있다.
임의 정밀도(Arbitrary Precision) 구현 시 고려사항
고정점 반복을 매우 높은 정밀도로 수행해야 하는 상황(예: 다중 정밀도 연산 라이브러리 사용)에서는 부동소수점(Floating-Point) 오차가 커지지 않도록 주의해야 한다. 예컨대 $x_{n+1} = g(x_n)$ 계산 과정에서 $x_n$과 $g(x_n)$가 거의 같은 값이 되면, 부동소수점 뺄셈 오류(Cancellation Error)가 크게 발생할 수 있다. 이런 문제를 완화하기 위해,
같은 식을 더 세심하게 처리하거나, 정밀도를 점진적으로 올리는 전략, 혹은 여러 형태의 댐핑을 조합하는 방법을 모색할 수 있다.
병렬화와 분산 계산
고정점 반복의 큰 장점 중 하나는, $g(x)$를 여러 부분 문제로 분할하여 병렬 혹은 분산적으로 계산할 수 있는 구조를 잘 활용하면, 매우 대규모 문제에서도 계산 효율을 높일 수 있다는 점이다. 예컨대 $\mathbf{g}(\mathbf{x})$가 구성 요소별로 독립성이 높다면, 각 노드가 $\mathbf{g}$의 일부를 계산하고 결과를 종합하여 $\mathbf{x}_{n+1}$을 구하는 방식으로 확장 가능하다. 뉴턴 방법이 야코비 행렬을 구성하고 풀어야 하는 데 비해, 고정점 반복은 단순 함수 평가만 수행하면 되므로 병렬화가 상대적으로 쉬운 면이 있다.
이행 영역(Transient Region)에서의 거동
초기값이 해에 근접하지 않은 경우, 즉 이행 영역(Transient Region)에서의 거동은 고정점 반복에서 단순히 $|g'(p)|<1$ 조건만으로는 예측하기 어렵다. $g(x)$가 해 근처에서는 축약이더라도, 멀리 떨어진 영역에서는 $|g'(x)| \ge 1$인 지점이 존재할 수 있다. 따라서 이 영역을 어떻게 통과하여 해 근방으로 들어가는가에 따라 최종적으로 수렴할지 말지가 결정된다. 경우에 따라선, 이행 영역에서 $|x_{n+1} - x_n|$이 일정 범위 이상으로 커지지 않도록 인위적으로 제한(예: 클리핑, 스케일링)하거나, 매 반복 단계에서 해석적으로 $x_n$이 폭주하지 않도록 조정하는 방법을 쓴다.
차분방정식과의 관련성
고정점 반복은 미분방정식을 직접적으로 풀 때 사용하는 $\dot{x} = F(x)$ 형태의 초기값 문제와도 유사한 면이 있다. 예컨대 $\dot{x} = F(x)$를 오일러(Euler) 방법으로 전진 오차를 사용해 적분하면,
같은 차분방정식이 얻어진다. 이는 $g(x_n)=x_n + h,F(x_n)$ 형태의 고정점 반복으로 볼 수 있다. 따라서 연속계(연립 미분방정식)에서 불안정한 국소 해석을 보이는 구간은, 대응하는 고정점 반복에서도 유사한 불안정을 보여 주곤 한다. 이런 관점으로 보면, 적절히 댐핑(damping) 계수를 조정하는 것은 오일러 메서드에서의 시간 스텝 $h$를 조정하는 것과 같은 의미를 가진다.
안정성(Stability)과 진동 거동
고정점 반복에서, 고정점 근방의 유도함수($g'(p)$)가 갖는 부호나 복소성을 통해 반복의 안정성을 좀 더 자세히 살펴볼 수 있다. 실수 범위에서 $g'(p)$가 음수일 때, 예컨대 $g'(p)=-\alpha$ 형태로 $\alpha>0$이고 $|\alpha|<1$이라면 반복이 수렴하되, 단계마다 부호가 뒤바뀌어 $p$를 중심으로 양쪽을 오가며 진동하는 형태를 보인다. 이를 간단히 표현하면,
이므로, $n$이 1 증가할 때마다 오차 부호가 바뀌어 양방향으로 근접한다. $|\alpha|$가 1에 가까울수록, 진동 폭이 서서히 줄어들면서도 상당히 많은 반복 횟수를 거친 뒤에야 충분히 작은 오차를 얻을 수 있다.
만약 $g'(p)$가 복소수라면, 실제 계산에서 $g(x)$가 실수 함수라고 하더라도, 어떤 구간에서 국소적으로 복소 공액근을 형성하는 경우가 있을 수 있으며, 이는 2차 혹은 고차의 국소 다항 근사에서 나타나는 효과일 수 있다. 이때 고정점 근방에서 오차 항이 회전(Spiral)하며 줄어드는 양상을 보일 수도 있다. 단일 변수의 실함수에서 이런 현상은 드물지만, 다변수나 복소 함수로 확장하면 흔하게 등장한다.
카오스(Chaos)적 거동
$g(x)$가 단순한 축약 사상이 아니라, 특정 구간에서 $|g'(x)|>1$인 영역을 갖고 있으면, 초기값에 따라 극단적으로 다른 거동이 나타나기도 한다. 예컨대 고전적으로 알려진 로지스틱(logistic) 맵 $x \mapsto r x (1 - x)$ 같은 비선형 반복은, 파라미터 $r$가 특정 범위를 넘으면 고정점 반복이 수렴하지 않고 주기궤도나 혼돈(Chaos)이 발생한다. 일반적인 비선형 방정식 해석에서도, $g$ 함수를 잘못 정의하면 부분적으로 혼돈 현상이 생길 수 있다. 이 경우 해에 대한 접근이 사실상 불가능하다. 따라서 $g(x)$의 선택이 적절해야만, 안정적 수렴을 기대할 수 있다.
앤더슨 가속(Anderson Acceleration)
Steffensen 및 Aitken 계열 기법 외에도, 다차원이나 실용적 고정점 반복에서 많이 활용되는 방법 중 하나가 앤더슨 가속(Anderson Acceleration)이다. 이를 앤더슨 혼합(Anderson Mixing)이라고도 부른다. 기본 아이디어는 최근 여러 단계의 갱신 벡터(오차 또는 $g(\mathbf{x}_n) - \mathbf{x}_n$ 등)를 선형 결합하여, 가장 빠른 감소를 기대하는 방향으로 보정하는 것이다. 예를 들어,
라 하고, 최근 $m$단계 동안의 $\mathbf{r}_k$와 $\Delta \mathbf{x}_k = \mathbf{x}k - \mathbf{x}{k-1}$ 등을 모아두면, 이를 통해 사후적(Ex-post) 선형 결합 계수를 구하여 다음 단계 해석에 반영한다. 그렇게 함으로써 단순한 고정점 반복보다 훨씬 빠른 수렴을 얻을 수 있는데, 특히 비선형 시스템이나 고차원 문제에서 효과적이다. 앤더슨 가속은 다음과 같은 형태의 과정을 거친다.
기본 고정점 반복으로부터 $\mathbf{x}_{n+1}^{(0)} = \mathbf{g}(\mathbf{x}_n)$을 얻는다.
최근 몇 단계의 잔차 $\mathbf{r}_k$와 해 증분 $\Delta \mathbf{x}_k$를 모아, 최소제곱 문제를 푼다.
그 결과를 이용해 $\mathbf{x}{n+1} = \mathbf{x}{n+1}^{(0)} + \dots$ 식으로 보정한다.
이 방식은 특히 $g$가 해 근방에서 $|\mathbf{g}'(\mathbf{p})|\approx 1$에 근접한 경우, 혹은 선형 근사만으로는 개선이 어렵지만 다수의 관측 정보를 합성하면 수렴율을 높일 수 있는 문제에서 큰 위력을 발휘한다. 다만, 매 단계에서 추가적인 선형 대수 계산(작은 규모의 선형계 혹은 최소제곱 문제 해결)이 필요하므로, $g$의 평가 비용과 별도로 연산이 증가한다는 점을 고려해야 한다.
크릴로프(Krylov) 기반 비선형 해법
비선형 고정점 반복에서, 한 단계마다 발생하는 오차 $\mathbf{r}_n$에 대해 크릴로프 서브스페이스(Krylov Subspace)를 활용하는 방안도 연구되어 왔다. GMRES나 BiCGSTAB 같은 선형 크릴로프 반복법의 비선형 판본에 해당하는 기법들은, 현재 잔차를 해소하기 위한 적절한 선형 결합 방향을 탐색한다. 이를 단순 고정점 반복의 보조로 사용하는 방법을 ‘비선형 GMRES’ 또는 ‘N-GMRES’ 등으로 부르기도 한다. 이는 앤더슨 가속과 근본적으로 비슷한 사상으로 이해할 수도 있지만, 구현 관점이나 수렴 분석 측면에서 약간의 차이가 있다. 이런 크릴로프 기반 알고리즘은 대규모 비선형 방정식(특히 편미분방정식 유한차분, 유한요소 해법)에서 유용하며, 뉴턴 방법보다 매 반복에서의 미분(혹은 야코비 행렬) 계산 부담을 낮추고자 할 때 고정점 반복과의 혼합으로 사용된다.
준안정점(Semi-Stable Fixed Point)
비선형 동역학이나 반복법에서, $g'(p)=1$인 경우를 준안정(Semi-stable) 상태라고 부르기도 한다. 이 경우 매우 느리게 수렴하거나, 수렴 반경이 극도로 작아서 초기값이 조금만 멀어도 발산해 버릴 수 있다. 즉,
이면, $p$가 고정점이지만 (엄밀하게) 축약 사상이 아니므로 Banach 고정점 정리는 직접 적용이 어렵다. 실제 계산에서는 $p$ 근방에 진입해야만 겨우 수렴하게 된다. 게다가, $g'(p)$가 1을 초과하거나 -1 이하로 떨어지면(즉, $|g'(p)|>1$) 오히려 발산 혹은 복잡한 주기점으로 이행할 위험이 있다. 이럴 때는 뉴턴 방법, 앤더슨 가속, 또는 다른 고차 반복 방법을 병행 고려해야 한다.
실험적 수렴율 추정
실제 계산에서 고정점 반복의 수렴율을 평가하려면, 여러 단계의 해 $x_n$을 저장하고 각 단계의 오차나 잔차가 어떻게 줄어드는지 모니터링한다. 예컨대 단일 변수에서 정확한 해 $p$를 알고 있다면,
값의 극한을 관측함으로써 $|g'(p)|$를 가늠할 수 있다. 해 $p$를 모르는 상황에서는, 이미 충분히 근접한 $x_{n}$과 $x_{n+1}$, $x_{n+2}$에 대하여
형태로 추정한 뒤, 수렴이 선형(일정 비율로 감소)인지, 혹은 더 높은 차수로 떨어지는지를 추적한다. 또한 다변수 상황에서는 벡터 노름이나 $\max$ 노름 등을 활용해 유사한 아이디어로 추정할 수 있다.
고정점 반복의 임계적 활용
실제 산업 응용이나 대형 해석 소프트웨어에서는, 고정점 반복이 뉴턴 방법 등과 함께 보완적으로 사용되는 경우가 많다. 예컨대 방정식의 구조나 행렬 성질상, 매 반복에서 야코비 행렬이나 해의 선형화 문제를 풀기 어렵다면, 간단히 $g(\mathbf{x})$를 구성해 매 스텝을 계산하는 방식을 택한다. 또는 큰 스텝으로 뉴턴 보정이 어려울 때, 고정점 반복을 이용해 스텝 크기를 줄이면서 구조를 보존하는 전처리 역할을 수행한다. 이처럼 고정점 반복은 간단성(simple implementation)과 병렬화 용이성, 그리고 부가적인 미분 계산이 필요 없다는 장점을 지니므로, 다양한 맥락에서 최적화나 비선형 해석의 기본 도구로 여전히 활발히 쓰인다.
혼합 정리(Hybrid Methods)와 활용 예시
실무에서는 고정점 반복만으로는 충분한 수렴 성능을 확보하기 어렵거나, 뉴턴 방법 같은 고차 기법은 도함수 계산이 부담스러울 때, 두 가지를 혼합하여 사용하는 방법이 활발히 응용된다. 예컨대 초기 단계에서는 고정점 반복을 사용해 상대적으로 먼 영역에서 안정적(혹은 단순한) 접근을 시도하고, 해 근방에 도달했다고 판단되면 뉴턴 혹은 준뉴턴으로 전환하여 빠른 이차 수렴(quadratic convergence)을 구현할 수 있다. 이를테면 다음과 같은 절차를 구상할 수 있다.
먼저, $f(x)$에 대해 단순 고정점 반복 $x_{n+1} = g(x_n)$을 적용해, $x_n$이 안정적으로 수렴 영역 안에 들어오도록 유도한다.
만일 오차가 어느 정도 이하로 떨어지거나, 혹은 $|x_{n+1} - x_n|$이 매우 작아지는 시점에 도달하면, 뉴턴 단계
혹은 다른 고급 기법으로 교체한다.
이 과정을 통합적으로 구성하면, 이행 구간에서 발생하는 발산 위험을 줄이고 최종 국소 영역에서의 빠른 수렴을 최대한 누릴 수 있다. 다변수 방정식에서도 마찬가지로 $\mathbf{x} = \mathbf{g}(\mathbf{x})$ 반복과 준뉴턴, 혹은 앤더슨 가속 등을 조합하여 혼합 전략을 쓸 수 있다.
예측자-보정자(Predictor-Corrector) 관점
수치적 해석 전반에서 자주 등장하는 ‘예측자-보정자’(Predictor-Corrector) 프레임워크로도 고정점 반복을 설명할 수 있다.
예측자(Predictor)는 단순화된 고정점 반복(혹은 간단한 선형화)을 통해 임시 해 $\tilde{x}_{n+1}$을 얻는다.
보정자(Corrector)는 더 정교한 식(예: 뉴턴 단계, 혹은 댐핑된 보정)을 사용해 $\tilde{x}{n+1}$을 보완한 뒤 실제 해 $x{n+1}$을 결정한다.
이런 이중 구조를 택하면, 매 단계마다 $f'(x)$를 정확히 구하지 않고도 ‘예측’을 빠르게 수행한 뒤, 보정에서 오차를 크게 줄여 수렴 성능을 높일 수 있다. 다만, 보정 과정에서 추가 계산이 발생하므로, 예측과 보정의 균형점을 어떻게 잡을지는 문제 규모와 $g$의 성질에 따라 달라진다.
불연속 함수 및 특이점
고정점 반복은 $g(x)$가 연속적이며, $g'(x)$가 (국소적으로라도) 존재하는 상황에서 보통 다룬다. 하지만, 실무에서는 비연속 점이나 특이점(singularity)이 있는 문제를 만나기도 한다. 예컨대 $g(x) = \frac{1}{x}$와 같은 형태는 $x=0$에서 특이점을 가진다. 이런 경우
특이점을 피하는 구간에서 초기값을 선정하고, 특이점 바깥에서 반복이 이뤄지도록 제어해야 한다.
특이점 근방에서 $g'(x)$가 발산하기 쉽고, $|g'(p)|<1$ 조건이 쉽게 깨질 수 있으므로, 반복 도중에 $x_n$이 특이점에 접근하지 않도록 방어적으로 알고리즘을 설계해야 한다.
만약 $g(x)$가 불연속성을 갖는다면, 어떤 점 $p$에서 $p=g(p)$가 형식적으로 성립하더라도, 국소적 연속성과 미분 가능성이 깨져 버리므로 일반적인 고정점 정리나 수렴 분석을 적용하기 힘들다. 이때는 문제 구조를 재검토하여, 불연속이나 특이점이 없는 다른 형태로 방정식을 재정의할 필요가 있다.
고정점 반복 기반의 간단 최적화 기법
최적화(Optimization) 문제도, $\nabla f(\mathbf{x}) = \mathbf{0}$을 해석한다는 점에서, ‘미분=0’ 형태의 고정점 해석과 연결된다. 예컨대 스칼라 함수 $J(x)$를 최소화하는 문제에서 $\frac{d}{dx} J(x) = 0$을 풀면, 결국 $x = x - \alpha \frac{d}{dx}J(x)$ 같은 ‘경사 하강법(Gradient Descent)’을 생각해 볼 수 있다. 이는
형태로, 고정점 반복으로 해석하면 $g(x) = x - \alpha \nabla J(x)$가 된다. 여기서 $\alpha$가 충분히 작으면 국소적 축약 사상이 될 수 있으며, 결국 고정점 반복으로써 최적화 문제의 해에 접근한다. 물론 $\alpha$를 적절히 설정해야만, 수렴성이 유지된다. 좀 더 진보된 최적화 알고리즘(예: 비선형 공선 탐색, LBFGS 등)도 근본적으로는 고정점 형태 $\mathbf{x} = \mathbf{x} - \mathbf{B}^{-1}\nabla J(\mathbf{x})$를 반복하는 과정으로 이해할 수 있다.
결어 없이 마무리
이상으로 고정점 반복의 기초 개념, 수렴 이론, 다양한 가속화 기법 및 적용 사례 등을 폭넓게 살펴보았다. 이에 관한 더욱 세부적인 사항이나 예제, 그리고 다른 근사 알고리즘과의 비교 등은 뒤이어 다루게 될 것이다.
Last updated