Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
1  
In general, the "basin of convergence" for an iteration method like Newton-Raphson has a fractal boundary. See this for instance. –  J. M. Oct 3 '11 at 14:06
    
@J.M: Thanks for the reference. –  Chan Oct 4 '11 at 7:14

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.