Overview

Root Finding Algorithm은 다항 방정식의 근을 구하거나 최적화 문제에서 objective function(목적 함수)의 최소점을 찾는 것에 활용할 수 있다.

Root Finding

Root Finding(근 찾기)는 주어진 함수 $f$에 대해 $f(x)=0$의 해를 찾는 것이다.

종류

• Bisection Method
• Newton’s Method
• Secant Method

Bisection Method

Bisection Method는 중간값 정리를 이용한 방법으로, 함수 $f$가 구간 $[a,b]$에서 연속이고 $f(a)$와 $f(b)$의 부호가 다를 때, $f(p)=0$를 만족하는 $p \in (a, b)$가 존재함을 이용하여 구간을 계속 반으로 나누어 가며 해를 찾는 방법이다.

• 사진

Conditions

• $f \in C[a, b]$
• $f(a) \cdot f(b) < 0$

Theorem

• Suppose that
  • $f \in C[a,b]$
  • $f(a) \cdot f(b) < 0$
• Bisection Method
  • $p$에 근사하는 수열 $\{p_n\}_{n=1}^\infin$을 생성
  • $\displaystyle |p_n - p| ≤ \frac {b-a} {2^n}$
    • 단, $n ≥ 1$

Algorithm

1. 초기 구간 $[a_0, b_0]$ 설정
2. 반복
   1. $p_n = \frac {a_n + b_n} {2}$
   2. If $f(a_n) \cdot f(p_n) < 0$: then $b_{n+1}=p_n$
   3. If $f(b_n) \cdot f(p_n) < 0$: then $a_{n+1}=p_n$