Newton's method - weird triple oscillation $x^5-x+1$

Question

I'm investigating iterations using Newton's method for $f(x)=x^5-x+1$.

I'm getting unusual results though. I've found that some starting values will result with a "triple oscillation" of results where iterations will loop between values of approximately $1.0003$, $0.7504$ and $-0.0871$.

However the only consistency that I could find in these starting values is that you none of the values that are less than $-0.669$, where the maximum turning point of the graph is, will create this oscillation.

Edit: I'm using the real plane, with starting values that will converge (such as 0.660 and 1.220) and values that will oscillate (such as -0.500 and 2.100).

What is the explanation for this?

Answer 1

Newton's method constructs the tangent line to the graph and finds the intersection of that tangent with the $x$ axis to find the next point. If you are close to the root you expect the tangent to be a good approximation to the graph and for the next iteration to be close to the root. Your function is graphed below. You can see that in the region roughly $(-0.6,0.8)$ the tangent points somewhere above $1$. If you arrived at one of the local extrema the derivative becomes zero and the method fails entirely. If you are close to one of the extrema the derivative is very small and your next point will be far away. You need to get below the local maximum at about $-0.8$ to have the tangent point near the root. If you are above it the tangent will not point below it. As there is no root up there you will oscillate.

People like Newton's method because it is quadratically convergent, but that only applies when you are close enough to the root for the Taylor series to be a good approximation. There is a good discussion of this in Numerical Recipes chapter 9. They make a big deal about bracketing roots.

Answer 2

Newton's method iterates $N(x)=x- \dfrac{f(x)}{f'(x)}$.

What you have seen is explained by the fact that, in your example, $N^3=N\circ N \circ N$ has seven real fixed points:

• $-1.1673039$, which is fixed by $N$ and is the root of $f$

• $-0.0833570, 0.7503218, 1.0002575$, which form one 3-cycle under $N$

• $ 0.3366437, 0.8086456, 1.0501426$, which form another 3-cycle under $N$

Starting with $x_0=0$ leads to the first cycle, which is an attracting cycle. The second cycle is a repelling cycle.

An $n$-cycle containing a point $x^*$ is attracting when $|(N^n)'(x^*)|<1$ and repelling when $|(N^n)'(x^*)|>1$.