7
$\begingroup$

Is there any way I can find a polynomial given any 2 points (with x coordinate OF MY CHOICE): Let's say there's some polynomial I don't know(p(x)=2x3+x2+3), but my machine will give me an output. I give one x value of my choice, and it returns p(x), where p(x) is the polynomial function. I give another value of my choice., x+h, and get the output p(x+h). Given these outputs, I have to find p(x) as a polynomial.

What I've done is plugged in 0, which gives me the final term of the polynomial that is not multiplied by any power of x. Then I plug in 1, getting another output. When I find the "slope" of the two points, I get the sum of all the coefficients of all the terms that are powers of x. If I do this for the given p(x), I get 3, which is the sum of 2 and 1. However, I can't figure out what powers of x there are and what specific coefficients there are. Does anyone know how to solve this?

@GerryMyerson and @Shash said I can find the polynomial given the bound of the coefficients. I am confused as to what that means. There is only one number that is the sum of the coefficients. How is there a bound? Also, how do I find this sum of coefficients with just one value? I need to use one more value, M+1, as Shash said, so I can't use 2 values to find the max/sum, as I won't be able to ask for a value that is M+1. Can anyone help? Thanks.

EDIT: Non-negative integer coefficients are assumed.

$\endgroup$
  • $\begingroup$ Hmmm. So there's no way I can strategically choose my numbers to get an output I can use? $\endgroup$ – bob the pie Nov 28 '14 at 16:22
  • $\begingroup$ @Winther: If you know that all the coefficients are non-negative integers, then two points are enough. Perhaps this was the original question, and the OP mangled it a bit. $\endgroup$ – TonyK Nov 28 '14 at 17:26
  • $\begingroup$ @Winther: No it doesn't! See Shash's answer and Gerry Myerson's comment. $M = f(1)$ is a upper bound of each coefficient, so $f(M+1)$ lets you read off the coefficients in base $M+1$. $\endgroup$ – TonyK Nov 28 '14 at 17:32
  • $\begingroup$ If all the coefficients $a_n,...,a_0$ are non-negative, then each of them must be $\le a_n+\cdots+a_0 = f(1)$. (Yes, @ notifies them.) $\endgroup$ – TonyK Nov 28 '14 at 17:59
  • $\begingroup$ This has been asked before (I know that I have answered this before), but it's been a while $\endgroup$ – Hagen von Eitzen Nov 28 '14 at 19:59
13
$\begingroup$

If all the coefficients are non-negative integers and if we know the max of all the coefficients, then it is easy to find the coefficients with just ${one\ point}$ of choice. Let's say the max is $M$. Then evaluate the polynomial at $M+1$. The output will be equal to the decimal number system representation of a number whose base $M+1$ number has digits as the coefficients of the polynomial. So, given the output, just get the base $M+1$ representation.

So, even if have just an upper bound (can be very lose upper bound), just set that as $M$ and proceed as above.

As Gerry Myerson points out in the comments, if you do not have an upper bound, you can use $M = p(1)$. Then only two evaluations will be required to determine the coefficients.

$\endgroup$
  • 4
    $\begingroup$ Note that we don't need to know the degree here :) $\endgroup$ – Shash Nov 28 '14 at 8:16
  • 4
    $\begingroup$ And if you don't have a bound for the coefficients, you can get one by evaluating at $x=1$. So (if the coefficients are nonnegative integers) you can get the whole polynomial by 2 evaluations. $\endgroup$ – Gerry Myerson Nov 28 '14 at 8:44
  • $\begingroup$ @GerryMyerson Myerson: how do I only use x=1 to find the bound? I thought I need to use both $x=0$ and $x=1$. $\endgroup$ – bob the pie Nov 28 '14 at 16:27
  • $\begingroup$ Wait, so I can start with $x=0$, then ask $x=1$? This gives me a bound, and I then use that bound? Or do you mean something else $\endgroup$ – bob the pie Nov 28 '14 at 16:47
  • 1
    $\begingroup$ @VardaanBhat: what is meant here is that if your polynomial is $p(x)=2x^3+x^2+3$, you can read the coefficients in $p(10)=2103$; if the coefficients can have at most, say three digits, then evaluate $p(1000)$. Like $p(x)=234x^2+15x$, and $p(1000)=234 015 000$. And so on. $\endgroup$ – Yves Daoust Nov 28 '14 at 17:26
7
$\begingroup$

With two points you can only uniquely determine $p(x)$ if it has degree one. In general if $p(x)$ has degree $n$, you will need the computer give $(n+1)$ outputs, each for a different input.

For example if $p(x)$ has degree 2 and you input $0$ and $1$ and get outputs $a$ and $b$ respectively, there are an infinite number of parabolas which pass through these points. Here are some:

$p(x) = (b-a)x^2+a$

$p(x) = bx^2-ax+a$

$p(x) = 2bx^2-(b+a)x+a$

$p(x) = -3ax^2+(b+2a)x+a$

$\endgroup$
  • $\begingroup$ This is not true in this special case because of the non-negative integers clause. First evaluate the polynomial at $p(1)$ to find an upper bound for all the coefficients, $M$. Then evaluate at $p(M+1)$ and refer to Shash's answer. $\endgroup$ – 6005 Nov 29 '14 at 6:10
  • $\begingroup$ I think this answer needs more explanation. It is of course well-known that in the case of real numbers two points will not suffice. This is also true in the integers, I think, as well as in the nonnegative real numbers, but not in the nonnegative integers. By just referring to $p(x)$ without talking about where its coefficients lie at all, you are avoiding the crux of the problem. $\endgroup$ – 6005 Nov 29 '14 at 6:12
  • $\begingroup$ (Although, I notice now that the non-negative integers edit was added after you posted this answer.) $\endgroup$ – 6005 Nov 29 '14 at 6:18
  • $\begingroup$ Yes, the question was modified after I answered $\endgroup$ – David Peterson Nov 29 '14 at 6:30
3
$\begingroup$

No. You would a minimum of $n$ points, where $n$ is the dimension of the polynomial. For instance, let's try to find a cubic polynomial $p$ where $p(0)=0$ and $p(1)=1$. Notice that $p_1(x)=x^3-x^2+1$ and $p_2(x)=x^3-x+1$ both satisfy the given criteria.

$\endgroup$
3
$\begingroup$

A polynomial of degree $n$ has $n+1$ coefficients. If you know the degree but don't know anything about those coefficients, you'll need $n+1$ values of the polynomial to determine them. If you don't know the degree, no amount of values of the polynomial will suffice.

$\endgroup$
  • $\begingroup$ True from a pure math sense. However, if you get enough (way more than 2 points), you could use curve-fitting techniques to guess the original polynomial. Also, if the polynomial is quadratic, and you have 5 points (thus assume a quartic), the leading coefficients will be zeros. ($0x^4+0x^3+cx^2+dx+e=y$). $\endgroup$ – FundThmCalculus Nov 29 '14 at 3:51

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.