ITP 방법

1. 개요

ITP 방법(Interpolate–Truncate–Project method)은 부호가 바뀌는 구간 안의 근을 찾는 구간 축소형 근 찾기 알고리즘으로, 매 반복마다 ① 가위치법의 보간점을 구하고(Interpolate) ② 이를 이분법 중점 쪽으로 조금 끌어당긴 뒤(Truncate) ③ 이분법이 그 시점에 보장하는 폭을 넘지 않도록 사영한다(Project). 이름이 곧 알고리즘이다.

배경은 오래된 긴장이다. 이분법은 정확도 $\varepsilon$ 를 얻는 데 $n_{1/2}=\lceil\log_2\frac{b-a}{2\varepsilon}\rceil$ 번이 필요하고, 함수값만 보는 방법 중 최악의 경우 이보다 적게 쓰는 방법은 없다(minmax 최적). 대신 함수가 아무리 매끄러워도 한 번에 1비트씩만 얻는다. 할선법·가위치법·브렌트 방법 같은 보간형은 평균적으로 훨씬 빠르지만, 최악의 경우 이분법보다 많이 걸릴 수 있다 — 브렌트도 최악 반복 수가 이분법의 대략 제곱 수준까지 갈 수 있다는 것이 알려져 있다.

이반 올리베이라와 히카르두 타카하시가 보인 것은 둘 중 하나를 고를 필요가 없다는 것이다. ITP 는 최악 반복 수가 $n_{1/2}+n_0$ 로 이분법보다 고정된 상수 $n_0$ 이상 늘지 않으며($n_0=0$ 이면 이분법과 같다), 동시에 $f$ 가 매끄럽고 근이 단순하면 초선형으로 수렴한다.¹ 논문 제목이 그대로 요약이다 — An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality.

2. 알고리즘

입력은 $a<b$, $f(a)f(b)<0$, 허용오차 $\varepsilon$, 초매개변수 $\kappa_1\in(0,\infty)$, $\kappa_2\in[1,1+\varphi)$, $n_0\ge0$ 이다($\varphi$ 는 황금비). 미리 $n_{1/2}=\lceil\log_2\frac{b-a}{2\varepsilon}\rceil$, $n_{\max}=n_{1/2}+n_0$ 를 계산하고, $j=0$ 부터 $b-a>2\varepsilon$ 인 동안 반복한다.

준비. 이분 중점, 사영 반지름, 절단 크기를 계산한다.

$$x_{1/2}=\frac{a+b}{2},\qquad r_j=\varepsilon\,2^{\,n_{\max}-j}-\frac{b-a}{2},\qquad \delta_j=\kappa_1(b-a)^{\kappa_2}$$

보간(Interpolate). 양 끝점을 잇는 직선의 영점, 즉 가위치(regula falsi) 점을 구한다.

$$x_f=\frac{f(b)\,a-f(a)\,b}{f(b)-f(a)}$$

절단(Truncate). $\sigma=\operatorname{sign}(x_{1/2}-x_f)$ 로 두고, $x_f$ 를 중점 방향으로 $\delta_j$ 만큼 민다. 단 중점을 넘어서지는 않는다.

$$x_t=\begin{cases} x_f+\sigma\delta_j & \delta_j\le|x_{1/2}-x_f| \\ x_{1/2} & \text{otherwise}\end{cases}$$

사영(Project). 중점에서 $r_j$ 이상 떨어졌으면 반지름 $r_j$ 의 구간 경계로 끌어온다.

$$x_{\mathrm{ITP}}=\begin{cases} x_t & |x_t-x_{1/2}|\le r_j \\ x_{1/2}-\sigma r_j & \text{otherwise}\end{cases}$$

그다음 $f(x_{\mathrm{ITP}})$ 의 부호로 구간을 갱신하고 $j$ 를 하나 늘린다. 반복당 함수 평가는 딱 한 번이다.

2.1. 세 단계가 각각 하는 일

• 보간은 속도를 담당한다. 매끄러운 함수에서 가위치 점은 근에 아주 가깝다.
• 절단은 가위치법의 고질병인 끝점 고정을 깬다. 원판 가위치법은 볼록한 함수에서 한쪽 끝만 계속 갱신되고 다른 끝은 영영 안 움직여 1차 수렴으로 주저앉는데(가위치법 문서의 핵심 주제다), $\delta_j$ 만큼 중점 쪽으로 밀면 새 점이 근의 반대편에 떨어질 확률이 생겨 구간이 양쪽에서 줄어든다. $\delta_j\propto(b-a)^{\kappa_2}$ 라서 구간이 작아질수록 미는 양은 그보다 빠르게 작아져, 보간의 정확도를 망치지 않는다.
• 사영은 보장을 담당한다. $r_j$ 는 “앞으로 남은 반복 $n_{\max}-j$ 번을 전부 이분법으로 써도 $\varepsilon$ 에 도달할 수 있는 최대 여유”다. 이 여유 안에서는 보간을 믿고, 벗어나면 이분법 쪽으로 물러난다. $n_0$ 는 처음부터 여유를 $2^{n_0}$ 배 넉넉하게 주는 장치다. $n_0=0$ 이면 첫 반복의 $r_0$ 가 0 이어서 첫 걸음은 순수 이분이 된다.

3. 왜 최악이 이분법 + 상수인가

사영 단계가 보장하는 불변식은 이것이다: $j$ 번째 반복 뒤 구간 폭은 언제나

$$b_j-a_j\le 2\varepsilon\,2^{\,n_{\max}-j}$$

이다. 중점에서 $r_j$ 이내의 점은 어느 쪽으로 갱신되든 새 구간 폭을 $\frac{b-a}{2}+r_j=\varepsilon\,2^{\,n_{\max}-j}$ 이하로 만들기 때문이다. 그러면 $j=n_{\max}$ 에서 폭이 $2\varepsilon$ 이하이고, 중점을 답으로 내면 오차 $\varepsilon$ 이 보장된다. 보간이 아무리 엉터리여도(불연속에 가까운 함수, 평평한 구간, 계단) 이 상한은 깨지지 않는다.

비교하자면 브렌트 방법의 안전장치는 “보간이 직전 두 걸음만큼 줄지 않으면 이분으로 바꾼다” 는 사후 검사라서, 보간이 조금씩만 나아지는 시나리오에서 이분 전환이 늦게 걸린다. ITP 의 사영은 매 걸음 남은 예산을 계산하는 사전 검사다. 이 차이가 최악 보장의 차이다.

4. 수렴 — 매끄러운 경우

$f$ 가 두 번 연속미분 가능하고 근이 단순하면, 구간 폭은 차수 $\kappa_2$ 로 초선형 수렴한다(원 논문의 결과, $n_0>0$ 일 때. $n_0=0$ 에서는 $\frac{b-a}{\varepsilon}$ 에 대한 기술적 조건이 하나 붙는다). $\kappa_2$ 의 상한이 $1+\varphi\approx2.618$ 로 묶인 것은 원 논문의 분석에서 나온 조건으로, 절단 크기 $\delta_j$ 가 보간 오차보다 충분히 빨리 작아져서 매끄러운 경우에 결국 보간을 방해하지 않게 하기 위한 것이다.

실무에서는 $\kappa_2=2$, $n_0=1$ 근처가 무난하다. $\kappa_1$ 은 절대값보다 처음 구간 폭 $L=b-a$ 로 무차원화해 $\kappa_1=c\,L^{1-\kappa_2}$ 로 정하는 게 자연스럽다($\kappa_2=2$ 이면 $c/L$). 그래야 $\delta_j=c\,L\,\big((b-a)/L\big)^{\kappa_2}$ 가 되어 $x$ 의 단위를 바꿔도 같은 궤적이 나온다. 아래 검산은 $b-a=1$ 이라 $c$ 와 $\kappa_1$ 이 같다.

5. 검산 — 월리스의 삼차식

가위치법 문서에서 쓴 $f(x)=x^3-2x-5$, $[2,3]$, $\varepsilon=10^{-10}$ 을 그대로 돌렸다($n_{1/2}=33$, 근 $2.0945514815423265$).

방법	함수 평가 수	비고
이분법	33	보장 그대로
원판 가위치법	21	끝점 $x=3$ 고정, 근 $10^{-10}$ 이내 도달까지
일리노이 변형	7
ITP ($\kappa_1=0.2$, $\kappa_2=2$, $n_0=1$)	7	구간 폭: 0.16 → 0.07 → 6.3e-3 → 2.9e-4 → …
ITP ($\kappa_1=0.2$, $\kappa_2=1.5$, $n_0=1$)	10	차수가 낮아 한두 걸음 더
ITP ($\kappa_1=0.1$, $\kappa_2=2$, $n_0=1$)	33	아래 함정 참고

마지막 줄이 재미있다. 6번째 반복에서 폭이 $7.5\times10^{-9}$ 가 되자 $\delta=0.1\times(7.5\times10^{-9})^2\approx5.6\times10^{-18}$ 이 근 근처 배정밀도의 간격(약 $4.4\times10^{-16}$)보다 작아져, $x_t$ 가 $x_f$ 와 비트 단위로 같아졌다. 그런데 $x_f$ 는 이미 반올림 수준에서 근과 같은 수여서 매번 같은 쪽 끝점만 갱신되고 구간이 안 줄었다 — 실수 연산에서 사라졌던 끝점 고정이 부동소수점 연산에서 부활한 것이다. 그래도 사영의 여유 $r_j$ 가 줄어들다 0 에 닿자 이분 쪽으로 강제됐고, 정확히 $n_{1/2}=33$ 번째에 종료했다. 보장이 일을 했다. 실무 교훈은 둘이다: 종료 판정에 ”$|f(x)|$ 가 반올림 수준이면 그 $x$ 를 답으로” 를 하나 더 넣을 것, 그리고 $\kappa_1$ 이 너무 작으면 절단이 반올림에 묻힌다는 것.²

6. 브렌트와의 관계, 그리고 실무

ITP 는 브렌트 방법을 대체하려고 나온 것이 아니라 브렌트가 비워 둔 칸을 채운다.

• 매끄러운 함수의 평균 평가 수는 둘이 비슷하다. 역이차보간을 쓰는 브렌트가 조금 빠른 경우도 흔하다.
• 최악 보장은 ITP 가 확실히 낫다. 함수 평가 하나가 CFD 한 번 돌리기만큼 비싸서 상한을 예산으로 잡아야 하는 상황(예: 파라미터 하나를 맞추는 바깥 루프, 하드 실시간 시스템)이 ITP 의 자리다.
• 구현은 브렌트보다 훨씬 짧다. 분기 두 개짜리 식 세 줄이 전부라 검증·이식이 쉽다.

참조 구현은 존 버카트의 zero_itp(C·MATLAB 등) 가 있고, 몇몇 언어의 근 찾기 라이브러리(예: Julia 의 Roots.jl 에 ITP() 가 있다)가 선택지로 넣었다. 다만 2026년 현재 SciPy brentq 처럼 “그냥 기본값” 이 된 곳은 드물다. 브렌트가 50년 동안 쌓은 신뢰를 넘기엔 아직 시간이 필요하다.³

7. 관련 문서

• 이분법 · 가위치법 · 할선법 · 브렌트 방법
• 뉴턴-랩슨법 · 스테펜센 방법 · 뮬러 방법
• 수렴성 · 일리노이 알고리즘 · 부동소수점 연산

8. Footnotes

1. “minmax 최적” 이란 가장 운 나쁜 함수에 대해 필요한 평가 수를 최소화한다는 뜻이다. 이분법이 이 의미에서 최적이라는 것은 1950년대부터 알려진 사실이고, 그래서 “이분법보다 빠르다” 는 모든 주장에는 “평균적으로는” 이라는 각주가 붙어 왔다. ITP 는 그 각주를 “평균적으로는 빠르고, 최악이어도 $n_0$ 번만 더” 로 바꿨다. ↩

2. 이 현상은 이 문서를 쓰면서 직접 돌려 보다가 발견했다. 논문의 정리는 실수 연산 기준이라 틀린 데가 없다. 수치해석 알고리즘이 “정리는 맞는데 컴퓨터에선 다르게 군다” 를 보여 주는 소박한 사례로, 계산 결과를 손으로 한 번 보는 습관이 왜 필요한지 다시 일깨운다. ↩

3. 브렌트의 1973년 책에 실린 ALGOL 60 코드가 거의 그대로 포트란·C·파이썬으로 번역돼 내려왔다. 알고리즘에도 “레거시가 곧 신뢰” 라는 공식이 통한다. 새 알고리즘이 표준 라이브러리 기본값이 되려면 증명보다 사용 사례 10년이 더 필요하다는 게 국룰. ↩