Bisection Method

Bisection Method

 

1. 개념

 

bisection method란 근을 찾는 알고리즘이다. 근이 존재하는 구간을 반으로 나눠 점점 좁혀나가는 방법으로 이해하면 된다. 일정 오차 내의 1개의 해는 무조건 도출이 가능하나 상대적으로 속도가 느린 방식이다.

 

Bisection Method (위키백과)

해의 존재여부 판단에는 중간값 정리(Intermediate-Value Theorem)를 활용하게 된다. 연속인 함수 f가 폐구간 [a,b]에서 f(a)f(b) < 0 을 만족한다면 반드시 구간내에 해가 존재함을 알 수 있기 때문에 이를 통해 해의 존재구간을 줄여나갈 수 있다.

 

 

2. Python 구현

 

함수  $f(x) = x^{3}+3x^{2}+1$의 해를 bisection method를 통해 구해보는 실습을 진행하였다. 다음과 같이 bisection method를 파이썬으로 구현해 보았다.

import matplotlib.pyplot as plt
import matplotlib
def function1(x):
    return x**3 + 3*x + 1

Nmax = 100
eps = 1e-7
x0 = -1
x1 = 0
x0_history, x1_history = [], []

y0 = function1(x0)
y1 = function1(x1)
if y0 * y1 > 0 :
    assert False, "초기값 다시 설정하세요"
gap = x1 - x0

for ii in range(Nmax):
    gap *= 0.5
    c = x0 + gap
    yc = function1(c)
    if abs(gap) < eps:
        print("convergence!")
        print("soltuion is ", c)
        break
    if y0 * yc < 0:
        x1 = c
        y1 = yc
    else:
        x0 = c
        y0 = yc
    x0_history.append(x0)
    x1_history.append(x1)
    print(ii)

print(x0_history)
print(x1_history)
plt.figure()
plt.plot(x0_history, 'r' )
plt.plot(x1_history, 'b')
plt.show()
print(function1(-0.32218533754348755))
print(matplotlib.__version__)

 

해의 존재구간이 절반씩 감소하는 모습을 확인할 수 있다

오차범위 1e-7 내에서 구한 해는 -0.32218533754348755로, 여기까지 도달하기 위해 해의 존재구간을 22회에 걸쳐 줄여나갔음을 확인할 수 있었다. 구한 해를 원래 함수 f에 대입하면 약 5.656e-8의 값을 얻을 수 있었다.