Newton tangent method (1D)

Question

Newton tangent method for finding root of $f(x)=x^2-a \;$ is $$x_{k+1} = x_k-\dfrac{x_k^2-a}{2x_k},\;\;(k=0,1,2,...)$$ and its error $$|x_k-\sqrt{a}|\leq \dfrac{M}{2m}|x_k-x_{k-1}|^2$$ where $M=\max_{[c,d]}|f''(x)|$ and $m=\min_{[c,d]}|f'(x)|$. In one reference, I find special case $a=3$ and it needs to be found with precision $10^{-6}$. First $6$ approximations are
$$3.00000,\;2.0000000,\; 1.7500000,\; 1.7321429,\; 1.7320508,\; 1.7320508$$ They stopped when $x_k$ and $x_{k+1}$ got same first $6$ digits. Is it always case and does this guarantee that error will be less than $10^{-6}$ or is this some practical evaluation? I ask this because of these two numbers $M$ and $m$, it seems to me that they are ignored. No matter how small $|x_k-x_{k-1}|$, $M$ and $m$ can produce some large number. Can someone explain me is this $100$% correct to stop when $x_k$ and $x_{k-1}$ get same first $6$ digits

Answer 1

The formula give you the certainty that the error, the distance to the root, is indeed bounded by the step updates. Remember that if the step updates go to zero like $1/n$ or $1/n^2$ or even still with a geometric behavior with a factor close to $1$, then the step updates themselves have no or little information on the remaining distance to the limit.

Now here you have $|x_5-x_4|\le 10^{-7}$, which gives $|x_5-\sqrt3|\le \frac{M}{2m}10^{-14}$, so that if the derivatives behave not too extreme, the first factor is smaller than, say, $100$, the goal for the accuracy is reached.

If you take $x_{k+1}$ as proxy for the limit $\sqrt a$, then $\frac{|x_{k}-x_{k+1}|}{|x_k-x_{k-1}|^2}$ is a guess for the factor $\frac{M}{2m}$. For the gien values that gives \begin{array}{c|c|c} k & x_k & \frac{|x_{k}-x_{k+1}|}{|x_k-x_{k-1}|^2} \\ \hline 0& 3.00000000&\\ 1& 2.00000000& 0.25 \\ 2& 1.75000000& 0.2857 \\ 3& 1.73214286& 0.2887 \\ 4& 1.73205081& 0.2887 \end{array} so that indeed the amount of correct decimal digits doubles in every step after the second step.