# Numerical analysis

• Jul 9th 2009, 09:27 AM
Amer
Numerical analysis
I want just how to solve it give me a hint

The question:-

Use fixed-point iteration method to determine a solution accurate to within $10^{-2}$ for $x^3-x-1=0$ on [1,2] use $p_{0}=1$

here is my solution (correct me if I was wrong )

first we should dtermine F(x)=x so

$x^3-x-1=0 \Rightarrow x^3=x+1 \Rightarrow x=\sqrt[3]{x+1}\Rightarrow F(x)=\sqrt[3]{x+1}$

$F'(x)=\frac{1}{3\sqrt[3]{(x+1)^2}}$

$\mid F'(x) \mid <1$ so F(x) is converge now

$F(p_{0})=\sqrt[3]{2}=1.2599210498949=p_1$

$F(p_1)=1.3122938366833=p_2$

$F(p_2)=1.3223538191388=p_3$

..................etc

when I should stop ??
my solution is correct or it is wrong ??

Thanks for the help
• Jul 9th 2009, 10:41 AM
arbolis
You should stop when the first 2 digits after the coma don't change with newer iterations.
For the rest I can't help you because I have to revise my Numerical Analysis course first.
• Jul 9th 2009, 11:01 AM
Random Variable
Why not use Newton's Iteration?
• Jul 9th 2009, 11:06 AM
arbolis
Quote:

Originally Posted by Random Variable
Why not use Newton's Iteration?

Because the question ask to use fixed-point iteration.(Wink)
• Jul 9th 2009, 11:06 AM
Amer
Quote:

Originally Posted by Random Variable
Why not use Newton's Iteration?

I know it but I should understand how this work to understand fixed point iteration and newton is a special function F(x)

I can use it to find F(x) but I do not know how to work with fixed point iteration in general
• Jul 10th 2009, 12:50 PM
halbard
Say you decide that the answer should be $x=1.32$ correct to 2~decimal places. How can you check your answer? Use the sign change method.

If $1.32$ is correct to 2 d.p. then the root must lie in the interval $(1.315,1.325)$.

$f(x)=x^3-x-1$, $f(1.315)=-0.0411$ and $f(1.325)=0.0012$ (4 d.p.).

Since $f(x)$ changes sign and is continuous on $(1.315,1.325)$, the root is $1.32$ correct to 2 d.p.
• Jul 15th 2009, 02:59 AM
CaptainBlack
Quote:

Originally Posted by Amer
I want just how to solve it give me a hint

The question:-

Use fixed-point iteration method to determine a solution accurate to within $10^{-2}$ for $x^3-x-1=0$ on [1,2] use $p_{0}=1$

The iteration we will consider is generated from the rearrangement:

$x=f(x)=(1+x)^{1/3}$

then:

$x_n=f(x_{n-1})$

is our iteration.

Now we expand $f(x)$ as a Taylor series about the root:

$f(x+\varepsilon)=f(x)+\varepsilon f'(x)+ \varepsilon^2 R(x)$

where $\varepsilon^2 R(x)$ is the remainder term, and as the serier is alternating from the second term onwards we know that this is bound by the absolute value of the first neglected term: $|\varepsilon^2 f''(x)/2!|< 0.2a; \varepsilon^2$ (please justify this last inequality yourself, or something tighter if you like)

Hence as on $[1,2]$ $|\varepsilon|<1$ we have $\varepsilon^2 R(x)<0.2\;\varepsilon$

and so:

$
|f(x)-f(x+\varepsilon)|<0.5 \varepsilon.
$

Hence in the iteration the error more than halves at each pass (in fact it does better than this I leave it to the reader to find tighter bounds here).

Hence the error after $n$ passes through the iteration is less than $2^{-n}$ and we need to find $n$ such that:

$2^{-n}<10^{-2}$

this will guarantee that our error is less than the required limit, which looks like 6 iterations to me.

(in fact this is pessimistic since I have been rather generous in estimating the bounds)

CB