Let $f$ be a monic univariate polynomial with real coefficients:


$$f\_A(x) = x^n + a\_{n-1}x^{n-1} + ... + a\_{0}$$


The values of $A=(a\_{n-1},...,a\_0)$ are unknown, but are estimated as $B=(b\_{n-1},...,b\_0)$ with error $\epsilon$. Therefore, $b\_i - \epsilon \leq a\_i \leq b\_i + \epsilon$. Furthermore, the value of $\epsilon$ can be reduced arbitrarily, but cannot be set to 0. (Changing $\epsilon$ will alter the $B$ estimates). $lim\_{\epsilon\rightarrow 0} B = A$


**Question 1) Is there any method of determining if $f\_A$ has a repeated root using $B$ and the ability to reduce $\epsilon$?**


I've worked out how to isolate the roots of $f\_A$ if $f\_A$ does not have repeated roots as follows:


$D(A)$, the discriminant of $f\_A$, must be non-zero. As computing $D(B)$ from the Sylvester resultant of $f\_B$ and $f\_B'$ can be accomplished with only $+$ and $\*$ operators, $g(\epsilon,B)$, the error propagated while calculating the resultant, must strictly increase. We can decrease the value of $\epsilon$ until $D(B) + g(\epsilon,B) < 0$ or $D(B) - g(\epsilon,B) > 0$. This gives us the bound $|D(A)| \geq \min(|D(B) + g(\epsilon,B)|,|D(B) - g(\epsilon,B)|)$. This lower bound for $|D(A)|$ can be plugged into Rump's inequality to generate a root separation bound. Then Sturm's theorem can be applied until the roots are sufficiently isolated (including the error generated from $\epsilon$).


**Question 2) If $f\_A$ has multiple roots, is there any way of isolating these roots?**


In this case, Sturm's theorem can isolate the roots to an arbitrary degree of precision, but without a root separation bound, there is no way to disambiguate between repeated roots and close roots.


If we try to calculate the number of distinct zeros as $n - \gcd(f\_B,f\_B')$, there will always be a remainder term $r$. By reducing $\epsilon$, we might be able to make $r$ arbitrarily close to 0, but we run into the same problem as with Sturm's theorem in that we don't have an bound on $r$ which differentiates between $r=0$ and $r$ is just small.



Determining Roots of a Polynomial with Interval Estimates of Coefficients
Polynomials with a multiple root form a Zariski closed set (vanishing of the discriminant, which is a certain polynomial in the coefficients); hence, this set is nowhere dense, whereas its complement is dense. In other words, in any neighborhood of any point, "most" polynomials are nonsingular, and it's very unlikely one can detect the singularity unless the coefficients are known exactly.


