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

Homework Help: Fixed point iteration

  1. Apr 19, 2010 #1
    Let p>0 and [tex] x = \sqrt{p+\sqrt{p+\sqrt{p+ \cdots }}}[/tex] , where all the square roots are positive. Design a fixed point iteration [tex]x_{n+1} = F (x_{n})[/tex] with some F which has x as a fixed point. We prove that the fixed point iteration converges for all choices of initial guesses greater than -p+1/4.



    Let [tex]x_{n+1}=F(x_{n})= \sqrt{p+x_{n}}[/tex] so x is a fixed point for F since F(x)=x.
    Now let [tex]g(x)=\sqrt{p+x}[/tex].
    We have [tex] g'(x)=\frac{1}{2 \sqrt{p+x} } [/tex]


    I can see that for [tex] x > -p + 1/4 [/tex], we have that g'(x) <1.

    From there I am not sure how to proceed to obtain convergence for [tex] x_{0} > -p +\frac{1}{4} [/tex] .
     
    Last edited: Apr 19, 2010
  2. jcsd
  3. Apr 19, 2010 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    What are the necessary and sufficient conditions for convergence of a fixed point iterator?
     
  4. Apr 19, 2010 #3
    It (g(x)) must be continuously differentiable on a closed interval [a,b], and g([a,b]) C[a,b].
    Also, max {|g' (x)|: x in [a,b] } < 1.

    Then the iterations converge to the unique fixed point for any initial guess x_0 in [a,b].

    I can see that for x > -p + 1/4 , we have that g'(x) < 1. So can I say that max {|g' (x)|: x> -p + 1/4 } < 1 ? Also, I am not quite sure how to deal with the fact that the interval that I have in this case is an open interval (-p + 1/4 , infty).
     
  5. Apr 20, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You can look at the set [itex][a,\infty)[/tex] in two ways:

    1. As the limit of a closed interval as the upper bound goes to infinity:

    [tex][a,\infty) = \lim_{b\to\infty} [a,b][/tex]


    2. As the union of all closed intervals [a,b]:

    [tex][a,\infty) = \bigcup_{b>a}\,[a,b][/tex]


    Either way, you can use the results you have already obtained to show that the fixed point iteration converges.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook