1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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