# understanding the least squares criterion

I was given 20 data points and asked to choose the most suitable lowest degree polynomial to fit them using the least-squares criterion.

I looked it up, but what i found seems far too complex or just confuses me. Can i have the general steps to solve a question of this nature, or have an example with a much smaller data set?

-
There is information missing. With a polynomial $p(x)$ of degree no larger than 19 you can force equality $p(x_i) = y_i$ for all 20 data points $(x_i, y_i),$ as long as the $x_i$ are all different. With a lower bound on degree there is a least-squares solution. Maybe you had better start by finding the best line for three (non-collinear) points, then the best parabola for four points that do not lie on a line or parabola. Given a family of functions parametrized by a finite number of constants (coefficients here) there is a least-squares fit. – Will Jagy Nov 15 '12 at 23:01
Well in the notes I wrote, there is something about a method for a discrete case involving partial derivatives and a matrix. Since our teacher is kind of fast, my notes are incomplete. Does that sound familiar? – rex Nov 15 '12 at 23:22
Sure. Suppose you are allowed up to degree 9. Your polynomial is then $p(x) = a_0 + a_1 x + \cdots a_9 x^9.$ You want to minimize $$f(a_0, a_1, \ldots, a_9) = \sum_{i=1}^{20} \left( y_i - p(x_i) \right)^2.$$ With that definition, you simultaneously solve ten equations, $$\frac{\partial f}{\partial a_j} = 0.$$ Try the two easier cases I mentioned. – Will Jagy Nov 15 '12 at 23:57
Thanks, i will give it a try. – rex Nov 16 '12 at 0:18

The MathWorld article is fairly easy to understand, I think: http://mathworld.wolfram.com/LeastSquaresFittingPolynomial.html. Its shows the essential parts of the process: at a minimum, some partial derivatives are zero, and this leads to a set of linear equations that you can solve.

But, before you get started, you have to decide what degree to use. The heuristic approach is to just plot the data, stare at it, and try to decide whether its shape seems to be linear (degree 1), or parabolic (degree 2), or something more complex. If the data has $n$ turning points, then you should start with a polynomial of degree $n+1$.

A more rigorous approach is to decide what maximum error you are willing to accept. Then, just keep increasing the degree until this error is achieved. This iteration will always work -- as Will Jagy said, by the time you get to degree = 19, the error will be zero (but zero error is probably not what you want).

-