Why Newton's method converges to second root in parabola?

1.1k Views Asked by At

Have been looking for the solution for 2 hours, decided to try here instead. We have this unprecise picture, let me try to explain it. Picture of parabola with 2 roots

How starting guess $x_0$ defines towards what root the converging will be taking place? So my professor said that in the case described on the picture although $x_0$ is far away from $x_2$, it will still converge to that point, instead of $x_1$ point, that seems more logical as $x_0$ is near $x_1$.

Why that happens? It has to do with double roots, or the $x_0$ is still too far away from $x_1$ and that's why imprecision comes in?

2

There are 2 best solutions below

4
On BEST ANSWER

The Newton's method what it does geometrically is define over the $x$-axis a sequence of points $(x_n)$ through the iterative construction of tangents to the function.

Let define the perfect interval $[\min\{x_0,r\},\max\{x_0,r\}]$ for some root $r$, that is, $f(r)=0$, and some starting point for the iteration $x_0$.

If $f$ is convex (alternatively concave) in this interval and $f(x_0)>0$ (alternatively $f(x_0)<0$) then the sequence starting by $x_0$ converges monotonically to $r$.

Proof: without lose of generality suppose that $f$ is convex and the interval is $[x_0,r]$ (as in your example). By the definition of convexity every tangent line to $f$ is below $f$, that is, $h(x)\le f(x)$ for all $x\in[x_0,r]$ and $h$ being any tangent line to some point in $(x_0,r)$ (I exclude the endpoints for some trivial cases where $h$ could be zero).

The tangent to $(x_0,f(x_0))$ (for differentiable $f$) is

$$h(x)=f'(x_0)(x-x_0)+f(x_0)\tag{1}$$

Equating $h(x)=0$ above we can define the standard Newton's iterative sequence

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\tag{2}$$

Because $f$ is convex then $h(x)\le f(x)$, then if $f(x_0)>0$ we have, from (1) and (2), that $h(x_1)=0\le f(x_1)$, and by induction $f(x_n)\ge0$ for all $n\in\Bbb N$.

WLOG suppose that $f'(x_n)>0$ and $f'(x_{n+1})<0$, then $f$ have a local minimum $m\in(\min\{x_n, x_{n+1}\},\max\{x_n, x_{n+1}\})$ such that $f(m)>0$ (because a convex function is above of it tangent lines and as I showed before $f(x_n)\ge 0$ for all $n\in\Bbb N$) what is a contradiction with the assumption that $f$ has a zero in $r$, so $f'(x_n)$ have the same sign for all $n\in\Bbb N$.

From the same sign of $f'$ in $(x_n)$, and because a convex function is above to it tangent lines, and because (2), is easy to check that the sequence $(f(x_n))\downarrow 0$ what implies that $(x_n)\to r$ monotonically.

For $f$ concave we can prove a similar result when $f(x_0)<0$.


All this ugly proof (if it is written correctly, what Im not completely sure) can be "sorted", for the exemplification of the phenomenon for this specific case for $f$ convex and $f(x_0)>0$, with a graph were we show how the sequence works for the case where $f$ is convex and $f(x_0)>0$ but by now Im unable to graph it in some graphic software.

In short words: $x_n$, for all $n\in\Bbb N$, is at the left of the root $r$ of the example, then it cannot be possible that $(x_n)$ converge to some root at the right of $r$.


Using some geogebra applet like this we can see some graphical examples about how the Newton's method build the recursion that approach to some root.

This is an example for the case discussed above when $f$ is convex and $f(x_0)>0$ (the red lines are tangents, and the blue lines represent the recursion from one tangent line to other):

enter image description here

And this is an example when the recursion goes to a root far away from the starting point:

enter image description here

Of course is possible that the Newton's method doesnt converge at all to any root of $f$.

1
On

In general, even if you know all the roots of a polynomial it is not easy to say to which root Newton's method will converge for a given starting point. This is because for general (complex valued) polynomials the sets of those point become fractals. Below is a picture where each color corresponds to the root of $p(z) = z^3 -1$ the Newton method converges against.

Newton fractal of <span class=$z^3-1$" />