1
$\begingroup$

Let say we have a arbitrary number of given points and there is at least one function, for which every point lies on its graph. Is it possible to find that function using only X and Y coordinates of every given point?

Example:

We are given points $A(0,1)$; $B(0.27;0)$ and $C (3.73;0)$. All of these points lie on the graph of the function $f(x) = x^2 - 4x + 1$. Is it possible to find this function using only X and Y coordinates of the point A,B and C.

Note: The number of point is can be really big and also the exponent of the function.

$\endgroup$
  • $\begingroup$ I assume by "function" you mean "formula"? A function that matches all points you specify and is zero everywhere else satisfies the question and counts as a function. $\endgroup$ – Robert Mastragostino May 29 '13 at 10:38
  • $\begingroup$ Chech my edit. Maybe it'll be clearer to you. $\endgroup$ – Stefan4024 May 29 '13 at 10:48
  • $\begingroup$ @RobertMastragostino, it doesn't always. The "given points" must have different $x$ coordinates to be part of a function. If they have, use Lagrange interpolation and you are set with a continuous function going through all. $\endgroup$ – vonbrand May 29 '13 at 11:48
4
$\begingroup$

There are many such functions so in general it's not possible to recover the one you started with.

For example if you had a set of points $\{(n,n): n\in\mathbb N\}$ both the functions $f(x) = x$ and $g(x) = x+sin(\pi x)$ would pass through all the points.

If you have a finite number of points you can find a polynomial that passes through them all.

One way to find it would be the following algorithm.

Let the coordinates of the points be $(x_1,y_1), (x_2,y_2),\dots, (x_N,y_N)$

First we find a function $f_1$ that passes through $(x_1,y_1)$ that's easy. $F_1(x) = y_1$.

Now suppose we've constructed $F_n$ that passes through $(x_1,y_1), \dots,(x_n, y_n)$ (so far we've only done this for $n=1$).

Let $$g_n(x) = \prod_{i=1}^n (x-x_i)$$ then $g_n(x_i) = 0$ for every $i\leq n$. Therefore for every value of $\lambda$ the function $F_n(x_i) + \lambda g_n(x_i) = y_i$ for every $i\leq n$. So set $$\lambda_n = \frac{y_{n+1} - F_n(x_{n+1})}{g_n(x_{n+1})}$$ and $$F_{n+1}(x) = F_n(x) + \lambda_n g_n(x).$$

Then $F_{n+1}$ passes through $(x_i,y_i)$ for every $i\leq n+1$. So apply this step repeatedly until you get $F_N$, which passes through every point.

Let's try it with your equation I'm going to choose slightly different points so that we can use whole numbers. Set $$\begin{array}{rlrl} x_1 &=0 & y_1 &=1 \\ x_2 &=2 & y_2 &=-3 \\ x_3 &=5 & y_3 &=6 \end{array}$$

It's easy to check that $x^2-4x+1$ passes through all three points. So let's follow the recipe.

First we set $F_1(x) = y_1 = 1$ and $g_1(x) = (x-x_0) = x$.

Then we can calculate $$\begin{array}{rl}\lambda_1 &= \frac{y_2 - F_1(x_2)}{g_1(x_2)} \\&= -2\end{array}$$ Hence $$\begin{array}{rl}F_2(x) &= F_1(x) + \lambda_1 g_1(x) \\ &= 1 -2x \end{array}$$

We can check that $F_2(0)=1$ and $F_2(2)=-3$.

Next we have $g_2(x) = x(x-2) = x^2-2x$ and we can work out $$\begin{array}{rl}\lambda_2 &= \frac{y_3 - F_2(x_3)}{g_2(x_3)} \\ &= \frac{6 - (-3)}{40} \\&= 1\end{array}$$

So $\lambda_2 = -\frac 3{15}$ and we have

Then we have $$\begin{array}{rl}F_3(x) &= F_2(x) + \lambda_2 g_2(x) \\ &= (1-2x) + (x^2 - 2x) \\ &= x^2-4x+1 \end{array}$$

Then as we've run out of points we set $f(x) = F_3(x)$ and we are done.

$\endgroup$
  • $\begingroup$ I need to find at least one function that satisfy the condition. Also by infinite number of point, i mean you may be given 10 000, 20 or 10 points. $\endgroup$ – Stefan4024 May 29 '13 at 10:47
  • 1
    $\begingroup$ @Stefan4024: So by "infinite", you mean "finite"? $\endgroup$ – Chris Eagle May 29 '13 at 10:50
  • $\begingroup$ Somehow. I'm don't speak good English, so i didn't know how to say that the number of points can be so big number. $\endgroup$ – Stefan4024 May 29 '13 at 10:53
  • 2
    $\begingroup$ I think the correct term would be an arbitrary number of points. $\endgroup$ – Tim May 29 '13 at 10:53
  • 1
    $\begingroup$ @Stefan4024 I've just updated this answer to give you a method for an arbitrary list of points. $\endgroup$ – Tim May 29 '13 at 11:15
1
$\begingroup$

Suppose you have $n$ given points. Assume a polynomial function of order $n-1$ with unknown constant coefficients. You'll now have to solve simultaneously $n$ number of equations for coefficients that make the polynomial curve pass through the points.

For example in your case, there are $3$ given points $A(0,1)$, $B(0.27,0)$ and $C(3.73,0)$.

Now assume a polynomial of order $2$ with unknown constant coefficients.

$$y=A+Bx+Cx^2$$

Plug in the $3$ points to get $3$ equations in $A$, $B$ and $C$ and simultaneously solve them.

And indeed $A=1$, $B=-4$ and $C=1$.

This can be employed for any arbitrary set of points, though the process gets increasingly tedious with large number of points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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