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

Fixed Point Iteration Requirements

  1. Nov 15, 2007 #1

    I wrote a numerical analysis midterm earlier this week and there was one question I couldn't figure out. I was wondering if anyone had some insight.

    What I've been told and what I've read in many many places is that
    f(x) will converge to a fixed point on an interval I if
    1. f(x) is continuous and differentiable on I
    2. |f'(x)|<1 on I

    Now the question I was posed was given [itex] x_{n+1}=\frac{1}{3}(x_n^2+2)[/itex] prove that [itex]x_n\rightarrow 1[/itex] as [itex]n\rightarrow\infty [/itex] if [itex] -2<x_0<2[/itex] (that is prove [itex]x_{n+1}[/itex] is between [itex]x_n[/itex] and 1 when [itex]n \geq 1[/itex])

    What was most natural to me was to find the interval where |f'(x)|<1 which happens to be on [itex](-\frac{3}{2},\frac{3}{2})[/itex]. It easy to see (but not so easy to prove) that the interval (-2,2) will work as well. How would you go about showing that? Do think that it would be possible to generalize this such that the requirement |f'(x)|<1 would not be needed for fixed point iteration?

    Anyway, hope this interest someone else.
  2. jcsd
  3. Nov 15, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you looked at a few of the sequences produced from different starting points? The behavior is very easy to describe... it's the sort of behavior whose existence I would expect to be very easy to prove directly (particularly due to the algebraically simple nature of the iteration).
  4. Nov 15, 2007 #3
    Yes I have looked at different starting points. I did show that for all starting points on (-2,2) you end up on (1,2). I also noted that the iteration function was strictly decreasing after the first iteration but I wasn't able to show that. I guess if I was more specific I would have said that was my question.
  5. Nov 15, 2007 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    All of them? Are you sure?

    In other words,
    If y = (x^2 + 2)/3 and x is in (1, 2), then y < x

    But you can do better than that... you know that it's strictly decreasing to 1; in other words, the distance from 1 is decreasing. This suggests it's more natural to seek to prove
    |y-1| < |x-1|.​
  6. Nov 15, 2007 #5
    Whoops. no. that should have been [itex](\frac{2}{3},2)[/itex]
    but I guess it doesn't matter much because I had already showed that it converges on [itex](-\frac{3}{2},\frac{3}{2})[/itex]

    So then it remains to be shown that on [itex](\frac{3}{2},2)[/itex] that

    I'm still confused. I do know that it is strictly decreasing but I don't know how to prove it.
    What you're suggesting to me is prove:

    [tex]|x_{n+1}-1|<|\frac{x_n}{3}-\frac{1}{3}|[/tex] for any [tex]x_n\in(\frac{3}{2},2)[/tex]
    I still don't know how to do that though. I there just something really stupid that I'm missing.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook