Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Functional iteration and convergence

  1. Jun 13, 2010 #1
    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
     
  2. jcsd
  3. Jun 13, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Try this:

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

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

    Are you sure that the limit is [itex]\sqrt{10}[/itex] for any initial value or only for positive initial values? It seems to me that it might happen that if [itex]s_0[/itex] is negative, the sequence converges to [itex]-\sqrt{10}[/itex]. If this were my problem, I'd want to check that!
     
    Last edited by a moderator: Jun 19, 2010
  4. Jun 13, 2010 #3
    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
     
  5. Jun 13, 2010 #4
    Oh, and I have just checked but even picking negative initial values converges to positive root 10 not negative root 10
     
  6. Jun 13, 2010 #5

    Gib Z

    User Avatar
    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.
     
  7. Jun 13, 2010 #6
    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
     
  8. Jun 13, 2010 #7

    Gib Z

    User Avatar
    Homework Helper

    That's weird. Just to be certain, try -3, -3.5, -4, -3.16, and -rt10.
     
  9. Jun 13, 2010 #8
    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
     
  10. Jun 19, 2010 #9
    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?
     
  11. Jun 14, 2011 #10
    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
     
  12. Jun 14, 2011 #11

    Mute

    User Avatar
    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 [itex]\{s_n\}[/itex] 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

    [tex]s_{n+1} = \frac{s_n + a}{s_n + b + 1}[/tex]
    which has fixed points [itex]s^\ast = (1/2)(-b \pm \sqrt{b^2 + 4a})[/itex]. Note that when b^2 + 4a < 0 there are no fixed points.
     
  13. Jun 14, 2011 #12

    uart

    User Avatar
    Science Advisor

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

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

    For the function in question we have,

    [tex]f(x) = \frac{x+10}{x+1}[/tex]

    [tex]f'(x) = \frac{-9}{(x+1)^2}[/tex]

    [tex]f'(+\sqrt{10}) \simeq -0.52[/tex]

    [tex]f'(-\sqrt{10}) \simeq -1.93[/tex]
     
    Last edited: Jun 14, 2011
  14. Jun 14, 2011 #13

    uart

    User Avatar
    Science Advisor

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

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

    Case 1.

    Rearrange the above to

    [tex]x = \frac{9}{x+1} + 1[/tex]

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

    Case 2.

    You can also rearrange the original equation to

    [tex]x = \frac{9}{x-1} - 1[/tex]

    Only the negative root is numerically stable for this case.
     
    Last edited: Jun 14, 2011
  15. Jun 14, 2011 #14
    thanks everybody..!:smile:

    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?
     
  16. Jun 15, 2011 #15

    uart

    User Avatar
    Science Advisor

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook