1

I took a class about numerical analysis.

And when f(x)=sin(x) and what to do is find approximation of Pi.

Then in Newton method, it has hyperquadratic convegergence, and actually its order is 3.

I don't know why. (I tried to solve this problem through proof of Newton method using Taylor expansion, but I couldn't.)

최선웅
  • 337
  • I would recommend to solve $\sin(x)=\frac12$ to find $\frac\pi6$ as the Taylor series converges faster for smaller arguments. Which gets you faster and more stable numerical results. But of course you lose the third order convergence. Use Halley's method, which can be written as Newton method for a modified function, to systematically get third order convergence. – Lutz Lehmann Oct 08 '17 at 10:46
  • You can use Householder method for fourth order. – Claude Leibovici Oct 08 '17 at 13:34

1 Answers1

2

Newton's method is a fixed point iteration, i.e. $$ x_{n+1} = g(x_n)$$ for a very special $g$, i.e. $$ g(x) = x - \frac{f(x)}{f'(x)}. $$ In general, we have $$ g'(x) = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2},$$ and $f(x)=0$ implies $g(x)=0$.

It is the fact that $g'$ vanishes at the root which gives us (local) quadratic convergence of Newton's method in general.

If you want higher order convergence, then more derivatives of $g$ must vanish. Find higher derivatives of $g$ and evaluate them at your root. The known properties of $\sin$, $\cos$ and $\tan$ will suffice.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37
  • If $f''(x^)=0$ at the root $x^$, as is here the case, then $g'(x^)$ has at least a double root, which automatically makes $g''(x^)=0$ leading to at least third order convergence. In general Newtons method applied to $h(x)=f(x)/\sqrt{|f'(x)|}$ leads to the third order Halley method, see its wiki page. – Lutz Lehmann Oct 08 '17 at 10:43