1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fixed point iteration

  1. Aug 18, 2011 #1
    1. The problem statement, all variables and given/known data

    "Use a fixed-point iteration method to find an approximation to [itex]\sqrt[3]{25}[/itex]that is accurate to within10^-4"

    i need the solution in step by step ...

    2. Relevant equations

    x=g(x)

    3. The attempt at a solution

    all i can get is the range

    [itex]\sqrt[3]{8}[/itex] [itex]\leq [/itex][itex]\sqrt[3]{25}[/itex] [itex]\leq[/itex] [itex]\sqrt[3]{27}[/itex]

    then [a,b] = [2,3]

    i can't get g(x) or solve this problem.

    ---------

    update i've completed some of the question but still i get wrong answer

    x^3-25=0
    x.x^2=25
    x^2=25/x
    x= 5/[itex]\sqrt[2]{x}[/itex]

    g(2)= 5/[itex]\sqrt[2]{2}[/itex] = 3.53553391 ( not in the bounded area)
    g(3)=5/[itex]\sqrt[2]{3}[/itex] = 2.88675135 (correct)

    i can't use this formula unless both answers are withing the range 2-3....
     
    Last edited: Aug 18, 2011
  2. jcsd
  3. Aug 18, 2011 #2

    uart

    User Avatar
    Science Advisor

    Why is that?
     
  4. Aug 18, 2011 #3
    Can you describe what is a "fixed point iteration" as you understand it?

    I see it as an iterative function F(x) such that
    Xn+1 = F(Xn)
    similar to Newton's method which eventually gives a value very close to the required solution.

    See also:
    http://en.wikipedia.org/wiki/Fixed_point_iteration
     
  5. Aug 18, 2011 #4

    rcgldr

    User Avatar
    Homework Helper

    Last edited: Aug 18, 2011
  6. Aug 18, 2011 #5
    1st condition of fixed point iteration solutions must be within the range [2-3]

    it's very similar to newton but i must use it to get the roots

    i've checked wikipedia but still i can't figure out what's wrong , i've checked the solution manual of numerical analysis burdon , they got the same g(x) and same range[2-3] but still i get the wrong answer
     
  7. Aug 18, 2011 #6

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member



    Your iterations may be outside of the specifed region but the answer is not. You need to show us some results of your iterations.

    Not sure why you say 2.88675135 is correct, since cubing it gives 24.05626132. This is not within your specified error.

    Pick either end point or the mid point of your region and iterate. You will arrive at the correct answer within a dozen iterations.
     
  8. Aug 18, 2011 #7
    Newton's works very well when we put
    f(x)=x^3-25
    It converges to 2.924017738212866 in 7 iterations starting with x0=2, and in 5 starting with x0=3.
     
  9. Aug 18, 2011 #8
    there are 3 rules that every equation must pass before making iterations

    1. function is continuous
    2. max and min value of the function is between [a,b] which in this case is 2,3
    3. [g'(x)]<1

    so when i put 2 it should be within 2-3 range same for 3... but when i add 2 it gives answer out of the permitted range.

    yeah netwon method works fine but i need to solve it with fixed point :wink:
     
  10. Aug 18, 2011 #9

    rcgldr

    User Avatar
    Homework Helper

    Fixed point math would use the same method. Are you thinking fixed point means integer? It uses the integer instructions of a cpu, but the logical format of the numbers is

    xxxxxxxx.xxxxxxxx

    where the x's represent the 0's and 1's of a fixed point number (16 bit number example here) with the fixed point in the middle (or off center if wanted). You'll need to shift to the right after any multiply and shift the divisor to the left before any divide (you may need to use multiple steps for the divide).

    I updated my previous post to include a link to cube root algorithms.

    For a more general function, you can base the initial guess via a lookup table that's indexed by the location of the most significant (non-zero) bit of the number (you'd need 32 entries for a 32 bit number, 64 entries for a 64 bit number), where you've pre-calculated exact solutions for powers of 2 in the table entries.
     
  11. Aug 18, 2011 #10

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This thread is about fixed point iteration. Please leave Newton's method to threads about Newton's method.
     
  12. Aug 18, 2011 #11
    OK, use
    Xn+1=5/sqrt(Xn), but you can use
    a=2.8, a^3=21.952
    b=3, b^3=27
    then 5/sqrt(a)=2.988<3 and 5/sqrt(b)=2.886...>2.8
     
  13. Aug 18, 2011 #12
    then the 2nd condition "2. max and min value of the function is between [a,b] which in this case is 2,3" doesn't meet with this equation.

    i've tried to get the solution from fixed point iteration calculator

    http://maccery.com/maths/fixed_point.php [Broken]

    x=(25)^(1/3)
    Accuracy = 10^-4
    Starting Value=2

    x1 = 2.92401773821
    x2 = 2.92401773821
    (25)^(1/3)
    (25)^(1/3)

    ANSWER: 2.9240177382

    --------

    the result is right but still i don't know how it was done .
     
    Last edited by a moderator: May 5, 2017
  14. Aug 18, 2011 #13
    There is no iteration in
    x=(25)^(1/3)
    so the calculator simply evaluated the expression and gave the answer.

    x needs to be on the right hand side to initiate iterations (e.g. x0=2)

    if x=5/sqrt(5) does not satisfy the [2,3] interval conditions, you'll need to find other functions such as x=sqrt(5*sqrt(x)) which iterates 19 times to give the same answer as above, using an initial value of 2 where sqrt(5sqrt(2))=2.659 is within [2,3].
     
  15. Aug 18, 2011 #14
    yeah i know this equation but this is the answer in the solution manual

    24m9mqq.jpg

    also what's the equation for knowing the number of iteration in fixed point?

    i know this equation

    (k^n)/(1-k) [b-a] <error

    is there an easier form ?
     
  16. Aug 18, 2011 #15

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You have the equation:

    [tex] x= \frac 5 {\sqrt x} [/tex]

    Now perform iterations.

    [tex] x_n= \frac 5 {\sqrt {x_{n-1}}} [/tex]

    Take x0= 2.5

    compute x1 ,x2 etc until you get inside of the desired error.
     
  17. Aug 19, 2011 #16
    the equation will get a result out of the range [2-3]

    -----

    another question how can i know the number of iteration in fixed point , if i'm given the g(x) equation and error occur withing 10^-5

    ex:

    x=((e^x)/3)^(1/2) within 10^-5

    I'm not given the range of the period.
     
  18. Aug 19, 2011 #17

    uart

    User Avatar
    Science Advisor

    Hi Enger. Where exactly did you get this specified range of [2..3] from?

    The function 5/sqrt(x) has derivative magnitude less than unity for all x > 2.5^(2/3), which is approx x > 1.842. So it seems that the [2..3] interval is some arbitrary restriction that you're imposing and which does not appear to be part of that original problem description.
     
    Last edited: Aug 19, 2011
  19. Aug 20, 2011 #18

    uart

    User Avatar
    Science Advisor

    If either the convergence is rapid or if the error is alternating (as in 1.85, 1.62, 1.79, 1.73 etc) then the difference between successive x values, ([itex]x_n - x_{n-1}[/itex]), is a reasonable estimate of the error. It's actually an over-estimate of the error if the convergence is alternating and an underestimate if the convergence is monotonic. If the convergence is fairly rapid then this underestimate is not too severe, however if you've got slow monotonic convergence then the difference between successive x values will significantly underestimate the error.

    In that case you need to calculate the derivative to get a better estimate of the error. If M is the maximum value of [itex]g'(x)[/itex] on the interval [itex]x_{n-1}..x_n[/itex] then a good estimate of the error is:

    [tex]\frac{\left| x_{n} - x_{n-1} \right|}{1-M}[/tex]
     
    Last edited: Aug 20, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook