CODEWITHSUNDEEP
pythonmathsequence
user3880632
user3880632

Reputation: 99

Finding a polynomial formula for sequence of numbers

I was wondering if there is a way in Python (or any language for that matter), where I can supply a list of numbers and I get back a polynomial of smallest degree that results in that list of numbers.

E.g. If I supply the sequence 1,4,9,16 I should get back n**2 or n^2.

Upvotes: 0

Views: 1366

Answers (1)

Rory Daulton
Rory Daulton

Reputation: 22544

You can code a routine yourself using the sympy module in Python. (This is a popular third-party module for Python.) This code uses the base formula for the Lagrange polynomial, the polynomial of smallest degree that yields a given sequence. This code allow you to define your own x-values in addition to the y-values: if you do not define the x-values, this routine will use 1, 2, .... Note that there are other ways to get this polynomial--I used the formula used in Wikipedia in the link.

import sympy

x = sympy.symbols('x')
zeropoly = x - x
onepoly = zeropoly + 1


def lagrangepoly(yseq, xseq=None):
    """Build a Lagrange polynomial from a sequence of `y` values.
    If no sequence of `x`s is given, use x = 1, 2, ..."""
    if xseq is None:
        xseq = list(range(1, len(yseq) + 1))
    assert len(yseq) == len(xseq)

    result = zeropoly
    for j, (xj, yj) in enumerate(zip(xseq, yseq)):
        # Build the j'th base polynomial
        polyj = onepoly
        for m, xm in enumerate(xseq):
            if m != j:
                polyj *= (x - xm) / (xj - xm)
        # Add in the j'th polynomial
        result += yj * polyj
    return sympy.expand(result)

With that routine, executing print(lagrangepoly([1, 4, 9, 16])) gets the printout

x**2

which is x^2 in Python notation.

Upvotes: 4

Related Questions