Deriving an equation that satisfies many points

Question

Say I have a collection of points, for example the following:

(1, 167), (2, 11), (3, 255), etc

Is it possible to construct an equation that satisfies all of them? I have a maximum of 32 points.

Answer 1

Given any $n$ points in the plane, none of which lie on the same vertical line as another, and with at least one lying off the $x$-axis (if they all lie on the $x$-axis, then the $0$ function works), there exists a unique polynomial of degree $n-1$ that passes through all of those points. Also, there are infinitely-many polynomials of any given higher degree passing through those points.

In particular, say the points are $(x_1,y_1),...,(x_n,y_n)$ (where $x_i\neq x_j$ for $i\neq j$). For $1\leq i\leq n$, define the polynomial $$P_i(x):=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}.$$ These (and any of their non-0 scalar multiples) are clearly real polynomials of degree $n-1$, and it can be determined rather readily that for any $i,j\in\{1,...,n\}$, we have $$P_i(x_j)=\begin{cases}0 & i\neq j\\1 & i=j.\end{cases}$$ Consequently, we see that $$P(x):=\sum_{j=1}^ny_jP_j(x_j)$$ is a polynomial of degree at most $n-1$ such that $P(x_j)=y_j$ for all $1\leq j\leq n$.

As it turns out, the above construction generalizes rather nicely to points in $\Bbb C^2$ (rather than $\Bbb R^2$), though we won't (necessarily) get a real polynomial in this way.

Answer 2

Yes; in fact there are many ways to construct such an equation, depending on the properties you want it to have.

For example, there will be a Lagrange polynomial (of degree at most 31) that passes through all your points; this is likely to be the simplest-looking equation (from an algebraic standpoint) that you can get, but its geometric properties are not so great (it can wiggle up and down a lot, and small changes in your points will potentially lead to large changes in your equation).

If you want something that's geometrically a little better-behaved, you might want to try cubic spline interpolation instead.

Answer 3

I'd prefer that the exponents do not exceed the value of 50 and that the coefficients are integers, but these are not requirements, only preferences.

Here is a (tedious?) way to construct such polynomial. Let $$ \{ (x_1, y_1), (x_2, y_2), \ldots, (x_{32}, y_{32}) \} $$ denote your data points. Construct the following linear system $Af = y:$ $$ \pmatrix{ 1 & x_1 & x_1^2 & x_1^3 & \cdots & x_1^{50} \\ 1 & x_2 & x_2^2 & x_2^3 & \cdots & x_2^{50} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{32} & x_{32}^2 & x_{32}^3 & \cdots & x_{32}^{50} } \pmatrix{f_0 \\ f_1 \\ \vdots \\ f_{50}} = \pmatrix{y_1 \\ y_2 \\ \vdots \\ y_{32}} $$ Both the matrix $A$ and the vector $y$ are built using the input data points. $f$ is the unknown vector. Our goal is to solve for $f,$ and infer the polynomial $f(x) = f_0 + f_1 x + \ldots + f_{50} x^{50}.$ Please note that some $f_i$'s can be zero, including $f_{50}.$ Obviously, you can change that $50$ into something else, or even force some $f_i$'s to be $0$ or $1.$

The system above is an under-determined system. However, it could be solved once we impose more conditions on $f.$

If we want $f$ such that the errors $\{y_i - f(x_i)\}$ are the smallest, in an $\ell_2$ norm fashion, then you can use least-squares. That is, $f = (A^{T}A)^{-1}A^{T}y,$ or using better computational methods cf the Wikipedia page.

Of course, integer (or rational) linear algebra could be used instead of numerical linear algebra, in order to make sure that $f$ is, in fact, an integer vector.