Does This Sequence Converge to the Fixed Point?

[GregA]

[SOLVED] Proof of convergence

Homework Statement

Let [itex]\alpha[/tex] be a fixed point of $$x = g(x)$$ and let $$(x_n)$$ be the sequence generated by the fixed point iteration scheme. Using the first two terms of the Taylor series for<br /> $$g(x)$$ about [itex]\alpha[/tex] we can get an approximation for $$g(x_n)$$:<br /> [itex]g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)[/tex]<br /> (Assuming the terms in the sequence are close to α we have neglected non-<br /> linear terms.)<br /> <br /> Show that [itex]|x_n - \alpha| = |x_0 - \alpha||g'(\alpha)|^{n}[/tex] for all n $$\geq 1$$ hence show that the sequence $$(x_n)$$ converges to [itex]\alpha[/tex] for $$g'(x)< 1$$<br /> <h2>Homework Equations</h2><br /> <h2>The Attempt at a Solution</h2><br /> 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 what's happening if I can.<br /> If I suppose that my function $$g(x) = \sqrt{x+1}$$ then the value of a fixed point [itex]\alpha = \frac{1+\sqrt{5}}{2}[/tex]<br /> Now if I let $$x_0 = 2$$ and set n = 1 then $$x_1 = \sqrt{2+1}$$ and I am under the impression that I can now show:<br /> [itex]|\sqrt{3} - \alpha| = |2 -\alpha||\frac{1}{2}(\frac{1}{\sqrt{\alpha+1}})|[/tex]<br /> $$\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}})|$$<br /> But this is false!...How am I misinterpreting the given statement or what have I done wrong?<br /> Please don't prove the problem for me.[/itex][/itex][/itex][/itex][/itex][/itex][/itex]

 

[HallsofIvy]

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 $|x_n- \alpha|=|x_0- \alpha||g'(\alpha)^n$, to first order, by induction, is pretty easy if you replace $g(x_n)$ and $g(\alpha)$ in $g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)$ by $x_{n+1}$ and $\alpha$.

 

[GregA]

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