I'm facing the numerical analysis exam preparation right now and I have this proposition (about stopping criteria for iterative methods):
A general stopping criteria, valid whatever the iterative method is, could be this one: you can think about stopping the algorithm when you reach a value $x_k$ such that $f(x_k)$ is close to $0$. This, in floating point arithmetic, can be translated as follows:
$|f(x_k)| < \eta$
where $\eta$ is a positive real number greater than the machine accuracy $\epsilon_m$. This, anyway, doesn't guarantee itself that the $x_k$ that made the algorithm stop is even close to the actual root $x^*$, which can be really far from $x_k$ or in general, $|x_k - x^*| = |e| $ can be $> \eta$, being $e$ the absolute error. This criteria is then to use whenever you're not looking for the root itself but you can feel satisfied getting some $x_k$ such that it's value through the function is close to $0$.
The relationship between $|x_k-x^*|$ and $|f(x_k)|$ depends on the local behavior of the $f$ around $x^*$ and in particular from the value of $f(x^*)$.
[...]
I'm not able to figure out on my own how is that relationship between the two related to the value of $\frac{d}{dx}f(x)$ in $x = x^*$. Any illumination?
Yes. Assumptions are required. Let $I \subseteq \mathbb R$ be an open interval and let $f : I \rightarrow \mathbb R$ be differentiable. Let $\x^* \in I$ be a zero of $f$ and let $x \in I$. Then $f(x^*) = 0$ and $$ f(x) = f'(x^*)(x - x^*) + \epsilon(x-x^*)(x-x^*),$$ where $$\epsilon(y) \rightarrow 0, \quad y \rightarrow 0, \quad y \not= 0.$$ If $f'(x^*) \not = 0$, then we can deduce $$ x - x^* = \frac{f(x)}{f'(x^*) + \epsilon(x-x^*)},$$ when $x$ is is sufficiently close to $x^*$, i.e., when $|\epsilon(x - x^*)| < |f'(x^*)|$.
If $f'$ is continuous, then it follows $$ x^* \approx x - \frac{f(x)}{f'(x)},$$ when $x$ is sufficiently close to $x^*$.
Beware of the fact that you do not know if you are sufficiently close to a root. You will be better served by refining a bracket around the root, but that is a question for another day.