Newton's Method: Found a case where it doesn't work. Why?

Question

So I was looking to use Newton's Method to evaluate $x^3-2*x+2 = 0$. I noticed that I could plug in a negative number for $x_0$ and it worked but when I tried $x_0 = 0$ then my code started going crazy and did not find the root. Anyone know why this does this, and how I can fix it? Thanks!

Answer 1

$$ x_{new} = x_{old} -\frac{x_{old}^3 -2x_{old} +2}{3x_{old}^2-2} $$ First iterations with $x_0$ $$ x_{1} = 0 -\frac{2}{-2} = 1\\ x_2 = 1 -\frac{1}{1} = 0 = x_0 $$ Thus you hit a limit cycle (attractor) where the values will just repeat.

Answer 2

Chinny84 is right, unfortunately the orbit produced by the Newton method with starting point $x_0=0$ is periodic in this case, and does not converge to the root of your polynomial.

I just would like to stress that the convergence of the Newton method is a really tricky issue, indeed, you can produce fractals based on the convergence of this method applied to particular (bivariate) polynomials :)

http://en.wikipedia.org/wiki/Newton_fractal

Answer 3

In general, Newton's Method is not guaranteed to work for every initial point. The immediate basin of attraction of the zero $p$, i.e. the largest open interval containing $p$ such that from every starting point in this interval the iteration converges to $p$, will have one of the following forms:

1. $(-\infty, \infty)$
2. $(-\infty, b)$ where $f'(b) = 0$
3. $(a,\infty)$ where $f'(a) = 0$
4. $(a,b)$ where $a$ and $b$ form a repelling two-cycle for Newton's method.

In this case we have case (2) with $b = -\sqrt{6}/3 = -.8164965809$ approximately.