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.