5
$\begingroup$

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.

  • 0
    @J.M: Thanks for the reference.2011-10-04

2 Answers 2

3

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.

  • 0
    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).2011-10-03
3

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.

  • 0
    As above, I want to know where I can reference this.2015-09-24