Fun with Newton's Method - Infinitely many cycles

Question

I'd like to preface this problem by saying that I have absolutely no clue if it is solvable or not. This is just the result of some musings, and I'm looking for either some guidance, or to be pointed in the direction of a solution if one is known.

The goal is to find a function, hopefully a polynomial, but this is not a requirement, which contains infinitely many cycles in it when Newton's Method is applied to it. An example of such a cycle is a 2-cycle which arises in the function $f(x)=x^3-2x+2,$ along with the starting point $x=0$ as the starting point. Applying Newton's Method ($N(x)=x- \frac {p(x)}{p'(x)})$ to this yields $N(0)=0-\frac {2}{-2}=1$. Taking $1$ as the next point then gives. $N(1)=1-1=0,$ yielding the 2-cycle.

Now, I know that there exists an ordering of the natural numbers, so that the existence of some cycles implies the existence of other cycles, which, if I remember correctly, is called the Sarkovskii ordering. Since this ordering shows that $2 \rhd 1,$ there should be a fixed point to this function. In the context of Newton's Method, this should be somewhat obvious - that somewhere for $f(x)$ there shoudl be a point $x_0$ such that $f(x_0)=0$. A quick sketch of this function shows that there is such a point. However, the ordering says a good deal about the existence of these cycles, and in particular, that the existence of a 3-cycle implies the existence of a cycle of any other period.

Knowing this information, I'm seeking a function with a 3-cycle, so that all other periods exist as well. I have tried investigating this issue by hand, by seeking the period 3 points of the function $N(x)$ and hopefully noting some useful pattern but it's immediately clear to me that even $N^2(x)$ is quite difficult to work with (if $N^2(x)=N(N(x))$, that is). Since

$N^3(x)=N(N^2(x))=N((x- \frac {p(x)}{p'(x)})- \frac {p (x- \frac {p(x)}{p'(x)})} {p'(x-\frac {p(x)}{p'(x)})})$

So I'm hoping that someone knows another way to cook up a function which will behave like this. Or can at least point me in the right direction. Also, I don't know what tags to use properly for this question, so I tagged the same things I used when I was in an introductory course in dynamical systems.

Answer 1

Try $p(x) = (x−2)(x−1)x(−{9x^2 \over 8}+{21x \over 8}−{1 \over 2})+1$.

You have $p(0) = p(1) = p(2) = 1$ and $p'(0) = p'(1) = -1, p'(2) = {1 \over 2}$.

Using $x_{n+1} = x_n - { p(x_n) \over p'(x_n) }$ we find that with $x_0 = 0$, we get $x_1 = 1, x_2 = 2, x_3 = 0,...$

Answer 2

A general strategy to find functions with desired properties is to study a parametrized family of functions. This is exactly the path to the bifurcation diagram in real dynamics and the Mandelbrot set in complex dynamics.

A super-attractive orbit of period 3

After a little experimentation, I decided to look at the family of cubic polynomials $f_{\lambda}(x)=\lambda+x-x^3$, which has the associated Newton's method iteration function $$n_{\lambda}(x)=\frac{2 x^3 + \lambda}{3 x^2-1}.$$ Note that $$n_{\lambda}'(x)=\frac{6 x \left(x^3-x-\lambda \right)}{\left(1-3 x^2\right)^2}$$ so that $x=0$ is a critical point. Thus, to find a value of $\lambda$ so that $n_{\lambda}$ has a super-attractive orbit of period 3, it suffices to find a value of $\lambda$ such that $n_{\lambda}(n_{\lambda}(n_{\lambda}(0))) = 0$. Grabbing just the numerator of the left hand side, this equation is equivalent to $$-16 \lambda ^9+51 \lambda ^7-39 \lambda ^5+11 \lambda^3-\lambda = 0.$$ Using your favorite numerical solver, it turns out that $\lambda\approx -1.49175$ does the trick.

A repulsive orbit of period 3

If you stick to quadratic polynomials, you're not going to find any attractive orbits of period 3, but you can find repelling orbits of period 3. Indeed, consider the polynomial $p(x)=x^2+1$. This has no real roots so perhaps it's not surprising that the corresponding Newton's method iteration function $$n(x)=\frac{x}{2}-\frac{1}{2 x}$$ displays chaotic behavior on the real line. Thus, we might expect a point of period 3. To find it, simply solve the equation $n(n(n(x))) = x$. This is equivalent to $$\frac{x^8-28 x^6+70 x^4-28 x^2+1}{8 x \left(x^6-7 x^4+7x^2-1\right)} = x.$$ Or using your favorite numerical solver again, you can find the roots. There are six real roots forming two orbits of period 3 namely $$2.07652 \rightarrow 0.797473 \rightarrow -0.228243 \rightarrow 2.07652$$ and $$-2.07652 \rightarrow -0.797473 \rightarrow 0.228243 \rightarrow -2.07652.$$