When I use Bisection method to find a solution $r$ of equation $f \in C^2[a,b]$, within tolerance $10^{-k}$ and approximate to the $k$rd decimal place.
For each step, assume that $x_n=\frac{a_n+b_n}{2} \in \mathbb Q^c$. I want to approximate $x_n$ to the $l-$rd decimal place $\overline{x_n}$ ($l > k$). I know that exit $N \in \mathbb N$ such that $$|\overline{x_n} - r| \leq 10^{-k } \text{ } \forall n \geq N.(1)$$ I tthink it will help calculate easier and guarantee the accuracy of approximation $\overline{x_n}$.
Prove (1)
Let $d_n=\frac{a_n-b_n}{2}$ $$|\overline{x_n} - r| \leq |\overline{x_n} - x_n | + |x_n -r| \leq \frac{1}{2}10^{-l}+\frac{d_n}{2}$$ clearly, $$d_{n+1} \leq \frac{d_n}{2}+\frac{1}{2}10^{-l}\leq ... \leq \frac{d_1}{2^n}+\frac{1}{2}10^{-l}. (2)$$ So that $$|\overline{x_n}-r|\leq \frac{d_1}{2^n}+10^{-l}$$ When $ n \longrightarrow \infty$ , $\frac{d_1}{2^n} \longrightarrow 0$, as $k >n$ , exit $N$ such that $$|\overline{x_n} - r| \leq 10^{-k } \text{ } \forall n \geq N.$$ When I use Newton's method, I also want to have (1), but it's so hard for me to have the estimation like (2). I just know that $$|x_n -r| \leq \frac{M}{2m}d_n^2$$ $M:=\max_{[a,b]}|f|, m:=\min_{[a,b]}|f'|$. (Assume this method is successful).
Help me, thank you so much !
I suppose that $d_n=\vert x_{n-1}-r\vert$. Then your estimate is almost true. $M$ has to be replaced by $M_2:=\max_{[a,b]}|f''|$ (see wikipedia on Newton iteration for example).
But this is not what you are looking for. But you get an explicit estimate $|x_n-r|$ by observing $f(r)=0$, $|f(x_n)|=|f(x_n)-f(r)|=|f'(\xi) (x_n-r)|\geq m |x_n-r|$ or $|x_n-r|\leq\frac{|f(x_n|}{m}$.