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

Math Help - Contraction mapping theorem

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    8

    Contraction mapping theorem

    Show that the fixed point iteration x_{n+1}=g(x_n),  n=0,1,.., with g defined as
    g(x)=\frac{5-e^x-2x}{4}
    cannot be guaranteed to converge to x_* when x_0 $\in$ [0,1]

    I approached this by using contraction mapping theorem and differentiating g(x) to get g'(x)=-\frac{e^x}{4}-\frac{1}{2} which can be said to be less than -\frac{e}{4}-\frac{1}{2} in the interval [0,1] and so, by calling this constant L, is always negative and is not a contraction and so cannot be guaranteed to converge? Am I on the right track or way off?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Bloodzeed View Post
    Show that the fixed point iteration x_{n+1}=g(x_n),  n=0,1,.., with g defined as
    g(x)=\frac{5-e^x-2x}{4}
    cannot be guaranteed to converge to x_* when x_0 $\in$ [0,1]

    I approached this by using contraction mapping theorem and differentiating g(x) to get g'(x)=-\frac{e^x}{4}-\frac{1}{2} which can be said to be less than -\frac{e}{4}-\frac{1}{2} in the interval [0,1] and so, by calling this constant L, is always negative and is not a contraction and so cannot be guaranteed to converge? Am I on the right track or way off?
    Differentiation is good. Plugging in x = 1 is great, too. However, what you're really trying to do is tie into the Banach fixed-point theorem. What does plugging in x = 1 into the derivative tell you about whether g is a contraction mapping or not?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    Quote Originally Posted by Ackbeet View Post
    Differentiation is good. Plugging in x = 1 is great, too. However, what you're really trying to do is tie into the Banach fixed-point theorem. What does plugging in x = 1 into the derivative tell you about whether g is a contraction mapping or not?
    I have considered an alternative way but I am not really sure if it is correct.

    Let's check if it is a contraction!
    abs(g(x)-g(y))=abs((e^y-e^x+2y-2x)/4)

    This should be <=L*abs (x-y) with o<L<1 for all x,y exist in [0,1] for g to be a contraction.

    Let x=0.6 and y=1 then abs(g(x)-g(y)) is equal to 0.424 (to 3 d.p) so 0.424<=0.4L and L>=1.06!!! so L is not in the interval (0,1) so g is not a contraction and so cannot be guaranteed to converge!

    What do you think Ackbeet?
    Last edited by Darkprince; November 8th 2011 at 04:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    I have considered an alternative way but I am not really sure if it is correct.

    Let's check if it is a contraction!
    abs(g(x)-g(y))=abs((e^y-e^x+2y-2x)/4)

    This should be <=L*abs (x-y) with o<L<1 for all x,y exist in [0,1] for g to be a contraction.

    Let x=0.6 and y=1 then abs(g(x)-g(y)) is equal to 0.424 (to 3 d.p) so 0.424<=0.4L and L>=1.06!!! so L is not in the interval (0,1) so g is not a contraction and so cannot be guaranteed to converge!

    What do you think Ackbeet?
    That's a good approach. You should check with your teacher about whether decimal approximations are allowed in your counterexample. If not, you may need to get creative with inequalities in order to show that your function isn't a contraction. Certainly, using the definition like you have is the most straight-forward approach to take. I was thinking more along the lines of showing that the derivative has magnitude greater than one somewhere in the interval. But your way is more direct.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Contraction mapping theorem

    The assumptions of the fixed point theorem imply that:

    \left|\frac{f(x)-f(y)}{x-y}\right|<1

    for (x,y) \in [0,1] \times [0,1]

    which since f(x) is differentiable imples that:

    |f'(x)|\le 1 for x \in (0,1)

    Now:

    f'(x)=\frac{-e^x-2}{4}

    and since e>2 we have |f'(x)| is greater than 1 close to x=1. We can be more precise and state that |f'(x)|>1 for x \in (\ln(2),1), I leave the detail of this to the reader.

    CB
    Last edited by Ackbeet; November 8th 2011 at 01:28 PM. Reason: Typo.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    How can I be creative to find in general that it is not a contraction without just finding a counterexample? also have no clue on what cb did based om differentiability. is it possible to have an analytic explanation? thank you very much!!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    How can I be creative to find in general that it is not a contraction without just finding a counterexample? also have no clue on what cb did based om differentiability. is it possible to have an analytic explanation? thank you very much!!
    I'm not saying you shouldn't find a counterexample. What I am saying is that your counterexample may need to be touched up in rigor a bit, depending on the standards of your teacher. Rigorous inequalities can help you in this regard.

    As for the derivative approach, if the derivative exists everywhere and is less than 1 in magnitude, then the function is Lipschitz, of Lipschitz constant less than 1. Then the Banach fixed point theorem applies. That is, having a derivative everywhere that's less than 1 in magnitude is a stronger condition than being Lipschitz.

    Overall, what you're trying to do is show that the Banach fixed point theorem does not apply to this function, because this function doesn't satisfy the assumptions of the theorem.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    ... also have no clue on what cb did based om differentiability. is it possible to have an analytic explanation? thank you very much!!
    For the contraction mapping theorem to apply on [0,1] requres that there exists a positive k<1 such that:

    |f(x)-f(y)|<k|x-y|

    for all x,y \in [0,1].

    Or:

    \frac{|f(x)-f(y)|}{|x-y|}<k<1

    But the left hand side of the above is the absolute value of a difference quotient and so:

    |f'(x)|\le k<1

    So what problem do you have with this?

    (note the inequality here is stronger than in the earlier post, but it does not need to be)

    CB
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    Quote Originally Posted by Ackbeet View Post
    I'm not saying you shouldn't find a counterexample. What I am saying is that your counterexample may need to be touched up in rigor a bit, depending on the standards of your teacher. Rigorous inequalities can help you in this regard.

    As for the derivative approach, if the derivative exists everywhere and is less than 1 in magnitude, then the function is Lipschitz, of Lipschitz constant less than 1. Then the Banach fixed point theorem applies. That is, having a derivative everywhere that's less than 1 in magnitude is a stronger condition than being Lipschitz.

    Overall, what you're trying to do is show that the Banach fixed point theorem does not apply to this function, because this function doesn't satisfy the assumptions of the theorem.
    Still can't understand how my counterexample may be touched up in rigor a bit! Can you show me the way please? Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    Quote Originally Posted by CaptainBlack View Post
    For the contraction mapping theorem to apply on [0,1] requres that there exists a positive k<1 such that:

    |f(x)-f(y)|<k|x-y|

    for all x,y \in [0,1].

    Or:

    \frac{|f(x)-f(y)|}{|x-y|}<k<1

    But the left hand side of the above is the absolute value of a difference quotient and so:

    |f'(x)|\le k<1

    So what problem do you have with this?

    (note the inequality here is stronger than in the earlier post, but it does not need to be)

    CB
    I have never been told about a difference quotient so I don't know what it is and why does it imply that abs(f'(x))<=k. It would be helpful if you can explain to me. So say I am supposed to use a counterexample instead of the "derivative way" is my counterexample a good way? But I would still be happy to know the explanation of the difference quotient since it seems like a more rigorous way than my counterexample.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    Still can't understand how my counterexample may be touched up in rigor a bit! Can you show me the way please? Thank you very much!
    Hmm. Well, according to your setup, you need to show that

    \left|\frac{e^y-e^x+2y-2x}{4}\right|>|x-y|

    for some x,y\in[0,1].

    You either need to use inequalities in a rigorous fashion here, or pick some values for x and y for which you can compute various quantities exactly. Suppose x = 0, y = 1. Then you've got to show

    \left|\frac{e-1+2}{4}\right|>1, or

    \left|\frac{e+1}{4}\right|>1.

    I don't think those two values will work for you. However, you will notice that I did not use decimal approximations. I could try x = 4/5, and y = 1. Both are in the desired interval. Then I need to show that

    \left|\frac{e-e^{4/5}+2-2(4/5)}{4}\right|>|(4/5)-1|, or

    \left|e-e^{4/5}+2/5\right|>4/5, or

    e-e^{4/5}>2/5.

    Not sure how you can do that. The inequality holds, but I'm not sure how to prove it. Again, this is just an illustration so you can see how it's done.

    Maybe it's easier, after all, just to show that the function's derivative is greater than 1 in magnitude somewhere on the interval (which it is).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    Quote Originally Posted by Ackbeet View Post
    Hmm. Well, according to your setup, you need to show that

    \left|\frac{e^y-e^x+2y-2x}{4}\right|>|x-y|

    for some x,y\in[0,1].

    You either need to use inequalities in a rigorous fashion here, or pick some values for x and y for which you can compute various quantities exactly. Suppose x = 0, y = 1. Then you've got to show

    \left|\frac{e-1+2}{4}\right|>1, or

    \left|\frac{e+1}{4}\right|>1.

    I don't think those two values will work for you. However, you will notice that I did not use decimal approximations. I could try x = 4/5, and y = 1. Both are in the desired interval. Then I need to show that

    \left|\frac{e-e^{4/5}+2-2(4/5)}{4}\right|>|(4/5)-1|, or

    \left|e-e^{4/5}+2/5\right|>4/5, or

    e-e^{4/5}>2/5.

    Not sure how you can do that. The inequality holds, but I'm not sure how to prove it. Again, this is just an illustration so you can see how it's done.

    Maybe it's easier, after all, just to show that the function's derivative is greater than 1 in magnitude somewhere on the interval (which it is).

    x=0, y=1 definitely don't work since then we have k<0.92 (with decimal approximation) so basically the counterexample has to show that k>1 or k<0 (so k is not between 0 and 1)

    Say I want to do it with the derivative way, I have never been told about a difference quotient so I don't know what it is and why does it imply that abs(f'(x))<=k as I said to CB above!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    x=0, y=1 definitely don't work since then we have k<0.92 (with decimal approximation) so basically the counterexample has to show that k>1 or k<0 (so k is not between 0 and 1)

    Say I want to do it with the derivative way, I have never been told about a difference quotient so I don't know what it is and why does it imply that abs(f'(x))<=k as I said to CB above!
    A difference quotient is essentially the slope of a secant line.

    Are you familiar with the Banach fixed point theorem concerning Lipschitz functions? And do you see how being differentiable, with the magnitude of the derivative being less than one, implies that a function is Lipschitz of the appropriate kind? If not, where does your understanding stop?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Nov 2010
    Posts
    164

    Re: Contraction mapping theorem

    Quote Originally Posted by Ackbeet View Post
    A difference quotient is essentially the slope of a secant line.

    Are you familiar with the Banach fixed point theorem concerning Lipschitz functions? And do you see how being differentiable, with the magnitude of the derivative being less than one, implies that a function is Lipschitz of the appropriate kind? If not, where does your understanding stop?
    To tell you the truth I am not familiar with any of them! I am a second year and the only thing that I was taught is the Contraction theorem as the following:

    Part1:
    Suppose g:[a,b]|-> [a,b] is continuous and also a contraction, i.e abs(g(x)-g(y))<= L*abs(x-y) for all x,y in [a,b] where 0<L<1 then g has a unique fixed point x* in [a,b]
    g(x*)=x*

    Part 2 of the Contraction theorem:
    Suppose g:[a,b]|-> [a,b] is continuous and also a contraction, i.e abs(g(x)-g(y))<= L*abs(x-y) for all x,y in [a,b] where 0<L<1
    Then the sequence {x(k)} defined by x(k+1) = g(x(k)), k>=0 converges to the unique fixed point of g as k->infinity for any starting value x(0) in [a,b]


    This is the only thing we were been taught so that's why I was trying to find a counterexample and didn't know how to approach the exercise concerning the derivative or Lipschitz functions!!!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2

    Re: Contraction mapping theorem

    Quote Originally Posted by Darkprince View Post
    To tell you the truth I am not familiar with any of them! I am a second year and the only thing that I was taught is the Contraction theorem as the following:

    Part1:
    Suppose g:[a,b]|-> [a,b] is continuous and also a contraction, i.e abs(g(x)-g(y))<= L*abs(x-y) for all x,y in [a,b] where 0<L<1 then g has a unique fixed point x* in [a,b]
    g(x*)=x*

    Part 2 of the Contraction theorem:
    Suppose g:[a,b]|-> [a,b] is continuous and also a contraction, i.e abs(g(x)-g(y))<= L*abs(x-y) for all x,y in [a,b] where 0<L<1
    Then the sequence {x(k)} defined by x(k+1) = g(x(k)), k>=0 converges to the unique fixed point of g as k->infinity for any starting value x(0) in [a,b]


    This is the only thing we were been taught so that's why I was trying to find a counterexample and didn't know how to approach the exercise concerning the derivative or Lipschitz functions!!!
    Ah. The conditions in your theorems ARE Lipschitz conditions of a particular kind. Look here for a Lipschitz condition definition. You can see that the conditions in your theorems are that the function is Lipschitz with Lipschitz constant in the interval (0,1). If you look at the first property in the Properties section of the wiki, you will see that an everywhere differentiable function is Lipschitz if and only if its derivative is bounded, and it tells you what the Lipschitz constant is in that case: the least upper bound of the magnitude of the derivative! So there's a direct tie-in to the conditions of your theorems. Does that help?

    So your logic would work like this:

    1. The function is everywhere differentiable.
    2. The magnitude of the derivative is bounded by 1 - epsilon everywhere on the interval, for some epsilon greater than zero.
    3. Therefore, the function is Lipschitz with a Lipschitz constant in the interval (0,1).
    4. Therefore, the conditions of the theorem you've been given apply.
    5. Therefore, the conclusion of the theorem holds.

    And you're done. The major step here is # 2. What's epsilon?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Contraction Mapping.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 30th 2011, 08:38 AM
  2. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 20th 2011, 09:10 PM
  3. Contraction mapping theorem
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: November 28th 2010, 09:20 PM
  4. Help with Theorem - Local Contraction Mapping
    Posted in the Calculus Forum
    Replies: 0
    Last Post: August 5th 2010, 10:27 PM
  5. Contraction Mapping Theorem / Simple iteration
    Posted in the Calculus Forum
    Replies: 6
    Last Post: July 20th 2010, 06:16 AM

Search Tags


/mathhelpforum @mathhelpforum