Page 1 of 2 12 LastLast
Results 1 to 15 of 21

Thread: Fixed-point iteration 'show that' exercise

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1

    Fixed-point iteration 'show that' exercise

    Hi,

    problem:

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

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

    and deduce that $\displaystyle \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 $\displaystyle x_0$?

    attempt at solution:

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

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

    we have that,

    $\displaystyle 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 $\displaystyle 0\leq x_0 < \xi_2$ and $\displaystyle 1<\xi_2$ it means that $\displaystyle x_0$ could be any number larger than 1 but smaller than $\displaystyle \xi_2$. I figure that I could then choose some $\displaystyle x_0$ such that $\displaystyle x_1 > x_0$, in other words we would be moving away from $\displaystyle \xi_1$.

    Now if $\displaystyle 0 \leq x_0 < \xi_1$ instead of $\displaystyle 0\leq x_0 <\xi_2$, I could see how $\displaystyle \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.
    Last edited by Mollier; Sep 15th 2010 at 05:10 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by Mollier View Post
    Hi,

    problem:

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

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

    and deduce that $\displaystyle \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 $\displaystyle x_0$?

    attempt at solution:

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

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

    we have that,

    $\displaystyle 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 $\displaystyle 0\leq x_0 < \xi_2$ and $\displaystyle 1<\xi_2$ it means that $\displaystyle x_0$ could be any number larger than 1 but smaller than $\displaystyle \xi_2$. I figure that I could then choose some $\displaystyle x_0$ such that $\displaystyle x_1 > x_0$, in other words we would be moving away from $\displaystyle \xi_1$.

    Now if $\displaystyle 0 \leq x_0 < \xi_1$ instead of $\displaystyle 0\leq x_0 <\xi_2$, I could see how $\displaystyle \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:

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

    for obvious reasons

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    A fixed point is a solution of:

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

    for obvious reasons

    CB
    Hi,

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

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

    and

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

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

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

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

    and rewrite it as,

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

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

    I could use a hand here, thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    if:

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

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

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

    and:

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

    Then:

    $\displaystyle \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 $\displaystyle k >0$ such that $\displaystyle |x_k+\xi_1|<k<2$)

    CB
    Last edited by CaptainBlack; Sep 16th 2010 at 01:29 AM. Reason: Note this is not how I would do this from choice
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    if:

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

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

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

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

    Thank you for being so patient with me CB!
    Time to donate some cash to MHF
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by Mollier View Post
    So if $\displaystyle x_1<\xi_1$ and $\displaystyle x_2=\frac{1}{2}x_1+\frac{1}{2}c$ then I am sure that
    $\displaystyle x_2<\xi_2$?
    I know for sure that $\displaystyle \frac{1}{2}x_1<\xi_2$ and I also know that $\displaystyle \frac{1}{2}c<\frac{1}{2}$, but I am not able to see that $\displaystyle x_2$ must be smaller than $\displaystyle \xi_2$.
    All these inequalities are confusing me..

    Thank you for being so patient with me CB!
    Time to donate some cash to MHF
    $\displaystyle 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$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Hi,

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

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

    so,

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

    Is this what you had in mind CB?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Not quite since that is insufficient to prove that $\displaystyle \varepsilon_n \to 0$ as $\displaystyle n \to \infty$

    CB
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Hi,

    here's another try!

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

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

    $\displaystyle x_k+\xi_1 < 2.$

    We end up with,

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

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

    Perhaps I will approach the correct answer as $\displaystyle \textrm{(number of attempts)}\rightarrow\infty$.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Here's perhaps a better way of writing this..

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

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

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

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

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

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

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

    I think this is because the derivative of $\displaystyle \frac{1}{2}(x^2+c)$ is $\displaystyle x$ and when $\displaystyle x_0>\xi_2$ it means that $\displaystyle 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?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Lightbulb

    Quote Originally Posted by Mollier View Post
    Hi,

    problem:

    The iteration defined by $\displaystyle x_{k+1} = \frac{1}{2}(x^2_k+c)$, where $\displaystyle 0<c<1$,
    has two fixed points $\displaystyle \xi_1, \xi_2$ where $\displaystyle 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 $\displaystyle \{x_{k}\}_{k\in\mathbb{N}_{0}}$ for $\displaystyle c\in\mathbb{R}_{0}^{+}$ and define
    $\displaystyle x_{k+1}:=\frac{1}{2}\big(x_{k}^{2}+c\big)$ for $\displaystyle k\in\mathbb{N},\rule{2cm}{0cm}(1)$
    where $\displaystyle x_{0}\in\mathbb{R}_{0}^{+}$.
    It is clear that for $\displaystyle c,x_{0}\in\mathbb{R}_{0}^{+}$, $\displaystyle \{x_{k}\}_{k\in\mathbb{N}_{0}}\subset\mathbb{R}_{0 }$.
    Now, for $\displaystyle k\in\mathbb{N}$, compute
    $\displaystyle x_{k+1}-x_{k}=\frac{1}{2}\big(x_{k}^{2}-x_{k-1}^{2}\big)$
    ................_$\displaystyle =\frac{1}{2}\big(x_{k}+x_{k-1}\big)\big(x_{k}-x_{k-1}\big).$
    Let $\displaystyle \varphi(\lambda):=\lambda(\lambda-2)+c$ for $\displaystyle \lambda\in\mathbb{R}$.
    Repeating the procedure above with the abbreviation that the empty product
    is the unity, we get for all $\displaystyle k\in\mathbb{N}_{0}$ that
    $\displaystyle 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)$
    ................_$\displaystyle =\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$
    ................_$\displaystyle =\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, $\displaystyle \xi:=\lim_{k\to\infty}x_{k}$ exists (finite or infinite).
    Taking $\displaystyle \lim$ as $\displaystyle k\to\infty$ on both sides of (1), we get
    $\displaystyle \xi=\frac{1}{2}(\xi^{2}+c),\rule{2cm}{0cm}(3)$
    which gives the equlibrium points by solving the quadratic equation
    $\displaystyle \xi_{1}=1-\sqrt{1-c}<1$ and $\displaystyle \xi_{2}=1+\sqrt{1-c}>1$ for $\displaystyle c\in(0,1)$.
    If $\displaystyle \xi$ satisfies (3), then $\displaystyle c=2\xi-\xi^{2}$, and using (1), we have
    $\displaystyle 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 $\displaystyle k\in\mathbb{N}_{0}$.
    As the term $\displaystyle \varphi(x_{0})$ in (2) is quadratic, we can solve $\displaystyle \varphi(\lambda)=0$ for $\displaystyle \lambda$ and get that
    $\displaystyle \lambda_{1}=1-\sqrt{1-c}=\xi_{1}<1$ and $\displaystyle \lambda_{2}=1+\sqrt{1-c}=\xi_{2}>1$ for $\displaystyle c\in(0,1)$.
    • If $\displaystyle x_{0}\in[\xi_{1},\xi_{2})$, then $\displaystyle \varphi(x_{0})\leq0$, and the sequence is non-increasing.
      Then the sequence can not converge a value greater than $\displaystyle x_{0}$.
      Hence, if $\displaystyle x_{0}\in[\xi_{1},\xi_{2})$, then $\displaystyle \lim_{k\to\infty}x_{k}=\xi_{1}$.

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

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

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

    Therefore, the equilibrium point $\displaystyle \xi_{2}$ is unstable.
    Last edited by bkarpuz; Sep 20th 2010 at 12:15 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    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 $\displaystyle \{x_k\}_{k\in\mathbb{N}_0}$.
    I think $\displaystyle k\in\mathbb{N}_0\; \textrm{means that}\; \{k\in\mathbb{Z}:k\geq 0\}$.
    You then write $\displaystyle c\in\mathbb{R}^+_0$. I have not seen this notation before, with the $\displaystyle +$ sign and everything, but from the way $\displaystyle c$ is defined in the problem, I'm assuming that it means $\displaystyle 0<c<1$ ?

    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!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by Mollier View Post
    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 $\displaystyle \{x_k\}_{k\in\mathbb{N}_0}$.
    I think $\displaystyle k\in\mathbb{N}_0\; \textrm{means that}\; \{k\in\mathbb{Z}:k\geq 0\}$.
    You then write $\displaystyle c\in\mathbb{R}^+_0$. I have not seen this notation before, with the $\displaystyle +$ sign and everything, but from the way $\displaystyle c$ is defined in the problem, I'm assuming that it means $\displaystyle 0<c<1$ ?

    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,

    $\displaystyle \mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$
    and
    $\displaystyle \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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by bkarpuz View Post

    Now, for $\displaystyle k\in\mathbb{N}$, compute
    $\displaystyle x_{k+1}-x_{k}=\frac{1}{2}\big(x_{k}^{2}-x_{k-1}^{2}\big)$
    ................_$\displaystyle =\frac{1}{2}\big(x_{k}+x_{k-1}\big)\big(x_{k}-x_{k-1}\big).$
    Let $\displaystyle \varphi(\lambda):=\lambda(\lambda-2)+c$ for $\displaystyle \lambda\in\mathbb{R}$.
    Repeating the procedure above with the abbreviation that the empty product
    is the unity, we get for all $\displaystyle k\in\mathbb{N}_{0}$ that
    $\displaystyle 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)$
    ................_$\displaystyle =\dfrac{1}{2^{k}}\Bigg[\displaystyle\prod_{i=1}^{k}\big(x_{i}+x_{i-1}\big)\Bigg]\big(x_{1}-x_{0}\big)$
    ................_$\displaystyle =\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, $\displaystyle \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,

    $\displaystyle 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,

    $\displaystyle 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,

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

    and if I'm doing this right then,

    $\displaystyle 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 $\displaystyle x_k-x_{k-1}$ has one more term than $\displaystyle x_{k+1}-x_k$ and is therefore bigger.

    You rewrite $\displaystyle 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!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Lightbulb

    Quote Originally Posted by Mollier View Post
    Hi again bkarpuz,

    thanks for the quick intro to set-theory notation

    I can see how you get,

    $\displaystyle 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,

    $\displaystyle 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., $\displaystyle \geq 1$ or $\displaystyle \leq 1$ .

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

    $\displaystyle (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., $\displaystyle x_{k}<x_{k-1}$ (or $\displaystyle x_{k+1}<x_{k}$) for all $\displaystyle k$.
    And conversely, increasing if $\displaystyle x_{k+1}>x_{k}$.
    Actually, the forward difference operator $\displaystyle \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 $\displaystyle \Delta x_{k}>0$ for all $\displaystyle k\in\mathbb{N}$. For instance, $\displaystyle x_{n}:=2^{n}$.
    2. A sequence is decreasing if $\displaystyle \Delta x_{k}<0$ for all $\displaystyle k\in\mathbb{N}$. For instance, $\displaystyle x_{n}:=1/n$.
    3. A sequence is nondecreasing if $\displaystyle \Delta x_{k}\geq0$ for all $\displaystyle k\in\mathbb{N}$. For instance, $\displaystyle x_{n}:=\lfloor n/2\rfloor$, where $\displaystyle \lfloor\cdot\rfloor$ is the least integer function.
    4. A sequence is nonincreasing if $\displaystyle \Delta x_{k}\leq0$ for all $\displaystyle k\in\mathbb{N}$.
    In each case, the sequence is monotonic, and it has a limit. (compare this with derivative).

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

    $\displaystyle 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 $\displaystyle x_k-x_{k-1}$ has one more term than $\displaystyle x_{k+1}-x_k$ and is therefore bigger.
    Also I can say that
    5. If $\displaystyle \Delta x_{n+1}>\Delta x_{n}$ ($\displaystyle x_{n+2}-x_{n+1}>x_{n+1}-x_{n}$), which is equivalent to $\displaystyle \Delta^{2}x_{n}>0$ ($\displaystyle \Delta^{2}:=\Delta\Delta$), then the sequence is convex. For instance, $\displaystyle x_{n}=n^{2}$.
    If an increasing sequence is convex, then it tends to infinity.
    6. If $\displaystyle \Delta x_{n+1}<\Delta x_{n}$, which is equivalent to $\displaystyle \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, $\displaystyle x_{k}=\prod_{i=1}^{k}\frac{1}{2}$, which gives $\displaystyle x_{k+1}-x_{k}=\prod_{i=1}^{k+1}\frac{1}{2}-\prod_{i=1}^{k}\frac{1}{2}=-\frac{1}{2}<0$.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Fixed point iteration help
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: Nov 8th 2011, 11:19 AM
  2. Fixed Point Iteration
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Nov 10th 2010, 10:14 AM
  3. Fixed point iteration
    Posted in the Differential Geometry Forum
    Replies: 13
    Last Post: Oct 21st 2010, 03:36 AM
  4. Fixed point iteration
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Feb 2nd 2010, 07:30 AM
  5. Fixed Point Iteration
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Nov 12th 2009, 12:40 PM

Search Tags


/mathhelpforum @mathhelpforum