# How to find the interval $[a,b]$ on which fixed-point iteration will converge of a given function $f(x)$?

Theorem 1
If $g \in [a,b]$ and $g(x) \in [a,b] \forall x \in [a,b]$, then $g$ has a fixed point in $[a,b].$
If in addition, $g'(x)$ exists on $(a,b)$ and a positive constant $k < 1$ exists with $$|g'(x)| \leq k, \text{ for all } \in (a, b)$$ then the fixed point in $[a,b] is unique. Fixed-point Theorem Let$g \in C[a,b]$be such that$g(x) \in [a,b]$, for all$x$in$[a,b]$. Suppose, in addition, that$g'$exists on$(a,b)$and that a constant$0 < k < 1$exists with $$|g'(x)| \leq k, \text{ for all } x \in (a, b)$$ Then, for any number$p_0$in$[a,b]$, the sequence defined by $$p_n = g(p_{n-1}), n \geq 1$$ converges to the unique fixed-point in$[a,b]$These are two theorems that I have learned, and I'm having a hard time with this problem: Given a function$f(x)$, how can we find the interval$[a,b]$on which fixed-point iteration will converge? Besides guess and check, I couldn't find any other way to solve this problem. I tried to link the above theorems, but it involves two variables, so I have a feeling it can't be solved algebraically. I wonder is there a general way to find the interval of convergence rather trial and error? Thank you. - Well, any interval stable by$f$and such that$|f'|\le k$on this interval with$k<1$(that is what the theorem tells you, no?). If$f(x)=(x+3/x)/2$for example,$f'(x)=(1-3/x^2)/2$hence any closed interval included in$(1,+\infty)$will do. – Did Oct 3 '11 at 7:32 Thank you. I will think over it. – Chan Oct 3 '11 at 7:36 In general, the "basin of convergence" for an iteration method like Newton-Raphson has a fractal boundary. See this for instance. – J. M. is back. Oct 3 '11 at 14:06 @J.M: Thanks for the reference. – Chan Oct 4 '11 at 7:14 ## 2 Answers The iteration converges for any starting point in an interval stable by$f$and such that$|f'|\leqslant k$on this interval, with$k<1$(this is a mere rephrasing of the theorem). If$f(x)=(x+3/x)/2$for example,$f'(x)=(1-3/x^2)/2$hence any closed interval included in$(1,+\infty)$will do. - Your condition is sufficient but not necessary. In your example, the actual basin of attraction is$(0,\infty)$. – Robert Israel Oct 3 '11 at 18:18 Sure. The interval$(1,+\infty)$is the one the general theorem the OP is interested in provides. By the way, what you call my condition is hardly mine (as I indicate in my answer). – Did Oct 3 '11 at 18:42 Suppose the continuous function$f: {\mathbb R} \to {\mathbb R}$has an attracting fixed point$p$. Its immediate basin of attraction (i.e. the maximal interval$J$such that iteration of$f$starting at any point in$J$converges to$p$) must be an open interval$(a,b)$(infinite intervals allowed). If$a$is finite,$f(a)$must be either$a$or$b$, and similarly for$f(b)$. The possibilities are as follows: 1)$a = -\infty$,$b = \infty$2) One of$a$and$b$is a (non-attracting) fixed point, the other is infinite. 3) Both$a$and$b$are (non-attracting) fixed points. 4)$a$is a (non-attracting) fixed point and$f(b) = a$5)$b$is a (non-attracting) fixed point and$f(a) = b$6)$a$and$b$form a 2-cycle:$f(a) = b$,$f(b) = a$. To tell which case you are in, find the non-attracting fixed points of$f$, the points mapped to those, and the 2-cycles. Note that$(a,b)\$ can't contain any of those.

-
In what book can I find this precise theorem? Thanks. –  lhf Sep 23 at 12:40
As above, I want to know where I can reference this. –  DDaren Sep 24 at 10:22