5
$\begingroup$

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.

  • 0
    @J.Loreaux I'd prefer $t$hat the exponents do not exceed the value of 50 and that the coeff$i$cients are integers, but these are not requirements, only preferences.2012-07-10

3 Answers 3

7

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.

  • 0
    This is problem 4.2 in "Linear Algebra Done Right" by Sheldon Axler. I remember thinking what a great problem it was.2012-07-10
5

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.

  • 1
    @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.2012-07-10
0

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.