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.

  • $\begingroup$ 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? $\endgroup$ – Baffo rasta Feb 3 '18 at 21:50
  • $\begingroup$ I am applying the definition of differentiability of the function $f$ at the point $x^*$ and using $f(x^*) = 0$. $\endgroup$ – Carl Christian Feb 3 '18 at 23:07
  • $\begingroup$ Oh, I see. That topic in our class is in the second course of math analysis, which is more advanced than this (one term later). I got to eat that pill without understanding it... $\endgroup$ – Baffo rasta Feb 4 '18 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.