1. ## Fixed point iteration

Ok so I have a function $\displaystyle 1-2x^1^6$
the function has two real fixed points in the interval [-1,1]. One is -1 and the other is approx 0.8504

My question is can we expect the fixed point iteration converge to either of these fixed points? One, Both, None?

2. What, exactly, do you mean by 'fixed point' in this context ?
What is it about the two values that you give that makes them fixed points ?

3. Originally Posted by BobP
What, exactly, do you mean by 'fixed point' in this context ?
What is it about the two values that you give that makes them fixed points ?
A fixed point is a point $\displaystyle p$ such that $\displaystyle f(p)=p$

In case that $\displaystyle f[a,b]\subseteq [a,b]$, that is $\displaystyle f(x)\in [a,b]$ for all $\displaystyle x\in [a,b]$ then you can generate a sequence,

starting with some point $\displaystyle x_0\in [a,b]$, and define $\displaystyle x_{n+1}=f(x_n)$

If the fixpoint p is unique in $\displaystyle [a,b]$ and $\displaystyle |f'(x)|< 1$ for $\displaystyle x\in [a,b]$ then $\displaystyle x_n\to p$ as $\displaystyle n\to\infty$. (wich is a theorem )

However in this case $\displaystyle f=1-2x^{16}$ has 2 fixpoints in [-1,1]...and the problem is slightly different. So we need to find out for which $\displaystyle x_0\in [-1,1]$, the sequence $\displaystyle (x_n)$ converges to 1 or to 0.8504...

But we may not even expect it to converge...since $\displaystyle |f'(x)|<1$ only for $\displaystyle x\in (-2^{2/3}, 2^{2/3})$

And I'm still trying to find out myself

4. One is -1 and the other is approx 0.8504
My point was that the first of these values cannot possibly be correct and that the second (approximation) is not too good either.

The 'function' is even, so any zeros will appear in pairs equidistant from the origin.

For a given 'function' there will be an infinite number of fixed point iterations, some of which converge to a particular fixed point and some that do not. To refer to the fixed point iteration doesn't make sense unless we are told what the iteration is.

5. ??? Unless the original post has been edited, -1 certainly is a fixed point: $\displaystyle 1- 2(-1)^{16}= 1- 2= -1$. And 0.8504 is a fixed point to 4 decimal places, which is all that is claimed.

Yes, the function is even, but we are not talking about zeroes, we are talking about fixed points: f(x)= x. $\displaystyle 1- 2x^{16}= x$ is the same as $\displaystyle F(x)= x+ 2x^{16}- 1= 0$ which is neither even nor odd.

Yes, there are many different iterations that can be called "fixed point iterations". But the one that is used, for example, in the "Banach fixed point theorem" can probably be called the "standard" and is the simplest- to find a fixed point for f(x), that is, to solve f(x)= x, start with some $\displaystyle x_0$ and define $\displaystyle x_{n+1}= f(x_n)$. If that converges, it will converge to a fixed point of f.

ductiletoaster, you can always find some region around a fixed point such that that iteration converges to the given fixed point for all points in the region. Of course, it may be very small and there may also be points far from the given fixed point for which that iteration converges. In general, the set of all points a which this iteration converges to a fixed point is fractal. I don't know of any simple way of characterizing it.

6. Yes, quite right.
I was looking at it (incorrectly) from the point of view of using a fixed point iteration to solve the equation
$\displaystyle 1-2x^{16}=0,$ .

7. However, is it true to say that 'you can always find some region around a fixed point such that the iteration converges to the given fixed point for all points within the region' ? I thought that it was necessary that $\displaystyle f(x_{n})\rightarrow x_{n+1}$ was a contraction mapping, and that doesn't seem to be the case for this example ?

8. Originally Posted by BobP
However, is it true to say that 'you can always find some region around a fixed point such that the iteration converges to the given fixed point for all points within the region' ? I thought that it was necessary that $\displaystyle f(x_{n})\rightarrow x_{n+1}$ was a contraction mapping, and that doesn't seem to be the case for this example ?
Yeah, I was thinking the same. I don't think it's true...

Let $\displaystyle a$ be a fixpoint, then $\displaystyle |f(a+ \epsilon)-a|= |1-2(a+ \epsilon)^{16}-a|= |2\sum_{k=0}^{15}{16\choose k}a^k\epsilon^{16-k}|<\epsilon??$

Can we find $\displaystyle \epsilon$ small enough such that the above inequality holds for both fixpoints?? And if so...i doubt this is true for all f..

I think f must be a contraction mapping...

edit: for $\displaystyle a=0.8504$... this is not true $\displaystyle |f(a+\epsilon)-a|= |2\sum_{k=0}^{15}{16\choose k}a^k\epsilon^{16-k}|\geq |2*16*a^{15}\epsilon|\approx 2.8*\epsilon$

This means that $\displaystyle f(x_n)$ will definitely not converge to $\displaystyle a$ for any starting point $\displaystyle x_0$ in $\displaystyle (a,1]$

9. SO to confirm. U guys are saying that the function will not converge on the interval (-1,1) to either of the values -1 or .8504?
When i did the fixed point iteration my x value kept alternating between almost 1 and almost 0. and it seemed it would continue forever.

I appreciate all of your guys help and discussions

10. The way you have set up your iteration scheme, it will not converge, because, as has been mentioned, the function is not a contraction. However, you're not confined to one iteration scheme. Try this one:

$\displaystyle 1-2 x^{16}=x$

$\displaystyle 1-x=2 x^{16}$

$\displaystyle \dfrac{1-x}{2}=x^{16}$

$\displaystyle \sqrt[16]{\dfrac{1-x}{2}}=x$

$\displaystyle f(x)=\sqrt[16]{\dfrac{1-x}{2}},$ and look for fixed points of that. The fixed points of this new function will be the fixed points of the old, and this one appears to be more stable. I think you could even prove that it's a contraction mapping.

11. Thank You all for your help on this proble! Really Appreciate it.

Dinkydoe you gave a great explanation to why it wont converge toward .8504. Can that same reasoning be applied to why it wont converge to -1. I guess im a little confused on the reasons for it. Im trying to get as simple as an explanation as possible. Im pretty new to this stuff. Thanks agian

Also how would i show / prove that this particular function in the form will not converge?

Ok so now im really confused. Everyone here says it wont converge to either -1 or .8504. But when using maple 13 I got it to converge to -1 using several random points. I think people are forgetting about the Interval [-1,1].... I belive it does converge on that interval but not on some value outside that interval

12. Also my proffesor said that if you were to code this up in matlab u could expect it to have the oppsiite behaviour as if u did it by hand? Is that true and what did he mean?

13. If a function $\displaystyle f$ is a contraction mapping on a complete nonempty metric space, then the Banach Fixed-Point Theorem says that the function has one unique fixed point. Furthermore, the iterative sequence $\displaystyle x_{n}=f(x_{n-1})$ converges to the fixed point.

Here's the upshot: contraction mappings will converge to the fixed point using the iteration scheme I just mentioned. With non-contraction mappings, you're not guaranteed anything. It might converge, it might not.

But when using maple 13 I got it to converge to -1 using several random points.
What commands did you use, exactly?

Also my proffesor said that if you were to code this up in matlab u could expect it to have the oppsiite behaviour as if u did it by hand?
Might be alluding to round-off error. But that would also depend on what is meant by "by hand". For me, in this situation, I'd probably use a calculator, in which case round-off error would presumably be similar to what it would be on a computer. Your professor's statement is certainly non-intuitive for me. I'd be curious to know more about what he meant.

14. Originally Posted by ductiletoaster
Thank You all for your help on this proble! Really Appreciate it.

Dinkydoe you gave a great explanation to why it wont converge toward .8504. Can that same reasoning be applied to why it wont converge to -1. I guess im a little confused on the reasons for it. Im trying to get as simple as an explanation as possible. Im pretty new to this stuff. Thanks agian

Also how would i show / prove that this particular function in the form will not converge?

Ok so now im really confused. Everyone here says it wont converge to either -1 or .8504. But when using maple 13 I got it to converge to -1 using several random points. I think people are forgetting about the Interval [-1,1].... I belive it does converge on that interval but not on some value outside that interval
I think everyone is right....I somewhat got the same. Experimented a little with maple:

Tried some values for $\displaystyle a=-1$, for the function $\displaystyle |f(a+\epsilon)-f(a)|$ and I got for every small value $\displaystyle \epsilon>0$ I tried, that $\displaystyle |f(a+\epsilon)-f(a)|>\epsilon$

This is not a proof ofcourse, but it makes it very likely to diverge....For a=0.8504 divergence can pretty easily be proved. (as I partially did).

But for $\displaystyle a=-1$ It's hard to estimate the term $\displaystyle |f(a+\epsilon)-f(a)|$ with a good lower-bound.

For a=0.8504 also $\displaystyle |f(a-\epsilon)-f(a)|>\epsilon$ must be shown. (wich is true..but a little harder to show)

So my conclusion is..., there's no convergence at all! Except for the values $\displaystyle x_0=1,-1, 0.8504$