21
$\begingroup$

Is there any "algorithm" or steps to follow to get a formula from a table of values.

Example:

Using this values:

X                Result 1                3 2                5 3                7 4                9 

I'd like to obtain:

Result = 2X+1 

Edit

Maybe using excel?

Edit 2

Additional info:

It is not going to be always a polynomial and it may have several parameters (I think 2).

  • 0
    @J.M.: I thought so too - but then I found the tool mentioned below!2010-11-23

9 Answers 9

13

The best tool for doing this is that impressive piece of software:

http://www.nutonian.com/products/eureqa/

Edit: For your abovementioned very easy example, even WA will find the right formula:

http://www.wolframalpha.com/input/?i=3,+5,+7,+9,...

  • 0
    @masterxilo: Thank you, corrected the link2016-10-03
5

An easier method (assuming that the values were generated by a polynomial) would be to note that successive divided differences $\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$ are constant and equal to 2; thus your function is of the form $y=2x+c$. The constant $c$ is then determined by replacing both $x$ and $y$ with appropriate values, and then solving for $c$.

  • 0
    +1: Didn't know that - interesting! Just found this reference: http://en.wikipedia.org/wiki/Divided_differences2010-11-23
4

I have made a sample in my C# genetic algorithms library, GeneticSharp, that solves your question.

The sample called "Function Builder" receives the function's arguments values and the expected result, then, using genetic algorithms, it try to discover the math function.

Take a look:

GeneticSharp: Function Builder sample

  • 0
    @PatrikValkovič yes, here: https://github.com/giacomelli/GeneticSharp/blob/master/src/GeneticSharp.Runner.ConsoleApp/Samples/FunctionBuilderSampleController.cs2018-07-24
1

One way to obtain the desired relationship is to use the regression analysis. In the case that you know what form of the relationship you are expecting, say you know that $f(x) = a * x + b$ it is very simple to find the parameters $a$ and $b$ (see for example). In the case that you don't know what form your formula may take, it is common to use the nonparametric regression techniques.

1

The Online Polynomial Regression solver http://www.xuru.org/rt/PR.asp finds the correct function and finds a function minimizing the error, when there is no exact polynomial.

The Regression Tools http://xuru.org/rt/TOC.asp also provide non-polynomial solvers.

1

(This is way too complicated to use it here, one can always expect a desired polynomial that fits all the points.)

One of the possible algorithm is Langrange Interpolating Polynomial.

For a polynomial $P(n)$ of degree $(n-1)$ passes through $n$ points: $(x_1,y_1=f(x_1)),\ldots,(x_n,y_n=f(x_n))$

We have

$P(x)=\sum_{j=1}^n\left[y_j\prod^n_{k=1,k\neq j}\frac{x-x_k}{x_j-x_k}\right]$

Explicitly, $P(x)=\frac{y_1(x-x_2)\cdots(x-x_n)}{(x_1-x_2)\cdots(x_1-x_n)}+ \frac{y_2(x-x_1)(x-x_3)\cdots(x-x_n)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_n)}+\ldots +\\\frac{y_n(x-x_1)\cdots(x-x_{n-1})}{(x_n-x_1)\cdots(x_n-x_{n-1})}$

In this context,

\begin{align} P(n)&=\frac{3(n-2)(n-3)(n-4)}{(1-2)(1-3)(1-4)}+\frac{5(n-1)(n-3)(n-4)}{(2-1)(2-3)(2-4)}\\ &+\frac{7(n-1)(n-2)(n-4)}{(3-1)(3-2)(3-4)}+\frac{5(n-1)(n-2)(n-3)}{(4-1)(4-2)(4-3)} \end{align}

Simplify and we get

$P(n)=-\frac13(2 n^3-12 n^2+16 n-15) $

1

Whenever I am asked to find a formula from a range of values, I always use difference patterns.

Do with the data given:

x____________1_______2________3________4

y____________3_______5________7________9

$1^{st}$ diff:___________+2______+2________+2

I know that with the general formula $y = mx + c$ the difference pattern is:

x____________1_______2________3________4

y__________m + c____2m + c____3m + c_____4m + c

$1^{st}$ diff:_________+m______+m _______+m

So the first difference pattern is equal to $m$, i.e. $m = 2$.

I can then use $y(1) = m + c$ to find $c$

where $y(1) = 3$, and $m = 2$

$3 = 2 + c$

therefore $c = 1$

and putting it all together we get $y = 2x + 1$

You can use further difference patterns for polynomials such as $2^{nd}$ diff for $x^2$, $3^{rd}$ diff for $x^3$, etc. but note that for an exponential function you will need to look at a common ratio, rather than a difference pattern.

  • 0
    An [introduction to posting mathematical expressions](https://math.stackexchange.com/help/notation) may be of interested for the future.2017-08-16