MHB Minimum degree of a polynomial passing through points

[juantheron]

If p(x) is a polynomial such that p(0)=5 ,p(1)=4 ,p(2)=9,p(3)=20 ,

the minimum degree it can have

 

[Prove It]

Re: polynomial

If p(x) is a polynomial such that p(0)=5 ,p(1)=4 ,p(2)=9,p(3)=20 ,

the minimum degree it can have

You have four points, so for them to fit the polynomial exactly, you need it to at least have degree three. Anything more you'll have an infinite number of possibilities that will have all data points fit, and anything less then chances are you'll only be able to get a least squares approximation.

 

[Ackbach]

Re: polynomial

My approach: start with a straight line and see if it fits exactly. If not, try a quadratic. If that doesn't work, try a cubic. As Prove It has pointed out, a cubic (with four arbitrary constants) will definitely work. But you might be able to get by with fewer depending on where the points are.

 

[soroban]

Re: polynomial

Hello, jacks!

If p(x) is a polynomial such that: .p(0) = 5,\;p(1) = 4,\;p(2) = 9,\;p(3) = 20,
. . the minimum degree it can have is __.

Plotting the four points, a parabola might pass through them.

The general parabola is: .p(x) \:=\:ax^2 + bx + cUse the four point to construct a system of equations:

\begin{array}{ccccccc} p(0) = 5: &amp; a(0^2) + b(0) + c &amp;=&amp; 5 \\<br /> p(1) = 4: &amp; a(1^2) + b(1) + c &amp;=&amp; 4 \\<br /> p(2) = 9: &amp; a(2^2)+ b(2) + c &amp;=&amp; 9 \\<br /> p(3) = 20: &amp; a(3^2) + b(3) + c &amp;=&amp; 20 \end{array}Solve the system: .a = 3,\;b = \text{-}4,\;c = 5

Hence: .p(x) \;=\;3x^2 - 4x + 5The minimum degree of p(x) is two.

 

[HallsofIvy]

Re: polynomial

You have four points, so for them to fit the polynomial exactly, you need it to at least have degree three. Anything more you'll have an infinite number of possibilities that will have all data points fit, and anything less then chances are you'll only be able to get a least squares approximation.

Then polynomial, passing through four given points, will have degree at most three, not "at least". It is quite possible that the four points happen to lie on a parabola (which is apparently the case here) or even on a straight line.

 

[Prove It]

Re: polynomial

Then polynomial, passing through four given points, will have degree at most three, not "at least". It is quite possible that the four points happen to lie on a parabola (which is apparently the case here) or even on a straight line.

Really? I would have thought that there would be an infinite number of solutions to, say, four equations in five unknowns, which is what you would get if you substituted the four points into a general polynomial of degree 4...

 

[CaptainBlack]

Re: polynomial

Really? I would have thought that there would be an infinite number of solutions to, say, four equations in five unknowns, which is what you would get if you substituted the four points into a general polynomial of degree 4...

Four equations in five unknowns is what you will end up with when you try to fit a quartic, and we know you can always do that but the solution is not unique.

Fitting a cubic \(p(x)=a+bx+cx^2+dx^3\) will give you four equations in four unknowns, and as long as there is no degeneracy will have a solution. In this case the equations are:

\[ \left[\begin{array}{cccc} 1&0&0&0 \\ 1&1&1&1 \\ 1 & 2 & 4 & 8 \\ 1&3&9&27 \end{array} \right] \left[ \begin{array}{c} a \\ b \\ c \\ d \end{array} \right]=\left[ \begin{array}{c} 5 \\ 4 \\ 9 \\ 20 \end{array} \right]\]

Which may be solved using your favourite method of solving linear equations to give:

\[ \left[ \begin{array}{c} a \\ b \\ c \\ d \end{array} \right]=\left[ \begin{array}{c} 5 \\ -4 \\ 3 \\ 0 \end{array} \right]\]

Which corresponds to the polynomial:

\[ p(x)=5-4x+3x^2+0x^3=5-4x+3x^2 \]

We may note that this method would produce the required solution whateve the degree of the ploynomial was. And it works because the fitting cubic is unique and all polynomials of lower degree are cubics for the purposes of fitting to the data.

CB