Fixed point iteration

1. Aug 18, 2011

enger

1. The problem statement, all variables and given/known data

"Use a fixed-point iteration method to find an approximation to $\sqrt[3]{25}$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

$\sqrt[3]{8}$ $\leq$$\sqrt[3]{25}$ $\leq$ $\sqrt[3]{27}$

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/$\sqrt[2]{x}$

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

i can't use this formula unless both answers are withing the range 2-3....

Last edited: Aug 18, 2011
2. Aug 18, 2011

uart

Why is that?

3. Aug 18, 2011

mathmate

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

4. Aug 18, 2011

rcgldr

Last edited: Aug 18, 2011
5. Aug 18, 2011

enger

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

6. Aug 18, 2011

Integral

Staff Emeritus

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.

7. Aug 18, 2011

mathmate

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.

8. Aug 18, 2011

enger

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

9. Aug 18, 2011

rcgldr

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.

10. Aug 18, 2011

Integral

Staff Emeritus
This thread is about fixed point iteration. Please leave Newton's method to threads about Newton's method.

11. Aug 18, 2011

mathmate

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

12. Aug 18, 2011

enger

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
13. Aug 18, 2011

mathmate

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].

14. Aug 18, 2011

enger

yeah i know this equation but this is the answer in the solution manual

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 ?

15. Aug 18, 2011

Integral

Staff Emeritus
You have the equation:

$$x= \frac 5 {\sqrt x}$$

Now perform iterations.

$$x_n= \frac 5 {\sqrt {x_{n-1}}}$$

Take x0= 2.5

compute x1 ,x2 etc until you get inside of the desired error.

16. Aug 19, 2011

enger

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.

17. Aug 19, 2011

uart

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
18. Aug 20, 2011

uart

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, ($x_n - x_{n-1}$), 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 $g'(x)$ on the interval $x_{n-1}..x_n$ then a good estimate of the error is:

$$\frac{\left| x_{n} - x_{n-1} \right|}{1-M}$$

Last edited: Aug 20, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook