Explain what is happening in using Newton's method solving $x^3-2x+2=0$ with $x_0=0$

Question

Compute four steps of Newton's method to solve $x^3-2x+2=0$ with $x_0=0$. Explain what is happening.

What I have so far: Since $f(x)=x^3-2*x+2$, we have $f'(x)=3x^2-2$

Applying Newton's method $x_{n+1}=x_n-\frac{x_n^3-2x_n^2+2}{3x_n^2-2}$

Since $x_0=0$, we can get $x_1=1$, $x_2=0$, $x_3=1$, $x_4=0$

I am having trouble explaining what is happening partially because I am not sure what the problem is asking in this latter part. My guess is that it is asking me to explain why x here is jumping from 0 to 1 and this may somehow have something to do with the convergence?

Answer 1

The goal of the Newton algorithm is to find a sequence that converge to the roots of an equation (to approximate it). Here as your sequence doesn't converge, this is obviously a fail.

Now, you did prove earlier in your lessons (at least I hope so) a theorem that assure that under some hypothesis, the sequence converge : what hypothesis is missing here?

Answer 2

As with any not everywhere contractive fixed point map, the fixed point iteration $x=g(x)$ may converge to a cycle $$x_{k+1}=g(x_k)\text{ and }x_0=x_n=g(x_{n-1})$$ where $x_k\ne x_0$, $k=1,...,n-1$. This cycle will be stable if $$ |g'(x_0)|·|g'(x_1)|·…·|g'(x_{n-1})|<1, $$ which means that starting the iteration close enough to one of the points in the cycle will converge to the cycle.

Here the fixed-point iteration is the Newton method $$g(x)=x-\frac{f(x)}{f'(x)}\text{ and }g'(x)=-\frac{f(x)f''(x)}{f'(x)^2}$$ with $f(x)=x^3−2x+2$, $f'(x)=3x^2-2$, $f''(x)=6x$. It is now easy to verify that $g(0)=1$ and $g(1)=0$. The derivative of this 2-cycleis $0$ as $g'(0)=0$ and $g'(1)=-6$, so indeed it is stable.

---

The graph with tangent lines is (thanks to wikipedia on Newton's method)

The Newton fractal with cycle detection (from the corresponding wikipedia article) is

where the red regions are initial points converging towards the 0-1-cycle.