# Determining Roots of a Polynomial with Interval Estimates of Coefficients

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.

• Having a multiple root is an unstable condition, so it seems that it cannot be determined by an estimate only. – Alex Degtyarev Nov 9 '14 at 15:59
• I haven't heard the term "unstable condition" before. Could you please define that? I know about condition numbers (wikipedia link), and the associated terms "ill-conditioned" and "well-conditioned". – Ashwin Deshpande Nov 9 '14 at 17:30
• Your statement seems reasonable, but I'm still having a hard time convincing myself that there is no way to derive a root separation bound in the multiple root case. We can certainly determine if multiple roots exist with real coefficients, so why does the problem become impossible when dealing with arbitrarily small error? – Ashwin Deshpande Nov 9 '14 at 17:42
• I'm now convinced your statement is true. $f(x) = x^2 + ax + 1$ has a repeated rooted exactly when $a=2$. If our estimate of $a$ was bounded in the range $[2-\sigma,2+\sigma]$, there is no way to differentiate between when $a=2$ and $a=2+\rho$ other than a semidecidable approach, since externally, all parameters appear identical. – Ashwin Deshpande Nov 9 '14 at 18:01
• I just meant that a multiple root splits into a pair (or more) simple ones under a small perturbations. In other words, the set of polynomials with multiple roots is Zariski closed and nowhere dense, while its complement is open and dense. Your last comment illustrates this. – Alex Degtyarev Nov 9 '14 at 18:12

You might find the idea of Companion matrix to be useful. The eigenvalues $\lambda$ of the companion matrix $C$ are equal to the roots of a polynomial and its eigenvectors $v$ are functions of the eigen-values and $v$ are linearly independent iff the eigenvalues(ie, roots) are distinct.
Now the question becomes that if only have noisy estimates of the companion matrix then is the original matrix diagonalizable. Interestingly there is a construction in linear algebra that shows that diagonalizable matrices are dense which means that we can always find polynomials with distinct roots no matter how small $\epsilon$ is. This is a linear algebraic way of stating what @Alex said above.
I wish I could knew more about how the eigenvalues of $A$ change with perturbations (by using Weyl's inequalities perhaps) but I now realize that $A$ is non-hermitian and all the standard textbook theory only talks about hermitian matrices.
You may want to look into the notion of "pseudospectrum" or "pseudo-zero set". The $\epsilon$-pseudospectrum of a matrix $A$ is the set of points in the complex plane which are eigenvalues of matrices that are $\epsilon$-close to $A$ (under some choice of norm). The pseudozero set is an analogous quantity defined for polynomial zeros. Just by googling around I think one place to start would be the papers of Stef Graillat.