# Homework Help: Proof of convergence

1. Mar 8, 2008

### GregA

[SOLVED] Proof of convergence

1. The problem statement, all variables and given/known data
Let $\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 $$g(x)$$ about [itex]\alpha[/tex] we can get an approximation for $$g(x_n)$$: [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 $$\geq 1$$ hence show that the sequence $$(x_n)$$ converges to [itex]\alpha[/tex] for $$g'(x)< 1$$ 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 $$g(x) = \sqrt{x+1}$$ then the value of a fixed point [itex] \alpha = \frac{1+\sqrt{5}}{2}[/tex] 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: [itex]|\sqrt{3} - \alpha| = |2 -\alpha||\frac{1}{2}(\frac{1}{\sqrt{\alpha+1}})|[/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}})|$$ 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. Mar 8, 2008 ### 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 [itex]|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$.

Last edited by a moderator: Mar 8, 2008
3. Mar 9, 2008

### 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