가위치법

1. 개요

가위치법 Regula Falsi (False Position)
푸는 것	연속함수의 스칼라 방정식 f(x) = 0
필요한 것	부호가 바뀌는 구간 [a, b], 반복당 함수 평가 1회
수렴	원판은 1차(한쪽 끝점 고정), 일리노이 변형은 초선형
보장	근을 항상 구간 안에 가둔다 (폭이 0으로 간다는 보장은 없음)
친척	이분법 · 할선법 · 브렌트 방법 · ITP 방법

근을 가두는 건 이분법처럼, 다음 점을 고르는 건 할선법처럼. 둘의 장점만 모았는데 왜 둘 다보다 느린가.

가위치법(假位置法, regula falsi, method of false position)은 부호가 반대인 두 점 $(a, f(a))$, $(b, f(b))$ 를 잇는 직선이 $x$ 축과 만나는 점을 새 근사로 삼고, 그 점과 부호가 반대인 쪽 끝점을 남겨 근을 계속 구간 안에 가두는 방법이다. 공식만 보면 할선법과 똑같고, 구간을 유지하는 규칙은 이분법과 같다.

직관적으로는 “선형 보간으로 똑똑하게 고르면서 안전하기까지 한” 최강의 방법 같지만, 실제로는 원판 가위치법이 할선법보다 훨씬 느리고, 심하면 이분법보다도 느리다. 이 문서는 그 이유(끝점 고정 현상)를 수치로 확인하고, 그걸 고친 일리노이·앤더슨-비요르크 변형, 그리고 같은 고민의 현대적 결론인 브렌트 방법·ITP 방법까지 정리한다.

2. 공식과 역사

현재 구간 $[a,b]$ 에서 $f(a)f(b)<0$ 이라 하자. 두 점을 잇는 직선의 영점은

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

이다. $f(c)$ 의 부호가 $f(b)$ 와 반대면 $[b, c]$ 를, 같으면 $[a, c]$ 를 다음 구간으로 삼는다. 할선법은 이 부호 검사 없이 가장 최근 두 점을 무조건 쓴다는 점만 다르다. 수치적으로는 둘째 형태(최근 점 $b$ 에 보정량을 더하는 꼴)가 상쇄 오차에 덜 민감하다.

이름이 말해 주듯 이건 컴퓨터보다 훨씬 오래된 방법이다. “틀린 값을 두 번 넣어 보고, 각각 얼마나 틀렸는지로 정답을 비례 배분한다”는 이중 가정법은 고대 이집트·중국(『구장산술』의 영부족(盈不足) 장)에 이미 나오고, 피보나치의 『산반서』(1202)를 거쳐 중세 유럽 상인 산술의 표준 기법이 됐다.¹ 선형 문제에서는 한 번에 정답을 주니 당연히 인기였다. 비선형에서 반복하기 시작한 것이 지금의 가위치법이다.

3. 끝점 고정 — 왜 1차로 주저앉는가

$f$ 가 근 근처에서 볼록(또는 오목)하면, 직선은 매번 곡선의 같은 쪽에서 축을 자른다. 그러면 새 점은 늘 같은 쪽 끝점을 대체하고, 반대쪽 끝점은 처음 위치에 영원히 고정된다. 할선이 한쪽 다리를 근 근처에 두지 못하니 기울기 추정이 근에서의 접선과 끝까지 어긋난다.

고정된 끝점을 $b$ 라 하면, 근 $r$ 근처에서 오차 $e_k = x_k - r$ 는

$$e_{k+1} \approx \left(1 - \frac{f'(r)\,(b - r)}{f(b)}\right) e_k$$

로 선형 수렴한다. 괄호 안이 수렴률이고, $f$ 가 구간 위에서 많이 휠수록 1에 가까워진다.

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

이분법 문서와 같은 $f(x)=x^3-2x-5$ (근 $r=2.0945514815423265$) 를 $[2,3]$ 에서 돌렸다. $f''>0$ 이라 오른쪽 끝 $b=3$ 이 처음부터 끝까지 고정된다. 오차 비 $e_{k+1}/e_k$ 를 찍어 보면

반복	근사값	오차	오차 비
1	2.0588235	$-3.57\times10^{-2}$	—
2	2.0812637	$-1.33\times10^{-2}$	0.3719
4	2.0927396	$-1.81\times10^{-3}$	0.3689
8	2.0945181	$-3.34\times10^{-5}$	0.3684

이고, 위 공식이 주는 수렴률 $1 - f'(r)(3-r)/f(3) = 0.36837$ 로 정확히 붙는다. 오차 $10^{-12}$ 까지 26회가 걸렸다. 이분법(40회)보다는 낫지만, 같은 시작점에서 할선법은 한 자릿수 반복이면 끝난다.

더 나쁜 예가 $f(x)=x^{10}-1$, 구간 $[0, 1.3]$ 이다. $x<1$ 쪽이 거의 평평해서 직선이 매번 왼쪽 근처를 찍고, 오른쪽 끝 $1.3$ 은 고정된다. 오차 $10^{-12}$ 까지 113회. 이분법은 이 구간에서 41회면 끝나니, 가위치법이 이분법에 세 배 가까이 진다. “똑똑한 보간”이 순진한 반 자르기에 지는 대표 사례다.

4. 고치는 법 — 고정된 끝점의 함수값을 깎는다

같은 끝점이 연달아 두 번 남으면, 그 끝점의 함수값을 인위적으로 줄여서 다음 할선이 축을 반대쪽에서 자르도록 유도한다. 근을 가둔다는 성질은 그대로다(부호는 안 바꾸고 크기만 줄이니까).

• 일리노이 변형(Dowell & Jarratt, 1971). 남는 끝점의 함수값을 그냥 반으로 나눈다. 이름은 논문 전부터 일리노이 대학교 쪽에서 쓰이던 관행에서 왔다는 설명이 흔하다. 수렴 차수는 $3^{1/3}\approx1.442$ 로 알려져 있다.
• 페가수스 변형(Dowell & Jarratt, 1972). 반 대신 $f(b)/(f(b)+f(c))$ 배로 깎는다. 같은 저자들이 이듬해 낸 개선판이다.
• 앤더슨-비요르크 변형(1973). 배율 $m = 1 - f(c)/f(b)$ 를 쓰고, $m\le0$ 이면 $1/2$ 로 물린다. 남은 세 점을 지나는 포물선의 기울기를 흉내 내는 배율이다.

위 두 문제에 셋을 돌린 결과(오차 $10^{-12}$ 까지의 반복 수):

방법	$x^3-2x-5$, $[2,3]$	$x^{10}-1$, $[0, 1.3]$
원판 가위치법	26	113
일리노이	7	14
앤더슨-비요르크	6	24
(참고) 이분법	40	41

깎기 한 줄로 반복이 1/4~1/8로 준다. 다만 두 번째 열에서 보듯 “가장 좋은 변형”은 문제마다 다르다. 앤더슨-비요르크가 평소에 더 빠르지만, 극단적으로 평평한 함수에서는 배율이 1에 가까워 깎는 힘이 약해지고 $m\le0$ 폴백을 자주 탄다.²

5. 보장의 함정 — “가둔다” ≠ “구간이 준다”

이분법은 반복마다 폭이 정확히 반이 되니 “구간 폭 < 허용오차” 로 멈추면 된다. 원판 가위치법은 근을 가두긴 하지만 폭이 0으로 가지 않는다. 위 삼차식에서 26회 뒤에도 구간은 $[2.0945514815\ldots, 3]$ 으로, 폭이 0.9 넘게 남아 있다. 고정된 끝점이 안 움직이니까.

그래서 폭 기준으로 멈추게 짠 가위치법은 영원히 안 끝난다. 원판을 쓸 거라면 정지 조건은 “연속한 두 근사의 차” 나 $|f(c)|$ 로 줘야 하고, 그러면 이번엔 1차 수렴의 느린 꼬리 때문에 “차가 작다 = 근에 가깝다” 가 성립하지 않는다(수렴률 $\rho$ 의 선형 수렴에서 실제 오차는 스텝 크기의 대략 $\rho/(1-\rho)$ 배). 변형들은 양 끝이 모두 움직여 폭이 실제로 0으로 가므로 이 문제도 같이 풀린다.

6. 현대의 결론 — 브렌트와 ITP

“가두면서 빠르게”는 가위치법 하나로는 안 된다는 게 1970년대의 결론이었다. 그 뒤 나온 답들은 모두 빠른 스텝을 시도하되, 안 줄면 이분법으로 강제 후퇴하는 구조다.

• 브렌트 방법(1973)은 할선법·역 이차 보간을 시도하고, 직전 두 스텝에 비해 충분히 줄지 않으면 이분 스텝을 끼워 넣는다. 최악에도 함수 평가 수가 이분법 반복 수의 대략 제곱을 넘지 않는다는 보장이 있다.
• ITP 방법(Oliveira & Takahashi, 2020)은 가위치 점을 이분 중점 쪽으로 끌어당긴 뒤(interpolate–truncate–project), 이분법이 $k$ 번째에 보장하는 폭을 넘지 않게 사영한다. 최악의 경우 반복 수가 이분법보다 고정된 상수 이상 많아지지 않으면서, 매끄러운 함수에서는 초선형으로 수렴한다. 가위치법의 “보간은 좋은데 끝점이 고정된다” 문제를 정면으로 푼 셈이다.

결국 원판 가위치법은 지금 실무 라이브러리에 단독으로 거의 안 남아 있다. 그래도 교육용으로 가치가 큰 건, “근사 공식이 좋다”와 “반복이 빨리 끝난다”가 전혀 다른 이야기라는 걸 이만큼 깔끔하게 보여 주는 예가 드물어서다. 수렴 차수는 공식 한 줄이 아니라 점을 어떻게 갈아 끼우느냐가 정한다.³

7. 관련 문서

• 이분법 · 할선법 · 브렌트 방법 · 역 이차 보간 · 뉴턴-랩슨법
• 뮬러 방법 · 스테펜센 방법 · ITP 방법 · 수렴 차수
• 부동소수점 연산 · 사격법

8. Footnotes

1. “거짓 위치”라는 이름은 방법이 틀렸다는 게 아니라 일부러 틀린 값을 넣어 본다는 뜻이다. 중세 상인들은 이걸 수식 없이 외워서 썼다. 대수학 없이 일차방정식을 푸는 국룰이었던 셈. ↩

2. 알고리즘 이름이 대학 이름인 경우는 드물다. 유래 설명대로라면 논문이 나오기 전부터 다들 이렇게 짜고 있었다는 뜻이니, 사실상 구전 알고리즘이다. ↩

3. 할선법은 근을 놓칠 수 있어서 빠르고, 가위치법은 근을 절대 안 놓쳐서 느리다. 현생과 비슷하다. ↩