[Optimization] Bisection algorithm (이분법) 정리 / 설명

Bisection algorithm

 

Retrieved from https://www.geeksforgeeks.org/program-for-bisection-method/

 

---

• Assumption

  • Function

    • $g(x) : D \subset \mathbb{R} \rightarrow \mathbb{R}$

• 하고자 하는 것

  • find a root or solution $x^{*}$ of the equation

    • $g(x)=0, x\in[a,b]$

    • where $g$ is continuous and g(a)g(b) < 0

• $x^{*}$를 찾기 위한 조건

  • $\exists n > 0, s.t. |x_{n}-x^{*}| < \epsilon$,

  • where $x^{*}$ is the solution of $g(x)=0$

  • 위 조건을 만족하는 $x_{n}$ 찾아 $\hat{x}$ (approximated solution)으로 채택

---

(Intermediate value theorem) Suppose $g: [a,b] \rightarrow \mathbb{R}$ is continuous, $g(a)$ and $g(b)$ are of opposite sign. Then there exists a point $x \in (a,b)$ such that $g(x) = 0$

 

Bisection 알고리즘은 위 Intermediate value theorem의 아이디어를 차용한다.

 

---

Bisection algorithm

 

Bisection 알고리즘의 작동방식을 간단하게 나타내면 다음과 같다.

 

 

- 부호가 다른 함수값을 갖는 두 점 a, b를 초깃값 $(a_{1}, b_{1})$으로 설정한다.

 

- $a_{1}, b_{1}$의 중간 점인 ($[a_{1},b_{1}]$를 이분하는) $x_{1}$을 구한다. 

 

- $x_{1}$에서의 함수값이 갖는 부호 $(sign(g(x_{1}))$를 계산한다.

 

- $a_{1}, b_{1}$ 중 함수값의 부호가 $x_{1}$과 같은 점을 업데이트한다. 

 

    예) $g(a_{1})과 g(x_{1})$의 부호가 같은 경우,  $(sign(g(a_{1})) = sign(g(x_{1})))$

          $a_{2} = x_{1}$ 그리고 $b_{2} = b_{1}$ 으로 업데이트

 

- 새롭게 얻은 범위 $[a_{2}, b_{2}]$에 대해 Bisection algorithm 반복적용

 

- $|x_{n+1} - x_{n}| < \epsilon$ 조건 만족할 때 멈춤 ($x$의 변화가 미리 설정한 error bound 보다 작아지면 멈춤)

 

- 이 때의 $x_{n}$을 $\hat{x}$로 채택

 

 

 

 

아래는 구체적 알고리즘

 

• First step

  (1): set $a_{1} = a$ and $b_{1} = b$

         and let $x_{1} = (a_{1}+b_{1}) / 2$

  (2): If $g(x_{1}) = 0$ then stop, concluding that $x^{*} = x_{1}$

  (3): If $g(x_{1}) \neq 0$ then $g(x_{1})$ must have the same sign as either $g(a_{1})$ or $g(b_{1})$

      (3-1): If $g(x_{1})g(a_{1}) > 0$ then set $a_{2} = x_{1}$ and $b_{2} = b_{1}$

      (3-2): If $g(x_{1})g(b_{1}) > 0$ then set $a_{2} = a_{1}$ and $b_{2} = x_{1}$

  (4): Start over with the interval $[a_{2},b_{2}]$ instead of $[a_{2},b_{2}]$

 

• Full steps             

        (1): Set $a_{1} = a, b_{1}, = b$ and $x_{1} = (a+b)/2$

        (2): For $n = 1,2,\cdots,$ to the followings 

            (2-1): If $g(x_{n})g(a_{n}) > 0$ then set $a_{n+1} = x_{n}$ and $b_{n+1} = b_{n}$ 

            (2-2): If $g(x_{n})g(a_{n}) < 0$ then set $a_{n+1} = a_{n}$ and $b_{n+1} = x_{n}$  

            (2-3): Set $x_{n+1} = (a_{n+1}+b_{n+1})/2

            (2-4): If $|x_{n+1} - x_{n}| < \epsilon$ then stop

        (3): Set $\hat{x} = x_{n}$