0
$\begingroup$

I was going through some computations and I found something strange about Newton's Method. If anyone can verify it, it would be of great help.

Newton's method is given by $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$. Now, say I have a non differentiable function $f(x)$. But, the point of non- differentiabilty is away from the zero. Hence, if I apply Newton's Method with starting solution close to the root, in some cases I will get the solution (as desired).

Now, I think for smooth functions the starting value don't play an important role in finding the root. It surely helps in reducing the number of iterations but even if we start from some not so close point, we will still get the answer (Yes, the number of iterations will increase).

Whereas, for Non-Smooth functions the starting solution should be close to zero (again provided the non differentiable point is away from the root). If we start from some far away point then because of non differentiability we will have issues with the method.

Is my thinking, correct?

$\endgroup$
3
$\begingroup$

Regarding "Now, I think for smooth functions the starting value don't play an important role in finding the root.": It's not that simple. The study of the basins of attraction to roots under Newton's method is still an area of active research. That this can be complicated is demonstrated, for instance here, starting at "To which root Newton's method converges depends entirely on the point at which it starts. Surprisingly, this starting point is very sensitive." See also Fractals derived from Newton-Raphson iteration, where it demonstrated that there are very small neighborhoods meeting all the basins of attraction.

Regarding a function that is not everywhere differentiable... You can think of each such point having its own basin of attraction, the set of points whose Newton's iterates meet the nondifferentiable point. Each basin for a root can be partitioned into subsets and Newton's iteration maps subsets onto subsets. Suppose one root's basin of attraction contains a nondifferentiable point; then every piece of the basin's partition contains a point that eventually iterates to the nondifferentiable point. As you can see by looking at some of the pictures at the links above, this means there are little neighborhoods of the plane containing infinitely many points that will eventually iterate to the nondifferentiable point.

This problem is very similar to the difficulty of Newton's method when your function has a point with derivative zero. If iteration takes you exactly to that point, the division in Newton's method is undefined.

You exclude the possibility that the point of nondifferentiability is at the root, but this can be overoptimistic. For instance, the function $\sqrt[3]{x}$ has a root at $x=0$ and is not differentiable at $x=0$. In this example, iteration doubles the distance from the origin.

If the function is differentiable everywhere but the derivative is not continuous and it happens that the function has a discontinuous derivative at the root, iteration may fail to converge to the root no matter how close to the root you start.

$\endgroup$

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.