6
$\begingroup$

A polynomial $ p(x)$ is such that $p(0) =5, p(1) = 4, p(2) = 9 $ and $p(3) = 20 $.

What is the minimum degree it can have?

The problem can easily be solved by hit and trial method. First assuming that the degree is 1, then 2 and so on until the initial conditions are satisfied. This method gives the answer as 2, for the above problem.

But in spite of checking each and every value, starting from 1; is there any better approach to solve such problems ?

Many thanks !!

$\endgroup$
  • $\begingroup$ I would suggest first to plot the data points. It cannot be $1$ and it could not be greater than $3$ since you only have four data points. $\endgroup$ – Claude Leibovici Feb 13 '14 at 14:23
  • $\begingroup$ @ClaudeLeibovici Ummmm, I believe it can have degree greater than 3. In that case, the equation will have infinite possible solutions. The extra variable added to solve these equations would be free. Please correct me if I am wrong. $\endgroup$ – Gaurav Feb 13 '14 at 14:34
  • $\begingroup$ You are perfectly correct $\endgroup$ – Claude Leibovici Feb 13 '14 at 14:37
  • $\begingroup$ Certainly, you CAN find a polynomial of degree more than $3$; however, the question is asking for the minimum degree. We can, via polynomial interpolation, always find a polynomial of degree at most $n$ that will match any $n+1$ data points; so, no matter what, you can always find a polynomial of degree $3$ in this case, and considering any higher degree goes against the question you were asked. $\endgroup$ – Nick Peterson Feb 13 '14 at 14:38
6
$\begingroup$

For a linear polynomial $p$, you'll always have $p(n+1) - p(n)$ the same. If you write down a table

 1    2    3    4    5
p(1) p(2) p(3) p(4) p(5)

which in your case would be this:

0    1    2    3   
5    4    9    20

and then write the differences $p(2) - p(1)$, $p(3) - p(2)$, etc in a row beneath, you'd get (again in your case)

0    1    2    3   
5    4    9    20
  -1    5   11

That new row is called the "first differences". For a linear function, the entries would all be the same. You can also write down second differences:

0    1    2    3   
5    4    9    20
  -1    5   11
     6    6

For a quadratic function, these second differences will all be the same. Your values actually are all the same, so your function can be expressed as a quadratic.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ how to convince myself that this method works? Any proof would be helpful. :) $\endgroup$ – rohith Oct 25 '19 at 7:22
  • 1
    $\begingroup$ In general, if $p(n) = a_k n^k + \ldots + a_1 n + a_0$, then $p(n+1) - p(n)$ will be a degree $k-1$ polynomial. Example; $p(n) = 2n^2 -3n + 1$; then $p(n+1) - p(n) = 2(n+1)^2 - 3(n+1) + 1 - (2n^2 -3n + 1)$,$ = 2n^2 +4n + 2 -3n -3 + 2 - 2n^2 +3n - 1 = 4n$: the quadratic terms cancel. So if your data is fit by a degree-$k$ polynomial, the "first differences" will be fit with a degree $k-1$ polynomial, and so on. If some row of differences is all zeros, then the next row up is fit by a constant polynomial, the one after by a linear polynomial, and so on. $\endgroup$ – John Hughes Oct 25 '19 at 18:13

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.