MAT187 L04 - Polynomial Interpolation

#MAT187 PCE
Polynomial interpolation (Lagrange interpolation) is a method of interpolating between a bunch of points by summing polynomials that intersect one specific data point, and no others. This results in a polynomial that intersects all the data points.

Lagrange interpolation method
For the data points $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n - 1}, y_{n - 1}), (x_{n}, y_{n})$ , our Lagrange interpolation will follow the form:
$P_{n} (x) = y_{1} L_{1} (x) + y_{2} L_{2} (x) + \dots + y_{n - 1} L_{n - 1} (x) + y_{n} L_{n} (x)$

...where $L_{1} (x), \dots, L_{n} (x)$ are $(n - 1)^{t h}$ degree polynomials that, for $m ϵ [1, n]$ and $m ϵ N$ , fulfill $L_{m} (x_{m}) = 1$ and $L_{n} (x_{c}) = 0$ , $c \neq m$ , $c ϵ N$ .

Example
For a data set with 4 points, the formula is as follows:

...which is basically where the $L_{m} (x)$ polynomials consist of:

A numerator that equals to zero when any $x \neq x_{m}$ is subbed in.
A constant denominator that divides the numerator such that the result is zero if $x_{m}$ is subbed in.

Lagrange interpolation results in a function that:

100% accurately intersects all data points.
Does not account for noise in data.

Lagrange Polynomial for 3 data points:

	left=-2; right=6;
    top=5; bottom=-5;
	---
	(1,2)
	(5,4)
	(2,-3)
	y=\frac{2(x-2)(x-5)}{(1-2)(1-5)}+\frac{-3(x-1)(x-5)}{(2-1)(2-5)}+\frac{4(x-1)(x-2)}{(5-1)(5-2)}

Lagrange Polynomial for lots of data points: