Functional iteration and convergence

1. Jun 13, 2010

bbb999

Hey,

I am working with the equation y=(x+10)/(x+1), and have calculating the iterations of the sequence s_(n+1)=(s_n + 10)/(s_n + 1).

I find that whatever value of s(1) is chosen (the initial value) the sequence converges to root 10. However I am now trying to prove why this happens, and I have been told I should be able to prove it using just a standard test for convergence. Can anyone help?

2. Jun 13, 2010

HallsofIvy

Try this:

First suppose the limit does exist and call the limit "S". Then taking the limit of both sides of $s_{n+1}= (s_n+10)/(s_n+1)$, each limit is S: $S= (S+ 10)/(S+ 1)$. Multiplying both sides by S+ 1, $S(S+1)= S^2+ S= S+ 10$ so that $S= \pm\sqrt{10}$.

Now, suppose $s_0$ is some number less than $\sqrt{10}$. Then show, perhaps by induction, that $\{s_n\}$ is an increasing sequence and has an upper bound. By the "monotone convergence" property, then, it does convertg. Similarly, if $s_0> \sqrt{10}$, you can show it is a decreasing sequence having a lower bound.

Are you sure that the limit is $\sqrt{10}$ for any initial value or only for positive initial values? It seems to me that it might happen that if $s_0$ is negative, the sequence converges to $-\sqrt{10}$. If this were my problem, I'd want to check that!

Last edited by a moderator: Jun 19, 2010
3. Jun 13, 2010

bbb999

thanks, ok I understand the part about negative initial values converging to -root 10, and I understand how to find the limit using the fraction you gave.

But I am struggling with what you mean about finding an upper and lower bound to show it converges. What standard test would that use?

4. Jun 13, 2010

bbb999

Oh, and I have just checked but even picking negative initial values converges to positive root 10 not negative root 10

5. Jun 13, 2010

Gib Z

1)Halls is referring you to the Monotone Convergence theorem: If a sequence of real numbers has increasing and has an upper bound M, then the sequence converges.

2) Which negative values did you try? Try some more.

6. Jun 13, 2010

bbb999

I have tried a range of negative values such as -0.5, -5.5, -100 and they all result in convergence to positive root 10

7. Jun 13, 2010

Gib Z

That's weird. Just to be certain, try -3, -3.5, -4, -3.16, and -rt10.

8. Jun 13, 2010

bbb999

I have tried all of these values and they all converge to positive root 10 except for negative root 10 which stays at that point

9. Jun 19, 2010

bbb999

Can anyone confirm that this is correct: that for every initial value other than -root 10, the sequence converges to root 10 and in the case of -root 10 it remains at that point?

10. Jun 14, 2011

izdihar

Hye, I had the same problem like bbb999. I already tried all positive and negative values and the sequence will converge to positive square root ten. How about negative square root ten? huhu

11. Jun 14, 2011

Mute

It definitely looks like the positive root might be the only stable fixed point. The strategy HallsofIvy suggested on the first run of this thread won't work because the sequence $\{s_n\}$ isn't monotonically increasing or decreasing, as is easy to see from inspecting the cobweb diagram. See this site for an applet: http://www.emporia.edu/math-cs/yanikjoe/Chaos/CobwebPlot.htm

Even near the negative root the cobweb diagram trajectories end up shooting back over towards the positive root after a few iterations. This is by no means a proof, but it is suggestive.

I suspect part of the underlying reason for the strange behavior is the divergence at x = -1. It looks like this gives rise to a geometry that makes the negative root completely unstable and the positive root universally stable.

Perhaps some understanding can be found by studying the more general

$$s_{n+1} = \frac{s_n + a}{s_n + b + 1}$$
which has fixed points $s^\ast = (1/2)(-b \pm \sqrt{b^2 + 4a})$. Note that when b^2 + 4a < 0 there are no fixed points.

12. Jun 14, 2011

uart

Yes Mute, only the positive root is numerically stable for the given function under fixed point iteration.

Fixed point iteration of the form $x = f(x)$ is not numerically stable when $|f'(x)|>1$ at the given solution.

For the function in question we have,

$$f(x) = \frac{x+10}{x+1}$$

$$f'(x) = \frac{-9}{(x+1)^2}$$

$$f'(+\sqrt{10}) \simeq -0.52$$

$$f'(-\sqrt{10}) \simeq -1.93$$

Last edited: Jun 14, 2011
13. Jun 14, 2011

uart

Izdihar, here's some other ways we could find a function that converges to sqrt(10) under fixed point iteration.

Take $(x+1)(x-1) = 9$. It's easy to show that this has solutions of $\pm \sqrt{10}$.

Case 1.

Rearrange the above to

$$x = \frac{9}{x+1} + 1$$

You can show that only the positive root is numerically stable for this case.

Case 2.

You can also rearrange the original equation to

$$x = \frac{9}{x-1} - 1$$

Only the negative root is numerically stable for this case.

Last edited: Jun 14, 2011
14. Jun 14, 2011

izdihar

thanks everybody..!

uart:

"Fixed point iteration of the form x=f(x) is not numerically stable when |f′(x)|>1 at the given solution."
is this theorem?

15. Jun 15, 2011

uart

Yes, the absolute value of the derivative must be less than one on an interval containing the fixed point for it to be a "attractor" fixed point.

Similar Threads - Functional iteration convergence Date
B Characteristics of the parent logarithmic function Yesterday at 6:58 PM
I Trying to get an explicit function(ish) Sunday at 5:39 PM
B Beginner function question Feb 17, 2018
Fractional iteration of a function Sep 9, 2015
Iterative functional equation Mar 27, 2003