numerical analysis : Fixed point iteration

Question

Let $f(x)=x^3-2x+1$. To solve $f(x)=0$, the following fixed-pint problems are proposed. Derive each fixed point method and compute $p_1,p_2,p_3,p_4$. Which method seem to be appropriate?

a) $x=\dfrac{1}{2}(x^3+1), \quad p_0=\dfrac{1}{2}$

b) $x=\sqrt{2-\dfrac{1}{x}} \quad p_0=\dfrac{1}{2}$

My question is : I don't understand this part : "Derive each fixed point method..."

For instance a), if I define $g:x\to \dfrac{1}{2}(x^3+1)$, Is it for showing that $|g'(x)|\le k$, with $0<k<1$ for $x\in (a,b)$ (but I haven't got a and b)

Answer 1

Do the practical part first, compute the first iterates

xa, xb = 0.5, 0.7
for k in range(20): 
    print "%2d   %.16f   %.16f"%(k, xa, xb); 
    xa, xb = 0.5*(xa**3+1), (2-1/xb)**0.5

(Note that $p_0=0.5$ is a bad initial point for the second iteration) with the output

 0   0.5000000000000000   0.7000000000000000
 1   0.5625000000000000   0.7559289460184544
 2   0.5889892578125000   0.8228756555322952
 3   0.6021626445663060   0.8858609162721143
 4   0.6091720424515518   0.9333566429819850
 5   0.6130290024555829   0.9636379955296486
 6   0.6151895466090406   0.9809515320948682
 7   0.6164117575462150   0.9902432237224228
 8   0.6171069705010023   0.9950613504174247
 9   0.6175036508304039   0.9975153327668412
10   0.6177303928265216   0.9987537953960944
11   0.6178601291968180   0.9993759254816862
12   0.6179344041093612   0.9996877191250637
13   0.6179769410211693   0.9998437985881874
14   0.6180013063267487   0.9999218840416958
15   0.6180152643778877   0.9999609382066462
16   0.6180232609643845   0.9999804681496348
17   0.6180278423824228   0.9999902338363781
18   0.6180304672297162   0.9999951168585770
19   0.6180319711098671   0.9999975584143853

where one can observe the rather slow convergence towards the roots $\frac12(\sqrt5-1)=0.61803398874989..$ and $1$.

Then continue with your observation where the derivative has absolute value smaller $1$ and what roots lie inside that interval. A sign-change and monotonicity argument is sufficient if one can not guess the root.