Lagrange Interpolation Formula

Given $n$ distinct real values $x_1, x_2, \ldots x_n$ and $n$ real values $y_1, y_2, \ldots y_n$ (not necessarily distinct), the Lagrange Interperloation Formula gives a polynomial $P$ with real coefficients satisfying $P(x_i)=y_i$ for $i \in \{ 1,2, \ldots n \}$.

To describe polynomial $P$, we first solve the following problem: Given $n$ distinct real values $x_1, x_2, \ldots x_n$, does there exist a polynomial $f$ with real coefficients satisfying $f(x_1)=1$ and $f(x_i)=0$ for all values of $i \neq 1$?

By the Remainder-Factor Theorem, if such a polynomial exists, then for all $i\neq 1$, $(x-x_i)$ must be a factor of the polynomial. Consider the polynomial $g(x) = \prod \limits_{i=2}^n (x-x_i)$. This satisfies the conditions $g(x_i)=0$. Now let $F = g(x_1)$. Then since $F \neq 0$ (using the condition that the $x_i$ are distinct), we may divide by $F$ to obtain polynomial $f(x) = \frac{g(x)}{F}$. We have $f(x_i) = \frac {g(x_i)}{F} = 0$ and $f(x_1) = \frac {g(x_1)} {F} = 1$, giving the polynomial desired.

Let $P_j(x_j)$ be the polynomial with real coefficients satisfying $P_j (x_j)=1$ and $P_j (x_i)=0$ for all $i \neq j$. Then, $P(x) = \sum y_i P_i(x)$ is a polynomial with real coefficients satisfying $P(x_i)=y_i$ for all $i \in \{ 1,2, \ldots n \}$.

Worked Examples

1. If we want to find a polynomial that satisfies

$P(1)=1, P(2)=4, P(3)=1, P(4)=5,$ what are the polynomials $P_1(x), P_2(x), P_3(x), P_4(x), P(x)$?

Let $f(x) = (x-2)(x-3)(x-4)$. Then

$f(1) = (-1)(-2)(-3)=-6 \text{, so } P_1(x) = -\frac {1}{6}(x-2)(x-3)(x-4).$

Let $f(x) = (x-1)(x-3)(x-4)$. Then

$f(2) = (1)(-1)(-2) = 2 \text{, so } P_2 (x) = \frac {1}{2} (x-1)(x-3)(x-4).$

Let $f(x) = (x-1)(x-2)(x-4)$. Then

$f(3) = (2)(1)(-1) = -2 \text{, so } P_3 (x) = -\frac {1}{2} (x-1)(x-2)(x-4).$

Let $f(x) = (x-1)(x-2)(x-3)$. Then

$f(4) = (3)(2)(1) = 6 \text{, so } P_4 (x) = \frac {1}{6} (x-1)(x-2)(x-3).$

Hence,

$P(x) = 1\times (-\frac {1}{6})(x-2)(x-3)(x-4) + 4\times \frac {1}{2} (x-1)(x-3)(x-4)$ $+ 1\times (-\frac {1}{2}) (x-1)(x-2)(x-4)+ 5 \times \frac {1}{6} (x-1)(x-2)(x-3).$

2. Show that if we require the polynomial in Lagrange's Interpolation Formula to have degree at most $n-1$, then there is a unique polynomial satisfying the conditions. Show further that this polynomial is $P(x)$ itself.

Suppose two polynomials $R(x)$ and $S(x)$ satisfy the conditions of Lagrange's Interpolation Formula and have degree at most $n-1$. Consider the polynomial $T(x) = R(x)-S(x)$. By the conditions, we have $T(x_i) = R(x_i)-S(x_i) = y_i-y_i=0$. Hence, by the Remainder-Factor Theorem,, for all values of $i$, $(x-x_i)$ must be a factor of $T(x)$. Since the $x_i$ are distinct, we have $T(x) = U(x) \prod \limits_{i=1}^n(x-x_i)$. If $U(x)$ is not the zero polynomial, then the degree on the right hand side is at least $n$, while the degree on the left hand side is at most $n-1$, which is a contradiction. Thus, $U(x)=0$, and so $T(x)=0$, which gives $R(x)=S(x)$. Hence, there is a unique polynomial which satisfies the conditions in the question. It is clear that each of the $P_i(x)$ has degree at most $n-1$ (it can have degree 0 if $y_i=0$). Hence, since $P(x)$ is the linear combination of these polynomials, it also has degree at most $n-1$.

3. Given $n$ distinct complex values $x_1, x_2, \ldots x_n$ and $n$ (not necessarily distinct) complex values $y_1, y_2, \ldots y_n$, does there exist a polynomial with complex coefficients satisfying $P(x_i)=y_i$ for all values of $i$?

Solution: Repeat the above discussion by replacing "real" with "complex". Then $P(x)= \sum y_i P_i(x)$ is a polynomial with complex coefficients.