# Fixed point iteration

1. Apr 19, 2010

### math8

Let p>0 and $$x = \sqrt{p+\sqrt{p+\sqrt{p+ \cdots }}}$$ , where all the square roots are positive. Design a fixed point iteration $$x_{n+1} = F (x_{n})$$ 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 $$x_{n+1}=F(x_{n})= \sqrt{p+x_{n}}$$ so x is a fixed point for F since F(x)=x.
Now let $$g(x)=\sqrt{p+x}$$.
We have $$g'(x)=\frac{1}{2 \sqrt{p+x} }$$

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

From there I am not sure how to proceed to obtain convergence for $$x_{0} > -p +\frac{1}{4}$$ .

Last edited: Apr 19, 2010
2. Apr 19, 2010

### D H

Staff Emeritus
What are the necessary and sufficient conditions for convergence of a fixed point iterator?

3. Apr 19, 2010

### math8

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).

4. Apr 20, 2010

### D H

Staff Emeritus
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:

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

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

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

Either way, you can use the results you have already obtained to show that the fixed point iteration converges.