Higher Order Lagrange Interpolating Polynomials

So far we have looked at Linear Lagrange Interpolating Polynomials to interpolate two points $(x_0, y_0)$ and $(x_1, y_1)$ where $x_0$ and $x_1$ are distinct, and Quadratic Lagrange Interpolating Polynomials to interpolate three points $(x_0, y_0)$, $(x_1, y_1)$, and $(x_2, y_2)$ where $x_0$, $x_1$, and $x_2$ are distinct numbers. Suppose now that we have $n+1$ points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ where $x_0$, $x_1$, …, $x_n$ are distinct numbers. Then we would need a polynomial with degree $n$ or less to interpolate these points.

To match with our definitions of linear and quadratic interpolating polynomials, we wish to obtain a polynomial function $P_n$ in terms of functions $L_0$, $L_1$, …, $L_n$ such that:

(1)

\begin{align} \quad P_n(x) = y_0L_0(x) + y_1L_1(x) + … + y_nL_n(x) \end{align}

We also want $P(x_k) = y_k$ for each $k = 0, 1, …, n$. To do this, we will need $L_k(x_i) = 0$ for $i \neq k$, and $L_k(x_k) = 1$. We will let the numerator of $L_k$ be:

(2)

\begin{align} \quad (x - x_0)(x - x_1)…(x - x_{k-1})(x - x_{k+1})…(x - x_n) \end{align}

Now for $L_k(x_k) = 1$, we need that the denominator of $L_k$ be equal to the numerator when evaluated at $x = x_k$, that is the denominator of $L_k$ will be:

(3)

\begin{align} \quad (x_k - x_0)(x_k - x_1)…(x_k - x_{k-1})(x_k - x_{k+1})…(x_k - x_n) \end{align}

Thus for each $k = 0, 1, …, n$, define $L_k$ as follows:

(4)

\begin{align} \quad L_k(x) = \frac{(x - x_0)(x - x_1)…(x - x_{k-1})(x - x_{k+1})…(x - x_n)}{(x_k - x_0)(x_k - x_1)…(x_k - x_{k-1})(x_k - x_{k+1})…(x_k - x_n)} = \prod_{i=0}_{i \neq k}^n \frac{(x - x_i)}{(x_k - x_i)} \end{align}

Note that from the definition of $L_k$ above that we can easily obtain the general formulas for the linear Lagrange interpolating polynomials that pass through the points $(x_0, y_0)$ and $(x_1, y_1)$ ($x_0$ and $x_1$ distinct) and the quadratic linear Lagrange interpolating polynomial that passes through the points $(x_0, y_0)$, $(x_1, y_1)$, and $(x_2, y_2)$ ($x_0$, $x_1$, and $x_2$ distinct). We will now formally define higher order Lagrange interpolating polynomials.

Definition: The $n^{\mathrm{th}}$ Order Lagrange Interpolating Polynomial that passes through the $n + 1$ points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$ where $x_0$, $x_1$, …, $x_n$ are distinct numbers is $P_n(x) = y_0L_0(x) + y_1L_1(x) + … + y_nL_n(x)$.

Once again, we note that $P_n(x) = y_0L_0(x) + y_1L_1(x) + … + y_nL_n(x)$ 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$ since $L_k(x_j) = 0$ for $k \neq j$ and $L_k(x_k) = 1$. 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$ points where $x_0$, $x_1$, …, $x_n$ are distinct numbers, 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 $n + 1$ points such that $x_0$, $x_1$, …, $x_n$ are distinct numbers. 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:

(5)

\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 an $n^{\mathrm{th}}$ order Lagrange interpolating polynomial given four or more points.

Example 1

Find the quartic Lagrange interpolating polynomial, $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:

(6)

\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}

The graph of $y = P_4(x)$ is given below: