Root finding algorithm - Bisection method 설명, 코드 구현

이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다.


Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다.

Bisection method 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다.

여기선 Bisection method 의 장점과 단점을 생각해보려합니다.

장점

초기 두 지점 a, b 만 서로 부호가 다르게 설정된다면 반드시 해를 찾을 수 있는 방법입니다.

단점

1. 초기 두 지점 a, b 의 부호가 서로 같다면 알고리즘 적용이 불가능합니다. 이를 회피하기 위해서 두 지점간의 간격을 더 넓게 잡는다면 당연히 계산속도 또한 더 느려지게 됩니다.

2. Rate of convergence 가 1/2 로 상대적으로 다른 root finding 알고리즘에 비해 계산속도 측면에서 성능이 나쁜편입니다.

코드 구현

핑계일 뿐이지만, 제대로된 코딩 수업을 들어본 적이 없기 때문에 코드가 개똥 같을 수 있습니다.

코드는 python 으로 작성되었습니다. myEquation1() 함수의 return 에 Bisection method 를 적용하고자 하는 함수로 변경해서 사용하면 됩니다.

import math
import numpy as np

def myEquation1(x):
    return -1 * (x**3)

def bisection(a, b, iteration, my_func):
    iteration = iteration + 1
    bi_a = my_func(a)
    bi_b = my_func(b)

    if bi_a * bi_b > 0:
        print("wrong interval")
    elif bi_a * bi_b < 0.0000001 and bi_a * bi_b > (-1* 0.0000001):
        print("case close")
        print("iteration: ", str(iteration).ljust(3), "  x1: ",  str(a).ljust(25), "  x2: ", str(b).ljust(25))
    elif bi_a * bi_b < 0:
        c = (a+b)/2
        if (my_func(c) < 0.0000001 and my_func(c) > (-1* 0.0000001)) or (b-a) < 0.0000001:
            print("case close")
            print("iteration: ", str(iteration).ljust(3), "  x: ", str(c).ljust(25), "  f(x): ", str(my_func(c)).ljust(25))
        elif my_func(c) * bi_a < 0:
            b = c
            print("iteration: ", str(iteration).ljust(3), "  x1: ", str(a).ljust(25), "  x2: ", str(b).ljust(25))
            bisection(a, b, iteration, my_func)
        else:
            a = c
            print("iteration: ", str(iteration).ljust(3), "  x1: ", str(a).ljust(25), "  x2: ", str(b).ljust(25))
            bisection(a, b, iteration, my_func)

bisection(-100 ,50,0,myEquation1)

Bisection search 뜻 Bisection search 구현