[수치해석] 1. Bisectional Method

Root finding problem

• $f(x)=0$의 식을 만족하는 함수 f에 대해 근(해)를 찾는 과정
  • 이 식을 함수 f의 영점(zero) 라고 함.

Bisectional Method

• 중간값 정리(Intermediate Value Theorem, IVT)
  • 함수 f(x)가 [a, b] 범위 내에 정의 (f는 연속)
  • $f(a)f(b) < 0$이면 그 범위 내에 $f(p)=0$인 p가 존재
• bisectional method
  • $a_1=a, b_1=b$로 정의, a-b 사이의 중간점 p를 이용
  • $p_1 = \frac{a_1+b_1}{2}$
  • $f(a_1)f(p_1), f(p_1)f(b_1)$ 종 IVP를 만족하는 구간에 대해 위 과정을 반복
  • 오차가 일정 이하가 될 때 해당 값을 근으로 설정
• 오차
  • 절대오차(absolute error) : $p_N - p_{N-1} < \epsilon$
  • 상대오차(reletive error) : $|p_N - p_{N-1}|/|p_N| < \epsilon$
• Bisection method의 convergence rate
  • 수렴의 빠르기
  • $|p_n-p|\leq\frac{b-a}{2^n}$
  • $\therefore$ bisection method는 $O(\frac{1}{2^n})$의 빠르기로 수렴
  • Error bound : Convergence rate를 이용한 반복 회수 예측
    • $|p_N-p|\leq2^{-N}(b-a)<\epsilon=10^{-m}$
    • $-Nlog2<-m\rarr N>\frac{m}{log2}$