# Thread: Convergent iteration

1. ## Convergent iteration

Can someone help me with this problem?
Consider the fixed point iteration
$\displaystyle x_{k+1}=(m+1)x_k-{x_k}^2$, k=0,1,2,...where $\displaystyle 1\leq m \leq 2$
a) Show that the iteration converges for any initial guess $\displaystyle x_0$ satisfying $\displaystyle m-1/5 \leq x_0 \leq m+1/5$
b) Assume that the iteration converges, find m such that the method converges quadratically.

I think I got part a) by letting $\displaystyle g(x)=(m+1)x-x^2$, then take the derivative $\displaystyle g'(x)=2x+m+1$. I then show that there exists $\displaystyle 0<k<1$ such that $\displaystyle \mid g'(x) \mid <k$, and by a theorem this implies the iteration converges for any initial guess in the specified interval.
For part b), I need to find m such that $\displaystyle lim_{k\to \infty} \frac{|x_{k+1}-x|}{|x_k-x|^2}= lim_{k\to \infty} \frac{|(m+1)x_k-{x_k}^2-x|}{|x_k-x|^2}$ exists, but I don't get anywhere from here. Hope someone can give a hand.

2. Originally Posted by namelessguy
Can someone help me with this problem?
Consider the fixed point iteration
$\displaystyle x_{k+1}=(m+1)x_k-{x_k}^2$, k=0,1,2,...where $\displaystyle 1\leq m \leq 2$
a) Show that the iteration converges for any initial guess $\displaystyle x_0$ satisfying $\displaystyle m-1/5 \leq x_0 \leq m+1/5$
b) Assume that the iteration converges, find m such that the method converges quadratically.

I think I got part a) by letting $\displaystyle g(x)=(m+1)x-x^2$, then take the derivative $\displaystyle g'(x)=2x+m+1$. I then show that there exists $\displaystyle 0<k<1$ such that $\displaystyle \mid g'(x) \mid <k$, and by a theorem this implies the iteration converges for any initial guess in the specified interval.
For part b), I need to find m such that $\displaystyle lim_{k\to \infty} \frac{|x_{k+1}-x|}{|x_k-x|^2}= lim_{k\to \infty} \frac{|(m+1)x_k-{x_k}^2-x|}{|x_k-x|^2}$ exists, but I don't get anywhere from here. Hope someone can give a hand.
Assuming that the itteration converges it is obvious it must converge to either $\displaystyle x=0$ or $\displaystyle x=m$, but it is easy to show that itteration will not converge to $\displaystyle x=0$.

So suppose $\displaystyle x_n=m+\varepsilon$

Then:

$\displaystyle x_{n+1}=(m+1)(m+\varepsilon)-(m_\varepsilon)^2=m+\varepsilon(1-m)-\varepsilon^2$

So if $\displaystyle m=1$ the itteration converges quadraticaly to $\displaystyle x=m=1$

CB