We have known that if $g: [a,b] \rightarrow [a,b]$, $g$ is differential in $(a,b)$, $k \in (0,1)$ and $|g'(x)| \leq k, \forall x \in (a,b)$ then $g$ has a unique fixed point $x^*$. Moreover, for all $x_0\in [a,b]$, $x_{n+1}:=g(x_n) ,\forall n$ , we have $x_n \in [a,b], \forall n $ and $x_n$ converges to $x^*$.
Let see a problem, use the Fixed-point interation to find an approximation to correct to within $10^{-t}$ for $f(x)=0 \Leftrightarrow x=g(x)$.
We have to choose $x_0 \in [a,b]$ and let $x_{n+1}:=g(x_n),\forall n$. But for each step $x_n \in \mathbb {R} $/$ {\mathbb{Q}}$ , we just can take finite number of digits, we round $x_n$ off to $l$ decimal places ($l>k$) $$u_n:=\overline{x}_n=x_n+r_n , |r_n|\leq \frac{1}{2}10^{-l}$$ Then $u_{n+1}:=\overline{g(u_n)}=g(u_n)+r_{n+1}$
So we have $u_0=x_0+r_0$ and $ u_{n+1}=g(u_n)+r_{n+1}, \forall n$.
I want to prove: exits $n_0$ such that $$|u_{n+1}-x^*|\leq \frac{1}{2}10^{-t}, \forall n \geq n_0.$$
My ideal is:
If I can prove for $l$ is choosen, $u_n \in [a,b], \forall n$ (1)
then I have
$$u_1=g(u_0)+r_1=g(x_0+r_0)+r_1=g(x_0)+g'(c_0)r_0+r_1 = x_1++g'(c_0)r_0+r_1$$ ($c_0$ is between $x_0+r_0$ and $x_0$).
... $$u_{n+1}=x_{n+1}+g'(c_0)...g'(c_{n})r_0+...+g'(c_n)r_n+r_{n+1}$$ So $$|u_{n+1}-x^*|\leq |x_{n+1}-x^*|+\sum_{i=0}^n{|r_{i }|k^{n+1-i}}\leq|x_{n+1}-x^*|+\frac{1}{2}10^{-l}\frac{1-k^{n+2}}{1-k}$$
As $x_n \rightarrow x^*$, $\epsilon:= \frac{1}{2}10^{-t}-\frac{1}{2}10^{-l}\frac{1}{1-k}>0$ (choose $k >l$ and $ 10^{l-k} > \frac{1}{1-k}$), exits $n_0$ such that for all $n \geq n_0$ $|x_{n+1}-x^*|<\epsilon$
Then $|u_{n+1}-x^*|\leq \frac{1}{2}10^{-t}, \forall n \geq n_0.$
Is it ok? I still can't prove (1), help me, thanks!