[수치해석] 3. Newton's method

Newton's Method

• Fixed Point method의 특별 case(가장 빠른 수렴)
• newton method가 불가능한 경우 보통 bisection method 사용 (fixed point method는 상대적으로 잘 쓰이지 않음)

---

• Taylor Polynomal
  • 계산된 fixed point p에 대해서
  • $f(p)=f(p_0)+(p-p_0)f'(p_0)+\frac{(p-p_0^2)}{2}f''(\zeta(p))$
  • $\zeta(p)$는 p~p0 사이엥 위치
• p가 f(x)의 근이면 f(p)=0
  • 이 경우 $0=f(p_0)+(p-p_0)f'(p_0)+\frac{(p-p_0)^2}{2}f''(\zeta(p))$
  • 2차항은 error 취급 : $0\simeq f(p_0)+(p-p_0)f'(p_0)$ (p : 근사해)
  • p에 대해 정리하면 $p\simeq p_0-\frac{f(p_0)}{f'(p_0)}\equiv p_1$
• Newton's method
  • $p_n=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}(n\geq1)$을 반복하여 근사해로 수렴
  • 이때 $p_n=g(p_{n-1})$이므로, $g(p_{n-1})=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}$로 표기할 수도 있다.
    

    

  • 곡선의 근을 구하기가 힘들다는 점에서 곡선에 접하는 접선의 근을 반복적으로 계산하여 곡선의 근으로 수렴한다.
• 장점 : 매우 빠른 수렴
• 단점 : 적절한 point 선정 필요 / 실제 개발 시 미분을 요구하므로 계산이 복잡해짐
• Convergence theorem
  • 위 식에서 $g(x)=x-\frac{f(x)}{f'(x)}$
  • Converence rate : $g'(x)=\frac{f(x)f''(x)}{[f'(x)]^2}$
  • 고정점에서 f(p)=0이므로 newton's method의 수렴 속도는 0으로 수렴 (매우 빠르다)