할선(Secant) 방법과 매개변수 선택
배경과 동기
비선형 방정식 $f(x)=0$의 해를 수치적으로 구하는 고전적인 접근으로 뉴턴(Newton) 방법이 널리 쓰인다. 뉴턴 방법은 반복 과정에서 $f'(x)$를 직접 계산해야 하므로, 대상 함수가 미분 가능하고 미분값을 구하기 쉬운 경우에는 매우 효율적이다. 하지만 미분값을 구하기 어렵거나 계산 비용이 큰 문제에서는 뉴턴 방법을 적용하기가 곤란하다. 이러한 상황에서는 미분값을 직접 구하지 않고, 과거의 반복점들을 이용하여 미분값을 근사적으로 계산하는 할선(Secant) 방법이 유용하다.
뉴턴 방법은 $x_n$에서의 접선(slope)을 활용하여 $x_{n+1}$를 갱신한다면, 할선 방법은 $x_{n}$와 $x_{n-1}$를 지나는 할선의 기울기를 이용하여 $x_{n+1}$를 구성한다. 함수값만을 사용하므로, 반복 과정에서 도함수를 계산하지 않아도 된다는 이점이 생긴다.
할선법의 아이디어
할선법에서는 두 점 $x_{n}$, $x_{n-1}$에서의 함수값 $f(x_{n})$와 $f(x_{n-1})$를 바탕으로 다음 반복점 $x_{n+1}$를 예측한다. 즉, 두 점을 연결하는 선분(할선)의 기울기
을 미분값 $f'(x)$의 근사로 여긴다. 따라서 뉴턴 방법에서
이라는 공식을 쓴다면, 할선 방법에서는
가 된다. 이는 미분값 대신 할선의 기울기를 쓴 것이므로, $f(x)$가 미분 불가능하거나 미분값 계산이 곤란한 경우에도 적합하다.
반복식의 효율과 수렴
할선법은 도함수를 명시적으로 구할 필요가 없다는 점에서 계산 효율이 높아질 수 있으나, 기본적으로 뉴턴 방법보다 수렴 차수가 낮아진다. 뉴턴 방법은 국소적으로 이차 수렴(quadratic convergence)을 보이지만, 할선법은 국소적으로 약 1.618(황금비) 정도의 수렴 차수를 갖는다. 이는 슈타이너(Steffensen) 변환 등의 가속 기법으로 보완할 수 있기도 하지만, 단순 할선법만으로는 뉴턴 방법만큼 빠른 수렴을 기대하기는 어렵다.
할선법의 수렴 성능은 초기 추측값(초기화 구간)과 함수의 성질에 따라 큰 차이를 보인다. $x_{n-1}$과 $x_{n}$의 선택이 좋지 않으면 수렴성이 저하되거나 수렴점 근방에서의 최적 속도를 놓칠 수 있다. 따라서 실무적으로는 할선법의 초기값 설정이 매우 중요하다.
할선법의 매개변수 선택
수치 알고리즘을 구현할 때에는 단순히 공식만 그대로 쓰기보다, 반복 과정에서 나타날 수 있는 오차 축적, 초기가 너무 멀어 수렴하지 않는 현상 등을 고려해야 한다. 이러한 부분을 보완하기 위하여 할선법에 매개변수를 도입하여 더 robust하게 만들 수도 있다.
한 가지 기법은 이른바 damping 파라미터를 활용하는 방식이다. 즉,
와 같이 $\lambda_n$을 적절히 조정한다. 너무 큰 $\lambda_n$을 사용하면 뉴턴 방법을 흉내 내면서 빠른 수렴을 꾀할 수 있지만, 이때 오차가 크게 튀면서 발산할 위험도 있다. 반대로 $\lambda_n$을 매우 작게 잡으면 안정적이지만 느리게 수렴할 수 있다.
파라미터 $\lambda_n$을 균일하게 한 상수값으로 두어도 좋지만, $n$에 따라 동적으로 조정하는 방법도 가능하다. 예컨대,
와 같은 식으로 상하 경계를 설정해 두고, $\alpha_n$을 어떤 휴리스틱 규칙에 따라 산출하여 그 범위 내로 제한하기도 한다. 이때 $\alpha_n$은 할선법 반복에서 $|f(x_n)|$가 감소하는 비율, 혹은 $x_n$의 이동 거리를 고려해 정의할 수 있다.
매개변수 선택의 실제 예
비선형 문제에서 자주 등장하는 특징은 함수가 매우 완만하거나(즉, $f'(x)$가 극단적으로 작은 경우) 매우 급격히 변하는(즉, $f'(x)$가 큰 경우) 지점이 존재한다는 것이다. 이를 고려하지 않고 할선법을 고정된 방식으로만 쓰면, 다음 단계에서 수렴 구간을 벗어나 버릴 수 있다. 예를 들어 $f(x)$가 강한 비선형성을 보이는 구간에서는 $\lambda_n$을 줄이고, 상대적으로 완만한 구간에서는 $\lambda_n$을 크게 설정하여 반복 횟수를 줄일 수 있다.
할선법을 구현하면서 알고리즘이 발산할 가능성을 줄이기 위해, 다음과 같은 판단 절차를 코드 안에서 구현하기도 한다. 우선 현재 할선 기울기와 $f(x_n)$, $f(x_{n-1})$의 부호 등을 점검하여 기울기의 극단값을 회피한다. 함수값이 바뀌지 않아 $\frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}$가 0 근처가 되지 않도록 $x_n$과 $x_{n-1}$을 재조정하기도 한다. 그리고 $x_n$에서 계산한 $f(x_n)$이 이전 반복보다 크게 증가한 경우, 혹은 $x_{n+1}$가 이전 점보다 매우 멀리 이동하면 $\lambda_n$을 조정하여 스텝 크기를 줄이는 식이다.
예시 코드 (Python)
이 코드는 단순 할선법에 상수 스케일링 파라미터(damping)을 적용한 예시다. $x_{n+1}$ 계산식의 분모가 매우 작아질 위험을 방지하기 위해 $1e-14$ 정도의 하한선을 두었다. 이는 사용 환경에 따라 달리 설정할 수 있다. 실제 구현에서는 함수값이 폭발적으로 증가하거나 스텝이 너무 크게 변할 때, 동적으로 damping 값을 조절하도록 만들 수도 있다.
수렴 반경과 초기값 설정
할선법이 어느 정도의 수렴 반경을 갖는지에 대한 이론적 분석은 상대적으로 복잡하지만, 대체로 뉴턴 방법과 비슷하게 초기값이 근사해 근처에 있을수록 안정적으로 수렴한다. 그러나 뉴턴 방법은 국소 이차 수렴 성질에 힘입어 초기값이 조금 멀어도 비교적 빠르게 (또는 어떤 정도의 운으로) 해 근방으로 진입할 수 있는 반면, 할선법은 도함수 정보가 없는 대신 국소 수렴 차수(약 1.618 정도)가 다소 낮아서 초기값이 너무 멀면 수렴에 어려움을 겪거나 발산할 수 있다.
초기점 $x_0, x_1$ 선정에서 주의해야 할 점은 $f(x_1)$와 $f(x_0)$가 서로 다른 부호가 되는 구간을 고르는 것이 좋다는 것이다. 이렇게 하면 적어도 그 구간 안에 근이 하나 이상 존재한다는 (중간값 정리에 기반한) 보장이 있으므로, 반복 과정에서 극단적으로 큰 이동을 하거나 비정상적인 스텝이 발생할 가능성이 줄어든다. 또한 $|f(x_1)|$와 $|f(x_0)|$가 너무 작은 경우, 분모가 급격히 작아지면서 반복식이 불안정해지는 문제가 생길 수도 있으므로, 필요한 경우 초기에 다른 점으로 교체하거나 작은 댐핑($\lambda_n$)을 적용하여 안정성을 높인다.
일반화된 할선법과 변형
할선법의 기본 방정식은
이지만, 특정 문제 상황에 맞춰 기울기를 조금 다르게 정의할 수 있다. 예를 들어, 지수함수나 로그함수처럼 변동 폭이 매우 큰 함수에 대해서는 $f(x_n)$와 $f(x_{n-1})$를 단순히 뺀 값이 제대로 된 기울기를 반영하기 어려운 경우가 있다. 이때 함수값의 기울기를 보정하기 위해 가중치를 부여하거나, 이전 단계의 기울기를 일부 반영하는 방법을 고려할 수 있다.
가령
와 같은 기울기를 사용해, $\beta$라는 보정 상수를 조정함으로써 거친 변화를 완화하거나, 특정 구간에서 함수의 특성을 좀 더 적절히 반영하려 할 수 있다. 이를 통칭하여 Weighted Secant 또는 이와 유사한 변형 기법으로 부르기도 한다. 이 외에도 함수값에서 로그를 취한 형태로 변환하여 할선 기울기를 구한다든지, 문제 특성에 따라 여러 변형이 시도된다.
고차 할선법
다차 방정식을 풀 때, 혹은 여러 비선형 방정식이 서로 얽힌 시스템을 풀 때, 스칼라 단일 방정식의 할선법을 직접 적용하기보다는 그 확장판인 준-뉴턴(Quasi-Newton) 계열의 방법들을 고려한다. 특히 Broyden 방법은 $n$차원 비선형 시스템
에서 야코비 행렬 $D\mathbf{F}(\mathbf{x})$를 직접 계산하기 어려운 경우, 과거 반복점들을 활용하여 점진적으로 근사 행렬을 업데이트하는 방식이다. 이는 스칼라 문제에서의 할선법 아이디어를 고차원으로 확장한 것이라 할 수 있다.
뉴턴 방법은 $\mathbf{x}_n$에서 야코비 행렬 $J(\mathbf{x}_n)$을 구하여
을 사용하는데, Broyden 방법은 $J(\mathbf{x}_n)$ 대신에 근사 행렬 $B_n$을 반복적으로 업데이트하여
의 형태로 쓴다. 이때 $B_n$은 $\mathbf{x}n$과 $\mathbf{x}{n-1}$ 등 과거 정보를 이용해 (할선법과 유사한) 근사 기울기를 만족하도록 매번 재계산되며, 그 과정에서 Broyden 순방향 업데이트, Broyden 역방향 업데이트 등 다양한 형태의 업데이트 공식이 사용된다.
할선법과 이분법 혼합
비선형 방정식의 해가 특정 구간 안에 존재한다는 확증이 있고, 그 구간 내에서 함숫값의 부호가 달라지는 지점이 하나뿐이라는 전제가 성립한다면, 할선법은 이분법(bisection method)과도 혼합이 가능하다. 일반적으로 이분법은 비교적 느리지만 안정적인 수렴을 보장하며, 반면에 할선법은 속도가 빠를 수 있으나 발산 위험이 있다. 따라서 이분법과 할선법을 혼합하면, 빠른 수렴과 안전한 구간 유지 사이에서 균형을 맞출 수 있다.
혼합 방식은 다음과 같이 적용한다. 우선 할선법의 갱신식을 사용해 $x_{n+1}$을 구하되, 만약 $f(x_{n+1})$가 기존 구간 내에서 부호가 바뀌지 않는 등 이상 징후가 발생하면, 그때 이분법에 의한 갱신으로 교체하는 식이다. 또는 일정 횟수 이상 같은 구간에 머무르며 수렴이 지체될 때 이분법으로 구간을 반씩 줄이기도 한다. 이를 통해 단일 할선법에서 흔히 발생하는 불안정성을 줄이면서, 이분법보다 빠른 속도를 꾀할 수 있다.
연속 차분 근사와 미세 조정
실제 코드를 작성할 때는, $f'(x_n)$을 알 수 없을 때 단순 할선법 대신에 근사 미분을 쓰는 접근도 가능하다. 예컨대 아주 작은 $\delta$에 대해
와 같은 전진 차분(혹은 후진, 중앙 차분)을 사용해 뉴턴 방법을 흉내 내는 것이다. 이 방법도 사실상 할선법과 유사한 원리로 도함수를 근사하는 셈이지만, 분모에 $x_n - x_{n-1}$ 대신 명시적으로 $\delta$를 두어 편의성을 높이거나 수렴 속도를 미세하게 조정할 수 있다는 장점이 있다. 다만 $\delta$가 너무 작거나 크면 수치 오차나 근사 오차가 커질 수 있으므로, 적절한 크기를 실험적으로 정해야 한다.
할선법 적용 시 고려해야 할 예외 상황
함수 $f(x)$가 매우 복잡한 형태라서 극값(local maxima/minima) 혹은 변곡점 근처에서 $f(x_n)$과 $f(x_{n-1})$가 유사한 값을 갖게 되면, 할선의 기울기가 0에 가까워 분모가 작은 상태가 발생한다. 이 경우 $x_{n+1}$이 큰 폭으로 이동할 수 있으며, 심하면 발산하는 현상이 벌어진다. 이런 문제를 완화하려면, $x_n$에서의 $f(x_n)$이 $x_{n-1}$에서의 $f(x_{n-1})$와 어느 정도 이상 다를 때만 할선법을 적용하거나, $\lambda_n$을 단계적으로 축소하여 스텝 크기를 줄이는 방법 등으로 대처할 수 있다.
또한 $f(x_n)$이 너무 커서 부동소수점 연산 범위를 넘어가거나, $f(x_{n}) - f(x_{n-1})$가 기계 정밀도 수준으로 작아져 floating-point 오차가 누적되는 상황도 신중하게 처리해야 한다. 예컨대, 주어진 함수 $f$가 지수 폭발을 일으킬 가능성이 있다면, 로그 변환이나 스케일링 기법을 이용해 값의 범위를 줄여 주는 방식을 고려할 수 있다.
수렴 차수와 오차 해석
스칼라 단일 방정식 $f(x) = 0$을 대상으로 할선법을 적용한다고 하자. 해를 $x^$라 하고, 반복점 $x_n$의 오차를 $e_n = x_n - x^$로 정의한다. 뉴턴 방법에서는 해 근방에서
와 같은 형태가 성립하여 이차 수렴을 보인다. 반면 할선법은 도함수 $f'(x)$ 대신에 $x_n, x_{n-1}$에서의 함수값을 통해 기울기를 근사하므로, 오차 관계가 약간 다르다.
일반적으로 할선법에서 $n$이 충분히 커지고 $e_n$이 매우 작아졌다고 가정하면, 오차가 다음과 같은 점근적 형태를 가진다는 결과를 얻을 수 있다:
여기서 $\kappa$는 특정 상수(오차 상수)다. 이 관계로부터, 지수 양변에 로그를 취하여
로 볼 수 있다. 이를 인접한 두 단계 차이로 재귀적으로 풀어보면, 국소 해 근방에서 반복점이 약 $1.618\ldots$ 정도의 수렴 차수를 갖게 된다. 이 $1.618\ldots$은 황금비 $\phi = \frac{1 + \sqrt{5}}{2}$에 해당하는 값이다.
정확한 증명은 Taylor 전개와 고차 항 분석이 필요하지만, 결과적으로 할선법은 뉴턴 방법의 이차 수렴과 단순 이분법의 선형 수렴 사이의 성능을 갖는다. 다만 적절한 문제 상황과 초기값 선택에 따라서는 계산 효율이 매우 좋을 수 있으며, 또 뉴턴 방법처럼 도함수를 구하지 않아도 된다는 장점이 존재한다.
Steffensen 가속 (Aitken-Δ² 변환)
할선법은 국소적으로 1.618 차수로 수렴하지만, 이를 가속하기 위한 기법 중 하나가 바로 Steffensen 가속(혹은 Aitken-Δ² 변환 기법)이다. 일반적으로 고정점 반복
에서 $x_n$이 수렴할 때, Steffensen 방법은
을 통해 빠른 국소 수렴을 기대한다. 할선법 자체를 고정점 반복식으로 볼 수도 있으며, 그 형태에 이 변환을 적용함으로써 뉴턴 방법에 근접한 수렴 속도를 가질 수 있다.
하지만 Steffensen 기법을 적용하는 과정에서도 분모가 0에 가까워지는 문제가 발생할 수 있고, 원래 함수의 성질에 따라서는 발산 가능성이 있으므로, 실제 구현 시에는 안전장치가 필요하다. 예를 들어 반복 과정에서 $x_{n+2} - 2x_{n+1} + x_n$이 지나치게 작은 값을 보이면, 해당 스텝에 대해서는 가속을 중단하고 기본 할선법으로 되돌아가는 방식이 있다.
할선법에서의 추가 보호 기법
함수값의 크기가 지나치게 커지거나, 연속 구간을 지나쳐서 해를 놓칠 우려가 있을 때에는, 보조 알고리즘을 활용하여 스텝을 제한하는 방식을 고려한다. 예컨대 $x_{n+1}$을 계산한 뒤, 만약
와 같은 형태로 이동량이 너무 커지면, $x_{n+1}$을 직접 쓰지 않고 “보수적” 추정을 사용해
처럼 재설정할 수 있다. 여기서 $M$과 $\mu$는 1 이하의 적절한 상수로 택한다. 이 방식을 ‘underrelaxation’ 혹은 ‘step size control’이라 부른다. 매개변수 $\mu$가 작을수록 발산을 방지하는 효과는 커지지만, 수렴 속도는 저하될 수 있다.
또한 $f(x_{n+1})$와 $f(x_n)$의 부호가 다르지 않을 경우, 혹은 중간값 정리가 시사하는 해의 존재 구간을 벗어난 흔적이 보이는 경우에도 스텝을 되돌리는 과정을 둘 수 있다. 이를 통해 수렴 구간을 보존하며 불필요한 반복을 줄일 수 있다.
고급 이론: Gauss–Lucas 정리와 근 분포
할선법이 다항식 방정식의 해를 찾는 데 적용될 때, 특정 복소평면 상에서 근들의 분포가 미치는 영향도 고려할 수 있다. 예컨대 $n$차 다항식의 모든 근이 실수 구간 내에 놓여 있는 경우, (특히 중근이 있거나 근 간격이 매우 좁은 경우) 반복 과정에서 분모가 작아지는 현상이 자주 관측된다. 할선법은 스스로 도함수를 근사하기 때문에, $f'(x^*)=0$에 가까운 상황(즉 중근에 근접)에서는 오차가 느리게 줄어든다. 이 문제를 해결하기 위한 변형으로, 중근 근방에서 다른 안정적인 알고리즘(예: 이분법이나 Mueller 방법 등)으로 전환하는 방법이 제시되기도 한다.
Gauss–Lucas 정리는 다항식의 근들과 그 미분 다항식의 근들 관계를 서술하는데, 할선법을 통해 자동으로 ‘근의 미분 정보’를 대략 추적하는 과정을 수치적으로 해석할 때나, 여러 근 중 특정 근을 찾아갈 때 복소 평면 상의 상관관계를 응용하기도 한다. 다만 이는 실제 구현보다는 이론적 측면에서 의미가 큰 부분이므로, 실용 코드에서는 보통 성능 튜닝이나 발산 방지 기법에 더 초점을 둔다.
간단한 예시 (C++ 코드)
위 코드는 단순 할선법에 “스텝 크기 제한(step_ctrl)” 매개변수를 도입한 예시다. $x_{n+1}$이 $x_n$과 지나치게 멀어지면, 그 차이를 $step_ctrl$ 배 이하로 묶도록 하여 발산을 막는다. $step_ctrl$ 값이 1보다 크면 사실상 제약이 크게 의미가 없고, 1보다 작으면 점진적으로 이동을 축소함으로써 안정성을 도모한다.
Regula Falsi(가위치법)와의 관계
할선법과 비슷한 알고리즘으로 Regula Falsi(일명 가위치법)가 있다. 가위치법은 이분법과 할선법을 절충하는 형태로, 해가 존재하는 구간을 일정하게 유지하면서도 할선의 기울기를 사용하여 근을 추정한다. 즉, $x_{n-1}$과 $x_n$을 잡고 그 사이에 근이 존재한다는 것을 전제로 할선 기울기를 계산한다. 그리고 새 점 $x_{n+1}$이 구간 밖으로 벗어나지 않도록, $f(x_{n+1})$의 부호에 따라 구간을 축소한다.
가위치법은 이분법처럼 구간이 지속해서 축소되므로, 적어도 단조 감소하는 잔차(residual)에 기반하여 오차를 제어할 수 있다. 하지만 이분법에 비해 빠른 속도를 기대할 수 있으며, 단순 할선법처럼 발산 위험이 거의 없는 점이 장점이다. 반면 할선법보다 업데이트 폭이 제한되므로, 잘 맞는 문제 상황에서는 순수 할선법이 더 빠르게 근에 접근하기도 한다.
브렌트(Brent) 방법
수치해석에서 실무적으로 가장 자주 사용되는 스칼라 근찾기 알고리즘 중 하나로 브렌트(Brent) 방법이 있다. 이는 이분법의 안정성, 할선법(또는 3차 보간법)의 빠른 수렴 속도를 결합한 것으로, 구간을 유지하면서도 역방향 보간(inverse interpolation)을 통해 근을 추정한다. 브렌트 방법은 특정 보장(예: 수렴 보장)과 더불어 평균적으로 매우 효율적인 특징을 갖는다.
브렌트 방법의 내부에서 할선법이 사용되기도 하고, 상황에 따라 역 2차·3차 보간을 시도한다. 만약 추정값이 구간 밖으로 벗어나거나 분모가 작아지는 등 안전성이 떨어진다고 판단되면 이분법 스텝으로 돌아가는 식이다. 따라서 매우 견고하면서도, 할선법이나 보간법이 제공하는 이점을 적절히 활용한다.
할선법의 기하학적 직관
할선법은 이름에서 나타나듯, “접선” 대신 “할선”을 사용하는 방법이다. $x_{n-1}$과 $x_n$을 지나는 직선의 교점을 구함으로써, 마치 뉴턴 방법의 미분값 대신 근사 기울기를 사용한다. 이를 그래프로 그려 보면, 아래와 같은 구도를 생각할 수 있다.
위 그림에서 (간단히 표현한) 곡선 $y = f(x)$를 생각하고, $x_{n-1}$, $x_n$에서의 점을 연결하는 선분이 $x$축과 만나는 위치가 $x_{n+1}$다. 뉴턴 방법이라면 $x_n$에서의 접선이 $x$축과 만나도록 반복점을 이동하므로, 이와 비교했을 때 할선법은 더욱 단순화된 도함수 근사를 사용한다. 그만큼 미분이 불가능하거나 비용이 큰 문제에서 특히 유용해진다.
해석적 미분이 어려운 문제에서의 활용
고차 다항식이나 일반 초월함수에서도 미분이 존재하지 않는 구간이 있거나, $f'(x)$ 계산이 매우 복잡할 때 할선법은 상당히 실용적이다. 예를 들어, $f(x)$가 수치적으로 정의된 “까다로운” 함수(실험 데이터의 보간 결과, 또는 복잡한 라이브러리 호출 등을 포함)인 경우, 각 단계에서 $f'(x)$를 추출할 수 없으므로 뉴턴 방법을 직접 사용하기 어렵다. 이때 할선법은 $f(x_n)$과 $f(x_{n-1})$만으로 근사 기울기를 구해 반복 과정을 진행함으로써, 빠르게 근을 찾을 수 있다.
다만, 할선법을 사용할 때는 매우 작은 분모 문제를 비롯해, $x_{n-1}$과 $x_n$이 해 근방이 아닌 곳에 있을 때 중간에 큰 폭으로 이동해 버리는 문제 등도 항상 주의해야 한다. 가능하면 해가 존재하는 구간을 먼저 추정한 뒤, 그 안에서 반복을 돌리는 편이 안전하고, 오차가 폭발하지 않도록 스텝 크기를 제어하는 매개변수를 두는 식으로 보강할 수 있다.
재시도 전략
실무 환경에서 대규모 반복 계산을 수행할 때, 단 한 번의 발산으로 전체 계산이 실패하는 상황을 피하기 위해 “재시도” 전략을 두기도 한다. 예를 들어 할선법으로 $x_{n+1}$을 구했는데 예상보다 $|f(x_{n+1})|$가 훨씬 커진다면, 곧바로 이전 단계로 돌아가 $\lambda_n$ 값을 줄인 상태(또는 다른 근사 기법)로 재시도하여 안전한 구간 안에서 다시 할선 스텝을 수행한다. 이렇게 유연하게 설계된 알고리즘들은, 예측 불가능한 함수 형태에서조차 원활하게 동작한다.
재시도 전략은 $n$차원 문제를 다루는 준-뉴턴 방법이나, 비선형 최적화 문제를 해석할 때도 광범위하게 쓰인다. 이는 한 번의 잘못된 스텝이 전체 알고리즘을 망가뜨리지 않도록, “백트래킹(backtracking)” 기법이나 “Line Search” 방식을 구축한 것과 일맥상통한다. 할선법은 단순해 보이지만, 실제로는 이러한 온갖 안전장치와 스텝 조절 기법을 결합해야 산업 현장이나 대규모 계산에 투입될 수 있다.
고차원 문제에서의 Anderson Mixing (Anderson 가속)
여러 방정식이 얽힌 고차원 비선형 시스템
을 풀기 위해서는 뉴턴-유형 방법이나 Broyden 방법 외에도 다양한 확장판이 존재한다. 그중 Anderson Mixing(또는 Anderson 가속, Anderson 반복)은 고정점 반복
에서, 최근 여러 스텝들의 변화를 축적·가중합하여 “가속”을 시도한다는 점에서, 할선법을 고차원적으로 일반화한 구조를 가진다.
Anderson Mixing은 1965년 D. G. Anderson이 처음 제안한 기법으로, 비선형 편미분방정식을 해석하는 데에도 자주 쓰인다. 기본 아이디어는 다음과 같다. 고정점 반복으로부터 받은 점열 $\mathbf{x}_n$이 있을 때, $m$개 정도의 과거 정보
를 모아, 이 벡터들의 적절한 선형 조합을 통해 “최적”에 가까운 갱신 방향을 구하는 식이다. 1차원 할선법에서 “이전 점들로부터 기울기를 근사하여 다음 점을 얻는” 과정을, 다차원에서 여러 스텝을 동시에 활용해 일반화한 것으로 볼 수 있다.
그리고 이 과정을 반복하면서, 국소 수렴 속도를 대폭 높이게 된다. Anderson Mixing은 이론적으로는 준-뉴턴 기법(Broyden 계열)이나 Steffensen 가속과 유사한 면이 있지만, 구현상으로는 벡터 및 행렬 연산을 통해 매우 효율적인 고차 가속을 제공한다. 다만, $m$(과거 이력 스텝 수)을 크게 잡으면 연산량과 메모리가 급증할 수 있으므로, 문제 크기와 계산 환경에 맞추어 $m$을 적절히 제한한다.
대규모 병렬 계산에서의 할선법
현대 슈퍼컴퓨팅 환경에서는, 1차원 방정식 하나를 풀기보다는 복잡한 다차원 방정식을 풀거나, 대규모 최적화 문제의 서브 루틴으로 수많은 근찾기 연산을 병렬로 실행하는 경우가 많다. 이때 할선법이나 준-뉴턴 계열 알고리즘을 병렬화하는 전략이 중요하다.
순수 1차원 할선법 자체는 워낙 단계 의존도가 높아, $x_{n+1}$을 구하기 위해 반드시 $x_n, x_{n-1}$의 값을 알아야 하므로 반복 구조가 직렬적이다. 그러나 대규모 문제에서 (가령 격자점마다 또는 파라미터 조합별로) 서로 다른 식을 병렬로 풀 때는, 각 식마다 독립적으로 할선법을 적용하므로 병렬성이 자동으로 생긴다.
고차원 비선형 시스템에서의 준-뉴턴 방법, Anderson Mixing 등의 기법을 병렬화하려면, 행렬·벡터 연산(야코비 행렬 근사, 스텝 갱신 등)을 효율적으로 분산하여 계산해야 한다. 할선법적 방식은 도함수(또는 야코비 행렬)를 직접 계산하지 않는 대신, 서로 다른 반복점의 함수값 $\mathbf{F}(\mathbf{x}_i)$를 병렬로 구해두고, 이들을 모아 기울기 정보를 추정할 수 있다. 이는 뉴턴 방법보다 병렬화가 상대적으로 용이한 측면이 있으며, 대규모 문제에서의 장점으로 꼽힌다.
불연속 또는 구간적 정의 함수에서의 대응
실제 산업·공학 문제에서는 $f(x)$가 불연속이거나, 구간별로 다른 식으로 정의된 경우도 흔하다. 예를 들어 온도-압력 구간에 따라 상방정식(Equation of state)이 달라지거나, 절대값·최솟값 같은 연산이 들어간 복합 함수 등이 그렇다. 이런 경우 뉴턴 방법은 도함수 $f'(x)$가 불연속인 지점에서 크게 흔들리기 쉽고, 그 정보를 정밀하게 추적하기도 쉽지 않다.
반면 할선법은 함수값만으로 작업하므로, 불연속점이 존재해도 “바로 그 지점에서의 도함수”를 구하지 않아도 된다. 물론 불연속 근방에서는 함수값이 튀거나, 매우 큰 값이 관측될 수도 있으므로, 분모가 0 혹은 0에 가깝게 되는 위험은 여전히 존재한다. 따라서 “초기값 구간 설정”과 “스텝 제어”가 필수다. 혹은 불연속 근방에서는 이분법 같은 보다 안정적인 기법으로 스위칭하는 방식도 검토한다.
여러 해가 존재할 때의 처리
방정식 $f(x)=0$이 여러 근을 갖는 경우, 할선법은 해 하나를 찾으면 종료하는 형태로 설계되는 일이 잦다. 만약 모든 근을 찾으려면, 구간 분할 기법을 우선 사용해 각 구간마다 1개씩 근이 존재하도록 나눈 뒤, 각 구간에 할선법을 적용하는 방식이 대표적이다. 이때도 매개변수 선택을 잘못하면, 근 사이를 넘어 발산하거나 다른 구간 쪽으로 스텝이 옮겨갈 수도 있으므로, 각 구간을 벗어나지 않도록 강제하는 로직을 결합해야 한다.
물론 복소 근이나 중근, 또는 음수가 아닌 실근만을 원하는 문제 등 조건이 다양할 수 있는데, 그에 따라 할선법 한 가지로는 부족할 수 있다. 예컨대 중근이 있으면 국소적으로 수렴 속도가 매우 저하된다. 이 경우, 중근이 예상되는 구간에서는 Broyden 기법처럼 도함수 근사를 좀 더 풍부하게 사용하거나, 해석적으로 중근 여부를 사전에 파악한 뒤 (간단한 조정으로) 근을 더 빠르게 추정할 수 있다.
할선법의 기타 응용
할선법은 단순히 방정식을 푸는 데 그치지 않고, 최적화 문제에서 1차원 선 탐색(line search)을 수행할 때도 활용된다. 예를 들어, 다차원 최적화에서 매개변수 $\alpha$를 찾아 $\min_\alpha \phi(\alpha)$를 만족시키는 선 탐색 문제가 주어진다면, $\phi'(\alpha)=0$ 형태가 된다. 이때 $\alpha$ 차원에서 할선법을 실행하여 도함수가 없는 상황에서도 1차원 해를 빠르게 찾을 수 있다.
또한, 확률론이나 통계 분야에서 누적 분포함수(CDF)의 역함수를 수치적으로 구하는 작업(예: 분위수 계산)에도 유용하다. 예컨대 어떤 누적분포 $F(x)$가 주어졌을 때, $F(x) - p = 0$을 만족하는 $x$(즉 $p$ 분위수)를 구하려면, 할선법이나 이분법 등을 적용한다. $F$가 미분 가능하긴 해도, 실제로는 복잡한 적분 연산으로 정의되어 도함수를 구하기 곤란하면, 할선법이 큰 도움이 된다.
Last updated