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&#039;(x)|&gt;1 at the given solution.

For the function in question we have,

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

f&#039;(x) = \frac{-9}{(x+1)^2}

f&#039;(+\sqrt{10}) \simeq -0.52

f&#039;(-\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.