Approximate a function from points I would like to approximate a polynomial equation from a series of points. Searching around this site I found this post which pointed to the Lagrange Interpolating Polynomial.
The challenge however is that the points I have are inexact, differing by +/- 10% of the actual f(x).
Using the previously mentioned approach produces a result that is "perfect" with regard to the input points, except the degree of the polynomial is much higher than I'd like.
Is there a method to approximate a polynomial based on its points? Or alternatively reduce a higher-order polynomial?
 A: We can do a linear least square best fit if you know (or if we assume) the order of the polynomial. If the fit is not "good enough", we can increase the order.
Here's how it works.
Suppose we have the points $(x_1, y_1), ..., (x_n, y_n)$ and we want to interpolate it approximately with $y = a_m x^m + ... + a_0$.
Then we want to solve:
$$\mathbf y \approx \mathbf X \mathbf a$$
where:
$$\mathbf y = \begin{bmatrix}y_1 \\ \vdots \\ y_n\end{bmatrix}, \quad
\mathbf X = \begin{bmatrix}1 & \cdots & x_1^m \\ \vdots && \vdots \\ 1 & \cdots &x_n^m\end{bmatrix}, \quad
\mathbf a = \begin{bmatrix}a_0 \\ \vdots \\ a_m\end{bmatrix}$$
The best fit assuming equal variances in the errors of each $y_i$ (see wiki) is:
$$\mathbf a = (\mathbf X^T \mathbf X)^{-1}\mathbf X^T \mathbf y$$
Now we can determine the actual fit by evaluating the error $\mathbf e$:
$$\mathbf e = \mathbf y - \mathbf X\mathbf a$$
and see for instance if all entries are within $\pm 10\%$, or perhaps if the mean variance is within $10\%$ or some such. If not we can redo with a higher degree polynomial.
