Fixed point iteration help

With f defined as $\displaystyle f(x)=e^x+6x-5$, show the fixed point iteration

$\displaystyle x_{n+1}=\frac{5-e^{x_{n}}}{6}$, $\displaystyle n=0,1,...$

must converge to $\displaystyle x_{*}$ with $\displaystyle x_{0} $\in$ [0,1]$

Had a go at this by using contraction mapping theorem and putting it in the form $\displaystyle 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?

Re: Fixed point iteration help

Quote:

Originally Posted by

**Bloodzeed** With f defined as $\displaystyle f(x)=e^x+6x-5$, show the fixed point iteration

$\displaystyle x_{n+1}=\frac{5-e^{x_{n}}}{6}$, $\displaystyle n=0,1,...$

must converge to $\displaystyle x_{*}$ with $\displaystyle x_{0} $\in$ [0,1]$

Had a go at this by using contraction mapping theorem and putting it in the form $\displaystyle 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

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

Re: Fixed point iteration help

Quote:

Originally Posted by

**Ackbeet** You must examine the function

$\displaystyle g(x)=\frac{5-e^{x}}{6}$ on the interval $\displaystyle [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?

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.

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!!

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

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

Re: Fixed point iteration help

Quote:

Originally Posted by

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

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

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.

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 )