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: Proof of convergence

  1. Mar 8, 2008 #1
    [SOLVED] Proof of convergence

    1. The problem statement, all variables and given/known data
    Let [itex] \alpha[/tex] be a fixed point of [tex]x = g(x)[/tex] and let [tex](x_n)[/tex] be the sequence generated by the fixed point iteration scheme. Using the first two terms of the Taylor series for
    [tex]g(x)[/tex] about [itex]\alpha[/tex] we can get an approximation for [tex]g(x_n)[/tex]:
    [itex]g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)[/tex]
    (Assuming the terms in the sequence are close to α we have neglected non-
    linear terms.)

    Show that [itex]|x_n - \alpha| = |x_0 - \alpha||g'(\alpha)|^{n}[/tex] for all n [tex] \geq 1[/tex] hence show that the sequence [tex](x_n)[/tex] converges to [itex]\alpha[/tex] for [tex]g'(x)< 1[/tex]

    2. Relevant equations

    3. The attempt at a solution
    I'm not so worried about the proving second part (looks obvious if the first part is true) but before trying to prove the first I want to try a couple of examples and see whats happening if I can.
    If I suppose that my function [tex] g(x) = \sqrt{x+1}[/tex] then the value of a fixed point [itex] \alpha = \frac{1+\sqrt{5}}{2}[/tex]
    Now if I let [tex]x_0 = 2[/tex] and set n = 1 then [tex]x_1 = \sqrt{2+1}[/tex] and I am under the impression that I can now show:
    [itex]|\sqrt{3} - \alpha| = |2 -\alpha||\frac{1}{2}(\frac{1}{\sqrt{\alpha+1}})|[/tex]
    [tex]\Rightarrow |\sqrt{3} - \frac{1+\sqrt{5}}{2}| = |2 - \frac{1+\sqrt{5}}{2}||\frac{1}{2}(\frac{1}{\sqrt{\frac{1+\sqrt{5}}{2}+1}})|[/tex]
    But this is false!...How am I misinterpreting the given statement or what have I done wrong?
    Please don't prove the problem for me.
    Last edited: Mar 8, 2008
  2. jcsd
  3. Mar 8, 2008 #2


    User Avatar
    Science Advisor

    You are right, it is not true- it is only approximately true. After all, you neglected powers higher than the first in the Taylor expansion.

    Proving [itex]|x_n- \alpha|=|x_0- \alpha||g'(\alpha)^n[/itex], to first order, by induction, is pretty easy if you replace [itex]g(x_n)[/itex] and [itex]g(\alpha)[/itex] in [itex]g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)[/itex] by [itex]x_{n+1}[/itex] and [itex]\alpha[/itex].
    Last edited by a moderator: Mar 8, 2008
  4. Mar 9, 2008 #3
    Cheers for that HallsofIvy, it was the presence of an equals sign, not approximately equals that was throwing me; I couldn't see why it should have been true :redface:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook