2

I've been investigating into situations where the N-R method iterates between two $x$ values endlessly. So far I have derived that the relationship between the two values of $x$ should be as follows: $$\frac{f(x_{even})}{f'(x_{even})} = -\frac{f(x_{odd})}{f'(x_{odd})}$$

where $x_0$ is the initial value of $x$ to be taken.

This can be derived as follows:

Let $a$ denote the even $x$ iterations and let $b$ denote the odd $x$ iterations.

All values of $a$ will be equal as will all values of $b$ because the method returns back to the same point an even amount of iterations later.

Hence, using the forumla, $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)},$$ we can gather that,

$$b=a-\frac{f(a)}{f'(a)}$$

and,

$$a=b-\frac{f(b)}{f'(b)}$$

Re-arranging these gives the result, $$\frac{f(a)}{f'(a)}=-\frac{f(b)}{f'(b)}$$

as required.

I'm curious as to what general equations/types of curves there would be in which this situation would occur (if any) where there are real roots to be found, as I'm having little luck finding out myself.

Chris Wilson
  • 78
  • I think your condition might not be sufficient. Consider for example $f(x)=x^2$. Then the pair $(x,-x)$ satisfies your condition, but they do not form a two-cycle for Newton iteration. – felipeh Mar 28 '18 at 18:28
  • That situation would be invalid, as if we set $x_0$ to any $x$ value, then $x_1$ would not be be the negative of the initial $x$ value – Chris Wilson Mar 30 '18 at 12:39
  • You also need to take one of the previous two equations into account. Or also include that into the final equation which gives $$\frac{f(a)}{f'(a)}=-\frac{f(a-f(a)/f'(a))}{f'(a-f(a)/f'(a))}$$ as the full condition to solve. – Lutz Lehmann Mar 30 '18 at 14:57
  • @LutzL But, $a-f(a)/f'(a) = b$ so I guess it's the same. – Mark McClure Mar 30 '18 at 15:06
  • The point is that in this way you have one equation for one variable. Or you can take 2 equations for 2 variables. You seemed to conclude with one equation for 2 variables which would lose you information. – Lutz Lehmann Mar 30 '18 at 15:46
  • Yeah the two equations that I listed in the post could be manipulated to give that result as you said, though I didn't mention that in the post as the condition with 1 variable to solve. – Chris Wilson Mar 30 '18 at 16:03

1 Answers1

1

Newton's method is often understood as "riding the tangent line" to the root. Thus, the following image might represent two Newton steps from the green initial point:

enter image description here

From here, a simple continuity argument based on the following animation indicates that period 2 orbits often occur near an extreme that misses the $x$-axis:

enter image description here

Mark McClure
  • 30,510
  • I've updated the question and specified that I'm looking for situations where there are real roots to be found. Also that bottom animation doesn't satisfy the condition where the $x_{even}$ values are all the same as are all the $x_{odd}$'s – Chris Wilson Mar 30 '18 at 12:42
  • @ChrisWilson I'm not quite sure I follow. The function graphed in the answer is $f(x)=x^2+1$ and when we iterate $N(x)=(x^2-1)/(2x)$, we find that $\pm 1/\sqrt{3}$ forms a 2-cycle. With those values for $a$ and $b$, it's certainly the case that $f(a)/f'(a)=-f(b)/f'(b)$. The real root issue seems quite superfluous' it's easy to modify the example so that the function has real roots. The animation is only meant to be hint. I'm pretty certain that it's relevant to your exploration. – Mark McClure Mar 30 '18 at 15:05
  • Oh right, I misinterpreted the animation. I thought it was illustrating the N-R method being carried out and iterated on $f(x)$, whereas from what I'm gathering now it's showing the values of $x$ for which a 2-cycle forms. Could you provide one of these modified examples where the condition $f(a)/f'(a)=-f(b)/f'(b)$ would be met and a 2-cycle is formed and "gets stuck" for a graph that has real roots? – Chris Wilson Mar 30 '18 at 15:24
  • @ChrisWilson Right - the animation shows two Newton iterations for $f(x)=x^2+1$; the different frames in the animation show different starting values shown as green in the figure. For some starting values, the second iterate lies to the left of the green dot; for others, it lies to the right. By continuity, there should be a value where the second iterate hits the green dot exactly. It's not particularly important that the function is a quadratic; a cubic that narrowly misses the $x$-axis near one extreme should work as well. – Mark McClure Mar 30 '18 at 15:39
  • A really interesting example is $f(x)=x^5-x-1$. Not only is there a two cycle, but it's attractive! – Mark McClure Mar 30 '18 at 15:40
  • Okay, so using the condition $\frac{f(x_0)}{f'(x_0)}=-\frac{f(x_0-f(x_0)/f'(x_0))}{f'(x_0-f(x_0)/f'(x_0))}$ presented by LutzL, we could solve that equation to find which starting values of $x$ using the N-R method on the curve $f(x)=x^5-x-1$ would result in a 2 cycle iteration? – Chris Wilson Mar 30 '18 at 17:54
  • @ChrisWilson I think it's quite a bit easier than that. If, as I suggest, the periodic cycle is attractive, it should be just a matter of iterating from a critical point of $N(x)$. You might have to try more than one critical point but there's only a few of them. – Mark McClure Mar 30 '18 at 20:30