# Writing a function $f$ when $x$ and $f(x)$ are known

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.

-
First you'd need to explain how you're using the term "function". Under the standard usage of that term, your first table already defines a function and there would be nothing left to do. Perhaps you're looking for an expression in terms of basic arithmetic operations and/or well-known elementary functions? If so, you should specify which ingredients you would like to allow in this expression. –  joriki Feb 12 '12 at 18:35
2 - 2*sign(x) + floor(x/6) comes to my mind. –  mzuba Feb 12 '12 at 18:38
What you're looking for, in general, is called curve fitting – see en.wikipedia.org/wiki/Curve_fitting. Essentially, the question is this: given a set of points, what is the "best" curve to draw through those points? Naturally, the answer depends on what you mean by "best". –  Tanner Swett Feb 12 '12 at 19:01
@joriki: Thanks for clarifying the terminology. I'll avoid editing my post since people have already commented and answered, but you are exactly right: I'm looking for an expression in terms of basic arithmetic operations and/or well-known elementary functions. –  PunctuallyChallenged Feb 12 '12 at 19:09
@mzuba: Perfect, thanks! I'm looking forward to answers that describe the process of coming up with something like that. –  PunctuallyChallenged Feb 12 '12 at 19:12

Obviously function that we are looking for is not linear, then if we do not want to split it to cases and we want to use only basic operations, at least one possibility is to find coefficients of the following polynomial $$f(x)=a_1x^6+a_2x^5+\dots+a_6x+a_7$$ By solving system of your 7 given equations: $$\dots\dots\dots \\f(1)=a_1+a_2+\dots+a_6+a_7=0\\ \dots\dots\dots$$ Then if I am correct, the result is: $$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$$

-
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. –  PunctuallyChallenged Feb 12 '12 at 19:33

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.

-
This is often called Lagrange interpolation. –  JavaMan Feb 12 '12 at 22:14
@JavaMan: Indeed, I can't believe I forgot to mention the name of the method! I'll edit my post. –  Clive Newstead Feb 12 '12 at 22:50
Thank you for the detailed explanation. Just enough information for me to follow it. –  PunctuallyChallenged Feb 12 '12 at 23:15
An alternative to Lagrange interpolation is Newton’s polynomial interpolation algorithm. –  mzuba Mar 27 '12 at 11:56

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.

-
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 of the set $A$. –  kahen Feb 12 '12 at 19:18

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.

-

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.

-

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.

-