Contraction mapping theorem

Printable View

Show 40 post(s) from this thread on one page

November 6th 2011, 03:07 AM
Bloodzeed

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?
November 8th 2011, 02:10 AM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Bloodzeed

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?
November 8th 2011, 03:22 AM
Darkprince

Re: Contraction mapping theorem

Quote:

Originally Posted by Ackbeet

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?
November 8th 2011, 04:08 AM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

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.
November 8th 2011, 05:14 AM
CaptainBlack

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
November 8th 2011, 05:26 AM
Darkprince

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!!
November 8th 2011, 06:01 AM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

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.
November 8th 2011, 06:15 AM
CaptainBlack

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

... 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
November 8th 2011, 08:54 AM
Darkprince

Re: Contraction mapping theorem

Quote:

Originally Posted by Ackbeet

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!
November 8th 2011, 08:58 AM
Darkprince

Re: Contraction mapping theorem

Quote:

Originally Posted by CaptainBlack

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.
November 8th 2011, 09:35 AM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

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).
November 8th 2011, 09:41 AM
Darkprince

Re: Contraction mapping theorem

Quote:

Originally Posted by Ackbeet

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!
November 8th 2011, 12:36 PM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

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?
November 8th 2011, 12:47 PM
Darkprince

Re: Contraction mapping theorem

Quote:

Originally Posted by Ackbeet

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!!!
November 8th 2011, 12:55 PM
Ackbeet

Re: Contraction mapping theorem

Quote:

Originally Posted by Darkprince

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?

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 03:39 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.