# Given a function $f(x)$ under which condition $|f(x_k)|<\eta$ implies that $x_k$ is close to the function root?

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^*$.
• how do you tell that $f(x) = f'(x)(x-x^*)+\epsilon(x-x^*)(x-x^*)$? The first term remembers me the Taylor expansion of $f$ around the root $x^*$, is the second part some kind of a remainder? – Baffo rasta Feb 3 '18 at 21:50
• I am applying the definition of differentiability of the function $f$ at the point $x^*$ and using $f(x^*) = 0$. – Carl Christian Feb 3 '18 at 23:07