Newton's method - periodic sequence

[jbunniii]

Homework Statement

This is problem 2.4.11 from Thomson, Bruckner, and Bruckner, "Elementary Real Analysis." It is from the "Challenging Problems" section of Chapter 2, Sequences. Note that differentiation and continuity have not been covered at this point, but it is presumed that the reader knows how to differentiate elementary functions from a previous calculus course. Five of the 19 problems in this section are from old Putnam exams, but this isn't one of them.

Let $f(x) = x^3 - 3x + 3$. Apply Newton's method to obtain a sequence

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

Show that for any positive integer $N$ there is a starting value $\theta$ such that the sequence $(x_n)$ is periodic with period $N$.

Homework Equations

$$f'(x) = 3x^2 + 3$$

The Attempt at a Solution

We shall have $x_{N+1} = x_{1}$ if and only if $x_{N+1} - x_{1} = 0$ if and only if

$$y_N = \sum_{n = 1}^N \frac{p(x_n)}{q(x_n)} = 0$$

where

$$p(x) = f(x)$$
$$q(x) = f'(x)$$

Define

$$h(x) = x - \frac{p(x)}{q(x)} = \frac{xq(x) - p(x)}{q(x)} = \frac{r(x)}{q(x)}$$

where

$$r(x) = xq(x) - p(x)$$.

Then

$$x_{n+1} = h(x_n)$$

and

$$x_{n+1} = h^n(x_1) = h^n(\theta)$$

where the notation $h^n$ is defined inductively as

$$h^n = h^{n-1} \circ h = h \circ h^{n-1}$$

Now,

$$x_2 = h(x_1) = h(\theta) = \frac{r(\theta)}{q(\theta)}$$

where $r$ is a polynomial of order 3, and $q$ is a polynomial of order 2.

More generally, $x_n$ is a rational function of $\theta$:

$$x_n = \frac{r_{n-1}(\theta)}{q_{n-1}(\theta)}$$

where $r_{n-1}$ is a polynomial of order $3^{n-1}$ and $q_{n-1}$ is a polynomial of order $2^{n-1}$.

Then

$$\frac{p(x_n)}{q(x_n)}$$

is also a rational function of $\theta$, and a bit of algebra yields that the numerator is a polynomial of order $3^n$ and the denominator is a polynomial of order $2(3^{n-1}) + 2^{n+1}$. In particular, the order of the denominator is even, and strictly less than the order of the numerator.

It follows that

$$y_N = \sum_{n=1}^N \frac{p(x_n)}{q(x_n)}$$

is also a rational function of $\theta$. Its numerator has odd order, and its denominator has even order less than the order of the numerator.

Since the numerator has odd order, it has a real root. Thus, there is a $x_1 = \theta$ that yields

$$y_N = \sum_{n=1}^N \frac{p(x_n)}{q(x_n)} = 0$$

It follows that this choice of $\theta$ results in a periodic sequence $(x_n)$ whose period divides $N$.

What remains to show is that it is possible to choose $\theta$ such that the following two additional things are true:

1.

$$y_M = \sum_{n=1}^M \frac{p(x_n)}{q(x_n)} \neq 0$$

for M < N

i.e., I have only shown that the period of $(x_n)$ will divide $N$, not that it will equal $N$.

2.

$$q(x_n) = f'(x_n) \neq 0$$

for all $1 \leq n \leq N$. Otherwise, the recurrence is ill-defined due to division by zero, and everything I have written above is bogus.

I don't see any obvious way to prove 1 and 2, and my instinct is that there must be another way of looking at this problem that will be less grungy and more enlightening. Any ideas?

 

[stringy]

Hello there.

Let $f(x) = x^3 - 3x + 3$.

$$f'(x) = 3x^2 + 3$$

It looks like we have a sign error here. Which one is right? If the derivative is correct, then it looks like we don't have to worry about it ever vanishing!

More generally, $x_n$ is a rational function of $\theta$:

$$x_n = \frac{r_{n-1}(\theta)}{q_{n-1}(\theta)}$$

I'm not too sure I believe that. If $x_n = h^{n-1} (\theta)$ then

$$h^{n-1} (\theta) = \frac{r^{n-1} (\theta)}{q^{n-1} (\theta)}.$$

But if $h(\theta) = r (\theta)/q(\theta)$, then we can take n=3 and arrive at

$$h^2 (\theta) = h( h(\theta))=h( r (\theta)/q(\theta)) = \frac{r (\frac{r(\theta)}{q(\theta)})}{q(\frac{r(\theta)}{q(\theta)})} \neq \frac{r^2 (\theta)}{q^2 (\theta).}$$

Of course I've got so many r's, q's, h's, x's, f's, and thetas scribbled on my paper I may not be following.

This is a surprising problem. I know that Newton's Method is still being actively studied in discrete dynamic systems, and in this problem you're proving results about existence of periodic orbits. Discrete systems like this get very, very, very messy. Which you obviously already know!

For example, Google "periodic orbits" and Newton's Method. You'll get lots and lots of returns.

In short, this is my way of saying I'm throwing in the towel. There's got to be a simpler way without pulling out the high-powered machinery. Hopefully somebody else can chime in.

 

[jbunniii]

Thanks for the reply, stringy! Yes, sorry, that was a typo - f(x) is correctly written, but the derivative should be

$$f'(x) = 3x^2 - 3$$

so x = -1 or 1 is verboten.

I'll follow up in the morning with some more detailed calculations. It's quite possible that I made an error somewhere.

This is indeed a messy problem! I don't have much experience with dynamic systems other than some vague recollections about contraction maps. There can't be much machinery assumed - the authors haven't developed much other than the basics of sequences, subsequences, lim sups, etc. It's not the first exercise I've encountered that seemed out of place - I had to use generating functions on one of the earlier ones, although perhaps I missed a more elementary trick.

From the preface: "The exercises at the end of some of the chapters can be considered more challenging. They include some Putnam problems and some problems from the journal American Mathematical Monthly. They do not require more knowledge than is in the text material but often need a bit more persistence and some clever ideas. Students should be made aware that solutions to Putnam problems can be found on various Web sites and that solutions to Monthly problems are published; even so, the fun in such problems is in the attempt rather than in seeing someone else’s solution."

True enough, but after several hours banging my head against this problem, a hint would be great, if anyone has one...

 

[jbunniii]

P.S. Those are subscripts, not exponents: by

$$x_n = \frac{r_{n-1}(\theta)}{q_{n-1}(\theta)}$$

I meant only that $x_n$ is the ratio of two polynomials. I put subscripts on them because the polynomials are different for each $n$. It's a pain to calculate the polynomials explicitly, so I didn't. For now, the only information I am using about the polynomials is their order. My calculation of the orders was the result of a quick induction, which I didn't include. I'll follow up with more detail in the morning when I have my notes handy.

 

[stringy]

Oooooh, OK. That's my mistake then. I'll take another look at your work later on. I read your work till I got to your "mistake" and then tried a few approaches of my own that didn't yield much.

 

[jbunniii]

OK, here's some more detail about some of the calculations.

Recap of the notation:

$$p(x) = f(x) = x^3 - 3x + 3$$
$$q(x) = f'(x) = 3x^2 - 3$$
$$r(x) = r_1(x) = xq(x) - p(x) = 2x^3 - 3$$
$$h(x) = x - \frac{p(x)}{q(x)} = \frac{xq(x) - p(x)}{q(x)} = \frac{r(x)}{q(x)}$$
$$x_1 = \theta$$
$$x_{n+1} = h(x_n) = h^n(x_1) = h^n(\theta)$$

Then

$$h(\theta) = \frac{r(\theta)}{q(\theta)}$$

is a rational function of $\theta$, i.e., the ratio of two polynomials. The numerator has order 3, and the denominator has order 2.

Let us say that a rational function is "of type P" if it has the following properties:

1) the order of its numerator is a power of 3
2) the order of its denominator is even, and strictly less than the order of the numerator

I claim that $h^n$ (the composition of n copies of h) is a rational function of type P.

Proof of claim: it's true for $n = 1$. Assume that $n > 1$ and it's true up to $n - 1$. Then I may write

$$h^{n-1}(\theta) = \frac{r_{n-1}(\theta)}{q_{n-1}(\theta)}$$

where $r_{n-1}$ is a polynomial of order $3^{n-1}$ and $q_{n-1}$ is a polynomial of order $2k$, with $2k< 3^{n-1}$.

Then for $n > 1$ we have (dropping the argument $\theta$ for readability):

$$\begin{align*}x_{n+1} = h^n &= h(h^{n-1}) \\<br /> &= \frac{r(h^{n-1})}{q(h^{n-1})} \\<br /> &= \frac{r(r_{n-1}/q_{n-1})}{q(r_{n-1}/q_{n-1})} \\<br /> &= \frac{2(r_{n-1}/q_{n-1})^3 - 3}{3(r_{n-1}/q_{n-1})^2 - 3} \\<br /> &= \frac{2(r_{n-1})^3 - 3(q_{n-1})^3}{3(r_{n-1})^2(q_{n-1}) - 3(q_{n-1})^3}<br /> \end{align*}$$

The numerator of $h^n$ is the sum of two polynomials. The one with the highest order is $2(r_{n-1})^3$, which has order $3^n$.

The denominator of $h^n$ is the sum of two polynomials. The one with the highest order is $3(r_{n-1})^2(q_{n-1})$, which has order $2(3^{n-1}) + 2k$. Note that this order is even and strictly less than $3^n$.

So the claim is proved.

The next claim is that

$$\frac{p(x_n)}{q(x_n)}$$

is also a rational function (of $\theta$) of type P.

After proving that claim, I shall also prove another claim, namely that

$$\sum_{n=1}^{N}\frac{p(x_n)}{q(x_n)}$$

is also a rational function (of $\theta$) of type P.

From this (in particular, the fact that the numerator has odd order), it will follow that there is a real $\theta$ such that

$$\sum_{n=1}^{N}\frac{p(x_n)}{q(x_n)} = 0$$

I'll fill in the details of this in the next message, later today.

 

[jbunniii]

Claim:

$$\frac{p(x_n)}{q(x_n)}$$

is a rational function (of $\theta$) of type P.

Proof of claim:

$x_n$ is a rational function of type P, so it may be written as

$$x_n = h^{n-1}(\theta) = \frac{r_{n-1}(\theta)}{q_{n-1}(\theta)}$$

where $r_{n-1}$ is a polynomial of order $3^{n-1}$ and $q_{n-1}$ is a polynomial of order $2k < 3^{n-1}$.

Then

$$\begin{align*}\frac{p(x_n)}{q(x_n)} &= \frac{x_n^3 - 3x_n + 3}{3x_n^2 - 3} \\<br /> &= \frac{(r_{n-1}/q_{n-1})^3 - 3(r_{n-1}/q_{n-1}) + 3}{3(r_{n-1}/q_{n-1})^2 - 3} \\<br /> &= \frac{(r_{n-1})^3 - 3(r_{n-1})(q_{n-1})^2 + 3(q_{n-1})^3}{3(r_{n-1})^2(q_{n-1}) - 3(q_{n-1})^3}<br /> \end{align*}$$

The numerator is the sum of three polynomials. The one with the highest order is $(r_{n-1})^3$, which has order $3^n$.

The denominator is the sum of two polynomials. The one with the highest order is $3(r_{n-1})^2(q_{n-1})$, which has order $2(3^{n-1}) + 2k$. Note that this order is even and strictly less than $3^n$.

This proves the claim.

In the next message, I shall prove that

$$\sum_{n=1}^{N}\frac{p(x_n)}{q(x_n)}$$

is also a rational function, and that its numerator has odd order.

 

[jbunniii]

Claim:

$$\sum_{n=1}^{N}\frac{p(x_n)}{q(x_n)}$$

is a rational function, and its numerator has odd order.

Proof of claim: It suffices to show that the sum of two rational functions of type P is a rational function, with odd-ordered numerator. The general N case follows by a trivial induction.

Suppose, then, that

$$z(x) = \frac{a(x)}{b(x)} + \frac{c(x)}{d(x)}$$

where $a$ and $c$ are polynomials of order $3^n$ and $3^m$, respectively; and $b$ and $d$ are polynomials of order $2k < 3^n$ and $2j < 3^m$, respectively.

Then

$$z(x) = \frac{a(x)d(x) + c(x)b(x)}{b(x)d(x)}$$

The numerator is the sum of two polynomials. a(x)d(x) has order $3^n + 2j$. c(x)b(x) has order $3^m + 2k$. Therefore the order of the numerator is the larger of these two numbers, which in either case is an odd number.

This proves the claim.

It now follows that the numerator of

$$\sum_{n=1}^{N}\frac{p(x_n)}{q(x_n)}$$

has a real root, say $\theta_N$. Therefore, if I choose $x_1 = \theta_N$, I shall have

$$y_N = \sum_{n=1}^N \frac{p(x_n)}{q(x_n)} = 0$$

from which it follows immediately that

$$x_{N+1} = x_1$$

As each $x_{n+1}$ depends only on $x_n$, it follows that

$$x_{N+k} = x_k$$

for all $k$, which means that the sequence $(x_n)$ is periodic, and that its period divides $N$.

What remains to be shown is that $\theta_N$ can be chosen to satisfy two additional constraints:

1. The period of $(x_n)$ not only divides $N$, but actually equals $N$.

2. The sequence $(x_n)$ satisfies $q(x_n) \neq 0$ for all $n$.

 

[jbunniii]

How to prove the remaining issues?

1. is equivalent to proving that the chosen $\theta_N$ yields

$$y_N = \sum_{n=1}^N \frac{p(x_n)}{q(x_n)} = 0$$

but

$$y_M = \sum_{n=1}^M \frac{p(x_n)}{q(x_n)} \neq 0$$

if $M$ is a proper divisor of $N$.

It suffices to prove that if $\theta$ is any real root of the numerator of $y_N$, then it is not a root of the numerator of $y_M$. I'm not sure if this is true!

Alternatively, it suffices to prove that the numerator of $y_N$ has at least one real root that is not also a root of the numerator of $y_M$.

 

[jbunniii]

2. is true if and only if $x_n \neq \pm 1$ for all $n$.

$$x_{n+1} = \frac{r(x_n)}{q(x_n)}$$

so $x_{n+1}$ will be 1 if $r(x_n) = q(x_n)$, or

$$2x_n^3 - 3 = 3x_n^2 - 3$$

which will be true if $x_n = 0$ or $x_n = 3/2$.

Similarly, $x_{n+1}$ will be -1 if

$$2x_n^3 - 3 = -3x_n^2 + 3$$

or

$$5x_n^3 - 6 = 0$$

which is true if $x_n = (6/5)^{1/3}$

So this gives us a new set of forbidden values for $x_n$: 0, 3/2, $(6/5)^{1/3}$. These in turn will give an even larger set of forbidden values for $x_{n-1}$, and so on. I can't see any tractable way to ensure that my choice of $\theta_N$ results in a sequence $(x_n)$ that skips all of these forbidden values.

 

[stringy]

I was already thinking about that last night.

Any sequence that eventually sends the derivative to zero and hence blows Newton's method up is countable (obviously). And there are going to be countably many of these sequences (since we're dealing with functions that have finitely many zeros). So it's highly, highly, unlikely that if you're picking seed values from the continuum that you'd pick one that would make the method blow up.

Does this seem like a correct analysis? This is the only characterization that we can make (I think).

A very, very smart mathematician once gave me this advice: Take the simplest case you don't understand and figure it out. Then do that with the next simplest case. After you've got a handle on the simple cases, then hopefully you have gained insight into the general case. With that in mind, maybe we should try and prove the theorem true when N=2, i.e., find a seed value so that we generate a 2-periodic orbit.

 

[jbunniii]

I agree it's unlikely, in a sort of generic sense. But this isn't a probabilistic experiment, and the numbers involved - i.e., the $\theta$ value(s) that work and the illegal values for $x_n$ - are all ultimately functions of two simple polynomials.

Or, viewing it another way, it's also highly, highly unlikely that I would choose a seed value at random that would produce the desired periodicity.

I think focusing on the N=2 case is a good strategy at this point. I did play around with that case for a while yesterday and I have some notes scribbled, but I didn't actually find a solution. I'll take another look when I get home this evening and will post what I manage to come up with.

 

[stringy]

I agree it's unlikely, in a sort of generic sense. But this isn't a probabilistic experiment ...

My statement about it being unlikely to blow up was half said in humor.

On the other hand, determining whether a set is countable or not is saying something very specific. I think that's the best characterization we can make regarding this set. That was my only point.

 

[jbunniii]

My statement about it being unlikely to blow up was half said in humor.

On the other hand, determining whether a set is countable or not is saying something very specific. I think that's the best characterization we can make regarding this set. That was my only point.

Yes, agreed.

 

[jbunniii]

OK, here's an update. I solved the problem for N=1 and N=2. I'm afraid the solution for N=2 is pretty grungy (I used Wolfram Alpha for some of the symbol-pushing) and not very enlightening, but maybe if I stare at it for a while, a light will click on.

The N=1 case is straightforward:

$$x_{n+1} = x_{n}$$

if and only if $\theta$ is a real root of $p(x)$. This polynomial is third order but has only one real root, namely

$$\theta \approx -2.1038034027355365332$$

The closed form isn't very revealing:

$$\theta = \left(\frac{2}{3 - \sqrt{5}}\right)^{1/3} - \left(\frac{1}{2}(3 - \sqrt{5})\right)^{1/3}$$

The N=2 case goes as follows:

$$\begin{align*}<br /> x_3 = \frac{2(r/q)^3 - 3}{3(r/q)^2-3} &= \frac{2r^3 - 3q^3}{3r^2q - 3q^3} \\<br /> &= \frac{16\theta^9 - 153\theta^6 + 243\theta^4 +108\theta^3 -243\theta^2+27}{36\theta^8 -117\theta^6 - 108\theta^5 +243\theta^4 + 108\theta^3 -162\theta^2}<br /> \end{align*}$$

We want $x_3 = x_1 = \theta$, so setting the right hand side of the above to $\theta$ and simplifying, we get

$$20\theta^9 -117\theta^7 +45\theta^6 + 243\theta^5 -135\theta^4 -270\theta^3 + 243\theta^2 - 27 = 0$$

This 9th order equation has five real solutions, which are approximately as follows:

$$\theta = -2.1038034027355365332$$
$$\theta = -0.29725493940404253235$$
$$\theta = 0.52354012672943483306$$
$$\theta = 1.1161324135267332119$$
$$\theta = 1.2458005563848445681$$

[Side note: I made a small error initially; I mistranscribed the leading coefficient of the denominator as 38 instead of 36. Instead of 5 real solutions, I got only 3, and of course the sequences weren't quite periodic. Small perturbation = big change to solution set.]

Note that the first solution is actually the N=1 solution, i.e. its period is 1, not 2. It shows up here because 1 divides 2.

The other four solutions indeed yield sequences with period 2. I verified this by writing a short Matlab script as follows:

function doit

    theta1 = -2.1038034027355365332;  % period = 1; also a root of p(x)
    theta2 = -0.29725493940404253235;  % period = 2
    theta3 = 0.52354012672943483306;  % period = 2
    theta4 = 1.1161324135267332119; % period = 2
    theta5 = 1.2458005563848445681; % period = 2
    
    outfile = fopen('out.txt', 'w');
    
    for theta = [theta1 theta2 theta3 theta4 theta5];

        x1 = theta;
        x2 = h(x1);
        x3 = h(x2);
        
        fprintf(outfile, '-----------------\n');
        fprintf(outfile, 'x1 = %.15f\n', x1);
        fprintf(outfile, 'x2 = %.15f\n', x2);
        fprintf(outfile, 'x3 = %.15f\n', x3);
        
     end
     
     fclose(outfile);
	
end

function y = h(x)

    y = (2*x^3 - 3) / (3*x^2 - 3);
    
end

Here's the output:

-----------------
x1 = -2.103803402735537
x2 = -2.103803402735536
x3 = -2.103803402735536
-----------------
x1 = -0.297254939404043
x2 = 1.116132413526733
x3 = -0.297254939404043
-----------------
x1 = 0.523540126729435
x2 = 1.245800556384845
x3 = 0.523540126729435
-----------------
x1 = 1.116132413526733
x2 = -0.297254939404043
x3 = 1.116132413526733
-----------------
x1 = 1.245800556384845
x2 = 0.523540126729435
x3 = 1.245800556384845

I'll chew on this for a while and post again if I have any sort of analytical insight that can help make sense of these random looking numbers.

Hmm, notice that each x2 is also one of the x1's. Of course it's obvious why, but that's a fact that I hadn't thought about in my work up to this point. But this gives us an insight: namely that if there is to be a $\theta$ that yields a sequence of period 2, there also needs to be a second, distinct $\theta$ that works. Thus our complicated 9th order polynomial has to have at least two real roots. And since non-real roots come in complex conjugate pairs, a 9th order polynomial that has at least 2 real roots actually has to have at least 3 real roots (although it's not immediately clear that the third real root has to be distinct from the first two, i.e., it could be a repeated root). A similar argument should be possible for general N, but it becomes more complicated. This is starting to have a combinatoric flavor!

Of course, the above statements give us some information about what a solution must look like if it exists. But the problem is to prove the existence of the solution in the first place...

 

[Dick]

I'm not sure this direct polynomial approach is really leading you anywhere. My congratulations for pushing it so far, and maybe you will hit on something. If you get tired of pushing this and want to cheat, there is a literature on this subject. It's connected with a theorem of Sarkovskii. I started with an article you can find on the web by JA Walsh called The Dynamics of Newton's Method for Cubic Polyomials and just started following references. I can't say I've figured the whole thing out yet. But this looks horribly challenging for an elementary question. I think the solution is elementary, but subtle. Though maybe this is somehow a special case that has a 'duh' solution. I don't see it.

 

[stringy]

The Walsh article cited by Dick is an interesting read. It pops up in the first page of results on Google.

By the way, was this problem assigned by a professor or is this self-study?

 

[jbunniii]

Thanks for the info, I'm getting ready to declare that I've done enough with this problem and move on. Surely there's some clever trick that I'm missing, but I'm damned if I know what it is. This is self-study, or rather, self-challenge - I thought it would be fun to take some of the challenge problems in this book for a spin. Up until this one, they have been interesting and not too insanely hard - maybe 20-30 minutes of effort for most of them. This one is weird and I'm not sure what it's doing in an elementary analysis textbook, even as a challenge. I'm thinking about writing the authors to ask for a clue!

Cheers, and thanks for taking a look.

 

[jbunniii]

I've been reading a bit this morning about Sarkovskii's theorem. It certainly seems it will solve this problem. The Walsh article looks good. Another article of potential interest is:

K. Burns and B. Hasselblatt, "The Sharkovsky Theorem: A Natural Direct Proof"
http://math.arizona.edu/~dwang/BurnsHasselblattRevised-1.pdf

So it seems that 3-cycles are the key. If h has a 3-cycle, then h has cycles of every possible period.

I'll post more as I learn more, mainly for future reference in case anyone else stumbles across this problem.