# Thread: Fixed-point iteration 'show that' exercise

1. ## Fixed-point iteration 'show that' exercise

Hi,

problem:

The iteration defined by $x_{k+1} = \frac{1}{2}(x^2_k+c)$, where $0,
has two fixed points $\xi_1, \xi_2$ where $0<\xi_1<1<\xi_2$. Show that

$x_{k+1} - \xi_1 = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1), k=0,1,2,\cdots,$

and deduce that $\lim_{k\rightarrow \infty}x_k=\xi_1 \;\textrm{if}\; 0\leq x_0<\xi_2$. How does the iteration behave for other values of $x_0$?

attempt at solution:

$x_{k+1}-\xi_1 = \frac{1}{2}(x^2_k+c) - \xi_1
$

and since,

$\frac{1}{2}(\xi^2_1+c)=\xi_1 \Rightarrow c = 2\xi_1-\xi^2_1$

we have that,

$x_{k+1}-\xi_1 = \frac{1}{2}(x^2_k-\xi^2_1) = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1)$

I am a bit confused regarding the limit-question. If $0\leq x_0 < \xi_2$ and $1<\xi_2$ it means that $x_0$ could be any number larger than 1 but smaller than $\xi_2$. I figure that I could then choose some $x_0$ such that $x_1 > x_0$, in other words we would be moving away from $\xi_1$.

Now if $0 \leq x_0 < \xi_1$ instead of $0\leq x_0 <\xi_2$, I could see how $\lim_{x\rightarrow \infty}x_k= \xi_1$.

As I rarely have the insight to find errors in problems, I'm sure there's something I'm not getting here, and therefore I ask for you help.

Thanks.

2. Originally Posted by Mollier
Hi,

problem:

The iteration defined by $x_{k+1} = \frac{1}{2}(x^2_k+c)$, where $0,
has two fixed points $\xi_1, \xi_2$ where $0<\xi_1<1<\xi_2$. Show that

$x_{k+1} - \xi_1 = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1), k=0,1,2,\cdots,$

and deduce that $\lim_{k\rightarrow \infty}x_k=\xi_1 \;\textrm{if}\; 0\leq x_0<\xi_2$. How does the iteration behave for other values of $x_0$?

attempt at solution:

$x_{k+1}-\xi_1 = \frac{1}{2}(x^2_k+c) - \xi_1
$

and since,

$g(\xi_1)=\frac{1}{2}(\xi^2_1+c)=\xi_1 \Rightarrow c = 2\xi_1-\xi^2_1$

we have that,

$x_{k+1}-\xi_1 = \frac{1}{2}(x^2_k-\xi^2_1) = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1)$

I am a bit confused regarding the limit-question. If $0\leq x_0 < \xi_2$ and $1<\xi_2$ it means that $x_0$ could be any number larger than 1 but smaller than $\xi_2$. I figure that I could then choose some $x_0$ such that $x_1 > x_0$, in other words we would be moving away from $\xi_1$.

Now if $0 \leq x_0 < \xi_1$ instead of $0\leq x_0 <\xi_2$, I could see how $\lim_{x\rightarrow \infty} = \xi_1$.

As I rarely have the insight to find errors in problems, I'm sure there's something I'm not getting here, and therefore I ask for you help.

Thanks.
A fixed point is a solution of:

$x = \frac{1}{2}(x^2+c)$

for obvious reasons

CB

3. Originally Posted by CaptainBlack
A fixed point is a solution of:

$x = \frac{1}{2}(x^2+c)$

for obvious reasons

CB
Hi,

if I solve $x= \frac{1}{2}(x^2+c)$ for $x$ and call the solutions $\xi_1$ and $\xi_2$ I get,

$\xi_1 = 1 - \frac{1}{2}\sqrt{4-4c}$

and

$\xi_2 = 1 + \frac{1}{2}\sqrt{4-4c}$

Since $0, then $\xi_2<2$ and so I need to show that $\lim_{k\rightarrow\infty}x_k=\xi_1$ when $0\leq x_0<2$.

If my function, call it $g(x) = \frac{1}{2}(x^2+c)$ was a contraction in $(0,2)$, I think (not sure) I could find a way to show that it converges to $\xi_1 for x_0\in (0,2)$. The problem as I see it is that $g'(x)=x$ and so it cannot be a contraction on $(0,2).$

Perhaps I could use my previous result, that is
$
x_{k+1}-\xi_1=\frac{1}{2}(x_k+\xi_1)(x_k-\xi_1),$

and rewrite it as,

$|x_k-\xi_1|=\frac{2|x_{k+1}-\xi_1|}{x_k+\xi_1}.$

I would like $|x_k-\xi_1|$ to approach zero as $k$ goes to infinity, but I don't know how to show this...

I could use a hand here, thanks.

4. if:

$\xi_1=1-\sqrt{1-c}$

$\xi_2=1+\sqrt{1-c}$

$x_1<\xi_2\$ (which implies that $x_k<\xi_2$ for all $k=1, 2, ..$ )

and:

$x_{k+1} - \xi_1 = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1)$

Then:

$\varepsilon_{k+1}=x_{k+1}-\xi_1=\frac{1}{2}(x_k+\xi_1)\varepsilon_k$

etc (to complete this you need to show that there exists a $k >0$ such that $|x_k+\xi_1|)

CB

5. Originally Posted by CaptainBlack
if:

$\xi_1=1-\sqrt{1-c}$

$\xi_2=1+\sqrt{1-c}$

$x_1<\xi_2\$ (which implies that $x_k<\xi_2$ for all $k=1, 2, ..$ )

CB
So if $x_1<\xi_1$ and $x_2=\frac{1}{2}x_1+\frac{1}{2}c$ then I am sure that
$x_2<\xi_2$?
I know for sure that $\frac{1}{2}x_1<\xi_2$ and I also know that $\frac{1}{2}c<\frac{1}{2}$, but I am not able to see that $x_2$ must be smaller than $\xi_2$.
All these inequalities are confusing me..

Thank you for being so patient with me CB!
Time to donate some cash to MHF

6. Originally Posted by Mollier
So if $x_1<\xi_1$ and $x_2=\frac{1}{2}x_1+\frac{1}{2}c$ then I am sure that
$x_2<\xi_2$?
I know for sure that $\frac{1}{2}x_1<\xi_2$ and I also know that $\frac{1}{2}c<\frac{1}{2}$, but I am not able to see that $x_2$ must be smaller than $\xi_2$.
All these inequalities are confusing me..

Thank you for being so patient with me CB!
Time to donate some cash to MHF
$x_2=\frac{1}{2}(x_1^2+c)<\frac{1}{2}(\xi_2^2+c)=\f rac{1}{2}(1+2\sqrt{1-c}+(1-c)+c)=1+\sqrt{1-c}=\xi_2$

7. Hi,

$2\left(\frac{\epsilon_{k+1}}{\epsilon_k}\right)=x_ k+\xi_1$

$2\left(\frac{\epsilon_{k+1}}{\epsilon_k}\right)<\x i_2+\xi_1=2$

so,

$\frac{\epsilon_{k+1}}{\epsilon_k}<1$

Is this what you had in mind CB?

8. Not quite since that is insufficient to prove that $\varepsilon_n \to 0$ as $n \to \infty$

CB

9. Hi,

here's another try!

$x_{k+1}-\xi_1 = \frac{1}{2}(x_k+\xi_1)(x_k-\xi_1)$

Since $\xi_2+\xi_1 = 2$, and we have that $x_0<\xi_2$ and in fact that $x_k<\xi_2$ for $k=1,2,\cdots$, then

$x_k+\xi_1 < 2.$

We end up with,

$\epsilon_{k+1} = \frac{1}{2}(x_k+\xi_1)\epsilon_k,$

and so $\epsilon_{k+1}$ is decreasing and approaching zero as $k\rightarrow\infty$.

Perhaps I will approach the correct answer as $\textrm{(number of attempts)}\rightarrow\infty$.

10. Here's perhaps a better way of writing this..

$x_{k+1}-\xi_1 < \frac{1}{2}(\xi_2+\xi_1)(x_k-\xi_1)$

since $\xi_2+\xi_1 = 2$ we have that,

$x_{k+1}-\xi_1 < x_k-\xi_1$

Since $x_{k+1}=\frac{1}{2}(x^2_k+c)$ and
$c = 2\xi_1-\xi^2_1$, we have that

$\frac{1}{2}(x_k+\xi_1)(x_k-\xi_1) < (x_k-\xi_1)$ and so

$x_k+\xi_1 < 2$. Good times.

If I now look at what happens if $x_0>\xi_2$ in a similar fashion, I get that,
$x_k+\xi_1>2$ and so the sequence will not converge to $\xi_2$.

I think this is because the derivative of $\frac{1}{2}(x^2+c)$ is $x$ and when $x_0>\xi_2$ it means that $x_0>1$ and so the derivative is larger than 1. If our function has a derivative larger than 1 in the interval we are working on, fixed-point iteration will not converge.

Is this better?

11. Originally Posted by Mollier
Hi,

problem:

The iteration defined by $x_{k+1} = \frac{1}{2}(x^2_k+c)$, where $0,
has two fixed points $\xi_1, \xi_2$ where $0<\xi_1<1<\xi_2$. Show that
...
As I rarely have the insight to find errors in problems, I'm sure there's something I'm not getting here, and therefore I ask for you help.

Thanks.
May be you are looking for this.
I shall denote the sequence by $\{x_{k}\}_{k\in\mathbb{N}_{0}}$ for $c\in\mathbb{R}_{0}^{+}$ and define
$x_{k+1}:=\frac{1}{2}\big(x_{k}^{2}+c\big)$ for $k\in\mathbb{N},\rule{2cm}{0cm}(1)$
where $x_{0}\in\mathbb{R}_{0}^{+}$.
It is clear that for $c,x_{0}\in\mathbb{R}_{0}^{+}$, $\{x_{k}\}_{k\in\mathbb{N}_{0}}\subset\mathbb{R}_{0 }$.
Now, for $k\in\mathbb{N}$, compute
$x_{k+1}-x_{k}=\frac{1}{2}\big(x_{k}^{2}-x_{k-1}^{2}\big)$
................_ $=\frac{1}{2}\big(x_{k}+x_{k-1}\big)\big(x_{k}-x_{k-1}\big).$
Let $\varphi(\lambda):=\lambda(\lambda-2)+c$ for $\lambda\in\mathbb{R}$.
Repeating the procedure above with the abbreviation that the empty product
is the unity, we get for all $k\in\mathbb{N}_{0}$ that
$x_{k+1}-x_{k}=\dfrac{1}{2^{k-1}}\Bigg[\displaystyle\prod_{i=2}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{2}-x_{1}\big)$
................_ $=\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$
................_ $=\dfrac{1}{2^{k+1}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\varphi(x_{0}),\rule{2cm}{0cm}(2)$
which implies that the sequence is either non-decreasing or non-increasing.
Therefore, $\xi:=\lim_{k\to\infty}x_{k}$ exists (finite or infinite).
Taking $\lim$ as $k\to\infty$ on both sides of (1), we get
$\xi=\frac{1}{2}(\xi^{2}+c),\rule{2cm}{0cm}(3)$
which gives the equlibrium points by solving the quadratic equation
$\xi_{1}=1-\sqrt{1-c}<1$ and $\xi_{2}=1+\sqrt{1-c}>1$ for $c\in(0,1)$.
If $\xi$ satisfies (3), then $c=2\xi-\xi^{2}$, and using (1), we have
$x_{k+1}-\xi=\frac{1}{2}\big(x_{k}^{2}+2\xi-\xi^{2}\big)-\xi=\frac{1}{2}(x_{k}+\xi)(x_{k}-\xi)$ for all $k\in\mathbb{N}_{0}$.
As the term $\varphi(x_{0})$ in (2) is quadratic, we can solve $\varphi(\lambda)=0$ for $\lambda$ and get that
$\lambda_{1}=1-\sqrt{1-c}=\xi_{1}<1$ and $\lambda_{2}=1+\sqrt{1-c}=\xi_{2}>1$ for $c\in(0,1)$.
• If $x_{0}\in[\xi_{1},\xi_{2})$, then $\varphi(x_{0})\leq0$, and the sequence is non-increasing.
Then the sequence can not converge a value greater than $x_{0}$.
Hence, if $x_{0}\in[\xi_{1},\xi_{2})$, then $\lim_{k\to\infty}x_{k}=\xi_{1}$.

• Now, let $x_{0}\in[0,\xi_{1})$, then $\varphi(x_{0})>0$, and the sequence is strictly increasing.
By induction, we have $x_{k}<\xi_{1}$ for all $k\in\mathbb{N}_{0}$ implying that $\lim_{k\to\infty}x_{k}=\xi_{1}$.

This shows that the equilibrium point $\xi_{1}$ is stable.
• In the case, $x_{0}=\xi_{2}$, we have $x_{k}=\xi_{2}$ for all $k\in\mathbb{N}_{0}$, i.e., $\lim_{k\to\infty}x_{k}=\xi_{2}$.

• Finally, if $x_{0}\in(\xi_{2},\infty)$, then $\varphi(x_{0})>0$, and the sequence is strictly increasing.
By induction, we have $x_{k}>\xi_{2}$ for all $k\in\mathbb{N}_{0}$ implying that $\lim_{k\to\infty}x_{k}=\infty$.

Therefore, the equilibrium point $\xi_{2}$ is unstable.

12. Hi bkarpuz,

thank you for what looks like a wonderful answer. The only problem is that I do not understand it. First of all, some of the notation is giving me problems.
You first denote the sequence by $\{x_k\}_{k\in\mathbb{N}_0}$.
I think $k\in\mathbb{N}_0\; \textrm{means that}\; \{k\in\mathbb{Z}:k\geq 0\}$.
You then write $c\in\mathbb{R}^+_0$. I have not seen this notation before, with the $+$ sign and everything, but from the way $c$ is defined in the problem, I'm assuming that it means $0 ?

Again, thanks for taking the time to write out all that good stuff. I just hope it isn't wasted on me. Will try to understand it!

13. Originally Posted by Mollier
Hi bkarpuz,

thank you for what looks like a wonderful answer. The only problem is that I do not understand it. First of all, some of the notation is giving me problems.
You first denote the sequence by $\{x_k\}_{k\in\mathbb{N}_0}$.
I think $k\in\mathbb{N}_0\; \textrm{means that}\; \{k\in\mathbb{Z}:k\geq 0\}$.
You then write $c\in\mathbb{R}^+_0$. I have not seen this notation before, with the $+$ sign and everything, but from the way $c$ is defined in the problem, I'm assuming that it means $0 ?

Again, thanks for taking the time to write out all that good stuff. I just hope it isn't wasted on me. Will try to understand it!
Hi Mollier,

$\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$
and
$\mathbb{R}_{0}^{+}:=\mathbb{R}^{+}\cup\{0\}$
I am glad you like the solution.
Actually, what I have shown you above is the standard procedure to be followed for such kind of problems.

14. Originally Posted by bkarpuz

Now, for $k\in\mathbb{N}$, compute
$x_{k+1}-x_{k}=\frac{1}{2}\big(x_{k}^{2}-x_{k-1}^{2}\big)$
................_ $=\frac{1}{2}\big(x_{k}+x_{k-1}\big)\big(x_{k}-x_{k-1}\big).$
Let $\varphi(\lambda):=\lambda(\lambda-2)+c$ for $\lambda\in\mathbb{R}$.
Repeating the procedure above with the abbreviation that the empty product
is the unity, we get for all $k\in\mathbb{N}_{0}$ that
$x_{k+1}-x_{k}=\dfrac{1}{2^{k-1}}\Bigg[\displaystyle\prod_{i=2}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{2}-x_{1}\big)$
................_ $=\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$
................_ $=\dfrac{1}{2^{k+1}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\varphi(x_{0}),\rule{2cm}{0cm}(2)$
which implies that the sequence is either non-decreasing or non-increasing.
Therefore, $\xi:=\lim_{k\to\infty}x_{k}$ exists (finite or infinite).
Hi again bkarpuz,

thanks for the quick intro to set-theory notation

I can see how you get,

$x_{k+1}-x_k = \frac{1}{2^k}\Bigg[(x_1+x_0)(x_2+x_1)\cdots (x_k+x_{k-1})\Bigg](x_1-x_0)$,

which you then write as,

$x_{k+1}-x_k=\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$.

If I am reading this right, the sequence is decreasing if,

$(x_{k+1}-x_k)<(x_k-x_{k-1})$,

and if I'm doing this right then,

$x_{k}-x_{k-2} = \dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k-1}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$.

Then $x_k-x_{k-1}$ has one more term than $x_{k+1}-x_k$ and is therefore bigger.

You rewrite $x_{k+1}-x_k$ in several different ways and then say that the sequence is non-decreasing or non-increasing. I do not get that though..

Thanks a lot for helping me out!

15. Originally Posted by Mollier
Hi again bkarpuz,

thanks for the quick intro to set-theory notation

I can see how you get,

$x_{k+1}-x_k = \frac{1}{2^k}\Bigg[(x_1+x_0)(x_2+x_1)\cdots (x_k+x_{k-1})\Bigg](x_1-x_0)$,

which you then write as,

$x_{k+1}-x_k=\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$.
Up to now everything is okay.
But do not forget that we do not yet know how large is the product, i.e., $\geq 1$ or $\leq 1$ .

Originally Posted by Mollier
If I am reading this right, the sequence is decreasing if,

$(x_{k+1}-x_k)<(x_k-x_{k-1})$,
A sequence is decreasing if each term is greater than preceding one (or succeeding terms are greater than the present one), i.e., $x_{k} (or $x_{k+1}) for all $k$.
And conversely, increasing if $x_{k+1}>x_{k}$.
Actually, the forward difference operator $\Delta x_{k}:=x_{k+1}-x_{k}$ notation illustrates this better (analogue to differential operator).
With this notation
1. A sequence is increasing if $\Delta x_{k}>0$ for all $k\in\mathbb{N}$. For instance, $x_{n}:=2^{n}$.
2. A sequence is decreasing if $\Delta x_{k}<0$ for all $k\in\mathbb{N}$. For instance, $x_{n}:=1/n$.
3. A sequence is nondecreasing if $\Delta x_{k}\geq0$ for all $k\in\mathbb{N}$. For instance, $x_{n}:=\lfloor n/2\rfloor$, where $\lfloor\cdot\rfloor$ is the least integer function.
4. A sequence is nonincreasing if $\Delta x_{k}\leq0$ for all $k\in\mathbb{N}$.
In each case, the sequence is monotonic, and it has a limit. (compare this with derivative).

Originally Posted by Mollier
and if I'm doing this right then,

$x_{k}-x_{k-2} = \dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k-1}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$.

Then $x_k-x_{k-1}$ has one more term than $x_{k+1}-x_k$ and is therefore bigger.
Also I can say that
5. If $\Delta x_{n+1}>\Delta x_{n}$ ( $x_{n+2}-x_{n+1}>x_{n+1}-x_{n}$), which is equivalent to $\Delta^{2}x_{n}>0$ ( $\Delta^{2}:=\Delta\Delta$), then the sequence is convex. For instance, $x_{n}=n^{2}$.
If an increasing sequence is convex, then it tends to infinity.
6. If $\Delta x_{n+1}<\Delta x_{n}$, which is equivalent to $\Delta^{2}x_{n}<0$), then the sequence is concave.

Including more terms in the product on the right hand side does not mean that the sequence is decreasing or increasing.
For instance, $x_{k}=\prod_{i=1}^{k}\frac{1}{2}$, which gives $x_{k+1}-x_{k}=\prod_{i=1}^{k+1}\frac{1}{2}-\prod_{i=1}^{k}\frac{1}{2}=-\frac{1}{2}<0$.

Page 1 of 2 12 Last