0

In a generic rootfinding problem $f(x) = 0$, we assume that the probability that the root $x$ is a floating point representable is zero. Hence, the best floating point approximation $\hat{x}$ to $x$ gives $f(\hat{x}) = f(x(1+\delta)) = x\delta f'(x) + \mathcal{O}(\delta^2) \approx x\delta f'(x)$ where $|\delta| \le \mu_{M}$, where $\mu_{M}$ is the unit roundoff.

Hence, any rootfinding iteration can be terminated when $|f(\hat{x})| \le \mu_{M}|x f'(x)|$. However, this termination criteria fails in the presence of a double root.

What is a sensible termination criteria for a rootfinding problem in the presence of a double root? (The assumption being that $f \in C^{2}$ and $f''$ is available.)

@LutzLehman makes a valid point that this may be impossible in general. Nonetheless I have succeeded in every case I have tested for the case of polynomials by use of the expected residual

$$ \mu_{M}\left[\sum_{k=0}^{n} |c_k||x|^k + |xp'(x)| \right] $$

Maybe using a running error estimate in the evaluation of $f$ might succeed in the general case?

user14717
  • 2,155
  • 13
  • 14
  • 2
    How do you detect the presence of a double root? As a minimum of the function, a sign change in the derivative, detection of linear convergence in the Newton method, some other means? That is, how do you distinguish $f(x)=x^2-h^2$ from $f(x)=x^2$ from $f(x)=x^2+h^2$ if $h^2\sim \mu_M$ or only a little larger? – Lutz Lehmann Feb 24 '22 at 08:27
  • @LutzLehmann: I don't need it to detect the presence of a double root; all I need is to define a termination criteria for a rootfinding iteration that works with both double and single roots. – user14717 Feb 24 '22 at 16:19
  • 1
    I still maintain that such a criterion and if it exists depends on the root-finding method. With a bracketing method you will not find double roots or roots of even order. They might find roots of odd multiplicity, but with the usual errors of $\sim\mu_M^{1/m}$. With the Newton method, as said, you can check for linear convergence instead of the expected quadratic. Then apply step doubling or tripling to see if the next step from there proceeds in the opposite direction, essentially finding a bracketing interval for the derivative. – Lutz Lehmann Feb 24 '22 at 16:40

0 Answers0