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)
\begin{equation} P_n(x_i) - P_n'(x_i) = 0 \end{equation}
  • 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}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License