Where Will Fixed-Point Iteration Method Converge?

[khdani]

Hello,
How do i find the interval in which using Fixed-Point iteration method, the iteration will converge ?

 

[kidmode01]

Let g Є C[a,b] such that g(x) Є [a,b], for all x Є [a,b]. Suppose, in addition, that g' exist on (a,b) and that a constant 0 < k < 1 exists with |g'(x)| <= k, for all x Є (a,b)

Then, for any number Po in [a,b], the sequence defined by

Pn = g(Pn-1), n >= 1

converges to the unique fixed point p in [a,b].

Of course this is for just a fixed point for a function of one variable. Just work with your interval so that those conditions are satisfied.

 

[khdani]

The theorem you've written tells me that the iteration will converge to the fixed point
Po in [a,b], according to the terms of the theorem.
But my question is, how do i find the interval [a,b], especially for some non trivial function ?

 

[kidmode01]

The thing about numerical analysis as that the majority of the time you are going to run into functions or systems that are ill-conditioned. The theorem I wrote down is the fixed point iteration theorem which guarantees convergence. That is, those conditions are sufficient for convergence but not necessary. I haven't seen any other theorems about fixed point iteration that guarantee convergence, at least not in my Numerical Analysis textbooks.

Then the only way to find an interval that guarantees convergence is to make educated guesses about what interval you should use and then check if the conditions are satisfied. This is where programs like Maple/Matlab, etc come in handy, you could written a program that checks interesting intervals until you find an interval that works. I can't think of any other way, otherwise It would have probably been written a textbook right beside the theorem. Of course as you said, non-trivial functions probably won't satisfy one of the two conditions.

 

[khdani]

I understand now, Thank you!