Newton's finding root method - n digits accuracy

Question

I have read about the Newton's method in Wikipedia.

https://en.wikipedia.org/wiki/Newton%27s_method

By checking the pseudocode in the thread, I have noticed a tolerance is defined (in that case $10^{-7}$).

and if

$|x_n-x_{n-1}|\le tolerance\cdot|x_n|$

is satisfied then the root is found with the same accuracy (or better) of the tolerance (7 digits in our case).

I'd appreciate if anyone could explain why is that true?

For the sake of my question, let's assume that the method converges.

Answer 1

Close to the root you may assume that $|x_n-x_*|<C\cdot|x_n-x_{n-1}|^2=ϵ|x_n-x_{n-1}|$ with some reasonably small $ϵ\ll 1$. Thus it is safe to claim that more than $7$ leading digits are correct if the relative step size is $10^{-7}$.

For this to fail the factor $C$ would have to be excessively large, which could happen with closely clustered roots (like for example $x^7+10^{-9}$) or an otherwise wildly oscillating function. Most of the examples you see that do not involve large numbers or small constants do not fall in that class.