Lagrange interpolation

Lagrange Interpolation is a concept that allows us to find a polynomial of least degree passing through a given set of points. Specifically:

If , then the polynomial of least degree passing through all the points in is given by

where

or simply,

note that the degree of polynomial .

Here’s an example:

If is a function such that , then find

So we have . Using lagrange interpolation gives us as:

or, once simplified,

This technique is also useful for other stuff, such as finding patterns in hard-to-decipher sequences:

Find the nth term of the sequence

Letting and so on, lagrange interpolation gives us:

simplified:

Of course, there are some problems that cannot be solved by this technique, namely problems where it is specified that the polynomial is of a higher order than the number of points it passes through:

Let . If , then the value of is?

The lagrange interpolated polynomial for the above values is . However, this gives the wrong answer of . The correct answer is , because we have been asked to fit a polynomial of higher order in this equation.

Also, this technique should only be used as a last resort for pattern finding. This is extremely computation heavy and is more of a bruteforce algorithm, that is better suited to computers rather than manual calculation. Most math softwares have a lagrange interpolation function in them. Geogebra’s is called Polynomial().

The code I used to generate the above function:

import sys
 
pts = []
for i in range(1,len(sys.argv),2):
    pts.append([int(sys.argv[i]), int(sys.argv[i+1])])
 
output = "P(x) = "
 
for i in pts:
    nr = ""
    dr = ""
    for r in pts:
        if r is i:
            continue
        dr += "({})".format(i[0]-r[0])
        if r[0] < 0:
            nr += "(x+{})".format(-r[0])
        else:
            nr += "(x-{})".format(r[0])
    output += "\\frac{{{2}{0}}}{{{1}}} + ".format(nr,dr,i[1])
 
print(output)