Fixed point iteration help

• Nov 6th 2011, 03:55 AM
Bloodzeed
Fixed point iteration help
With f defined as $f(x)=e^x+6x-5$, show the fixed point iteration
$x_{n+1}=\frac{5-e^{x_{n}}}{6}$, $n=0,1,...$
must converge to $x_{*}$ with $x_{0} \in [0,1]$

Had a go at this by using contraction mapping theorem and putting it in the form $f(x)=x-g(x)$, and as f(x)=0 then can work out what g(x) is but I'm not sure it is a contraction so not sure how can know it converges?
• Nov 8th 2011, 03:12 AM
Ackbeet
Re: Fixed point iteration help
Quote:

Originally Posted by Bloodzeed
With f defined as $f(x)=e^x+6x-5$, show the fixed point iteration
$x_{n+1}=\frac{5-e^{x_{n}}}{6}$, $n=0,1,...$
must converge to $x_{*}$ with $x_{0} \in [0,1]$

Had a go at this by using contraction mapping theorem and putting it in the form $f(x)=x-g(x)$, and as f(x)=0 then can work out what g(x) is but I'm not sure it is a contraction so not sure how can know it converges?

You must examine the function

$g(x)=\frac{5-e^{x}}{6}$ on the interval $[0,1],$ and see if it is a contraction or not. What criteria do you have for showing a function is a contraction?
• Nov 8th 2011, 06:35 AM
Darkprince
Re: Fixed point iteration help
Quote:

Originally Posted by Ackbeet
You must examine the function

$g(x)=\frac{5-e^{x}}{6}$ on the interval $[0,1],$ and see if it is a contraction or not. What criteria do you have for showing a function is a contraction?

but here we dont have clue about L, except that it should be between 0 and 1 so how do we prove in general that this function is a contraction?
• Nov 8th 2011, 07:03 AM
Ackbeet
Re: Fixed point iteration help
Quote:

Originally Posted by Darkprince
but here we dont have clue about L, except that it should be between 0 and 1 so how do we prove in general that this function is a contraction?

Is the function differentiable everywhere? If so, can you put a bound on the derivative in the interval of interest? See your other thread for info about the derivative approach.
• Nov 8th 2011, 10:27 AM
Darkprince
Re: Fixed point iteration help
Quote:

Originally Posted by Ackbeet
Is the function differentiable everywhere? If so, can you put a bound on the derivative in the interval of interest? See your other thread for info about the derivative approach.

Hello again at this post :p Thank you very much, I think I have found another way to solve this exercise if you can review it and comment on how rigorous it is please! (and if it is correct)

abs(g(x)-g(y))=abs((e^(y)-e^(x)) / 6) = 1/6 * abs ( e^(x) * (e^(y-x)-1))=e^(x)/6 * abs (e^(y-x)-1), since e^(x)=abs(e^(x))

Then e^(x)/6 * abs (e^(y-x)-1) <= e/6 * abs (e^(y-x)-1) (since x=1 gives e^(x)=1 and x=1 is the maximum of the interval [0,1]

Now e/6 * abs (e^(y-x)-1) <= e/6 * abs( (e-1) (y-x))= e/6 * (e-1) * abs(x-y) [using that abs(e-1) = e-1 and that abs(y-x)= abs (x-y)

So finally abs(g(x)-g(y)) <= k abs(x-y) where k= e/6 * (e-1) and 0<k<1

Hope I found a rigorous, correct proof for contraction of our function, I will really appreciate if you review it!! Thank you very much again!!
• Nov 8th 2011, 10:54 AM
Ackbeet
Re: Fixed point iteration help
Quote:

Originally Posted by Darkprince
Hello again at this post :p Thank you very much, I think I have found another way to solve this exercise if you can review it and comment on how rigorous it is please! (and if it is correct)

abs(g(x)-g(y))=abs((e^(y)-e^(x)) / 6) = 1/6 * abs ( e^(x) * (e^(y-x)-1))=e^(x)/6 * abs (e^(y-x)-1), since e^(x)=abs(e^(x))

Then e^(x)/6 * abs (e^(y-x)-1) <= e/6 * abs (e^(y-x)-1) (since x=1 gives e^(x)=1 and x=1 is the maximum of the interval [0,1]

Now e/6 * abs (e^(y-x)-1) <= e/6 * abs( (e-1) (y-x))

Not sure where that's coming from. How do you get that

$\frac{e}{6}\,|e^{y-x}-1|\le\frac{e}{6}\,|(e-1)(y-x)|?$

Quote:

= e/6 * (e-1) * abs(x-y) [using that abs(e-1) = e-1 and that abs(y-x)= abs (x-y)

So finally abs(g(x)-g(y)) <= k abs(x-y) where k= e/6 * (e-1) and 0<k<1

Hope I found a rigorous, correct proof for contraction of our function, I will really appreciate if you review it!! Thank you very much again!!
• Nov 8th 2011, 11:27 AM
Darkprince
Re: Fixed point iteration help
Quote:

Originally Posted by Ackbeet
Not sure where that's coming from. How do you get that

$\frac{e}{6}\,|e^{y-x}-1|\le\frac{e}{6}\,|(e-1)(y-x)|?$

Consider (e^z)-1 and (e-1)*z. If you sketch both for z in [0,1] you see that (e^z)-1<=(e-1)*z for z in [0,1] So it can be justified by a sketch, don't really know if there is an algebraic manipulation for that. So does the proof considered rigorous?
• Nov 8th 2011, 12:17 PM
Ackbeet
Re: Fixed point iteration help
To use the derivative approach, all you need do is show that the derivative exists everywhere and is less than 1 in magnitude on the interval. That implies the function is Lipschitz with Lipschitz constant less than one, which implies that the function has a unique fixed point on that interval.
• Nov 8th 2011, 12:19 PM
Darkprince
Re: Fixed point iteration help
Quote:

Originally Posted by Ackbeet
To use the derivative approach, all you need do is show that the derivative exists everywhere and is less than 1 in magnitude on the interval. That implies the function is Lipschitz with Lipschitz constant less than one, which implies that the function has a unique fixed point on that interval.

Thank you again, sorry I edited my post, I just found that that inequality can be justified by a sketch as I wrote above. Do you think now is a good proof?

I think if I can justify the inequality even by a sketch is still justified and I am obtaining an exact L and at the same moment proving directly that it is a contraction!

But you may have a different opinion (your opinion is obviously "heavier" than mine :p )