7
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Any reasonable convergence criterion must be invariant to scaling of the function. A decent stopping criterion is therefore if $|f(x_k)| \le \varepsilon |f(x_0)|$ where $x_0$ is the starting point of the iteration. It's slightly 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. $\endgroup$ – Wolfgang Bangerth Nov 26 '18 at 22:44
  • 1
    $\begingroup$ There are two overlapping issues here: how to stop Newton's method correctly, and whether $f(x^*)$ can be expected to be small. The latter has much more to do with how exactly you define a "numerical root" of a function. You seem to expect that at a root, $|f(x^*)|<\epsilon$, but this isn't right at all and is generally not something you should rely on. $\endgroup$ – Kirill Nov 27 '18 at 15:44
  • $\begingroup$ @Kirill: What is a sensible definition of numerical root? $\endgroup$ – user14717 Nov 27 '18 at 19:11
  • $\begingroup$ It's a root if $f(x^\ast)$ is small compared to typical objects that have the units of $f$. If you measure weights in kilograms and $f(x)$ provides you with the weight of individual atoms, then $f(x^\ast)$ has to be exceedingly small for $x^\ast$ to be considered a root -- on the order of maybe $10^{-23} kg$. On the other hand, if $f(x)$ provides you with the mass of stars measured in kilograms, then you will be quite convinced that $x^\ast$ is a root if $f(x^\ast)$ is smaller than $10^{28}$ kg. $\endgroup$ – Wolfgang Bangerth Nov 28 '18 at 3:56
  • $\begingroup$ @WolfgangBangerth: I'm not sure this is actionable advice, unless the domain expert is also the one writing the root-finder. Most Newton solvers are black boxes. $\endgroup$ – user14717 Nov 28 '18 at 3:58
2
$\begingroup$

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.

$\endgroup$

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.