6
$\begingroup$

I'm trying to write a function. For each possible input, I know what I want for output. The domain of possible inputs is small:

$\begin{vmatrix} x &f(x)\\ 0 & 2\\ 1 & 0\\ 2 & 0\\ 3 &0\\ 4 &0\\ 5 &0\\ 6 &1\\ \end{vmatrix}$ My thought is to start with a function $g(x)$ that transforms $x$ to a value from which I can subtract a function $h(g(x))$ and receive my desired $f(x)$: $\begin{vmatrix} x &g(x)& h(g(x)) &f(x)\\ 0 & 7& 5 & 2\\ 6 & 6 & 5 & 1\\ 5 & 5 & 5& 0\\ 4 & 4 & 4 & 0\\ 3 & 3 & 3 & 0\\ 2 & 2 & 2 & 0\\ 1 & 1 & 1& 0 \end{vmatrix}$ But I'm not sure where to go from there, or even whether I'm heading in the right direction. How should I approach creating this function? Is there a methodical way to go about it, or is it trial and error (and knowledge)? Feel free to suggest modifications to how I'm stating my problem, too. Thanks.

  • 0
    @mzuba: Perfect, thanks! I'm looking forward to answers that describe the process of coming up with something like that.2012-02-12

6 Answers 6

1

If you have a set of discrete data points like this, and you want to inter a continuous function which satisfies all of these data points, you can basically plot the points and then draw straight lines between the closest points to obtain your continuous function. In other words, you can use linear interpolation. If you know two points ($x_1$, f($x_1$)), ($x_2$, f($x_2$)), then you can find the equation for a straight line between them "y=mx+b" by first finding the slope m of such a line:

m=(f($x_2$)-f($x_1$))/($x_2$-$x_1$). Then you can figure out b by substituting $x_1$ for x, and f($x_1$) for y. Applying that for all appropriate pairs of points here gives us:

 f(x)=-2x+2  if x belongs to (0, 1]       0      if x belongs to (1, 5)       x-5    if x belongs to [5, 6] 

Such a function is, of course, not differentiable everywhere.

Other interpolation methods do exist, and as Marc van Leeuwen, as well as others, hint at, many other interpolations methods could get developed if desired.

11

You can generalise the problem: suppose you know the value of $f(x)$ for a particular finite set of values of $x$. (Here, you know the value of $f(x)$ when $x=0,1,2,3,4,5,6$.) Then you can find a possible polynomial function $f$ which takes the given values using the following method.

Suppose you know the value of $f(x)$ when $x=x_1, x_2, \dots, x_n$, and that $f(x_j) = a_j$ for $1 \le j \le n$.

Let

$P_i(x) = \lambda (x-x_1)(x-x_2) \cdots (x-x_{i-1})(x-x_{i+1}) \cdots (x-x_n)$

Where $\lambda$ is some constant. That is, it's $\lambda$ times the product of all the $(x-x_k)$ terms with $x-x_i$ left out. Then $P_i(x_k) = 0$ whenever $k \ne i$.

We'd like $P_i(x_i) = 1$: then if we let

$f(x) = a_1 P_1(x) + a_2 P_2(x) + \cdots + a_n P_n(x)$

then setting $x=x_j$ sends all the $P_i(x)$ terms to zero except $P_j(x)$, leaving you with $f(x_j) = a_jP_j(x_j) = a_j$, which is exactly what we wanted.

Well we can set $\lambda$ to be equal to $1$ divided by what we get by setting $x=x_j$ in the product: this is never zero, so we can definitely divide by it. So we get

$P_i(x) = \dfrac{(x-x_1)(x-x_2) \dots (x-x_{i-1})(x-x_{i+1}) \dots (x-x_n)}{(x_i-x_1)(x_i-x_2) \dots (x_i-x_{i-1})(x_i-x_{i+1}) \dots (x_i-x_n)}$

Then $P_i(x_k) = 0$ if $k \ne i$ and $1$ if $k=i$, which is just dandy.

More concisely, if $f$ is to satisfy $f(x_j)=a_j$ for $1 \le j \le n$ then

$f(x) = \sum_{j=1}^n \left[ a_j \prod_{i=1}_{i \ne j}^n \frac{x-x_i}{x_j-x_i} \right]$

This method is called Lagrange interpolation.


So in this case, your $x_1, x_2, \dots, x_7$ are the numbers $0, 1, \dots, 6$ and your $a_1, a_2, \dots, a_7$ are, respectively, $2,0,0,0,0,0,1$. Substituting these into the above formula, we get:

$\begin{align} f(x) &= 2 \times \dfrac{(x-1)(x-2) \dots (x-6)}{(0-1) (0-2) \dots (0-6)} + 0 \times (\text{stuff}) + 1 \times \dfrac{x(x-1) \dots (x-5)}{6(6-1)(6-2) \dots (6-5)}\\ &= 2 \dfrac{(x-1) (x-2) \dots (x-6)}{720} + \dfrac{x(x-1) \dots (x-5)}{720} \\ &= \dfrac{(x-1)(x-2)(x-3)(x-4)(x-5)}{720} \left[ 2(x-6) + x \right] \\ &= \boxed{\dfrac{(x-1)(x-2)(x-3)(x-4)^2(x-5)}{240}} \end{align}$

You can check easily that this polynomial satisfies the values in your table.


In fact, in this particular case, all the above machinery wasn't necessary. It's plain that $f(x)=0$ when $x=1,2,3,4,5$, and so $x-j$ must divide $f(x)$ for $j=1,2,3,4,5$, and so $f(x) = (x-1)(x-2)(x-3)(x-4)(x-5)g(x)$ for some polynomial $g(x)$. Since we're only worried about $x=0,6$ beyond this, i.e. $2$ values of $x$, it suggests we have $2$ free parameters in $g(x)$ and hence $g(x)=ax+b$ is linear. That is, we have $f(x) = (x-1)(x-2)(x-3)(x-4)(x-5)(ax+b)$

Substituting $x=0$ and $x=6$, respectively, gives $\begin{align}2 &= -5! \cdot b \\ 1 &= 5! \cdot (6a+b) \end{align}$ and solving simultaneously gives $b=-\dfrac{2}{120}$ and $a = \dfrac{3}{720}$, which (after simplification) yields the desired result.

  • 0
    An alternative to Lagrange interpolation is [Newton’s polynomial interpolation algorithm](http://www.math-linux.com/spip.php?article72).2012-03-27
5

Use $f(x)=(x-1)(x-2)(x-3)(x-4)(x-5)(\frac{x}{240}-\frac{1}{60})$. The first five factors make the function $0$ at $1,2,3,4,5$. The last factor takes care of the rest.

  • 1
    As long as we're giving silly answers, here's another one: $f = \chi_{\lbrace0\rbrace} + \chi_{\lbrace0,6\rbrace} = 2\chi_{\lbrace0\rbrace} + \chi_{\lbrace6\rbrace}$, where $\chi_A$ denotes the [indicator function](http://en.wikipedia.org/wiki/Indicator_function) of the set $A$.2012-02-12
5

Clearly a function that we are looking for is nonlinear. If we do not want to split it into separate cases and want to use only basic operations, at least one possibility is to find suitable coefficients for the following polynomial: $f(x)=a_1x^6+a_2x^5+\dots+a_6x+a_7,$ By solving the system of your 7 given equations: $\dots \\f(1)=a_1+a_2+\dots+a_6+a_7=0\\ \dots$ we obtain that $f(x)=\frac{x^6}{240}-\frac{19x^5}{240}+\frac{29x^4}{48}-\frac{113x^3}{48}+\frac{587x^2}{120}-\frac{76x}{15}+2.$

  • 0
    Between this and Tanner's reference to Curve Fitting, I have a good sense of how to approach this now. While I much prefer mzuba's simple expression, I suspect that it is more of an ad-hoc solution than this general approach.2012-02-12
3

There is absolutely nothing wrong with using the table of values as the definition of the function $f:\{0,1,2,3,4,5,6\}\to\{0,1,2\}$ (or of a function $\{0,1,2,3,4,5,6\}\to\mathbb Z$, or anything similar, if you want that; the usual notion of function in mathematics requires you say it maps $X\to Y$ where you must specify both $X$ and $Y$, but there is no necessity that all values of $Y$ are actually attained by $f$). There is no need for a function to be given by an expression; that is merely a convenient method that is often used to avoid specifying the values of $f$ individually. As you can see form the other answers given, one can invent many different expressions that, when restricted to arguments in $\{0,1,2,3,4,5,6\}$, give the same value as those your table, but they are just different ways to describe the same function that you defined. And they are no more insightful than the table in your question.

1

I might as well: there is in fact a nice way to rewrite the Lagrange interpolating polynomial, called barycentric Lagrange interpolation, that allows you to quickly write down an expression for the interpolating polynomial, after which you only need to do a few more simplifications to get the actual polynomial you want. For the case of equally-spaced points like in the OP ($x_j=x_0+jh,\;j=0,1,\dots,n$) with corresponding $f(x_j)$, the barycentric form of the Lagrange interpolating polynomial looks remarkably simple:

$\frac{\sum\limits_{j=0}^n \frac{(-1)^j}{x-x_j}\binom{n}{j}f(x_j)}{\sum\limits_{j=0}^n \frac{(-1)^j}{x-x_j}\binom{n}{j}}$

In fact, for numerical evaluation purposes, one could use this form directly, with some care needed when $x$ is equal to an interpolation point. (If $x$ is nearly, but not equal to, an interpolation point, the method still performs with good accuracy; see the linked article for a deeper discussion.)

For OP's case, we obtain, thankfully due to most of the ordinates being zero, the expression

$\frac{\frac2{x}+\frac1{x-6}}{\frac1{x}-\frac6{x-1}+\frac{15}{x-2}-\frac{20}{x-3}+\frac{15}{x-4}-\frac6{x-5}+\frac1{x-6}}$

or, after a bit more algebraic massaging,

$\frac{x(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)}{720}\left(\frac1{x-6}+\frac2{x}\right)=\frac{(x-1)(x-2)(x-3)(x-4)^2(x-5)}{240}$


For the case of non-equispaced points, a bit more work needs to be done; see the Berrut/Trefethen paper I linked to above for more details.