브렌트 방법

1. 개요

브렌트 방법 Brent's Method
푸는 것	부호가 바뀌는 구간 안의 f(x) = 0
재료	이분법 + 할선법 + 역 이차 보간
보장	항상 수렴, 평가 횟수 상한 ≈ (이분법 횟수)²
평소 속도	단순근에서 초선형
구현	ZEROIN · MATLAB fzero · SciPy brentq

빠른 놈은 못 믿고, 믿을 만한 놈은 느리다. 그래서 둘 다 고용했다.

브렌트 방법(Brent’s method)은 부호가 바뀌는 구간 안에서 근을 찾을 때, 빠르지만 불안한 역 이차 보간·할선법 스텝을 먼저 시도하고, 그 스텝이 구간 안에 제대로 떨어지지 않거나 충분히 줄지 않으면 이분법으로 후퇴하는 혼합 근 찾기 알고리즘이다. 리처드 브렌트(Richard Brent)가 1971년 논문과 1973년 책에서 정리했고, 데커(Dekker, 1969)의 이분법+할선법 혼합을 개량한 것이다.

결과적으로 “근을 가두는 한 반드시 수렴”이라는 이분법의 보장과, 매끄러운 함수에서 초선형으로 끝나는 보간법의 속도를 함께 얻는다. 스칼라 근 찾기의 사실상 표준이라, 구간을 줄 수 있다면 일단 이걸 부르는 게 국룰이다.

2. 데커에서 브렌트로

데커의 방법은 세 점을 유지한다.

• $b$ — 지금까지의 최선 추정(함수값의 절댓값이 가장 작은 점)
• $c$ — $b$ 와 부호가 반대인 대척점(contrapoint). $[b, c]$ 가 항상 근을 가둔다.
• $a$ — 직전의 $b$

매 스텝 $a, b$ 로 할선 스텝을 계산하고, 그 결과가 $b$ 와 $[b,c]$ 의 중점 사이에 있으면 받고, 아니면 중점(이분법)을 쓴다. 그럴듯하지만 함정이 있다. 할선 스텝이 매번 구간 안쪽에 떨어지기는 하는데 아주 조금씩만 움직이는 함수가 있다. 그러면 이분법으로 한 번도 안 내려가면서 허용오차 크기의 걸음을 수없이 반복해, 최악에는 평가 횟수가 $(b-a)/\delta$ 에 비례하게 된다. 이분법보다 기하급수적으로 느려질 수 있다는 뜻이다.

브렌트의 개량은 두 가지다.

1. 역 이차 보간 추가. 세 점의 함수값이 서로 다르면 할선 대신 역 이차 보간을 쓴다. 점 $a, b, c$ 가 이미 손에 있으니 추가 평가 없이 차수만 올라간다.

2. “충분히 줄었는가” 조건. 보간 스텝 $d$ 는 다음 두 조건을 모두 만족할 때만 받는다.

   • 새 점이 $b$ 에서 $c$ 쪽으로 구간의 3/4 안쪽에 떨어질 것
   • $|d|$ 가 두 스텝 전 걸음의 절반보다 작을 것

   둘 중 하나라도 어기면 이분법 스텝을 쓴다. 두 번째 조건이 핵심이다. 보간 스텝이 연달아 쪼잔하게 굴면 걸음 크기가 두 스텝마다 반 이상 줄어야 하므로, 오래 버티지 못하고 이분법이 끼어든다.

여기에 허용오차 $\text{tol}_1 = 2\epsilon|b| + \tfrac12 \text{tol}$ 보다 작은 걸음은 강제로 $\text{tol}_1$ 만큼 걷게 해, 반올림 수준에서 제자리걸음하는 것을 막는다($\epsilon$ 은 기계 엡실론).

이렇게 해서 브렌트는 평가 횟수가 이분법 횟수 $N$ 에 대해 대략 $N^2$ 을 넘지 않음을 보였다. 데커의 $(b-a)/\delta$ 에 비하면 천지 차이지만, 이분법보다 느려질 수 있다는 사실 자체는 남아 있다 — 아래 검산 참고.

3. 한 반복의 흐름

포사이스·말콤·몰러(1977)의 교과서에 실린 Fortran 판 ZEROIN — MATLAB fzero 의 바탕 — 계열 구현의 한 반복을 말로 풀면 이렇다.

1. $f(b)$ 와 $f(c)$ 의 부호가 같으면 $c \leftarrow a$ 로 대척점을 다시 잡는다.
2. $|f(c)| < |f(b)|$ 면 $b$ 와 $c$ 를 바꿔 $b$ 가 항상 최선이 되게 한다.
3. 중점까지 거리 $m = (c-b)/2$ 가 $\text{tol}_1$ 이하이거나 $f(b)=0$ 이면 끝.
4. 직전 걸음이 충분히 컸고 $|f(a)| > |f(b)|$ 면 보간을 시도한다 — $a = c$ 면 할선, 아니면 역 이차 보간.
5. 위의 두 수락 조건을 보고 보간 스텝 또는 이분 스텝 $m$ 을 고른다.
6. $a \leftarrow b$ 로 밀고, $b$ 를 걸음만큼 옮겨 $f(b)$ 를 새로 계산한다(반복당 평가 1회).

구현이 짧은 만큼 조건 하나하나가 의미가 있어서, “더 깔끔하게” 다시 쓰다가 보장을 깨는 사고가 잦다. 포팅할 때는 원본 ALGOL/Fortran 의 부등호까지 그대로 옮기는 게 정답이다.¹

3.1. 검산 — 평소와 최악

ZEROIN 을 그대로 옮긴 구현으로, 허용오차 $10^{-12}$ 에서 함수 평가 횟수를 셌다(이분법은 SciPy bisect 의 집계, 양 끝점 평가 포함).

함수 · 구간	브렌트	이분법
$x^3-2x-5$, $[2,3]$	8	42
$\cos x - x$, $[0,1]$	8	42
$x^2-2$, $[1,2]$	8	42
$(x-0.3)^9$, $[-1,\ 1.7]$	112	44

매끄러운 단순근에서는 다섯 배 넘게 빠르다. 그런데 근에서 극단적으로 평평한 $(x-0.3)^9$ 에서는 보간 스텝이 계속 쪼잔하게 굴다 이분법에 밀려나기를 반복해 평가가 112회, 이분법(44회)의 2.5배가 됐다(그중 이분 스텝이 32회). 알레펠트·포트라·시의 TOMS 748 도 같은 함수에서 109회로 사정이 비슷했다.

실무 함정 하나. SciPy brentq 는 기본 maxiter=100 이라, 위 마지막 함수를 기본값으로 부르면 RuntimeError: Failed to converge after 100 iterations 를 낸다. 알고리즘이 틀린 게 아니라 상한이 짧은 것이니, 중근에 가까운 함수를 다룰 땐 maxiter 를 늘리거나, 애초에 $f$ 대신 $\operatorname{sign}(f)\,|f|^{1/9}$ 같은 변환으로 근을 단순근으로 펴 주는 게 낫다.

4. 이름이 같은 다른 것들

브렌트의 1973년 책 제목이 「도함수 없는 최소화 알고리즘」이라, 같은 이름의 알고리즘이 여럿이다.

• 브렌트 최소화(localmin, fmin). 단봉함수의 최솟값을 황금분할 탐색법과 포물선 보간으로 찾는다. 구조가 근 찾기판과 판박이 — 빠른 보간을 시도하고 안 되면 안전한 황금분할로 후퇴 — 라서 이름을 공유한다. SciPy 에서 brent/minimize_scalar(method='brent') 는 이쪽이고, 근 찾기는 brentq 다. 헷갈려서 최솟값 대신 근을 찾는 사고가 자주 난다.
• brenth. 역 이차 보간 대신 쌍곡선 외삽을 쓰는 버스·데커(Bus & Dekker, 1975)의 변종. 평가 횟수는 대개 비슷하다.
• praxis. 같은 책에 실린 다차원 도함수 없는 최소화(파월 방법 개량). 근 찾기와는 무관하다.

5. 언제 브렌트가 아닌가

• 구간을 모를 때. 부호 변화 구간이 없으면 시작을 못 한다. 좋은 초기 추측만 있다면 뉴턴-랩슨법이나 할선법으로 가고, 구간을 찾는 별도 단계(구간을 두 배씩 넓혀 가며 부호 변화를 찾는 bracketing)를 앞에 둔다.
• 도함수가 싸게 나올 때. 뉴턴 스텝을 안전장치 안에 넣은 “안전한 뉴턴”(rtsafe 류)이 더 적은 평가로 끝난다.
• 다변수. 브렌트 방법은 본질적으로 1차원이다. 구간 가두기라는 개념 자체가 고차원에서 성립하지 않기 때문에, 연립 비선형 방정식은 브로이던 방법·뉴턴-크리로프법 같은 다른 계열의 몫이다.
• 잡음 섞인 $f$. 보간 스텝은 잡음에 휘둘린다. 부호만 믿을 수 있으면 이분법이 더 정직하고, 브렌트는 결국 이분 스텝 위주로 굴러가며 이분법보다 약간 손해를 본다.

시뮬레이션 쪽에선 사격법의 초기 기울기 찾기, 상태방정식에서 온도·압력 역산, 이벤트 탐지(적분 중 $g(t)=0$ 이 되는 시각 찾기) 같은 1차원 하위 문제에서 거의 자동으로 불려 나온다.²

6. 관련 문서

• 이분법 · 할선법 · 역 이차 보간 · 뉴턴-랩슨법
• 황금분할 탐색법 · 브로이던 방법 · 뉴턴-크리로프법
• 사격법 · 부동소수점 연산 · 가위치법 · 머신 엡실론

7. Footnotes

1. “이 조건문 왜 있지? 지워도 테스트 다 통과하는데”는 수치 라이브러리 포팅의 유명한 마지막 유언이다. 테스트 함수가 착하면 안전장치는 영원히 안 불린다. ↩

2. 상미분방정식 적분기가 “공이 바닥에 닿는 순간”을 찾는 이벤트 기능도 대개 스텝 안의 보간 다항식에 브렌트류 근 찾기를 돌린 것이다. 물리 엔진 밖에서 몰래 일하는 근 찾기 노동자. ↩