0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The method is not converging. What about the graph of the function is relevant here? Hint: find the critical point(s), classify them with the second derivative test, and use that to get a sketch of the function. (Or get a graph numerically.) $\endgroup$ – Ian Oct 28 '15 at 1:30
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hi! Thanks a lot for your comment. It definitely helped me! I'm considering: x=x^3-3x+2=(x-1)(x^2+x-1). This, we can see x=1 is a fixed point. f'(1), however, is 1, which violates the hypothesis that the absolute value of f'(s) where s is a fixed point should be between 0 and 1. (Sorry for the terrible formatting/potential error in calculation as I'm typing in my phone and I mind calculated those things...) $\endgroup$ – QmmmmLiu Oct 28 '15 at 3:23
  • 1
    $\begingroup$ No, this is not the Newton's method. You're looking for a fixed point of $\phi(x) = x - \frac{f(x)}{f'(x)}$. A fixed point $a$ of $\phi$ verify $f(a) = 0$. But $\phi'(x) = 1 - \frac{(f'(x))^2 - f(x) f''(x) }{(f'(x))^2} $, so $\phi'(a) = 0$, and the fixed point $a$ is attractive. No, the two problems that may arise are : 1) $f'(a) = 0$, making $\phi$ ill defined 2) You start too far from the fixed point. $\endgroup$ – Tryss Oct 28 '15 at 3:45
  • 1
    $\begingroup$ @QiminLiu : Indeed, we only proved that $\phi$ is contractive near $a$. But if you go far enough, "everything is possible". And this is what happens here : you start outside the region of convergence. And this is the big problem of the Newton method. See this link to see a nice exemple of what looks like the regions of convergence of the Newton method for the roots of the polynomial $z^3-1$ in $\Bbb C$ : en.wikipedia.org/wiki/Newton_fractal . $\endgroup$ – Tryss Oct 28 '15 at 3:50
2
$\begingroup$

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$ and $x_0=x_n=g(x_{n-1})$ where $x_1\ne x_0$. This cycle may even 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 $g(x)=x-\frac{f(x)}{f'(x)}$ 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$ so that we see that $g'(0)=0$ and $g'(1)=-6$ so that the derivative of the 2-cycle is $0$.


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

The Newton fractal is (used in the corresponding wikipedia article)

Newton fractal

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

$\endgroup$
  • $\begingroup$ Hi, I just want you to know that I really appreciate your answer. However, Tryss's hint and comments have already helped me to arrive at a similar, if not same, answer as yours. So I adopted his answer. But I really like your answer and I really appreciate it! $\endgroup$ – QmmmmLiu Oct 28 '15 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.