2

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?

Community
  • 1
Chris Smith
  • 123
  • 1
  • 5
  • in this case you need to use methods for data fitting (least squares) – Freshman42 Jun 25 '16 at 18:26
  • @Navaro the link you have provided doesn't work for me. – Jean Marie Jun 25 '16 at 20:52
  • @JeanMarie: Sorry, here is the link: https://en.wikipedia.org/wiki/Curve_fitting –  Jun 25 '16 at 20:55
  • 1
    @ChrisSmith: if you're interested only in the result, then There are a lot of software that can help, Personally I use EXCEL sometimes to do the task –  Jun 25 '16 at 20:58
  • For reference, Wolfram Alpha can do all this too: https://www.wolframalpha.com/examples/RegressionAnalysis.html – Chris Smith Jul 02 '16 at 21:47

1 Answers1

3

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.

Klaas van Aarsen
  • 5,908
  • 1
    This is actually linear least squares, in the usual sense of the term. The problem is linear in the coefficients even though it is nonlinear in the original independent variable. – Ian Jun 25 '16 at 21:31
  • @Ian, you're quite right, so I've edited the reference. – Klaas van Aarsen Jun 26 '16 at 00:38