Lagrange Interpolation

Introduction

• Given a set of points:

  x	0	0.5	1
  y	0.1	0.2	1

• We can plot them on a graph:
• But we only have values for 3 points.
• This means that we need to use interpolation for every other value.
• Using linear interpolation (above) is simple but not very smooth.
• Instead, we can use a polynomial:
• This is now nice and smooth.
• Lagrange interpolation is a method for finding this equation.

Calculating the Lagrange Interpolation

• Lagrange Interpolation can be performed for any number of points.
• But let's keep things simple and just use 3 for now:
• A polynomial that interpolates N points needs a degree of N - 1
• A quadratic equation can be used to interpolate 3 points:
• We know that the equation will have a value of y_i for each x_i in our set of points P
• The equation can be split into 3 sub-equations:
  • Each sub-equation deals with a single point
  • It will have a value of y at x
  • And a value of 0 at all other points in P
• The final equation will be a sum of the three sub-equations:

Sub-equation 1

• For our first equation:
  • y = 0.1 when x = 0
  • y = 0 when x = 0.5
  • y = 0 when x = 1
• Let's start with the second and third conditions.
• If we write the quadratic equation in its factorized form:
• Then we know y will be 0 when either:
  • (x - r₁) = 0
  • (x - r₂) = 0
• We get our equation by setting r₁ and r₂ to 0.5 and 1
• We can plot this to visualize and check:
• Let's handle our first condition:
  • y = 0.1 when x = 0
• Our second and third condition generated a function that produces 0 at x = 0.5 and x = 1.
• We can multiply our function by a constant without affecting this property.
• Our first condition resolved by:
  • Multiplying the function by a constant such that:
    • y = 1 when x = 0
  • Then multiply the function by 0.1
    • This will mean that y = 0.1 when x = 0
• We have our equation:
• When x = 0:
• If we divide this by 0.5 then:
• Or more generally:
• Lastly, we multiply by 0.1:
• And expanding gives us:
• Let's plot this to make sure we are right:
• Sub-equation 1 is now:
  • 0.1 at x = 0
  • 0 at x = 0.5
  • 0 at x = 1

Sub-equation 2

• For our second sub-equation:
  • y = 0.2 when x = 0.5
  • y = 0 when x = 0
  • y = 0 when x = 1
• Our unscaled sub-equation will be:
• And scaled:
• Expanded:

Sub-equation 3

• Following the same method as above we get:
• Expanded:
• Our three equations are:
• If we add these 3 equations together we get:

Generalized form of Lagrange Interpolation

• n is the number of points
• The set of points is:
• We get a set of n - 1 equations:
• Which are summed together.
• In summation and product notation, it can be reduced to:

Code (Python) without SciPy

import numpy as np
from numpy.polynomial import Polynomial

points = np.array([
	[0, 0.1],
	[0.5, 0.2],
	[1, 1]])

n = len(points)
poly = Polynomial(np.zeros(n))

for j in range(n):
    k = [k for k in range(n) if k != j]
    roots = -1 * points[k, 0]
  
    sub_poly = Polynomial.fromroots(points[k, 0])
    scale = points[j, 1] / np.prod(points[j, 0] - points[k, 0])
    sub_poly.coef *= scale
    
    poly.coef += sub_poly.coef

print(poly)

Code (Python) with SciPy

import numpy as np
from scipy.interpolate import lagrange

points = np.array([
	[0, 0.1],
	[0.5, 0.2],
	[1, 1]])

poly = lagrange(points[:, 0], points[:, 1])
print(poly)