# Higher Order Polynomial Interpolation

So far we have looked at Linear Polynomial Interpolation to interpolate two points and Quadratic Polynomial Interpolation to interpolate three points. Suppose now that we have $n+1$ distinct points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$. Then we would need a polynomial with degree $n$ or less to interpolate these points. The polynomial that would interpolate these points is defined below.

Definition: If $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ are $n + 1$ distinct points, then Lagrange's Formula for the polynomial interpolation of these points is $P_n(x) = y_0L_0(x) + y_1L_1(x) + ... + y_nL_n(x)$. |

The functions $L_0(x)$, $L_1(x)$, …, $L_n(x)$ can be obtained with the following formula for $i = 0, 1, ..., n$:

(1)Once again, we note that $P_n$ does indeed pass through the points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ since for $j = 0, 1, 2, ..., n$ it is not hard to see that $P_n(x_j) = y_j$. In fact, such a polynomial $P_n$ that satisfies these conditions is unique as we'll prove with the following theorem.

Theorem 1: If $n ≥ 0$ and $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ are $n + 1$ distinct points ($x_i \neq x_j$ for $i = 0, 1, ..., n$, $j = 0, 1, ..., n$ and $i \neq j$), then for all polynomials of degree less than or equal to $n$ there exists only one polynomial $P_n(x)$ such that $P_n(x_i) = y_i$ for $i = 0, 1, ..., n$. |

**Proof:**Suppose that $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ are distinct points for which the first coordinates of any two points do not equal each other. Suppose that there exists two polynomials $P_n$ and $P_n'$ that satisfy the properties given in the hypothesis of Theorem 1. Note that both of these polynomials have degree less than or equal to $n$. If we subtract these two polynomials, we get a polynomial $P_n(x) - P_n'(x)$ which has degree less than or equal to $n$, however, since $P_n(x_i) = y_i$ and $P_n'(x_i) = y_i$, then for $i = 0, 1, ..., n$ we have that:

- This implies that $x_i$ for $i = 0, 1, ..., n$ are roots of $P_n(x) - P_n'(x)$. But there are $n+1$ roots of the polynomial of degree $n$ or less which would contradict the Fundamental Theorem of Algebra unless $P_n(x) - P_n'(x) = 0$, that is $P_n(x) = P_n'(x)$. $\blacksquare$

Let's look at an example of constructing a polynomial interpolation given more than three points.

## Example 1

**Find the polynomial interpolation $P_4(x)$ that interpolates the points $(-1, 4)$, $(1, 1)$, $(2, 0)$, $(6, 4)$, and $(7, -1)$.**

Applying the formula above directly and we get that:

(3)