# Polynomial least squares fit --- restrictions on order?

If we're finding an interpolating polynomial for 10 data pairs, the order of the polynomial has to be 9.

In class, my professor said that when doing a polynomial least squares fit, if you have 10 data pairs, then the polynomial with the maximum order will have an order of 9.

However, I've seen in some numerical methods book that they use that the maximum is 8 (which I think is wrong).

Wolfram's page includes no restriction whatsoever.

And as a homework I have been given the task to create a program for polynomial least squares fitting, where the user specifies the maximum order polynomial that is to be calculated.

I don't know if I should include a certain restriction here.

It seems arbitrary to include a restriction. What do you guys think? What is more mathematically sound/accepted/correct ?

Here's my guess.

Well suppose you have N data points. If you fit a polynomial of order M, then you essentially have N equations with M unknowns. If $M>N$ then you have more unknowns than equations. This is definitely not advisable (the regression requirements are not satisfied). If $M=N$, you have M equations and N unknowns and would get a perfect fit. (This might cause the least squares regression to give an error in some cases). That leaves $M<N$

Edit: I forgot about the constant. A polynomial of order $M$ would imply $M+1$ unknowns and this $M\leq (N-2)$. That might be where the $8$ comes from. Therefore, my explanation of the difference comes from the fact that one might to avoid the case where the polynomial "perfectly" matches the data.

• Hi Greg. I don't agree with what you've said. In least squares approximation what matters are the summations of the data pairs. Unknowns and equations will always be the same because if you have a $M$th order polynomial you'll have $M+1$ equations (if you're taking partial derivatives with respect to each coefficient), which is perfectly fine and is what makes your system solvable.
– DLV
Jun 28, 2015 at 0:50
• The standard solution in a linear regression is $(X'X)^{-1}X'y$ where X is an $N x K$ matrix with N observations and K parameters. In order to be valid the matrix $X'X$ must be invertible. This requires , by definition, that $N \geq K$.
– Greg
Jun 28, 2015 at 3:39
• I think we're speaking of distinct things, or I'm not seeing your point. Linear approximation with the least squares technique strictly uses a 2x2 matrix. See mathworld.wolfram.com/LeastSquaresFitting.html . This matrix is always invertible as it is a Vandermonde matrix.
– DLV
Jun 28, 2015 at 3:46
• The example in the link you provided is solving a simple regression with a constant term and a variable x. ($y=a+bx$) This is a regression with 2 independent variables. That's why the matrix is 2x2. (Using the formula in my previous comment, X'X is a 2 x 2 matrix). But, you want to know (or at least I think you want to know) largest order you can include in a regression of y on x, $x^2$, $x^3$, and so forth. This will require solving higher order matrices. Edit: Here's a better link. mathworld.wolfram.com/LeastSquaresFittingPolynomial.html
– Greg
Jun 28, 2015 at 4:13

Here is a post which shows that, thanks to the magic of least squares, let's you fit to any order: Polynomial best fit line for very large values

Folk lore on fitting order: Least Square fit for signal data (360 points)