7.135 수렴 차수의 정의와 분류

1. 수렴 차수의 정의

수렴 차수(order of convergence)는 반복 알고리즘이 해에 접근하는 속도를 정량적으로 특성화하는 개념이다. 수열 $\{\mathbf{x}_k\}$ 가 $\mathbf{x}^*$ 에 수렴할 때, 오차를 $e_k = \lVert \mathbf{x}_k - \mathbf{x}^* \rVert$ 로 정의하면, 수렴 차수 $p \geq 1$ 은 다음을 만족하는 양의 상수 $C$ 가 존재하는 경우로 정의된다.

$\lim_{k \to \infty} \frac{e_{k+1}}{e_k^p} = C, \quad 0 < C < \infty$

$p$ 가 클수록 더 빠른 수렴이다. $p = 1$ 이면 선형 수렴, $p = 2$ 이면 이차 수렴이라 한다.

2. 선형 수렴 (Q-선형 수렴)

$\lim_{k \to \infty} \frac{e_{k+1}}{e_k} = \rho, \quad 0 < \rho < 1$

수렴비(convergence ratio) $\rho$ 는 매 반복마다 오차가 일정한 비율로 감소함을 의미한다. $\rho$ 가 1에 가까우면 수렴이 느리고, 0에 가까우면 빠르다.

예: 고정 학습률의 경사 하강법은 강볼록 함수에서 선형 수렴하며, 수렴비는 $\rho = (\kappa - 1)/(\kappa + 1)$ 이다.

$\epsilon$ -정확도( $e_k < \epsilon$ )를 달성하기 위해 필요한 반복 횟수는 $O(\log(1/\epsilon))$ 이다.

3. 초선형 수렴 (Q-초선형 수렴)

$\lim_{k \to \infty} \frac{e_{k+1}}{e_k} = 0$

수렴비가 반복에 따라 영으로 감소한다. 선형 수렴보다 빠르지만 이차 수렴보다 느리다.

예: BFGS 준뉴턴법은 최적해 근방에서 초선형 수렴한다. 유효 수렴비가 반복에 따라 점차 작아져 후기 반복에서 급속한 수렴이 관찰된다.

4. 이차 수렴 (Q-이차 수렴)

$\lim_{k \to \infty} \frac{e_{k+1}}{e_k^2} = C, \quad C > 0$

매 반복마다 유효 자릿수가 두 배로 증가한다. $e_k = 10^{-3}$ 이면 $e_{k+1} \approx C \cdot 10^{-6}$ , $e_{k+2} \approx C^3 \cdot 10^{-12}$ 이다.

예: 뉴턴 방법은 최적해 근방에서 이차 수렴한다. $\epsilon$ -정확도를 달성하기 위해 $O(\log\log(1/\epsilon))$ 회의 반복이 필요하며, 이는 실용적으로 5~10회 이내이다.

5. R-수렴과 Q-수렴

위의 정의는 Q-수렴(quotient convergence)에 해당하며, 연속 오차의 비율(quotient)에 기반한다. R-수렴(root convergence)은 다음과 같이 정의된다.

$\limsup_{k \to \infty} e_k^{1/k} = \rho$

R-선형 수렴은 오차가 기하급수적으로 감소함( $e_k \leq M\rho^k$ , $M > 0$ , $0 < \rho < 1$ )을 의미한다. Q-선형 수렴은 R-선형 수렴을 함의하지만, 그 역은 일반적으로 성립하지 않는다. R-수렴은 단조롭지 않은 오차 감소에서도 전체적인 수렴 속도를 측정할 수 있는 장점이 있다.

6. 수렴 차수의 비교

수렴 차수	$e_k = 10^{-1}$ 후 3회 반복	대표 알고리즘
선형 ( $\rho = 0.5$ )	$10^{-1} \to 10^{-1.3} \to 10^{-1.6} \to 10^{-1.9}$	경사 하강법
초선형	$10^{-1} \to 10^{-2} \to 10^{-4} \to 10^{-8}$ (점차 가속)	BFGS
이차	$10^{-1} \to 10^{-2} \to 10^{-4} \to 10^{-8}$	뉴턴법
삼차	$10^{-1} \to 10^{-3} \to 10^{-9} \to 10^{-27}$	할리(Halley) 방법

7. 수렴 차수와 반복당 비용의 상충

높은 수렴 차수는 적은 반복 횟수를 의미하지만, 높은 차수의 알고리즘은 통상 반복당 비용이 높다. 총 계산 비용은 반복 횟수와 반복당 비용의 곱이므로, 단순히 수렴 차수가 높은 알고리즘이 항상 효율적인 것은 아니다.

정보 효율(information efficiency): 반복당 요구하는 도함수 정보의 차수와 계산 비용을 고려하면, 뉴턴법은 반복당 $O(n^3)$ 이지만 이차 수렴, 경사 하강법은 반복당 $O(n)$ 이지만 선형 수렴이다. 대규모 문제에서는 경사 하강법의 총 비용이 뉴턴법보다 작을 수 있다.

8. 로봇 공학에서의 함의

실시간 로봇 제어에서는 수렴 차수보다 제한된 반복 횟수 내에서의 해의 품질이 중요하다. 모델 예측 제어에서 1~5회의 반복만을 수행하는 경우, 이차 수렴 알고리즘이 선형 수렴 알고리즘보다 현저히 나은 결과를 산출한다. 반면, 오프라인 최적화에서는 반복당 비용이 총 시간을 지배하므로 반복당 비용이 낮은 알고리즘이 선호될 수 있다.

9. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press.
Dennis, J. E., & Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM.

version: 1.0