# 근사해의 수렴 속도와 오차 평가 #### 수렴 속도의 정의와 일반적 고찰 비선형 방정식을 해석적으로 풀 수 없을 때, 수치적 접근 방법을 통해 근사해를 구한다. 이때 사용되는 반복법의 성능을 평가하기 위해서는 해당 반복법이 어떤 속도로 근사해에 접근하는지를 파악하는 것이 중요하다. 근사해가 실제 해(정확해)에 얼마나 빨리 수렴하는지를 나타내는 척도를 수렴 속도라고 한다. 보통 다음과 같은 일반적 개념들을 사용하여 수렴 속도를 정의한다. 근사해를 구하기 위해 반복법을 사용한다고 하자. 이를 간단히 표현하면 $$ x\_{n+1} = \phi(x\_n) $$ 와 같은 꼴로 나타내게 된다. 여기에서 $x\_n$은 $n$번째 반복에서의 근사해이며, $x^\*$는 실제로 구하고자 하는 해라고 가정한다. 수렴 속도를 이해하기 위해 크게 두 가지가 필요하다. 하나는 오차를 어떻게 측정하느냐(오차 척도)이며, 다른 하나는 그 오차가 반복을 통해 어떤 양상으로 줄어드느냐(수렴 차수)이다. #### 오차 척도 수치해에서 오차를 평가할 때는 보통 절대 오차와 상대 오차를 구분한다. 절대 오차는 $$ e\_n = |x\_n - x^\*| $$ 로 정의한다. 이와 달리 상대 오차는 $$ \varepsilon\_n = \frac{|x\_n - x^*|}{|x^*|} $$ 로 정의한다. $x^\*$가 0에 가까운 경우 상대 오차는 잘 정의되지 않으므로, 실질적인 상황에 따라 적절한 오차 정의 방식을 택해야 한다. 또한 $x\_n$의 순열이 점차 $x^\*$에 근접하는 경우, $e\_n$이 0으로 수렴하게 될 것이다. 그런데 이 수렴의 형태가 빠른지 느린지는 다음의 개념으로 이해할 수 있다. #### 수렴 차수(Order of Convergence) 반복법이 $x\_n \to x^\*$로 수렴한다고 가정하자. 수렴 차수를 논의하기 위해 보통 다음과 같은 정의를 사용한다. 어떤 상수 $c>0$와 양의 정수 $p$가 존재하여, 충분히 큰 $n$에 대해 $$ e\_{n+1} \le c (e\_n)^p $$ 를 만족하면, $p$를 그 반복법의 수렴 차수라고 한다. 여기서 $p$가 큰 값일수록 오차가 매우 빠르게 줄어든다는 뜻이다. 가장 흔하게 나타나는 경우는 $p=1$인 선형 수렴(linear convergence)과 $p=2$인 이차 수렴(quadratic convergence)이다. 또한 $p>1$이고 1보다 작은 단계로 단계적으로 증가하는 경우를 초선형 수렴(superlinear convergence)이라고 한다. 예를 들어, 유명한 Newton 방법의 경우, 적절한 조건하에서 이차 수렴($p=2$)을 만족하는 것으로 알려져 있다. 선형 수렴의 경우, $p=1$이므로 다음과 같은 표현을 자주 쓴다. $$ e\_{n+1} \approx \lambda e\_n $$ 이때 $|\lambda| < 1$이면 $e\_n$이 기하급수적으로 0으로 가까워진다. Newton 방법처럼 $p=2$인 이차 수렴인 경우에는 $$ e\_{n+1} \approx c (e\_n)^2 $$ 의 형태로 오차가 감소하므로, 반복이 진행될수록 오차가 매우 급격하게 줄어든다. #### 고정점 반복의 수렴 속도 비선형 방정식 $f(x) = 0$을 해석할 때, $f(x^*)=0$인 해 $x^*$에 대해 임의의 함수를 $\phi(x)$라 두고 $x^\* = \phi(x^*)$를 만족하도록 식을 변형할 수 있다면, $x\_{n+1} = \phi(x\_n)$ 형태의 고정점 반복법을 구성할 수 있다. 이 방법이 실제로 $x^*$로 수렴하기 위해서는 고정점 정리(고정점 이론)에서 요구하는 일정 조건이 충족되어야 한다. 가장 간단한 예로, 구간 $\[a,b]$에서 $\phi$가 수축 사상(contraction mapping)이면, 그 구간 내에 단 하나의 고정점(해)이 존재하며, 임의의 초깃값을 주어도 반복이 수렴함을 보장한다. 수축 사상이란 임의의 $x, y$에 대해 $$ |\phi(x) - \phi(y)| \le \kappa |x - y| $$ 를 만족하는 것을 말하며, 여기서 $0 \le \kappa < 1$이면, $\phi$를 수축 사상이라고 한다. 이 경우 실제 수렴 속도는 $$ |x\_{n+1} - x^*| = |\phi(x\_n) - \phi(x^*)| \le \kappa |x\_n - x^\*| $$ 로 나타난다. 즉, $e\_{n+1} \le \kappa e\_n$를 만족하므로, 선형 수렴 성질을 가진다. #### Newton 방법과 수렴 차수 $f(x)=0$을 풀기 위한 Newton 방법은 $$ x\_{n+1} = x\_n - \frac{f(x\_n)}{f'(x\_n)} $$ 로 정의된다. Newton 방법이 국소적으로 이차 수렴을 가진다는 고전적 사실은 $f'(x^\*) \neq 0$ 그리고 $f$가 해 주변에서 충분히 매끄럽다는(예를 들어 2차 이상 미분 가능) 조건을 가정한다. 이때 $$ e\_{n+1} \approx \frac{|f''(x^*)|}{2|f'(x^*)|} (e\_n)^2 $$ 에 의하여 $p=2$가 됨을 보인다. 위 식은 여러 가정하에 전개식을 축약한 형태이지만, 실제로는 Newton 방법의 빠른 수렴 속도를 잘 나타내준다. Newton 방법은 수렴만 보장된다면 매우 빠르게 근사해를 얻을 수 있으나, $f'(x\_n)=0$에 가까운 특이한 영역에서 발산하거나, 더 이상 진행이 불가능해지는 경우도 있으므로, 초깃값 선택 및 $f'(x)$가 0에 가까워지지 않는 조건 등에 주의해야 한다. #### 오차에 대한 사후 평가 비선형 방정식 해석 시, 반복법을 통해 구한 $x\_{n+1}$에 대해 실제 해 $x^\*$와의 차이를 직접 알 수 없기 때문에, 내부적으로 추정한 오차 척도를 확인하거나, 반복법으로부터 유도된 다른 표현식을 통해 오차 한계를 평가한다. 예를 들어, Newton 방법에서 만약 $x\_{n+1}$이 어느 정도 근사해에 가까워졌다면, 다음 반복에서의 오차 상계를 사후적으로 추정하여 반복을 중단할 수 있다. 오차 평가를 위한 사후 추정 방식을 구체적으로 살펴보기 위해서는, 예를 들어 $x\_n$ 근방에서의 $f(x)$ 전개나 가재승계(가선근사) 등을 고려한다. 이러한 과정은 뉴턴 계수(Newton iteration coefficient) 등을 이용해 보다 엄밀히 추정할 수 있다. #### 구현 예시 (Python) 아래 예시 코드는 단순한 Newton 방법의 반복을 간단히 구현한 것이다. $f$와 $f'$가 명시되어 있다고 가정하고, 일정한 조건이 충족된다면 빠르게 근사해에 접근함을 살펴볼 수 있다. ```python import math def f(x): return x**2 - 2.0 def fprime(x): return 2.0*x def newton_method(x0, tol=1e-8, max_iter=100): x = x0 for i in range(max_iter): fx = f(x) fpx = fprime(x) if abs(fpx) < 1e-14: break x_new = x - fx/fpx if abs(x_new - x) < tol: return x_new x = x_new return x init_guess = 10.0 approx_root = newton_method(init_guess) print("근사해:", approx_root) print("실제 sqrt(2):", math.sqrt(2)) ``` 이 코드를 통해 $x^2 - 2 = 0$의 해를 찾고, 그 결과가 $\sqrt{2}$에 빠르게 근접함을 확인할 수 있다. Newton 방법의 이차 수렴 성질에 따라, 초깃값이 적절하다면 기하급수적인 오차 감소를 보인다. #### 고차 수렴 방법과 초선형 수렴 Newton 방법과 같은 이차 수렴 방법 외에도, 특정 함수에서 더 높은 차수로 수렴하는 알고리즘이 존재한다. 예를 들어, Halley 방법은 세 번 미분까지 고려하여 구성되며, 적절한 조건하에서 3차 수렴을 달성한다. 그러나 이러한 고차 수렴법이 실제 계산 과정에서 항상 효율적인 것은 아니다. 이유는 매 반복 시 다항식의 높은 차수 미분 계수를 직접 구해야 하며, 이로 인한 계산 비용 증대나 반올림 오차 누적 문제가 발생할 수 있기 때문이다. 초선형 수렴(superlinear convergence)은 $p>1$이지만 $p$가 정수나 이처럼 명확한 분수 형태로 떨어지지 않을 때의 일반적인 분류 용어이다. 예를 들어, Secant 방법은 미분 계산 없이 근사 미분계수를 사용하여 $f'(x\_n)$ 대신 $$ f'(x\_n) \approx \frac{f(x\_n) - f(x\_{n-1})}{x\_n - x\_{n-1}} $$ 와 같은 형태로 계산한다. 이때 이론적으로 $p \approx 1.618\ldots$ (황금비 수렴 차수)라는 사실이 알려져 있다. $p=2$의 이차 수렴이 아니지만, $p=1$보다 큰, 즉 선형보다 빠른 수렴을 보인다는 점에서 초선형 수렴이라 부른다. #### 지역 수렴(Local Convergence)과 전역 수렴(Global Convergence) 비선형 방정식 근사에서 중요한 사실은 반복법이 모든 초깃값에 대해 해로 수렴하는지 여부다. 이러한 관점에서 전역 수렴(global convergence)과 지역 수렴(local convergence)을 구분한다. 전역 수렴이란, 해를 포함하는 특정 구간 내 임의의 초깃값을 주어도 반복이 수렴함을 의미한다. 반면, 지역 수렴은 해 주변의 제한된 범위에서만 반복이 수렴함을 의미한다. Newton 방법은 (특정 가정하에서) 국소적으로는 이차 수렴의 훌륭한 방법이지만, 전역적으로는 항상 수렴을 보장하지 않는다. 초깃값이 좋지 않을 경우, 특히 $f'(x)$가 0에 가까운 구간에 진입하거나 극단적 함수 형태를 만나면 발산할 위험이 있다. 고정점 수축 사상을 이용하는 방법은 보통 전역적 수렴을 보장하지만, 수렴 속도는 선형으로 비교적 느린 편이다. #### 잔차(Residual)와 후향오차(Backward Error), 전향오차(Forward Error) 비선형 방정식 해를 반복적으로 구할 때, 일반적으로 $x\_n$과 해 $x^*$ 사이의 실제 차이(전향오차: forward error)는 구하기 쉽지 않다. 대신에 $f(x\_n)$의 절댓값을 통해 잔차(residual)를 관측하거나, 혹은 $f$가 해석적으로 단순하다면 $x^*$를 근사함으로써 계산하는 간접적인 방법을 택한다. 잔차: $$ r\_n = |f(x\_n)| $$ 실제 해에서는 $f(x^*)=0$이므로, $r\_n$이 0으로 가까워지면 $x\_n$이 해에 가까워진다고 짐작할 수 있다. 그러나 $f'(x^*)$가 매우 작은 경우, 잔차가 충분히 작아도 오차(전향오차)가 그렇게 작지 않을 수 있으므로 주의해야 한다. 후향오차(Backward Error): $$ \Delta x\_n = \arg \min\_{\delta} |f(x\_n + \delta)| $$ 실제로는 함수값이 0이 되는 입력 $x^\* \approx x\_n + \Delta x\_n$을 찾기 위한 왜곡(perturbation)의 관점으로 이해한다. 즉, $x\_n$이 정확한 해가 되기 위해 함수 쪽을 얼마나 수정해야 하는지를 측정하는 방법이다. 선형 대수학의 해석과 유사하게, 비선형 문제에서도 후향오차는 “현재 근사해가 얼마나 ‘문제 설정 측면’에서 정확한 해인지”를 보여주는 한 척도가 될 수 있다. #### 수렴 계수와 조건수 비선형 방정식에서도 선형 시스템과 유사하게, 적절한 조건수(condition number)를 정의할 수 있다. 예를 들어, $f'(x^*) \neq 0$라고 가정하고 $x^*$가 해라고 할 때, $f(x^*)=0$ 근방에서 Taylor 전개를 고려해 보면, $x^*$ 근방의 민감도가 $|1/f'(x^\*)|$ 혹은 기타 유사 지표로 해석되는 경우가 많다. 민감도가 높을수록 입력의 작은 변화가 함수 값에 크게 반영되어, 근사해를 구하기 위한 반복에서 $f'(x\_n)$의 크기에 따라 수렴에 큰 영향을 미치게 된다. Newton 방법에서 $f'(x\_n)$의 크기가 매우 작으면, $f(x\_n)/f'(x\_n)$ 항이 커져서 다음 반복에서 $x\_{n+1}$이 급격히 변할 수도 있고, 심하면 분모가 0에 가까워질 수 있다. 이는 반복법의 오차를 크게 유발하거나 발산을 초래할 수 있다. #### a priori 추정과 a posteriori 추정 오차를 평가하는 두 가지 대표적 방식은 사전(a priori) 및 사후(a posteriori) 방식으로 나뉜다. * 사전 추정(a priori estimate)은 반복법이 수렴한다고 가정했을 때, 적절한 조건하에서 $e\_n$이 대략 어떻게 줄어드는지를 방정식 유도나 이론적 고찰을 통해 미리 예측하는 것이다. 예를 들어, Newton 방법은 해 근방에서 $e\_{n+1} \approx C(e\_n)^2$ 형태를 가지므로, 일정 구간 이후에는 오차가 2제곱 비율로 빠르게 감소한다는 식으로 요약할 수 있다. * 사후 추정(a posteriori estimate)은 실제로 반복을 수행한 후, 구해진 근사해와 그 주변 정보(함수값, 미분값 등)를 통해 잔차나 오차 상계를 실제로 계산하거나 추정하는 과정이다. 예를 들어, Newton 방법에서 $$ e\_{n+1} = x^\* - x\_{n+1} = x^\* - \bigl( x\_n - \frac{f(x\_n)}{f'(x\_n)} \bigr) $$ 를 통해, $x\_n$ 근방의 $f'$와 $f''$ 등을 참고하여 $e\_{n+1}$의 크기를 근사적으로 추정함으로써, 현재 반복에서의 오차가 어느 정도인지 파악할 수 있다. 보통 이러한 사후 추정은 반복을 중단할 시점을 결정하는 데 중요한 판단 근거가 된다. #### 고정점 반복에서의 오차 한계 수치해석에서 고정점 반복은 매우 일반적인 틀을 제공한다. $x\_{n+1} = \phi(x\_n)$의 형태를 취하는 모든 반복법은 고정점 반복으로 볼 수 있다. 각 반복에서의 오차를 $$ e\_n = x\_n - x^\* $$ 라 할 때, $$ e\_{n+1} = \phi(x\_n) - \phi(x^*) = \phi(x^* + e\_n) - \phi(x^\*) $$ 를 Taylor 전개하면, $$ \phi(x^\* + e\_n) \approx \phi(x^*) + \phi'(x^*) , e\_n + \frac{\phi''(x^\*)}{2!} , (e\_n)^2 + \cdots $$ 이므로, $e\_{n+1}$의 크기와 $e\_n$의 관계를 다항식으로 나타낼 수 있다. $\phi'(x^*)=0$이고 $\phi''(x^*) \neq 0$인 경우, $e\_{n+1}$은 $(e\_n)^2$에 비례하므로 이차 수렴처럼 동작한다. 그러나 $\phi'(x^*) \neq 0$이면, $e\_{n+1} \approx \phi'(x^*) e\_n$인 선형 수렴을 나타낼 수 있다. 고정점 반복에서 $\phi'(x^*)$가 1보다 작은 값을 가지면, 지역적으로 선형 수렴이 보장되며, 그때 수렴 속도는 대략 $|\phi'(x^*)|$에 의해 결정된다. 예를 들어, $|\phi'(x^*)|$가 0에 가깝다면(즉, 매우 작다면), 수렴 속도가 빨라지며, 이는 사실상 Newton 방법에서 $f'(x^*)$가 충분히 크거나, 적절히 변형된 형태의 $\phi(x)$를 사용했을 때 발생하는 이점과 유사하다. #### 수렴 반경과 선택적 재시동 복잡한 비선형 방정식에서는 $x\_n$이 해 근처로 충분히 접근한 후에야 이론적으로 예측된 빠른 수렴 속도를 실제로 경험하게 된다. 즉, 수렴 반경(convergence radius) 내로 초깃값이 들어왔을 때 그제야 이차 혹은 초선형 수렴이 나타나는 경우가 흔하다. 이 때문에 실제 구현에서는 초기 반복이 어느 정도 진행된 후에, 혹은 특정 검증을 거친 후에, Newton 방법(또는 이차 이상의 고차 방법)으로 전환하여 계산 효율을 높이는 전략도 있다. 다른 전략으로는, 이미 수행한 반복법이 너무 작은 오차 감소율을 보이면, 초깃값을 재조정하여(이를 재시동이라 한다) 다시 반복법을 시작함으로써 보다 빠른 국소 수렴을 유도하는 식의 혼합 기법도 활용된다. #### 고차원 비선형 시스템과 Broyden 방법 고차원(벡터) 비선형 방정식 $$ \mathbf{f}(\mathbf{x}) = \mathbf{0} $$ 을 풀기 위해 Newton 방법을 확장하면, $$ \mathbf{x}\_{n+1} = \mathbf{x}\_n - \mathbf{J}^{-1}(\mathbf{x}\_n) , \mathbf{f}(\mathbf{x}\_n) $$ 와 같은 형태를 취한다. 여기서 $\mathbf{J}(\mathbf{x}\_n)$은 $\mathbf{f}$의 야코비 행렬(Jacobian matrix)을 의미한다. 고차원 문제에서는 이 야코비 행렬을 구하고 매 반복 시 역행렬을 구하는 비용이 커질 수 있다. 이를 보완하기 위해 Broyden 방법을 비롯한 준(準)Newton 기법(quasi-Newton methods)이 제안된다. Broyden 방법은 Newton 방법과 유사하되, 매 반복 시 야코비 행렬을 직접 계산하지 않고, 이전 반복에서의 정보만으로 점진적으로 야코비 행렬을 근사한다. 이 경우에도 적절한 조건이 충족되면 초선형 수렴을 얻을 수 있다. 그러나 실제로는 야코비 행렬을 계속 업데이트해야 하므로, 구현 상의 세부 방식에 따라 수렴 속도나 계산 복잡도가 달라진다. #### Inexact Newton 방법과 실수 연산 오차 비선형 방정식을 풀 때, 이론적으로는 뉴턴 방법의 빠른 수렴 속도가 확립되어 있지만, 실제 계산에서는 부동소수점 연산 과정에서 반올림 오차가 발생하며, $f'(x)$를 정확히 구하기 어려울 수도 있다. 이를 고려한 방법 중 하나로 Inexact Newton 방법이 제안된다. 이는 매 반복에서 야코비 행렬(또는 스칼라 미분계수)의 역연산 과정을 완벽하게 수행하지 않고, 적절한 오차 범위 내에서 근사 연산을 수행하되 전반적인 수렴 특성을 해치지 않도록 제어한다. 예를 들어, $$ \mathbf{x}\_{n+1} = \mathbf{x}\_n - \mathbf{H}\_n , \mathbf{f}(\mathbf{x}\_n) $$ 라는 형태에서 $\mathbf{H}\_n$이 정확한 $\mathbf{J}^{-1}(\mathbf{x}\_n)$이 아니라, 그 근사 행렬이라도 여전히 적절한 조건을 만족하기만 하면 국소적으로 초선형 이상의 수렴을 유지한다. 고차원 문제에서 야코비를 직접 구하기 어려운 상황에 대비하여 Krylov 공간 기법(GMRES 등)과 결합한 Newton-Krylov 방법 등이 실제로 폭넓게 활용되고 있다. Inexact Newton 방법에서 가장 중요한 점은 반복마다 원하는 정확도의 선형계 해를 얻기 위해 얼마만큼 연산을 할 것이냐를 제어하는 것이다. 각각의 반복 단계에서 연산을 “매우 정밀하게” 하면 수렴은 좋을 수 있으나, 전체 계산 시간이 크게 늘어난다. 반면 “너무 거칠게” 하면 국소 이차 수렴 구간을 제대로 확보하지 못하고, 심지어 수렴을 놓칠 수도 있다. 따라서 주어진 문제의 크기와 조건을 바탕으로, 각 반복에서 역행렬 근사를 어느 수준으로 정확히 할 것인지를 결정하는 동적 제어가 핵심이 된다. #### 다중 근(degenerate root)과 수렴 개선 비선형 방정식 $f(x)=0$에서 $x^*$가 단순근이 아니라 다중 근(예: $f'(x^*)=0$이면서 $f(x^\*)=0$)인 경우에는 뉴턴 방법이 선형 또는 초선형 수렴보다 훨씬 느려질 수 있다. 예를 들어, $f(x) = (x - \alpha)^m$ 형태로 $m>1$인 경우, 일반적 뉴턴 방법은 $$ x\_{n+1} = x\_n - \frac{(x\_n - \alpha)^m}{m (x\_n - \alpha)^{m-1}} = x\_n - \frac{x\_n - \alpha}{m} $$ 가 되어서 오차가 반복마다 $1/m$ 정도만 줄어든다. 즉, 이차 수렴과는 정반대로 느린 선형 수렴 양상을 나타낸다. 이를 개선하기 위해서는 $$ x\_{n+1} = x\_n - \frac{m , f(x\_n)}{f'(x\_n)} $$ 와 같은 보정식을 쓸 수 있으며, 이 경우 근의 중복도를 알고 있어야 한다. 실질적 문제에서 $m$을 모르는 경우에는 해 근방의 국소 해석을 통해 추정하거나, 다른 보조적 정보를 활용할 수 있다. #### 혼합 방법과 적응적 반복 전략 큰 규모 혹은 복잡한 형태의 비선형 방정식을 풀 때, 하나의 단일 반복법으로는 전역적 수렴성과 국소적 빠른 수렴성이라는 두 마리 토끼를 동시에 잡기 힘든 경우가 많다. 이럴 때 혼합(Hybrid) 방법을 적용할 수 있다. 예를 들어, 초기 단계에서는 수축 사상 기반의 안전한 고정점 반복으로 전역 수렴을 확보하고, 일단 해 근처에 들어서면 뉴턴 방법으로 전환하여 국소적으로 급속한 이차 수렴을 이끌어내는 식이다. 반복 중에 잔차가 충분히 작아지거나, 혹은 $\phi'(x\_n)$의 크기가 작아지는 지표 등이 감지되면 뉴턴 방법으로 갈아탈 시점을 결정할 수 있다. 적응적(adaptive) 접근 또한 중요하다. 비선형 함수를 평가하는 비용이 크다면, 매 반복마다 잔차의 감소율이나 상대 오차를 확인하면서, 현재 단계에서의 이득 대비 계산 비용을 평가한다. 이를 통해, 다음 단계에서의 스텝 크기나 미분 근사 정밀도, 혹은 반복 기법 자체를 변경하는 식으로 효율을 높일 수 있다. 이는 실무적으로는 공학 시뮬레이션이나 최적화 문제에서 자주 활용된다. #### 반올림 오차와 정밀도 한계 반복이 충분히 진행되어 실제 해에 매우 가까워졌을 때, 반올림 오차가 지배적인 이슈가 될 수 있다. 특히 이차 또는 초선형 수렴 방식에서는 반복 후반부에 $e\_n$이 빠르게 줄어들다가 어느 순간부터 오차 감소가 정체되거나, 오히려 수렴 성능이 떨어지는 현상이 나타날 수 있다. 이를 스태그네이션(stagnation)이라고 부른다. 일반적인 부동소수점(Floating-point) 환경에서, 오차가 기계 정밀도(machine epsilon) 수준보다 더 작아지기를 기대하기 어렵다. 고정점 연산 시스템에서는 유효 숫자 자릿수(precision)가 한정적이라, 오차가 아주 작아질수록 $f(x\_n)$과 $f'(x\_n)$을 계산할 때 발생하는 차분이 일정 임계값 이하에서 정확히 표현되지 못하기 때문이다. 이런 상황에서는 반복을 무한정 계속해도 유의미한 개선을 얻기 힘들다. 실제 소프트웨어 구현에서는 오차가 기계 정밀도의 수 배 범위 내에 들어오면 반복을 중단하고 해를 ‘충분히 정확하다’고 본다. #### 자동 미분(Automatic Differentiation)의 역할 고차 수렴 방법, 특히 Newton 방법에서 $f'(x)$나 $\mathbf{J}(\mathbf{x})$를 계산해야 할 때, 복잡한 함수를 다룬다면 미분을 수작업으로 구하기 어렵다. 전통적으로는 수치미분(분차분) 기법을 사용하거나, 상징미분(symbolic differentiation) 도구를 활용했으나, 근래에는 자동 미분(AD) 기법이 널리 쓰이고 있다. 자동 미분은 연산 그래프를 따라 기호적이지 않은 형태로 프로그램 단위에서 미분 계산을 수행한다. 이는 $f$가 임의의 알고리즘으로 정의된 복합적 함수라도, 주어진 연산 절차에 대해 미분값을 정확히 계산할 수 있다는 장점이 있다. Newton-Krylov 방법이나 Broyden 방법을 쓰더라도, 초기 야코비 계산이나 검증을 위해 자동 미분은 큰 이점을 제공한다. #### 구간 연산(Interval Arithmetic)을 통한 오차 검증 수치해석에서 $x\_n$이 정말 해와 얼마나 가까운지, 단순히 잔차만 작다는 이유로 절대 안심할 수 없을 때가 있다. 예를 들어, $f'(x^\*)$가 0에 매우 가까운 해라면, 잔차가 작아도 근사해가 크게 틀려 있을 수 있다. 이런 상황을 보다 엄밀히 판단하기 위해 구간 연산(Interval Arithmetic)을 도입하여 $x\_n$ 주변의 모든 값을 오차 범위를 포함해 계산하는 방법이 있다. 구간 연산 기법은 어떠한 숫자 연산도 구간 단위로 표현하므로, 해당 구간 안에 진정한 해가 존재함을 보증할 수 있다. 다만, 이 기법을 정밀하게 적용하려면 계산 비용이 상당히 커지고, 구간 폭이 지나치게 커지지 않도록 세심하게 관리해야 한다. 그럼에도, 아주 높은 신뢰도로 해 근방을 확인하고, 발산 여부를 판단하는 등 유용하게 쓰인다. #### 실험적 오차 해석과 이론적 수렴도 비교 이론적으로는 $e\_{n+1} \approx C (e\_n)^p$ 꼴의 등식을 통해 수렴 차수를 말하지만, 실제 계산에서는 소수점 반올림 오차와 사전에 예상하지 못한 미분값의 변동, 혹은 다른 내부 제약들이 작동한다. 따라서 실제로 반복을 진행했을 때의 실험적 수렴 차수를 측정해 보면, 이상적인 이론값 $p$와는 다소 차이가 생길 수 있다. 실험적으로는 연속된 세 근사해를 $x\_{n-1}, x\_n, x\_{n+1}$라 할 때, $$ p\_{\text{exp}} \approx \frac{\ln(e\_{n+1}/e\_n)}{\ln(e\_n/e\_{n-1})} $$ 와 같은 식을 통해 근사적인 $p$를 추정할 수 있다. 이후 이 값을 이론적 $p$와 비교하며, 오차 요소 또는 민감도를 평가할 수 있다. 만일 $p\_{\text{exp}}$가 일정 구간 이후 이론값과 잘 맞아떨어지면, 충분히 해 근방에 도달한 것으로 보아 반복을 중단하거나, 필요한 경우 더 높은 정밀도를 사용할지 판단한다. ### 추가 고려사항 비선형 방정식을 실제로 풀 때, 반복 과정에서 고려해야 할 사항은 매우 다양하다. 지금까지는 수렴 차수나 조건수, 반올림 오차, Inexact Newton 기법 등의 개념을 살펴보았다. 이어서, 보다 실질적인 관점에서 몇 가지 추가적인 주제들을 더 다뤄보자. #### 수렴 해석의 일반화: Kantorovich 정리 Newton 방법 등과 같은 반복법에 대해, 국소적인 수렴뿐 아니라 좀 더 넓은 의미의 수렴 보장을 시도하는 이론적 틀로 Kantorovich 정리가 널리 알려져 있다. 이 정리는 (1) 적절한 초기 근사해 $\mathbf{x}\_0$의 선택, (2) 함수와 야코비 행렬(혹은 1차 도함수)에 대한 특정 Lipschitz 조건 등이 만족될 때, 고차원에서도 Newton 방법이 전역적으로 수렴하며 국소적으로 이차 수렴을 보인다는 것을 보장해 준다. 특히, Newton 방법이 단순히 “해 근처”라는 막연한 조건이 아니라, 해에서 어느 정도 떨어져 있어도 일정 구간 내에만 들어오면 수렴하게 된다는 사실을 명확히 기술해 준다는 데 의미가 있다. 그러나 실제 적용 시에는 Kantorovich 정리에서 제시하는 Lipschitz 상수를 구체적으로 산정하기가 어려워서, 이론적 참조로 사용하는 경우가 많다. #### 반복 중단 조건(Stopping Criterion) 비선형 방정식을 수치적으로 풀 때, 반복을 언제 멈출 것인지를 결정하는 문제는 매우 중요하다. 만약 해가 어느 정도 ‘충분히’ 정확한 수준에 도달했음에도 불구하고 불필요한 반복을 계속한다면, 시간과 자원이 낭비된다. 반대로 너무 이른 시점에 중단하면 오차가 클 수 있다. 아래와 같은 기준 중 하나 이상을 만족할 때 반복을 중단하는 방식이 일반적이다. 잔차 기반: $$ |f(x\_n)| \le \text{TOL} $$ 전향오차 기반(실제로는 추정치): $$ |x\_{n+1} - x\_n| \le \text{TOL} $$ 상대 오차 기반: $$ \frac{|x\_{n+1} - x\_n|}{|x\_{n+1}|} \le \text{TOL} $$ 여기에 최대 반복 횟수 제한 등을 병행하기도 한다. 예를 들어, $n$이 특정 값을 초과하면 수렴이 더 이상 기대되지 않는다 보고 중단한다. 이는 특별히 비정상적인 형태의 함수거나, 초깃값이 불운하게 선택되었을 때 무한정 반복하는 사태를 방지하기 위한 안전장치다. #### 구간법(Bracket Method)과 수렴 속도 한편, 해가 존재하는 구간을 알고 있고, 그 구간을 점차 좁혀 가면서 해를 탐색하는 방법도 있다. 전형적으로 이분법(bisection method)은 매우 단순하고 전역적 수렴을 보장하지만, 오차가 $2^{-n}$ 꼴로 줄어드는 선형 수준보다도 낮은 수렴 속도를 가진다. 그러나 미분 계산을 요구하지 않고, 발산 위험이 없다는 장점이 있다. 이분법의 변형으로서 가위분할법(false position method)이나 그 외 구간 분할 전략들이 제안되어 왔으며, 이런 방법들은 함수값 부호 변화를 이용하여 해의 존재 구간을 점차 좁히기 때문에, 고차 미분 가능성이 없어도 적용할 수 있다. 다만, 반복법으로서의 수렴 속도는 Newton 방법에 비해 느릴 수밖에 없으므로, 주로 초기 근사 구간을 안전하게 파악하기 위한 수단으로 많이 활용된다. #### Muller's Method와 복소근 탐색 실수 구간에서의 근 탐색도 중요하지만, 복소함수 해석이나 특수 방정식에서 복소근을 찾아야 할 때도 있다. 이때 Muller's method가 유용하게 쓰인다. Muller's method는 세 점(세 근사값)을 사용하여 이차 보간을 실시하고, 보간된 2차 다항식의 근을 다음 반복점으로 삼는 방식이다. 복소 영역에서도 다항식의 근을 구할 수 있으며, 일반적인 Secant나 Regula Falsi 방법에 비해 빠른 수렴을 보이는 것으로 알려져 있다. 그러나 구한 근이 가짜 근(잡근)으로 갈 수도 있으므로, 반복 과정 중 복소 평면에서의 근 위치를 세심하게 살펴야 한다. #### 비선형 시스템을 위한 Broyden 방법 (C++ 예시) 고차원 비선형 시스템 $$ \mathbf{f}(\mathbf{x}) = \mathbf{0} $$ 를 풀기 위해, Newton 방법을 확장하면 매 반복 시 야코비 행렬 $\mathbf{J}(\mathbf{x}\_n)$을 구하고 이를 역행렬(또는 선형계 풀이)로 사용해야 한다. 하지만 차원이 크면 이 작업은 매우 부담이 커진다. 따라서 Broyden 방법과 같은 준Newton 기법을 사용하여, 야코비 행렬을 매번 정확히 계산하지 않고 순차적으로 업데이트함으로써 반복 비용을 절감할 수 있다. 아래는 간단한 C++ 코드 예시로, Broyden 방법의 기본 골자를 보여준다. ```cpp #include #include #include #include // 예시 목적으로 매우 단순한 2차원 비선형 시스템 f(x1, x2)를 정의 // 실제로는 문제에 맞게 f를 일반화해야 함 std::vector f(const std::vector& x) { std::vector fx(2); // 예: f1(x1, x2) = x1^2 + x2^2 - 4 // f2(x1, x2) = x1 - x2 fx[0] = x[0]*x[0] + x[1]*x[1] - 4.0; fx[1] = x[0] - x[1]; return fx; } // 행렬-벡터 곱 std::vector matVec(const std::vector>& A, const std::vector& v) { std::vector result(A.size(), 0.0); for (size_t i = 0; i < A.size(); i++) { for (size_t j = 0; j < A[0].size(); j++) { result[i] += A[i][j] * v[j]; } } return result; } // 벡터 차 std::vector vecSub(const std::vector& a, const std::vector& b) { std::vector result(a.size()); for (size_t i = 0; i < a.size(); i++) { result[i] = a[i] - b[i]; } return result; } // 벡터 합 std::vector vecAdd(const std::vector& a, const std::vector& b) { std::vector result(a.size()); for (size_t i = 0; i < a.size(); i++) { result[i] = a[i] + b[i]; } return result; } // 스칼라-벡터 곱 std::vector scalarVec(double alpha, const std::vector& v) { std::vector result(v.size()); for (size_t i = 0; i < v.size(); i++) { result[i] = alpha * v[i]; } return result; } // 외적 outer product std::vector> outerProduct(const std::vector& u, const std::vector& v) { std::vector> mat(u.size(), std::vector(v.size())); for (size_t i = 0; i < u.size(); i++) { for (size_t j = 0; j < v.size(); j++) { mat[i][j] = u[i] * v[j]; } } return mat; } // 행렬-행렬 더하기 std::vector> matAdd(const std::vector>& A, const std::vector>& B) { std::vector> M(A.size(), std::vector(A[0].size())); for (size_t i = 0; i < A.size(); i++) { for (size_t j = 0; j < A[0].size(); j++) { M[i][j] = A[i][j] + B[i][j]; } } return M; } // Broyden 방법 std::vector broydenMethod(std::vector x0, double tol = 1e-8, int maxIter = 100) { const int n = x0.size(); // 초기 야코비 역행렬 근사치 B0를 단위행렬로 시작 std::vector> B(n, std::vector(n, 0.0)); for (int i = 0; i < n; i++) { B[i][i] = 1.0; } std::vector fx0 = f(x0); for (int iter = 0; iter < maxIter; iter++) { // s = -B * f(x0) std::vector s = matVec(B, fx0); for (size_t i = 0; i < s.size(); i++) { s[i] = -s[i]; } // x1 = x0 + s std::vector x1 = vecAdd(x0, s); std::vector fx1 = f(x1); // 오차 확인 double normF = 0.0; for (double val : fx1) { normF += val*val; } if (std::sqrt(normF) < tol) { return x1; } // y = f(x1) - f(x0) std::vector y = vecSub(fx1, fx0); // B를 랭크-1 업데이트 // B_new = B + (s - B*y)(s^T B) / (s^T B y) std::vector By = matVec(B, y); // s^T B y double denom = 0.0; for (size_t i = 0; i < n; i++) { denom += s[i]*By[i]; } if (std::fabs(denom) > std::numeric_limits::epsilon()) { std::vector tmp = vecSub(s, By); // (s - B*y)(s^T B) : outerProduct(tmp, matVec(B, s^T))와 유사하지만 // 여기서는 (s^T B) 자체가 벡터가 아니라 (s^T) * B 이므로 주의가 필요. // 간단화를 위해 (s^T B)를 먼저 구하자. std::vector sTB(n, 0.0); for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { sTB[i] += s[j]*B[j][i]; } } std::vector> outerTerm = outerProduct(tmp, sTB); // alpha = 1 / (s^T B y) double alpha = 1.0 / denom; // B = B + alpha * outerTerm for (size_t i = 0; i < n; i++) { for (size_t j = 0; j < n; j++) { B[i][j] += alpha * outerTerm[i][j]; } } } // 반복 준비 x0 = x1; fx0 = fx1; } return x0; } int main() { std::vector x0 = {2.0, 1.0}; std::vector root = broydenMethod(x0, 1e-12, 200); std::cout << "Broyden 근사해: (" << root[0] << ", " << root[1] << ")\n"; std::vector check = f(root); std::cout << "f(root) = [" << check[0] << ", " << check[1] << "]\n"; return 0; } ``` 위 코드가 실제로 잘 동작하려면, 문제 특성에 맞는 $f(\mathbf{x})$ 정의가 필요하고, 매 반복에서 편미분에 준하는 정보를 활용할 수 있도록 구조를 조금 더 다듬어야 한다. 그럼에도 불구하고 Broyden 방법이 야코비 역행렬 근사를 업데이트해 가며 반복하는 틀을 살펴볼 수 있다. #### 고차원 문제에서의 스케일링과 사전조건자(Preconditioner) 야코비 행렬이 심하게 치우친(singular에 가까운) 형태를 가진다면, Newton 또는 Broyden 같은 방법은 수치적으로 불안정해질 수 있다. 이때 스케일링(변수마다 적절한 크기 조정)을 적용하거나, 선형계 해법 측면에서 사전조건자(Preconditioner)를 사용함으로써 개선을 도모할 수 있다. 특히 Inexact Newton-크릴로프(Newton-Krylov) 계열의 알고리즘을 구현할 때, 사전조건자는 GMRES, BiCGSTAB 등 반복 선형계 풀이에 매우 큰 영향을 끼친다. 스케일링은 단순히 “$x\_i$ 축적 범위가 너무 커서 야코비 행렬 항들이 극단적으로 작거나 크게 표현되는 경우”를 방지하고, 잘 정의된 조건수의 새로운 변수 $\tilde{x}\_i$로 치환하여 문제를 푸는 아이디어다. 이는 실험적으로 자주 쓰이며, 해 근방에서의 민감도와 결합하여 수렴 속도를 크게 개선하기도 한다. #### 비선형 조합 반복(Nonlinear combination iteration) 복잡한 문제에서, Newton 방법과 고정점 반복, 혹은 다른 준Newton 방법을 섞어서 적응적으로 활용할 수 있다. 예를 들어, $$ \mathbf{x}\_{n+1} = \alpha \bigl(\mathbf{x}\_n - \mathbf{J}^{-1}(\mathbf{x}\_n)\mathbf{f}(\mathbf{x}\_n)\bigr) ;+; (1-\alpha) , \phi(\mathbf{x}\_n) $$ 와 같은 식으로 조합하거나, 혹은 단계별로 이분법 분할과 Newton 업데이트를 교대 시행하기도 한다. 이러한 혼합 전략은 전역적 안정성과 국소적 빠른 수렴이라는 양립하기 어려운 요구조건을 동시에 만족하는 실무 해법으로 거론된다. 물론, 어떤 방식을 어떤 비율로 섞을지는 전적으로 문제 구조와 수치적 경험에 좌우되므로, 일반적 이론보다는 실험적 파라미터 튜닝이 요구된다. #### 유한 정밀도 환경에서의 최적화와 근사해 비선형 방정식이 최적화 문제와 밀접한 관련을 가질 때, (예: $f(x)=0$ 문제를 $\min |f(x)|$로 해석) 공학 및 산업계에서는 반복법과 최적화 알고리즘을 결합하는 기법이 흔히 사용된다. 예컨대, Gradient descent 류의 방법과 Newton 방법을 혼합해, 단순히 $|f(x)|$를 최소화하거나, $f(x)^2$를 목적함수로 삼아 탐색하는 방식을 취하기도 한다. Newton 방법 자체도 2차 정보(헤시안 행렬)를 쓰는 최적화 알고리즘과 유사점이 많다. 이 관점에서, 해 해석을 위한 조건수와 최적화에서의 조건수가 긴밀히 연결되는 경우가 많으며, 이로써 수렴 분석에 필요한 또 다른 시각이 제공된다. \---적 평가 비선형 방정식의 근사해를 반복법으로 구하는 것은 수치해석의 핵심 주제 중 하나다. 단일 변수부터 고차원 벡터까지, 다양한 방법들이 존재하며, 각 방법의 수렴 속도, 안정성, 전역/국소 수렴 보장, 구현 복잡도, 반올림 오차 영향 등에 따라 선택이 달라진다. Newton 방법의 이차 수렴은 매우 인상적이지만, 초기값 의존성이나 야코비 계산 부담이 뒤따르고, 고정점 반복이나 이분법 계열은 비교적 느린 속도이지만 전역적으로 안정적이다. Broyden 등 준Newton 방법, 혼합 기법, 사전조건자, 자동 미분, 구간 연산 등은 이러한 단점을 보완하고 현대적 대규모 문제에 대응하기 위한 다양한 실용적 도구로 자리 잡았다.