# Functional iteration and convergence

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?

HallsofIvy
Homework Helper
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:
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?

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

Gib Z
Homework Helper
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.

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

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

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

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?

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

Mute
Homework Helper
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.

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:
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:
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?

uart