1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Piquito Dec 4 '15 at 13:43
2
$\begingroup$

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.

$\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.