[수치해석] 4. Secant method

Secant Method

• newton method : $p_n=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}$
• secant method : newton method의 미분항(f')를 근사
  • $f'(p_n)\simeq\frac{f(p_n)-f(p_{n-1})}{p_n-p_{n-1}}$
  • $\Rarr p_{n+1}=p_n-f(p_n)\cdot\frac{p_n-p_{n-1}}{f(p_n)-f(p_{n-1})}$
  • 장점 : 미분항이 없음 = 개발 시 용이
  • 단점 : 초반 point 수가 두개 ($p_n,\ p_{n-1}$), newton method보다는 느림

False Position (Ragula Falsi)

• 기존의 Secant method는 계산에 따라 진동하면서 수렴할 위험 존재
• 두번째 point인 $p_1$을 계산 기준점으로 삼아 uniform하게 수렴하도록 계산

Order of Convergence

• $\{p_n\}^\infty_{n=0}$이 p로 수렵할 때
• $lim_{n\rarr\infty}\frac{|p_{n+1}-p|}{|p_n-p|^{\alpha}}=\lambda$에서 계수 $\alpha$가 수렴 형태를 결정
  • $\lambda$ : error constant
  • $\alpha=1, \lambda<1$ : linearly convergent
    • 식이 p=0으로 수렴한다고 할 때, $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|}=0.5$
  • $\alpha=2$ : quadratically convergent
    • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|^2}=0.5$
  • secant method의 경우 $p_n$의 계수가 $\frac{1+\sqrt{5}}{2}$
• bisection method / fixed-point method
  • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|}=\lambda$ : $\lambda$가 작을수록 빠른 수렴 / 0.5면 bisection
  • $|p_n|\simeq\lambda^2|p_0|$
• newton method
  • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|^2}=\lambda$
  • $|p_n|\simeq\lambda^{2^n-1}|p_0|^{2^n-1}$