How do you create an optimal polynomial generating function from a sequence of numbers?

Answer 1

There are myriad techniques one could use to achieve this end. Some of the more common ones include polynomial interpolation and solving a system of equations (through Gaussian elimination for example).

As an example, consider the generating function f(x) = x^3

The corresponding sequence that represents f(x) is 1, 8, 27, 64, ......

Lets create a function g(x) that approximates f(x) given its first two terms (i.e. 1 and 8).

The degree of g(x) has to be 1 (since we're working with two terms).

Thus, let g(x) = (a * x) + b

Since g(x) equals f(x) for x = {1, 2}, g(1) = f(1) and g(2) = f(2)

g(1) = f(1)

g(1) = a * 1 + b = a + b; f(1) = 1

Thus, a + b = 1

Additionally, g(2) = f(2)

g(2) = 2 * a + b, f(2) = 8

Thus, 2a + b = 8

Solving these 2 equations yields a = 7, b = -6

Thus, g(x) = 7x - 6

You could go further by approximating f(x) with its first three terms (i.e. 1, 8 and 27)

This yields the polynomial 6x^2 - 11x + 6.

However, approximating f(x) with four or more terms yields f(x) itself.

Hope this helps. :)