Higher Order Polynomial Interpolation

# 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)
\begin{align} L_i(x) = \frac{(x - x_0)...(x - x_{i-1})(x - x_{i+1})...(x - x_n)}{(x_i - x_0)...(x_i - x_{i-1})(x_i - x_{i+1})...(x_i - x_n)} = \frac{\prod_{j=0, j \neq i}^n (x - x_j)}{\prod_{j=0, j \neq i}^n (x_i - x_j)} \end{align}

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:
(2)
$$P_n(x_i) - P_n'(x_i) = 0$$
• 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)
\begin{align} \quad P_4(x) = y_0 L_0(x) + y_1L_1(x) + y_2L_2(x) + y_3L_3(x) + y_4L_4(x) \\ \quad P_4(x) = y_0 \frac{\prod_{j=0, j \neq 0}^n (x - x_j)}{\prod_{j=0, j \neq 0}^n (x_0 - x_j)} + y_1 \frac{\prod_{j=0, j \neq 1}^n (x - x_j)}{\prod_{j=0, j \neq 1}^n (x_1 - x_j)} + y_2 \frac{\prod_{j=0, j \neq 2}^n (x - x_j)}{\prod_{j=0, j \neq 2}^n (x_2 - x_j)} + y_3 \frac{\prod_{j=0, j \neq 3}^n (x - x_j)}{\prod_{j=0, j \neq 3}^n (x_3 - x_j)} + y_4 \frac{\prod_{j=0, j \neq 4}^n (x - x_j)}{\prod_{j=0, j \neq 4}^n (x_4 - x_j)} \\ \quad P_4(x) = 4 \frac{(x - x_1)(x - x_2)(x - x_3)(x - x_4)}{(x_0 - x_1)(x_0 - x_2)(x_0 - x_3)(x_0 - x_4)} + 1\frac{(x - x_0)(x - x_2)(x - x_3)(x - x_4)}{(x_1 - x_0)(x_1 - x_2)(x_1 - x_3)(x_1 - x_4)} \\ + 4\frac{(x - x_0)(x - x_1)(x - x_2)(x - x_4)}{(x_3 - x_0)(x_3 - x_1)(x_3 - x_2)(x_3 - x_4)} - 1\frac{(x - x_0)(x - x_1)(x - x_2)(x - x_3)}{(x_4 - x_0)(x_4 - x_1)(x_4 - x_2)(x_4 - x_3)} \\ \quad P_4(x) = 4 \frac{(x - 1)(x - 2)(x - 6)(x - 7)}{(-1 - 1)(-1 - 2)(-1 - 6)(-1 - 7)} + 1\frac{(x + 1)(x - 2)(x - 6)(x - 7)}{(1 + 1)(1 - 2)(1 - 6)(1 - 7)} \\ + 4\frac{(x + 1)(x - 1)(x - 2)(x - 7)}{(6 + 1)(6 - 1)(6 - 2)(6 - 7)} - 1\frac{(x + 1)(x - 1)(x - 2)(x - 6)}{(7 + 1)(7 - 1)(7 - 2)(7 - 6)} \\ \quad \quad \quad P_4(x) = \frac{1}{84} (x - 1)(x - 2)(x - 6)(x - 7) - \frac{1}{60} (x + 1)(x - 2)(x - 6)(x - 7) - \frac{1}{35} (x + 1)(x - 1)(x - 2)(x - 7) - \frac{1}{240}(x + 1)(x - 1)(x - 2)(x - 6) \\ \end{align}