할선법

1. 개요

할선법 Secant Method
푸는 것	스칼라 방정식 f(x) = 0
필요한 것	초기값 두 개, 반복당 함수 평가 1회 (도함수 불필요)
수렴 차수	단순근에서 φ = (1+√5)/2 ≈ 1.618
계보	이중 가정법(regula duorum falsorum) → 할선법 → 브로이던 방법
약점	근을 가두지 않음 — 전역 수렴 보장 없음

미분이 귀찮다고? 지난 두 점을 이으면 그게 미분이다.

할선법(secant method)은 방정식 $f(x)=0$ 의 근을 찾을 때 뉴턴-랩슨법의 도함수 $f'(x_k)$ 를 직전 두 반복점을 잇는 직선(할선)의 기울기로 바꿔 쓰는 반복법이다. 반복마다 새 함수값 하나만 계산하면 되고, 단순근 근처에서 수렴 차수가 황금비 $\varphi\approx1.618$ 이다 — 뉴턴의 2차보다 느리지만, 함수 평가 한 번당 따지면 오히려 뉴턴을 이기는 경우가 많다.

이 문서는 공식 자체보다 그 주변을 판다. 차수가 왜 하필 황금비인지, “평가당 효율”로 뉴턴과 비교하면 무슨 일이 벌어지는지, 근을 가두지 않는 약점을 실무가 어떻게 메우는지(가위치법·브렌트 방법), 그리고 다변수로 옮겼을 때 왜 브로이던 방법이 나오는지까지.

2. 공식과 기하

직전 두 점 $(x_{k-1},f_{k-1})$, $(x_k,f_k)$ 를 지나는 직선이 $x$ 축과 만나는 점을 다음 반복점으로 삼는다.

$$x_{k+1} = x_k - f_k\,\frac{x_k - x_{k-1}}{f_k - f_{k-1}}.$$

뉴턴법 $x_{k+1}=x_k - f_k/f'(x_k)$ 에서 $f'(x_k)$ 를 후진 차분 $(f_k-f_{k-1})/(x_k-x_{k-1})$ 로 바꾼 꼴이다. 그래서 흔히 “뉴턴의 차분 근사판”으로 소개되지만, 역사는 거꾸로다. 두 번 틀린 추측에서 비례로 정답을 뽑는 이중 가정법(rule of double false position)은 고대 이집트 린드 파피루스까지 거슬러 올라가고, 뉴턴법보다 수천 년 앞선다.¹ 할선법은 이 오래된 비례 규칙을 반복으로 돌린 것이다.

같은 식을 대칭형으로 쓰면

$$x_{k+1} = \frac{x_{k-1}f_k - x_k f_{k-1}}{f_k - f_{k-1}}$$

이 되는데, 수치적으로는 쓰지 마라. 근 근처에서 분자의 두 항이 거의 같아 상쇄 오차가 커진다. 첫 번째 형태는 “현재 값 + 작은 보정”이라 부동소수점 연산의 반올림 오차가 보정량에만 묻는다.

3. 왜 하필 황금비인가

근을 $r$, 오차를 $e_k = x_k - r$ 로 두고 $f$ 를 $r$ 근처에서 테일러 급수로 펼치면, 단순근($f'(r)\ne0$)에서

$$e_{k+1} \approx C\,e_k\,e_{k-1}, \qquad C = \frac{f''(r)}{2f'(r)}$$

가 나온다. 뉴턴은 $e_{k+1}\approx C e_k^2$ 이다 — 할선법은 오차 하나를 한 스텝 묵은 오차로 바꿔 끼운 셈이다. 이제 $|e_{k+1}| \sim A|e_k|^p$ 꼴을 가정하고 대입하면 $|e_k|^p \sim |e_k|\,|e_k|^{1/p}$ 이 되어

$$p = 1 + \frac1p \quad\Longrightarrow\quad p^2 - p - 1 = 0 \quad\Longrightarrow\quad p = \frac{1+\sqrt5}{2}.$$

로그 오차 $\log|e_k|$ 가 피보나치 점화식 $a_{k+1}=a_k+a_{k-1}$ 을 따르기 때문이다. 피보나치 수열의 인접 비가 황금비로 가니 차수도 황금비다.²

3.1. 검산 — 차수를 직접 재 본다

$f(x)=x^2-2$, $x_0=1$, $x_1=2$ 에서 오차 $|x_k-\sqrt2|$ 를 찍었다(배정밀도).

$k$	0	1	2	3	4	5	6	7
오차	4.1e-1	5.9e-1	8.1e-2	1.4e-2	4.2e-4	2.1e-6	3.2e-10	2.2e-16

관측 차수 $\log(e_{k+1}/e_k)/\log(e_k/e_{k-1})$ 는 $k=3,4,5,6$ 에서 2.02, 1.50, 1.67, 1.61 로 출렁이며 1.618 로 들어간다. 출렁임 자체가 피보나치형 점화식의 특징이다 — 한 스텝 묵은 오차가 섞이니 단조롭게 수렴하지 않는다. 같은 문제에서 뉴턴($x_0=2$)은 4스텝에 1.6e-12 에 닿았지만 그 4스텝에 $f$ 와 $f'$ 를 각각 4번, 합쳐 8번 평가했다. 할선법은 초기 두 점 포함 9번 평가로 기계정밀도에 닿았다. 이 장난감에서는 비기는 셈인데, 다음 절에서 보듯 $f'$ 가 비싸면 판이 기운다.

4. 평가당 효율 — 뉴턴과의 진짜 비교

트라웁(Traub, 1964)과 오스트롭스키가 정리한 효율 지수(efficiency index)는 차수 $p$ 를 반복당 평가 횟수 $w$ 로 나눠 $p^{1/w}$ 로 잰다. 정밀도 자릿수가 평가 한 번당 몇 배로 불어나는가를 뜻한다.

방법	차수 $p$	반복당 평가 $w$	효율 지수 $p^{1/w}$
뉴턴 ($f'$ 가 $f$ 만큼 비쌀 때)	2	2	$\sqrt2 \approx 1.414$
할선법	1.618	1	1.618
뉴턴 ($f'$ 가 공짜일 때)	2	1	2

도함수를 해석적으로 거의 공짜로 얻을 수 있으면 뉴턴이 이긴다. 그러나 $f$ 가 블랙박스 시뮬레이터 — 예컨대 “입구 속도를 넣으면 CFD를 한 바퀴 돌려 출구 압력을 내놓는” 함수 — 라서 $f'$ 를 수치미분으로 얻어야 한다면 뉴턴은 평가 2회짜리가 되고 할선법이 깔끔하게 앞선다. 사격법으로 경계값 문제를 풀 때 바깥 루프에 할선법이 국룰로 붙는 이유다.

5. 약점 — 근을 가두지 않는다

할선법은 국소 수렴만 보장한다. 초기 두 점이 근에서 멀면 할선이 엉뚱한 방향으로 날아가고, $f_k \approx f_{k-1}$ 이면 분모가 0 에 가까워 반복점이 무한대로 튄다. 근을 낀 구간을 유지하는 이분법과 달리, 할선법의 두 점은 근의 같은 쪽에 있어도 상관하지 않는다.

처방은 대략 세 갈래다.

• 가위치법(regula falsi, false position) — 할선법과 공식은 같되, 새 점을 부호가 반대인 쪽 점과 짝지어 항상 근을 가둔다. 안전하지만 한쪽 끝점이 고정돼 버리는 경우가 잦아 1차 수렴으로 주저앉는다. 일리노이 변형처럼 고정된 쪽의 함수값을 반으로 깎아 주면 초선형이 돌아온다.
• 브렌트 방법(Brent, 1973) — 이분법·할선법·역 이차 보간을 섞어, 빠른 스텝이 구간 밖으로 나가거나 충분히 줄지 않으면 이분법으로 후퇴한다. 반드시 수렴하고 최악의 평가 횟수에 상한(대략 이분법 횟수의 제곱)이 있으며 평소엔 초선형이다. SciPy의 brentq, MATLAB의 fzero 가 이 계열이다.
• 멈춤 판정을 두 개로 — $|x_{k+1}-x_k|$ 와 $|f_{k+1}|$ 를 함께 본다. 할선법은 분모가 작아지는 정체 구간에서 $x$ 가 거의 안 움직이며 “수렴한 척”을 할 수 있다.

중근($f'(r)=0$)에서는 뉴턴과 마찬가지로 차수가 1로 떨어진다. 중근에서의 할선법 선형 수렴률은 상수가 황금비의 역수 $1/\varphi\approx0.618$ 이 되는 것으로 알려져 있는데, 실무에선 이 상황 자체를 “근 찾기 대신 극값 찾기 문제로 바꾸라”는 신호로 읽는 편이 낫다.

6. 다변수로 — 할선 조건

$n$ 차원 $\mathbf F(\mathbf x)=\mathbf 0$ 에서 할선법의 정신을 살리려면 야코비안 근사 $B$ 가 마지막 관측을 재현해야 한다.

$$B_{k+1}(\mathbf x_{k+1}-\mathbf x_k) = \mathbf F(\mathbf x_{k+1}) - \mathbf F(\mathbf x_k).$$

이게 할선 조건이다. 1차원에선 이 식 하나가 기울기를 유일하게 정하지만, $n$ 차원에선 식 $n$ 개로 미지수 $n^2$ 개를 정해야 해서 해가 무수히 많다. 그중 “기존 $B_k$ 에서 가장 덜 바뀌는 것”을 고른 것이 브로이던 방법이고, 최적화 쪽에서 헤시안의 대칭·양정치성까지 지키게 고른 것이 BFGS 등의 준-뉴턴법이다. 이 갱신이 랭크-1 이라서 역행렬을 셔먼-모리슨 공식으로 $O(n^2)$ 에 고칠 수 있다는 게 다변수 할선법이 실용적인 이유다.

할선 조건을 최근 $m$ 개 관측 전부에 대해 걸면 다중 할선 방법이 되고, 이것이 앤더슨 가속과 같은 족속임이 알려져 있다. 1차원 할선법 하나에서 준뉴턴·가속 기법 일가가 다 뻗어 나온 셈이다.³

7. 실무에서 남는 것

• 초기 두 점은 가깝게, 그러나 너무 가깝지 않게. 둘이 거의 같으면 첫 할선 기울기가 반올림 오차에 먹힌다. 흔한 관행은 $x_1 = x_0(1+10^{-4}) + 10^{-4}$ 정도의 상대·절대 섭동이다(SciPy newton 이 도함수 없이 호출되면 이런 식으로 두 번째 점을 만든다).
• 근을 가둘 수 있으면 가둬라. 부호가 바뀌는 구간을 알면 그냥 브렌트를 쓴다. 할선법 단독은 구간을 모를 때, 혹은 근 근처에서 좋은 추측이 이미 있을 때의 마무리 투수다.
• 함수가 잡음을 품고 있으면 조심. 반복 솔버의 수렴 허용오차만큼 $f$ 에 잡음이 끼어 있으면, 두 점이 가까워질수록 할선 기울기가 잡음에 휘둘린다. $|f|$ 가 잡음 수준에 닿으면 멈추는 게 맞다.

8. 관련 문서

• 뉴턴-랩슨법 · 브로이던 방법 · 준-뉴턴법 · 앤더슨 가속
• 이분법 · 역 이차 보간 · 브렌트 방법 · 사격법
• 수치미분 · 테일러 급수 · 부동소수점 연산 · 셔먼-모리슨 공식

9. Footnotes

1. 파파콘스탄티누·타피아(2013)는 “할선법은 뉴턴법에서 나왔다”는 통념이 틀렸다고 정색하고 3500년치 족보를 캤다. 뉴턴 입장에선 자기 이름이 붙은 방법보다 선배가 수천 살 많다는 걸 알게 된 셈. ↩

2. 수치해석 시험에서 피보나치가 나오면 대개 이 문제거나 황금분할 탐색이다. 둘 다 “왜 하필 1.618이냐”를 묻는 국룰 문제. ↩

3. 도함수를 안 구하겠다는 게으름 하나로 이만한 가문을 일궜다. 게으름은 수치해석의 미덕이라는 증거로 자주 인용된다(인용자: 본 문서). ↩