Polynomial interpolation given only Y values

[Aydin]

Hi
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 can we recover the original polynomials 2) or even find a few roots of these polynomials? *** We only have the (Y and Z) values of two polynomials not the X values at which these polynomials evaluated***

 

[Ishuda]

Hi
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?

The coefficients of a polynomial P of degree d can be determined by a set S of values of P such that
S = {P(x_j), j = 0, 1, 2, 3, ..., d; if j \(\displaystyle \ne\) k then x_j \(\displaystyle \ne\) x_k}
see
http://en.wikipedia.org/wiki/Lagrange_polynomial

So you could change the 2d + 1 to d + 1 as long as they were distinct points. The answer to (1) is yes and the answer to (2) is probably in a 'reasonable amount of time'.

 

[Aydin]

The coefficients of a polynomial P of degree d can be determined by a set S of values of P such that
S = {P(x_j), j = 0, 1, 2, 3, ..., d; if j \(\displaystyle \ne\) k then x_j \(\displaystyle \ne\) x_k}
see
http://en.wikipedia.org/wiki/Lagrange_polynomial

So you could change the 2d + 1 to d + 1 as long as they were distinct points. The answer to (1) is yes and the answer to (2) is probably in a 'reasonable amount of time'.

Please note that the X values are not available.

 

[Ishuda]

Please note that the X values are not available.

Use x_j = j or, if that is not allowed, then the answer to (1) is no. As proof, note that I could choose any set of (d+1) x values I liked as long as they were distinct and get a polynomial which would have those set of (d+1) values and thus, by implication, could have at least any one zero I wanted. In fact, given the d + 1 values of P, I can construct a polynomial of any given degree n, n \(\displaystyle \ge\) d, which has the given P values whether the x values are given or not.

 

[Aydin]

Use xj = j

The main question here is whether it is possible to recover either of these two polynomials without the knowledge of X values? why?

 

[Ishuda]

The main question here is whether it is possible to recover either of these two polynomials without the knowledge of X values? why?

See post edit above. Basically, the answer is I can construct an infinity of polynomials having those (d+1) values, just let x_j = a j, where a not zero and use the Lagrange polynomial.