Fixed point iteration help

With f defined as , show the fixed point iteration

,

must converge to with

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

, show the fixed point iteration

,

must converge to

with

Had a go at this by using contraction mapping theorem and putting it in the form

, 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

on the interval 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

on the interval

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

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

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 )