Numerical analysis

• Jul 9th 2009, 08: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 $\displaystyle 10^{-2}$ for $\displaystyle x^3-x-1=0$ on [1,2] use $\displaystyle p_{0}=1$

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

first we should dtermine F(x)=x so

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

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

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

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

$\displaystyle F(p_1)=1.3122938366833=p_2$

$\displaystyle 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, 09: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, 10:01 AM
Random Variable
Why not use Newton's Iteration?
• Jul 9th 2009, 10: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, 10: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, 11:50 AM
halbard
Say you decide that the answer should be $\displaystyle x=1.32$ correct to 2~decimal places. How can you check your answer? Use the sign change method.

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

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

Since $\displaystyle f(x)$ changes sign and is continuous on $\displaystyle (1.315,1.325)$, the root is $\displaystyle 1.32$ correct to 2 d.p.
• Jul 15th 2009, 01: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 $\displaystyle 10^{-2}$ for $\displaystyle x^3-x-1=0$ on [1,2] use $\displaystyle p_{0}=1$

The iteration we will consider is generated from the rearrangement:

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

then:

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

is our iteration.

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

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

where $\displaystyle \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: $\displaystyle |\varepsilon^2 f''(x)/2!|< 0.2a; \varepsilon^2$ (please justify this last inequality yourself, or something tighter if you like)

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

and so:

$\displaystyle |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 $\displaystyle n$ passes through the iteration is less than $\displaystyle 2^{-n}$ and we need to find $\displaystyle n$ such that:

$\displaystyle 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