# 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)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)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)Thus for each $k = 0, 1, …, n$, define $L_k$ as follows:

(4)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:

- 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)The graph of $y = P_4(x)$ is given below: