Functional iteration and convergence

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

thanks in advance

 

[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!

 

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

thanks in advance

 

[bbb999]

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

 

[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.

 

[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

 

[Gib Z]

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

 

[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

 

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

 

[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

 

[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.

 

[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$$

 

[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.

 

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

 

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

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.