Introduction
- Given a set of points:
- We can plot them on a graph:
![a linear interpolation of the points](linear interpolation.svg)
- 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:
![a lagrange interpolation of the points](lagrange interpolation.svg)
- 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:
![(0, 0.1), (0.5, 0.2), (1,](latex_2.svg)
- A polynomial that interpolates N points needs a degree of N - 1
- A quadratic equation can be used to interpolate 3 points:
![y = ax^2 + bx + c](latex_3.svg)
- We know that the equation will have a value of yi for each xi 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
![all 3 sub-equations plotted on a graph](subequations.svg)
- The final equation will be a sum of the three sub-equations:
![all 3 sub-equations ang lagrange plotted on a graph](subequations and lagrange.svg)
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:
![y = (x - r_1)(x - r_2)](latex_4.svg)
- Then we know y will be 0 when either:
- We get our equation by setting r1 and r2 to 0.5 and 1
![y = x^2 - 1.5x + 0.5](latex_6.svg)
- We can plot this to visualize and check:
![sub-equation 1 plotted on a graph](subequation 1.svg)
- Let's handle our first condition:
- 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:
- Then multiply the function by 0.1
- This will mean that y = 0.1 when x = 0
- We have our equation:
![y = (x - 0.5)(x - 1)](latex_7.svg)
- When x = 0:
![y = 0.5](latex_9.svg)
- If we divide this by 0.5 then:
![\begin{align} y &= \frac](latex_10.svg)
- Or more generally:
![y = \frac{(x - 0.5)(x - 1](latex_11.svg)
- Lastly, we multiply by 0.1:
![y = \frac{0.1(x - 0.5)(x](latex_12.svg)
- And expanding gives us:
![y = 0.2 x^2 - 0.3 x + 0.1](latex_13.svg)
- Let's plot this to make sure we are right:
![scaled sub-equation 1 plotted on a graph](scaled subequation 1.svg)
- 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:
![y = (x - 0)(x - 1)](latex_14.svg)
- And scaled:
![y = \frac{0.2(x - 0)(x -](latex_15.svg)
- Expanded:
![scaled sub-equation 2 plotted on a graph](scaled subequation 2.svg)
Sub-equation 3
- Following the same method as above we get:
![y = \frac{1(x - 0.5)(x -](latex_17.svg)
- Expanded:
![scaled sub-equation 3 plotted on a graph](scaled subequation 3.svg)
- Our three equations are:
![all 3 sub-equations plotted on a graph](subequations.svg)
- If we add these 3 equations together we get:
![all 3 sub-equations plotted on a graph](lagrange.svg)
Generalized form of Lagrange Interpolation
- n is the number of points
- The set of points is:
![(x_1, y_1), (x_2, y_2) \d](latex_21.svg)
- We get a set of n - 1 equations:
![\begin{align} y &= \frac](latex_22.svg)
- Which are summed together.
- In summation and product notation, it can be reduced to:
![\sum_{j = 1}^{n}\left( \p](latex_23.svg)
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)