Deriving an equation that satisfies many points

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.

-
Perhaps you can be more explicit about the conditions you want on such an equation. – J. Loreaux Jul 10 '12 at 22:13
Sure. In many ways. For example you can even get a polynomial, by using the Lagrange Interpolation Formula. But sometimes a simple expression that fits reasonably well is more useful than a complicated expression that fits perfectly. – André Nicolas Jul 10 '12 at 22:16
@J.Loreaux 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. – George Brown Jul 10 '12 at 22:18

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.

-
This is problem 4.2 in "Linear Algebra Done Right" by Sheldon Axler. I remember thinking what a great problem it was. – process91 Jul 10 '12 at 22:19

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.

-
Quite contrary, complexity is preferred, is there a method that produces complex equations? – George Brown Jul 10 '12 at 22:20
@GeorgeBrown: What do you mean be complexity? Given any equation that satisfies your conditions, you can always make it as much more complicated as you want (e.g., if your $x$-coordinates are $x_1, x_2, \dots, x_{32}$, take any continuous function $f(x)$ and add $f(x)(x-x_1)(x-x_2)\cdots(x-x_{32})$ to your original equation). – Micah Jul 10 '12 at 22:25
Interesting, thanks. – George Brown Jul 10 '12 at 22:28
@GeorgeBrown: It's worth noting that the LaGrange polynomial is the construction in my answer. It's also worth noting that the $f(x)$ referred to in Micah's comment need not be even remotely continuous--for example, take the characteristic function of any set of reals that includes the $x$-values of all your points. – Cameron Buie Jul 10 '12 at 22:41

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.

-