Fixed-point iteration method to find an approximation

[enger]

Homework Statement

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

Homework Equations

x=g(x)

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

 

[uart]

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

Why is that?

 

[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

 

[rcgldr]

A cube root can be a problem for Newton's method:

http://en.wikipedia.org/wiki/Newton's_method#Derivative_does_not_exist_at_root

Some iterative algorithms for cube root:

http://www.mathpath.org/Algor/cuberoot/cube.root.iterations.htm

 

[enger]

Why is that?

1st condition of fixed point iteration solutions must be within the range [2-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

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

Are you supposed to use something like Netwon's method? Link to wiki example for square root of a number. The Wiki article doesn't explain how to choose the initial number (it could use a table look up based on the left most non-zero bit), or you could start with 1 and just iterate more. A cube root solution could have the issue of diverging if the initial guess value is not close.

http://en.wikipedia.org/wiki/Newton's_method#Square_root_of_a_number

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

 

[Integral]

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

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.

 

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

 

[enger]

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.

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.

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.

yeah netwon method works fine but i need to solve it with fixed point

 

[rcgldr]

Netwon method works fine but i need to solve it with fixed point.

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.

 

[Integral]

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.

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

 

[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

 

[enger]

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

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

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 .

 

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

 

[enger]

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

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 ?

 

[Integral]

You have the equation:

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

Now perform iterations.

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

Take x₀= 2.5

compute x₁ ,x₂ etc until you get inside of the desired error.

 

[enger]

You have the equation:

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

Now perform iterations.

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

Take x₀= 2.5

compute x₁ ,x₂ etc until you get inside of the desired error.

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.

 

[uart]

the equation will get a result out of the range [2-3].

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.

 

[uart]

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.

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}$$