이분법 - 정의, 알고리즘 및 예

이분법이란 무엇입니까?

이분법(Bisection Method)은 다항 방정식의 근을 찾는 기본적인 수치 해법 중 하나입니다. 그것 brackets 방정식의 근이 놓여 있는 간격을 구하고 근을 찾을 때까지 각 반복에서 방정식을 반으로 세분화합니다. 따라서 이등분법을 브라케팅법이라고도 합니다.

그러나 작동 메커니즘이 이진 검색 알고리즘과 유사하므로 이분법 방법은 이진 검색 방법, 절반 방법 또는 이분법이라고도 합니다. 이는 주로 중간가치정리(Intermediate value theorem)에 기초합니다.

방정식의 근 찾기

이 예에서는 독립 변수가 하나인 방정식만 고려합니다. 선형이거나 비선형일 수 있습니다. 선형 방정식은 직선의 그래프를 나타내는 데 사용되는 반면, 비선형 방정식은 곡선을 나타내는 데 사용됩니다.

방정식의 근은 방정식을 만족하는 독립변수의 값을 의미합니다. 예: 방정식의 근 f(x)= 4-x2 = 0은 2입니다. 왜냐하면 f(2) = 4-2이기 때문입니다.2 = 0.

f(x)를 실수 연속 함수로 생각해 봅시다. 중간값 정리에 따르면 f(a)f(b) < 0인 경우 방정식 f(x)=0은 a와 b 사이에 최소한 하나의 근을 갖습니다. 함수 f(x)는 근 "c"를 갖습니다. a와 b 사이.

방정식의 근 찾기

이등분 방법의 그래픽 표현

더 폴로wing 그래프는 이분법의 작동 메커니즘을 나타냅니다. 그래프에서 방정식의 근이 빨간색으로 표시되어 있음을 알 수 있습니다.

우선 첫째로:

  • 우리는 먼저 두 가지 초기 추측을 했습니다.1 그리고 b1, f(a1)f(b)1) < 0. 중간값 정리에 따르면 근은 [a1, b1].
  • 우리는 a의 중간점을 찾을 수 있다.1 그리고 b1, 그건 b야2. 따라서 초기 간격은 이제 [a1, b2] 왜냐하면 f(a1)f(b)2) < 0.
  • 같은 방식으로 근사해를 찾을 때까지 간격이 줄어듭니다.

이등분 방법의 그래픽 표현

이분법 알고리즘

방정식 f(x)=0의 근을 찾기 위해 이분법 알고리즘을 적용하는 단계는 다음과 같습니다.

단계 1) 초기 추측 a, b 및 공차율 e를 선택합니다.

단계 2) f(a)f(b) >=0이면 근은 이 구간에 있지 않습니다. 따라서 해결책이 없습니다.

단계 3) 중간점 찾기, c = (a+b)/2

(i) 중점 f(c)의 함수 값이 0이면 c는 근입니다. 5단계로 이동합니다.
(ii) f(a)f(c) < 0이면 근은 a와 c 사이에 있습니다. 그런 다음 a = a, b = c로 설정합니다.
(iii) 그렇지 않으면 a = c, b = b로 설정됩니다.

단계 4) 절대 오차가 공차율보다 높거나 (ba) > e인 경우 3단계로 이동합니다.

단계 5) c를 대략적인 근으로 표시합니다.

이분법 알고리즘의 예를 살펴보겠습니다.
우리는 폴로의 뿌리를 찾아야 한다wing 이분법 공식을 사용한 연속 함수.

에프(엑스) = 엑스3 -x2 + 2

이분법 방법의 예

단계 1) 가정해보자,

         a = -10,
         b = 10이고,
         e = 1% 또는 0.01

단계 2) 이제 f(a)f(b) >= 0인지 확인하겠습니다.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

따라서 위 함수의 근은 이 구간 [-10, 10]에 있습니다.

단계 3) 그러면 중간점 c가 먼저 계산됩니다.

이분법 방법의 예

이제 팔로우wing 조건을 확인해야 합니다.

(i) f(c) = 0인지 여부:
         f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) f(a)f(c) < 0인 경우:
         에프(c)에프(a) = 2*(-1098) < 0

조건이 충족되었습니다. 다음 반복에서 값은 다음과 같습니다.

         a = a = -10
         b = c = 0

단계 4) (ba) = (0-(-10)) = 10>0.05이므로 이 과정이 반복됩니다. 다음 반복이 표에 표시됩니다.

되풀이 a b c 에프(기음)
1 -10 0 0 10 2
2 -5 0 -5 5 -148
3 -2.5 0 -2.5 2.5 -19.875
4 -1.25 0 -1.25 1.25 -1.52562
5 -1.25 -0.625 -0.625 0.625 1.36523
6 -1.25 -0.9375 -0.9375 0.3125 0.297119
7 -1.09375 -0.9375 -1.09375 0.15625 -0.50473
8 -1.01562 -0.9375 -1.01562 0.078125 -0.0791054
9 -1.01562 -0.976562 -0.976562 0.0390625 0.115003
10 -1.01562 -0.996094 -0.996094 0.0195312 0.0194703
11 -1.00586 -0.996094 -1.00586 0.00976562 -0.0294344

단계 5) 11번째 반복에서는 4단계 조건이 false가 됩니다. 따라서 이 방정식의 근은 -1.00586입니다.

이등분법 논리도

이등분법 논리도

의사 코드

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

C/C++의 이분법 예제

입력:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

출력:

The root is :-1.00586

Python의 이분법 방법 예

입력:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

출력:

The root is :  -1.0059

이분법의 장점과 한계

이분법의 장점과 단점은 다음과 같습니다.

장점 단점
구현하기 쉽고 간단한 루트 찾기 방법입니다. 단순히 간격을 반으로 나누는 것을 기반으로 하기 때문에 수렴이 느립니다.
이후 brackets 루트는 항상 수렴합니다. 초기 추측 중 하나가 근에 가까우면 근에 도달하려면 더 많은 반복이 필요합니다.
반복 횟수를 늘리거나 줄여서 오류율을 제어할 수 있습니다.