Results 1 to 14 of 14

Math Help - Fixed point iteration

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    27

    Fixed point iteration

    Ok so I have a function 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    663
    Thanks
    133
    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 ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Quote Originally Posted by BobP View Post
    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 p such that f(p)=p

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

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

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

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

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

    And I'm still trying to find out myself
    Last edited by Dinkydoe; October 20th 2010 at 05:01 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2009
    Posts
    663
    Thanks
    133
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,453
    Thanks
    1868
    ??? Unless the original post has been edited, -1 certainly is a fixed point: 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. 1- 2x^{16}= x is the same as 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 x_0 and define 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2009
    Posts
    663
    Thanks
    133
    Yes, quite right.
    I was looking at it (incorrectly) from the point of view of using a fixed point iteration to solve the equation
    1-2x^{16}=0, .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2009
    Posts
    663
    Thanks
    133
    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 f(x_{n})\rightarrow x_{n+1} was a contraction mapping, and that doesn't seem to be the case for this example ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Quote Originally Posted by BobP View Post
    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 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 a be a fixpoint, then |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 \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 a=0.8504... this is not true |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 f(x_n) will definitely not converge to a for any starting point x_0 in (a,1]
    Last edited by Dinkydoe; October 20th 2010 at 03:05 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2010
    Posts
    27
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    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:

    1-2 x^{16}=x

    1-x=2 x^{16}

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

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

    So set up your function

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2010
    Posts
    27
    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
    Last edited by ductiletoaster; October 20th 2010 at 05:36 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Oct 2010
    Posts
    27
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    If a function 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 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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Quote Originally Posted by ductiletoaster View Post
    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 a=-1, for the function |f(a+\epsilon)-f(a)| and I got for every small value \epsilon>0 I tried, that |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 a=-1 It's hard to estimate the term |f(a+\epsilon)-f(a)| with a good lower-bound.

    For a=0.8504 also |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 x_0=1,-1, 0.8504
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fixed point iteration help
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: November 8th 2011, 12:19 PM
  2. Fixed Point Iteration
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 10th 2010, 11:14 AM
  3. Fixed Point Iteration and Logistic Map
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 2nd 2010, 01:15 PM
  4. Fixed point iteration
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 2nd 2010, 08:30 AM
  5. Fixed Point Iteration
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 12th 2009, 01:40 PM

Search Tags


/mathhelpforum @mathhelpforum