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

## 2 Answers

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 '15 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 '15 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 '15 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 '15 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)