# Finding Roots of a Polynomial Represented in Point-Value Form

Consider we have $n$ pairs of $(x_i,y_i)$. We all know that given the $n$ pairs we can interpolate a polynomial of degree at most $n-1$.

Also, it is clear if we want to find roots of a interpolating polynomial, (given the $n$ pairs); we need to:

1- interpolate the polynomial.

2- find the roots of it.

Question: given the $n$ pairs, is there any way (or shortcut) to find roots of interpolating polynomial, without interpolating the polynomial first?

Note: I am after a faster way of finding the interpolating polynomial's roots than going through the above two steps. However, I DO NOT know whether possible to do it.

• You ask about the determination of the roots of a polynomial which you do not know. I think it is impossible without a hard work, harder than the explicit calculation of the polynomial – Piquito Dec 4 '15 at 13:43

The knowledge of $(x_i,y_i)$ directly gives you only a vague idea where some of the zeros are: if two adjacent $y$-values have opposite signs, there is a zero between them. Otherwise, there is no shortcut to get from the points to zeros.
Indeed, consider an arbitrary polynomial $p$ of $n$th degree. You can pick any $n+1$ points, evaluate $p$ at them, and thus get the point set $(x_i,y_i)$ for which $p$ is the interpolating polynomial. If there was a shortcut to the zeroes of $p$ from here, we'd have a new easy way to find the roots of any polynomial. But finding roots is hard; it's far more difficult then constructing the interpolating polynomial.