Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Perhaps you can be more explicit about the conditions you want on such an equation. –  J. Loreaux Jul 10 '12 at 22:13
1  
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

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
Quite contrary, complexity is preferred, is there a method that produces complex equations? –  George Brown Jul 10 '12 at 22:20
1  
@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
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. –  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.