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.

Answer 3

The Newton-Raphson algorithm can fail to converge to a root under certain conditions. The theorem you're referring to is likely the convergence theorem for Newton's method, which states that if certain conditions are met, then the sequence of guesses generated by the method will converge to a root of the equation.

The conditions for convergence are:

The function $f(x)$ must be continuously differentiable in an open interval containing the root. And the derivative $f'(x)$ must be nonzero in the interval containing the root and the initial guess $x_0$ must be sufficiently close to the root. In the case of the equation $x^3 - 2x + 2 = 0$, the first two conditions are satisfied, as the function is continuously differentiable and the derivative is nonzero near the root. However, the initial guess $x_0 = 0$ is too far away from the root, and so the algorithm fails to converge. For your problem of $x^3 - 2x + 2 = 0$ with $x_0 = 0$, we have:

$$f(x) = x^3 - 2x + 2$$ with the derivative $$f'(x) = 3x^2 - 2$$

The first guess is $x_0 = 0$, so we can plug this into the formula to get:

$$x_1 = x_0 - f(x_0)/f'(x_0) = 0 - f(0)/f'(0) = -2/(-2) = 1$$

So the first iteration gives us a new guess of $x_1 = 1$. We can then repeat the process with $x_1$ as the new guess:

$$x_2 = x_1 - f(x_1)/f'(x_1) = 1 - f(1)/f'(1) = 1.1666666666666667$$

We can continue the iterations until we reach a desired level of accuracy or until we see that the sequence of guesses is not converging. In this case, the sequence of guesses converges to the root at around $x = 1.7693$.

If we had chosen a different initial guess that was closer to the root, the algorithm may have converged. For example, if we had chosen $x_0 = 1$, the algorithm would have converged to the root at $x = 1.7693$.