이분법 근 찾기 계산기

근에서의 f(x) 값	-0.0000000000000263
사용된 반복 횟수	50
방법	이분법 (구간 반분법)

이분법이란?

이분법은 연속함수 f(x)의 근, 즉 f(x) = 0이 되는 x 값을 찾는 가장 오래되고 안정적인 방법 중 하나입니다. 함수의 부호가 바뀌는 구간 [a, b]에서 출발해, 그 구간을 절반으로 계속 나누면서 여전히 근을 품고 있는 쪽 절반만 남기는 방식으로 작동합니다. 매 단계마다 부호 변화가 유지되기 때문에, f가 연속이고 f(a)와 f(b)의 부호가 서로 반대이기만 하면 반드시 수렴하는 것이 보장됩니다. 이 계산기는 무차원의 실함수라면 모두 처리할 수 있으며, 삼각함수는 라디안을 기준으로 계산합니다.

점 a와 b 사이에서 x축을 지나는 연속 곡선, 중점 표시 — 이분법은 f(a)와 f(b)의 부호가 반대인 구간에 근을 가둡니다.

계산기 사용법

f(x) 칸에 x를 변수로 사용해 함수를 입력하세요(예: x-cos(x), x^2-2, exp(x)-3). 근이 두 끝점 사이에 오도록 하한 a와 상한 b를 설정하면 됩니다. 이때 $f(a)\cdot f(b)$의 값이 0 이하여야 합니다. 최대 반복 횟수 n과 표시할 자릿수를 고른 뒤 계산하면, 근의 근삿값과 그 지점에서의 함숫값(0에 가까워야 합니다), 그리고 실제로 필요했던 반복 횟수를 알려줍니다.

계산 공식

각 단계에서 근의 추정값은 구간의 중점 $x_n = (a_n + b_n) / 2$입니다.

$$c = \frac{a + b}{2} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} &\text{if } f(a)\cdot f(c) < 0 \Rightarrow b \leftarrow c \\ &\text{else} \Rightarrow a \leftarrow c \\ &\text{repeat up to } n \text{ times} \end{aligned} \right.$$

$|f(x_n)|$이 허용 오차보다 작아지면 $x_n$을 근으로 받아들입니다. 그렇지 않으면 부호 변화가 남아 있는 쪽 절반을 택합니다. 즉, $f(a_n)\cdot f(x_n) > 0$이면 근은 오른쪽에 있으므로 $a = x_n$으로, 그렇지 않으면 왼쪽에 있으므로 $b = x_n$으로 갱신합니다. 구간 폭은 $(b-a)/2^n$으로 줄어들기 때문에 수렴은 선형이며, 한 단계마다 대략 정확한 이진 자릿수 하나씩을 얻는 셈입니다.

구간을 반복적으로 절반으로 줄여 근에 수렴하는 모습 — 각 반복마다 구간을 절반으로 나누고 근을 포함한 쪽을 유지합니다.

예제 풀이

구간 $[-10, 10]$에서 $f(x) = x - \cos(x)$를 생각해 봅시다. $f(-10) \approx -10.84$(음수), $f(10) \approx 10.84$(양수)이므로 근이 구간 안에 갇혀 있습니다. 구간을 반복해서 절반으로 나누면 $x \approx 0.7390851332151607$로 수렴하는데, 이는 $x = \cos x$를 만족하는 유명한 도티 수(Dottie number)이며 이때 $f(x)$는 사실상 0이 됩니다.

이분법을 손으로 하는 방법

이분법은 근이 있는 것으로 알려진 구간을 반복적으로 이등분하여 $f(x)=0$의 근을 찾습니다. 이것은 중간값 정리에 의존합니다: $f$가 $[a,b]$에서 연속이고 $f(a)$와 $f(b)$가 반대 부호를 가지면, 근이 반드시 그 사이에 있어야 합니다.

괄호를 확인하십시오. $f(a)\cdot f(b)<0$임을 확인합니다. 곱이 양수이면 구간이 근을 포함한다고 보장되지 않으므로 다른 $[a,b]$를 선택하십시오.
중점을 계산하십시오. $m=\dfrac{a+b}{2}$.
함수를 평가하십시오. $f(m)$을 구합니다. $f(m)=0$이거나 허용 범위 내에 있으면 $m$이 근이고 멈춥니다.
부호에 따라 끝점을 바꾸십시오. $f(a)\cdot f(m)<0$이면 근은 $[a,m]$에 있으므로 $b\leftarrow m$을 설정합니다. 그렇지 않으면 근은 $[m,b]$에 있으므로 $a\leftarrow m$을 설정합니다.
반복 $|b-a|<\text{허용값}$ 또는 $|f(m)|<\text{허용값}$이 될 때까지, 또는 최대 반복 횟수에 도달할 때까지 2단계부터 4단계까지 반복합니다.

예: $f(x)=x^{3}-x-2$를 $[1,2]$에서 계산합니다. 확인: $f(1)=-2$, $f(2)=4$, 곱 $<0$ — 괄호가 유효합니다.

반복	a	b	m=(a+b)/2	f(m)	새 구간
1	1.0000	2.0000	1.5000	−0.125	[1.5, 2]
2	1.5000	2.0000	1.7500	1.6094	[1.5, 1.75]
3	1.5000	1.7500	1.6250	0.6660	[1.5, 1.625]
4	1.5000	1.6250	1.5625	0.2522	[1.5, 1.5625]
5	1.5000	1.5625	1.5313	0.0591	[1.5, 1.5313]
6	1.5000	1.5313	1.5156	−0.0340	[1.5156, 1.5313]

더 많은 반복 후 구간이 참 근인 1.521380으로 수렴합니다. 이는 3차 방정식 $x^{3}-x-2=0$의 유일한 실수 근이기도 하며, 직접 풀이기로 찾은 1.521380입니다.

반복 횟수 대 허용값 및 구간 너비

각 이분 단계에서 구간을 이등분하므로 $n$번 반복 후 괄호 너비는 $(b-a)/2^{\,n}$입니다. 근의 위치에 대해 허용값 $\text{허용값}$에 도달하려면 대략

$$n \approx \log_2\!\left(\frac{b-a}{\text{허용값}}\right).$$

횟수는 정밀도의 로그와만 증가하므로 매우 엄격한 허용값도 상대적으로 적은 단계만 필요합니다. 표는 여러 조합에 대해 반올림된 반복 횟수를 보여줍니다.

초기 너비 $b-a$	목표 허용값	$\log_2((b-a)/\text{허용값})$	필요한 반복 횟수
1	$10^{-3}$	9.97	10
1	$10^{-6}$	19.93	20
1	$10^{-10}$	33.22	34
10	$10^{-6}$	23.25	24
20	$10^{-6}$	24.25	25
100	$10^{-8}$	33.22	34
0.5	$10^{-12}$	38.86	39

예를 들어, 너비 20인 괄호를 $10^{-6}$로 정제하려면 $\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=$ 25번의 반복이 필요하고, 너비 1인 괄호를 $10^{-10}$로 정제하려면 $\lceil 33.22\rceil=$ 34번이 필요합니다. 시작 너비를 이등분하면 정확히 한 번의 반복을 절약합니다. 정밀도를 제곱하면(소수점 한 자리 추가) 약 3.3번의 반복이 소요됩니다.

주요 용어

근. 함수가 0인 값 $x^{*}$, 즉 $f(x^{*})=0$. 영점 또는 방정식의 해라고도 합니다.
괄호 / 구간 $[a,b]$. 근을 포함한다고 생각되는 끝점 쌍입니다. 이분법의 경우 부호 변화 조건을 만족해야 합니다.
부호 변화. 조건 $f(a)\cdot f(b)<0$, 즉 $f$가 끝점에서 반대 부호를 취하는 것을 의미합니다. 연속 $f$의 경우 이것은 그 사이에 최소한 하나의 근이 있음을 보장합니다(중간값 정리).
중점. 현재 구간의 중심, $m=(a+b)/2$. 각 단계에서 이 점을 검사하고 근을 포함할 수 없는 절반을 버립니다.
허용값. 반복을 멈추는 정확도 목표로, 구간 너비 $|b-a|$ 또는 잔차 $|f(m)|$에 적용됩니다.
수렴(선형). 이분법은 선형으로 수렴합니다: 오차는 각 단계에서 대략 이등분됩니다(오차 $\le (b-a)/2^{n}$), 일정하지만 가속하지 않는 진행을 제공합니다 — 반복당 약 1개의 추가 올바른 이진 자릿수입니다.
반복. 중점 계산, 함수 평가, 끝점 업데이트의 한 전체 주기입니다. 반복 횟수는 최대 반복 설정으로 제한됩니다.