Defining a condition number and termination criteria for Newton's method

Question

The condition number of function evaluation $$ \mathrm{cond}(f,x) := \left| \frac{x f'(x)}{f(x)} \right| $$ is infinite at a root of $f$. Hence it is useless for rescaling a tolerance which defines an exit condition from Newton's method. For instance, naively, you would exit the Newton iteration $$ x_{k+1} := x_{k} - f(x_{k})/f'(x_{k}) $$ when (say) $|f(x_{k+1})| < \epsilon$, where $\epsilon$ is (again, say) the double epsilon. However, even if $x^{*}$ is the correct floating point approximation of the root, we have no guarantee that $|f(x^{*})| < \epsilon$, due to the aformentioned ill-conditioning.

Is there a way to define a generalized condition number $\kappa(f, x)$ for Newton's method so that a reasonable termination condition can written in the form $|f(x_{k})| < \kappa(f, x_{k}) \epsilon$.

Note, even the proposed form of the termination condition is problematic, because the sequence $\{x_{k}\}$ is invariant under rescaling $f\mapsto \lambda f$, but the proposed form of the termination condition is not. Can we write a termination condition which is scale invariant?

The function which lead me to these questions was $$ f(z) := 601080390z -185961388.136908293 + 141732493.98435241i $$ Applying Newton's iteration to this leads to convergence to the true root in just three iterations starting with the guess of $i$, but $|f(z^{*})| \approx 3\times 10^{-8}$, which somehow feels "far from zero" in double precision, so my termination condition was never satisfied.

Answer 1

Any reasonable convergence criterion must be invariant to scaling of the function. A decent stopping criterion is therefore if $\|f(x_k)\|≤ \epsilon\|f(x_0)\|$ where $x_0$ is the starting point of the iteration. It's slightly annoying that the stopping criterion now depends on the starting point, but because Newton's iteration converges so quickly close to the solution, this criterion in practice works pretty well.