역 이차 보간

1. 개요

역 이차 보간 Inverse Quadratic Interpolation
푸는 것	스칼라 방정식 f(x) = 0
필요한 것	점 세 개, 반복당 함수 평가 1회 (도함수 불필요)
수렴 차수	단순근에서 약 1.839 (t³ = t² + t + 1 의 실근)
주 용도	브렌트 방법의 가속 스텝
약점	함수값 셋이 서로 달라야 함, 근을 가두지 않음

$y$ 가 $x$ 의 함수라면, 근 찾기는 $x$ 를 $y$ 의 함수로 보고 $y=0$ 을 대입하는 일이다. 뒤집으면 끝.

역 이차 보간(inverse quadratic interpolation, IQI)은 방정식 $f(x)=0$ 의 근을 찾을 때 최근 세 점 $(x_i, f_i)$ 를 지나는 이차식을 $y=f(x)$ 가 아니라 $x$ 를 $y$ 의 함수로 맞춘 뒤, 그 식에 $y=0$ 을 넣어 다음 반복점을 얻는 방법이다. 이차방정식을 풀 필요가 없어 근의 공식·복소수가 끼어들 틈이 없고, 단순근 근처에서 수렴 차수가 약 1.839로 할선법의 1.618보다 높다.

단독으로 쓰이는 일은 거의 없다. 근을 가두지 않아 쉽게 탈선하기 때문이다. 대신 브렌트 방법의 엔진 — “안전할 때만 밟는 가속 페달” — 으로 세상 거의 모든 1차원 근 찾기 루틴 안에 들어가 있다.

2. 공식

세 점 $(x_0,f_0)$, $(x_1,f_1)$, $(x_2,f_2)$ 에서 $x$ 를 $y$ 의 이차식으로 라그랑주 보간하면

$$x(y) = \sum_{i=0}^{2} x_i \prod_{j\neq i} \frac{y - f_j}{f_i - f_j}.$$

$y=0$ 을 대입한 것이 다음 반복점이다.

$$x_3 = \frac{x_0 f_1 f_2}{(f_0-f_1)(f_0-f_2)} + \frac{x_1 f_0 f_2}{(f_1-f_0)(f_1-f_2)} + \frac{x_2 f_0 f_1}{(f_2-f_0)(f_2-f_1)}.$$

그리고 가장 오래된 점을 버리고 반복한다. 식을 보면 분모에 함수값의 차 $f_i - f_j$ 가 있다. 세 함수값 중 둘이 같으면 정의되지 않고, 비슷하기만 해도 $x_3$ 이 멀리 날아간다. 할선법의 ”$f_k \approx f_{k-1}$ 이면 터진다”는 약점이 그대로, 그것도 두 배로 이어진다.

왜 “역”인가. 정방향 이차 보간 — $y$ 를 $x$ 의 포물선으로 맞추고 그 포물선의 근을 구하는 것 — 은 뮬러 방법이다. 뮬러는 이차방정식을 풀어야 하고 판별식이 음수면 복소 근이 나온다. 다항식의 복소근을 찾을 때는 오히려 그게 장점이지만, 실수 근 하나만 원하는 상황에선 귀찮다. 역 보간은 $x(y)$ 를 평가만 하면 되니 그런 고민이 없다. 대신 $f$ 가 세 점 사이에서 단조가 아니면 역함수 $x(y)$ 자체가 의미를 잃는다.

3. 수렴 차수 1.839

할선법이 황금비 $\varphi$ 를 얻는 논리를 그대로 따라가면 된다. 오차 $e_k = x_k - r$ 에 대해 역보간의 오차는 대략 직전 세 오차의 곱에 비례한다.

$$e_{k+1} \approx C\, e_k\, e_{k-1}\, e_{k-2}.$$

$|e_{k+1}| \sim |e_k|^p$ 라고 놓고 지수만 비교하면 $p^3 = p^2 + p + 1$ 이 나오고, 이 식의 실근이

$$p \approx 1.839286755\ldots$$

이다. 이른바 트리보나치 상수다.¹ 같은 논리로 직전 $m$ 개 점을 모두 쓰는 역보간의 차수는 $p^{m} = p^{m-1} + \cdots + 1$ 의 근이 되고, $m$ 이 커질수록 2로 다가가지만 2를 넘지는 못한다. 점을 무한히 많이 써도 뉴턴의 2차를 못 넘는다는 이 결과는 트라웁(1964)의 고전적 분석에 정리돼 있다. 현실에서는 점을 늘릴수록 분모의 차 $f_i-f_j$ 가 작아져 반올림 오차가 커지니 셋에서 멈추는 게 국룰이다(TOMS 748 은 넷까지 쓴다 — 아래 참고).

3.1. 검산 — 할선법과 나란히

$f(x)=x^3-2x-5$, 근 $r=2.0945514815423265$. 할선법은 $x_0=2,\ x_1=3$, 역 이차 보간은 여기에 $x_2=2.5$ 를 더해 시작했다.

반복	할선법 $\lvert e\rvert$	역 이차 보간 $\lvert e\rvert$
1	$3.6\times10^{-2}$	$1.0\times10^{-2}$
2	$1.3\times10^{-2}$	$1.0\times10^{-3}$
3	$2.7\times10^{-4}$	$1.8\times10^{-6}$
4	$2.1\times10^{-6}$	$1.0\times10^{-11}$
5	$3.1\times10^{-10}$	$4.4\times10^{-16}$
6	$4.4\times10^{-16}$	$0$

반복당 정밀도는 역 이차 보간이 확실히 빠르다. 3회차→4회차에서 오차가 $1.8\times10^{-6}$ 에서 $10^{-11}$ 로 가는데, $1.84$ 승이면 대략 $3\times10^{-11}$ 대가 예상되니 이론과 맞는다.

그런데 총 함수 평가 횟수로 세면 할선법은 2+6=8회, 역 이차 보간은 3+5=8회(5회차에 이미 반올림 바닥)로 비긴다. 시작점이 하나 더 필요한 비용이 차수 이득을 거의 다 먹었다. 근 찾기의 효율은 “차수”가 아니라 “평가당 이득”이고, 실무 함수는 대개 몇 번 만에 끝나기 때문에 출발 비용이 무시되지 않는다. 역 이차 보간이 브렌트 방법 안에서 이미 확보된 세 점을 재활용할 때만 빛나는 이유다.

4. 언제 망가지는가

• 함수값이 겹칠 때. 세 점 중 둘의 $f$ 가 같으면 0으로 나눈다. 브렌트 방법은 이때 할선법(점 둘)으로 내려간다.
• 비단조 구간. 세 점 사이에 극값이 있으면 $x(y)$ 포물선이 근과 무관한 곳을 가리킨다. 원래 함수에는 근이 하나인데 역보간 포물선은 $y=0$ 에서 엉뚱한 $x$ 를 내놓는다.
• 근에서 멀 때. 이차 근사가 의미 있으려면 세 점이 이미 근 근처여야 한다. 멀리서 쓰면 다음 점이 구간 밖으로 튄다.²

이 셋 모두 “결과가 기존 구간 안쪽, 그것도 충분히 안쪽에 떨어지는가”만 확인하면 걸러진다. 브렌트 방법의 수락 조건이 정확히 그 일을 한다 — 보간 결과가 구간의 3/4 지점 안에 들어오고, 직전 스텝보다 충분히 작을 때만 받아들이고, 아니면 이분법으로 후퇴한다.

5. 친척들

• 역 삼차 보간. 알레펠트·포트라·시(Alefeld, Potra & Shi, 1995)의 TOMS 748 은 점 넷으로 역 삼차 보간을 하고, 가두기 구간을 함께 줄이는 장치를 붙였다. SciPy 의 toms748 이 이것이다.
• 할선법 = 역 일차 보간. 두 점을 잇는 직선은 정방향이든 역방향이든 같은 직선이라, 할선법은 “역 일차 보간”이라고 불러도 틀리지 않는다. 차이는 이차부터 생긴다.
• 스테펜센 방법·앤더슨 가속. 이전 반복점들을 엮어 외삽한다는 정신은 같지만, 근 찾기 대신 고정점 반복을 가속한다.

6. 관련 문서

• 할선법 · 이분법 · 브렌트 방법 · 뉴턴-랩슨법
• 보간과 근사 · 뮬러 방법 · 스테펜센 방법
• 앤더슨 가속 · 부동소수점 연산

7. Footnotes

1. 피보나치가 두 항을 더하면 황금비(할선법), 세 항을 더하면 트리보나치 상수(역 이차 보간). 근 찾기 수렴 차수 문제는 결국 수열 문제다. 수열 문제를 싫어하는 학생에겐 비보. ↩

2. 고차 방법일수록 “근 근처에서는”이라는 단서가 길어진다. 1.839차짜리 엔진을 단독으로 달고 출발하면 대개 첫 커브에서 이탈한다. 그래서 브레이크(이분법)와 같이 판다. ↩