이등분법

수학에서, 이등분법은 반대 부호가 있는 두 개의 값을 알고 있는 모든 연속 함수에 적용되는 루트 찾기 방법입니다.이 메서드는 이러한 값으로 정의된 간격을 반복하여 이등분하고 함수가 부호를 변경할 서브인터벌을 선택하는 것으로 구성됩니다.따라서 루트가 포함되어 있어야 합니다.이것은 매우 간단하고 견고한 방법이지만, 비교적 느리기도 합니다.이 때문에, 해답에 대한 대략적인 근사치를 구하는 데 자주 사용되며, 이 근사치는 보다 빠른 수렴 방법의 ^[1]시작점으로 사용된다.이 방법은 간격 분할법,^[2][4] 이진 검색법 ^[3]또는 이분법이라고도 합니다.

다항식의 경우, 구간에서 근의 존재를 테스트하기 위한 보다 정교한 방법이 존재한다.이를 통해 이등분법을 효율적인 알고리즘으로 확장하여 다항식의 모든 실제 루트를 찾을 수 있습니다. 실제 루트 분리를 참조하십시오.

방법

이 방법은 실수 변수 x에 대한 방정식 f(x) = 0을 수치적으로 푸는 데 적용할 수 있다. 여기서 f는 구간 [a, b]에 정의된 연속 함수이며 f(a)와 f(b)는 반대 부호를 가진다.이 경우 a와 b는 중간값 정리에 의해 연속함수 f는 간격(a, b)에 적어도 1개의 루트를 가져야 하므로 루트를 괄호로 묶는다고 한다.

각 단계에서 이 방법은 간격의 중간점 c = (a+b) / 2와 그 점에서의 함수 f(c) 값을 계산함으로써 간격을 두 부분/부분으로 나눈다.c 자체가 루트(가능성이 매우 낮지만 가능성이 있음)가 아닌 한 f(a)와 f(c)는 반대 부호가 있고 루트는 괄호, f(c)와 f(b)는 반대 부호가 있고 ^[5]루트는 괄호 중 하나입니다.이 메서드는 다음 단계에서 사용할 새로운 인터벌로 브래킷이 보증된 서브인터벌을 선택합니다.이와 같이 f의 0을 포함하는 간격은 각 단계에서 폭이 50% 감소합니다.이 과정은 간격이 충분히 작아질 때까지 계속됩니다.

명시적으로 f(a)와 f(c)의 부호가 반대일 경우 b의 새로운 값으로 c를 설정하고 f(b)와 f(c)의 부호가 반대일 경우 c를 새로운 a로 설정한다(f(c)=0일 경우 c를 해로 간주하여 프로세스를 정지한다).두 경우 모두 새로운 f(a)와 f(b)는 반대 부호를 가지므로 이 방법은 이 작은 ^[6]간격에 적용할 수 있다.

반복 태스크

이 방법의 입력은 연속 함수 f, 간격 [a, b] 및 함수 값 f(a) 및 f(b)입니다.함수 값은 반대 부호입니다(간격 내에 적어도1개의 제로 교차가 있습니다).각 반복은 다음 단계를 수행합니다.

1. 구간의 중간점인 c를 계산합니다. c =a + b/2 입니다.
2. 중간점 f(c)에서 함수 값을 계산합니다.
3. 수렴이 만족스러운 경우(즉, c - a가 충분히 작거나 f(c)가 충분히 작음)에는 c를 반환하고 반복을 중지한다.
4. f(c)의 부호를 검사하고 (a, f(a)) 또는 (b, f(b))를 (c, f(c))로 교체하여 새로운 간격 내에 제로 교차가 발생하도록 한다.

컴퓨터에 이 방법을 구현하면 한정된 정밀도에 문제가 있을 수 있으므로 종종 추가 수렴 테스트나 반복 횟수에 제한이 있습니다.f는 연속이지만 유한 정밀도는 함수 값이 0이 되는 것을 방지할 수 있습니다.예를 들어, f(x) = x - θ를 고려합니다. 0을 주는 x의 유한한 표현은 존재하지 않습니다.또한 a와 b의 차이는 부동소수점 정밀도에 의해 제한된다.즉, a와 b의 차이가 감소함에 따라 [a, b]의 중간점은 a 또는 b 중 하나의 부동소수점 정밀도와 수치적으로 동일해진다.

알고리즘.

메서드는 다음과 ^[7]같이 의사 코드로 기술할 수 있습니다.

INPUT:기능 f, 끝점에 가치를 두는, b, 관용 이착륙, 최대 반복 NMAX 조건:<>b, f(를)<0과 f(b)<>를 사용하여 0또는 f(를)<>를 사용하여 0과 f(b)<>이착륙 N보다 덜 ← 1에서 0출력:값 f())의 뿌리와)0인 반면 N≤ NMAX니//한계 반복 무한 루프 c←을 막기 위해(a +b)/2 새로운 m//f(c) = 0 또는 (b – a)/2 < TOL then // 솔루션이 출력(c) N + 1 // 부호(f) = 부호(f(a)인 경우 스텝 카운터를 증가시키면 a ← c else b ← // 출력("메서드 실패")이 최대 스텝 수를 초과하는 동안 새로운 인터벌 끝입니다. //

예:다항식의 근 찾기

이등분법이 다항식의 근을 찾는 데 사용된다고 가정하자.

${\displaystyle f(x)=x^{3}-x-2,}$

먼저 f$a)\displaystyle$ f$(a)$와 $f{\displaystyle }$$)\displaystyle$ f$(b)$의 부호가 반대인 두 $개$의 $숫자$를 찾아야 합니다$.$위 기능의 경우 a ${\displaystyle =}$ ${\displaystyle 1}${$displaystyle$ a$=1$}$$및 $b{\displaystyle }$ ${\displaystyle =}$ {$displaystyle$ b=$2}$는 $다음$과 같이 이 기준을 충족합니다.

${\displaystyle f(1)=(1)^{3}-(1)-2=-2}$

그리고.

${\displaystyle f(2)=(2)^{3}-(2)-2=+4,}$

함수는 연속적이므로 [1, 2] 간격 내에 루트가 있어야 합니다.

첫 번째 반복에서는 루트를 괄호로 묶는 간격의 끝점은 ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ $({displaystyle a_{1$}=$1$$}$ $및{\displaystyle {}_{}}$ ${\displaystyle {b\mathrm{}}_{}}$ 1 $=$ $({displaystyle b_{1$}=$2$이므로 중간점은 다음과 같습니다.

${\displaystyle c_{1}=black {2+1}{2}}=1.5}$

중간점의 함수 값은 $f{\displaystyle }$( ${\displaystyle {}_{}{1\mathrm{}}_{}}$) ${\displaystyle =}$ ( 1.${\displaystyle 5{}^{}}$)${\displaystyle {}^{}{3\mathrm{}}^{}}$- ( 1.${\displaystyle 5}$) - ${\displaystyle 2}$ $=$ -${{$$displaystyle$$f(c_${1}=($1.5)^3$} - ($1$5$)-2$=-0.125입니다${\displaystyle .}$ f (${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}${$displaystyle$ f$(c_{1})$는 음의 $디스플레이 =$이기 $때문$입니다.$)$ {$displaystyle$ f$(a)}$와 f$)$ {$displaystyle$ f$(b)}$의 부호는 반대입니다.$이$ 상태가 계속됨에 따라$$$a$와$$b$사이$의 간격은 점점 더 작아지고 함수의 루트에 수렴됩니다.다음 표에서 이 문제를 확인하십시오.

반복	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

13회 반복하면 다항식의 근인 약 1.521에 수렴이 있음을 알 수 있습니다.

분석.

이 방법은 f가 간격 [a, b]의 연속 함수이고 f(a)와 f(b)가 반대 부호를 갖는 경우 f의 루트로 수렴되는 것이 보증됩니다.절대 오차는 각 단계에서 절반으로 줄어들기 때문에 방법은 선형적으로 수렴됩니다.구체적으로₁, c = a+b/2가 초기 간격의 중간점이고_n, c가 n번째 단계에서 간격의 중간점이라면, c와 솔루션 c 사이의 차이는 다음과_n 같이 제한된다^[8].

$({displaystyle c_{n}-c \leq {frac { b-a }{2^{n}}).}$

이 공식을 사용하여 이등분법이 특정 공차 내에서 루트에 수렴해야 하는 반복 횟수의 상한을 미리 결정할 수 있습니다.필요한 허용 오차 θ(즉, 최대 θ가 보장되는 오차)를 달성하기 위해 필요한 반복 횟수 n은 다음과 같이 제한된다.

$\displaystyle n\leq n_{1/2}\equiv \left\lceil \log _{2}\frac {\silon _{0}}{\silon }\right\rceil,}$

여기서 초기 괄호 크기 ${\displaystyle {ϵ\mathrm{}}_{}}$ 0 $=$ - ${\displaystyle a}$ \$displaystyle$\$silon$_ { 0 } = $b-a$} 및$$ 필요한 괄호 크기 $ϵ{\displaystyle {ϵ\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$. {$displaystyle$\ $silon \ leq$ \ $silon$_ { 0$$} 。$$ 이등분법을 사용하는 주된 동기는 연속함수 집합에서 최악의 경우 n회 ^[9]미만의_1/2$절대오차$를 갖는 솔루션$$ c에 대한 추정치_n $c$를 생성할 수 있는 다른 방법이 없기 $때문입니다.$이는 함수 f와 근원 ^[9][10]근방의 함수 동작에 관한 몇 가지 일반적인 가정에서도 해당된다.

그러나 이등분 방법은 절대 오차 기준에서 최악의 경우 성능과 관련하여 최적화되었음에도 불구하고 표준 가정 하의 평균 성능 및 점근적 ^[13]성능과 관련하여 최적화되지 않았다.이등분법(secant method, Ridders' method, Brent's method 등)의 일반적인 대체 방법은 일반적으로 최악의 경우 성능을 균형 있게 조정하여 루트에 대한 높은 수렴 순서를 달성하기 때문에 더 나은 성능을 발휘합니다.또, 이등분법의 엄격한 개선을 ^[13][14]ITP법에 의한 최악의 경우 퍼포먼스와의 트레이드오프 없이 높은 컨버전스로 달성할 수 있다.

「 」를 참조해 주세요.

• 이진 검색 알고리즘
• 르메르-슈르 알고리즘, 복소 평면에서의 이분법의 일반화
• 내포 구간

레퍼런스

• Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm", Numerical Analysis (3rd ed.), PWS Publishers, ISBN 0-87150-857-5

추가 정보

• Corliss, George (1977), "Which root does the bisection algorithm find?", SIAM Review, 19 (2): 325–327, doi:10.1137/1019044, ISSN 1095-7200
• Kaw, Autar; Kalu, Egwu (2008), Numerical Methods with Applications (1st ed.), archived from the original on 2009-04-13

외부 링크

• Weisstein, Eric W. "Bisection". MathWorld.
• 전체론적 수치법 연구소의 이등분법 노트, PPT, Mathcad, Maple, Matlab, Mathmatica