0
$\begingroup$

Can we reconstruct a polynomial with only Y values? What if the number of Y values are far more than the degree of the polynomial? Also can we obtain the root of this polynomial with this Y's value without interpolating?(i.e. without knowing the coefficients of the polynomial)

$\endgroup$
4
  • $\begingroup$ Do you have a list of ordinates (table of Ys) with no Xs and want to "fit" a polynomial to that. That wouldn't make sense. You'd also need the abscissas (Xs). $\endgroup$ – user_of_math Sep 26 '14 at 17:57
  • $\begingroup$ Fine, Does "That wouldn't make sense" mean one cannot reconstruct that polynomial? What about its root(s)? $\endgroup$ – user153438 Sep 26 '14 at 18:02
  • $\begingroup$ Think of a bunch of y-ticks on a graph paper, corresponding to to your y's $y_1, y_2, ...$. You only get a point on a graph paper when you specify both x's and y's. I could, for example, pick $x=x_1$ and then I'd get a vertical line through $x_1, y_1$, $x_1, y_2$ etc. On the other hand, I could pick each $x_k = y_k$ and I'd get an inclined straight line. So talking about "that" polynomial doesn't make sense. $\endgroup$ – user_of_math Sep 26 '14 at 18:06
  • $\begingroup$ @user_of_math Can I have your idea about the following question please. Consider we evaluate a polynomial P of degree d on some points (say 2d+1 points or more) to obtain Y's. If we have the second distinct polynomial P2 with the same degree as before, and evaluate it on the same points as before to obtain Z's. 1) Given Y's and Z's recover the original polynomials 2) or even find a few roots of these polynomials? $\endgroup$ – user153438 Sep 28 '14 at 12:42
0
$\begingroup$

If we only have a set of values (which, as you defined, we can call Y-values) with no relation to another set values, there is no singular meaningful and unique way to create a function to interpolate them. This does not just apply to polynomials.

So no, if we are given simply a set of Y-values and told that they appear as certain $f(x)$ values in a polynomial, we do not have enough information to narrow the possibilities down to a single polynomial (and not even to a single power). The number of options we have is infinite. All we get to know, when we are given such a list, is that the range of the polynomial must at least have a global minimum or maximum corresponding the the smallest and largest y-values in the set of the presented points, if we are also told that its power is even. The polynomial may also transgress both the upper and lower y-values if its power is odd.

If you are unconvinced, consider the following: ones gives us an arbitrary (even infinite) list of y-values and says that they appear as $f(x)$s on a polynomial. Now we are asked what the polynomial is.

We can always answer $x=y$ and we will be right, not matter what the list (as long as we are just given y-values).

Regarding your final point, if we can't derive any meaningful information about the nature of the polynomial (as it really could be just about anything with the exception of certain even powered polynomials), it is not very meaningful to solve for a root, as the root could be anything.

For further reading, I would recommend you look up "functions" and what is means to form a "function".

Does hesitate to ask for clarification if something doesn't make sense.

Have a nice day :)

$\endgroup$
9
  • $\begingroup$ Many thanks for your answers. Can I complete my question by putting it in the following scenario:Consider we evaluate a polynomial P of degree d on some points (say 2d+1 points or more) to obtain Y's. If we have the second distinct polynomial P2 with the same degree as before, and evaluate it on the same points as before to obtain Z's. 1) Given Y's and Z's recover the original polynomials 2) or even find a few roots of these polynomials? $\endgroup$ – user153438 Sep 26 '14 at 18:15
  • $\begingroup$ I'll be pleased to have your idea about above scenario and what can be inferred from those values. $\endgroup$ – user153438 Sep 26 '14 at 18:45
  • $\begingroup$ Sure thing. So we have for 2 polynomials of the same degree and two sets of y-points with the same x-points, if I have understood correctly :) Now, though there is a constraint, it is not strong enough. Using a method called "lagrange interpolation" we can demonstrate this. This method, when given any number of points (say 2d+1, as you put it) will give a polynomial that goes through all these points and it will have a degree of 2d (1 less than num of points)! So in our case, we can state that the lagrange polynomial for our 2d+1 points must exist (we have no means of finding it explicitly). $\endgroup$ – Just_a_fool Sep 26 '14 at 19:16
  • $\begingroup$ A unique lagrange polynomial will exist for both sets of data and it will interpolate both of them perfectly (look up "lagrange interpolation" to see how this works). However, now consider we choose an x value outside of the ones corresponding to our data set of y's and z's. If we evaluate the f(x) of the lagrange polynomial at this x, we will clearly get some point (x,f(x)). However, we decide that we want a new polynomial that still interpolates all our previous points, but at x has a height of f(x) + k. The virtue of lagrange interpolation will allow up to construct such a polynomial too. $\endgroup$ – Just_a_fool Sep 26 '14 at 19:21
  • $\begingroup$ So for both sets of data (with the y and z height sets, we can create infinitely many lagrange polynomials which interpolate the data sets such that the the sum of any 2 lagrange polynomials (one form the z set and one form the y set), when summed will give at a point x from the data set height k (where k is equal to y+z). Essentially, we have shown that an infinite number of polynomials will exist which will satisfy our constraints and hence we cannot recover unique original polynomials. The constraint simply makes sure that at certain x-points, our polynomials must have heats y an z $\endgroup$ – Just_a_fool Sep 26 '14 at 19:25
0
$\begingroup$

I interpret the question as: given a set $\{y_1,\dots,y_n\}$ of values of an unknown polynomial, can one reconstruct the polynomial? The answer is an emphatic no: every polynomial of odd degree takes all real values, for example (and many polynomials of even degree will also be consistent with whatever finite data you have).

If you know that the values in question are taken in that order (so, there exist $x_1<x_2<\cdots x_n$ such that $f(x_j)=y_j$), then you can at least say that the degree cannot be too small (it has to be greater than the number of interior local extrema of the sequence $(y_1,\dots,y_n)$. But there's not much else you're going to be able to say.

$\endgroup$
2
  • $\begingroup$ can I have your idea about the following question please. Consider we evaluate a polynomial P of degree d on some points (say 2d+1 points or more) to obtain Y's. If we have the second distinct polynomial P2 with the same degree as before, and evaluate it on the same points as before to obtain Z's. 1) Given Y's and Z's recover the original polynomials 2) or even find a few roots of these polynomials? $\endgroup$ – user153438 Sep 27 '14 at 17:44
  • $\begingroup$ If you don't know which $2d+1$ points you're evaluating $P$ and $P_2$ on, then you won't be able to get any information at all. $\endgroup$ – Greg Martin Sep 27 '14 at 20:01

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.