Functional Lagrange Interpolation

I recently implemented Lagrange’s interpolation method in python, and I thought I would share it here. I’m posting it because I think it’s the most nested functions I ever used in python. I would have like to use partial functions, but python doesn’t support those (well not without using functools), so I made do with nested functions...

Probably don’t use the code in a production environment or for anything serious because it’s probably very slow. I’m 90% sure numpy has a better implementation.

# Tested on Windows 7 and Python 2.7

# the code
def lagrangian_interpolate(samples):
    """
    Takes some samples as a list of tuples and returns a function that's
    a lagrangian interpolation of all the samples.
    """
    X = 0 # the tuple index of the X variable in the samples
    Y = 1 # the tuple index of the Y variable in the samples
    n = len(samples)
    # define the L function as a function generator that generates L functions
    # for a given i
    def L(i):
        "This function generates an L function for a given x_i"
        def L_gen(x):
            ret = []
            for j in xrange(n):
                if j != i:
                    ret.append((x - samples[j][X])/(samples[i][X] - samples[j][X]))
            return reduce(lambda a,b: a*b, ret)
        return L_gen

    return lambda x: sum(L(i)(x) * samples[i][Y] for i in xrange(n))

# main
prob_1 = lagrangian_interpolate([(2,1.4142),(2.5,1.5811),(3.0,1.7321)])
print prob_1(2.2)

prob_1_b = lagrangian_interpolate([(2,1.4142),(2.5,1.5811),(2.7,1.6432)])
print prob_1_b(2.2)

prob_2 = lagrangian_interpolate([(2.0,1.4142),(2.5,1.5811),(3.0,1.7321),(3.5,1.8708)])
print prob_2(2.8)