Lagrange Interpolation

The Lagrange interpolation formula is a way to find a polynomial which takes on certain values at arbitrary points. Specifically, it gives a constructive proof of the theorem below.

Suppose we have one point (1,3). How can we find a polynomial that could represent it? \[ P(x) = 3 \] \[ P(1) = 3 \]

Suppose we have sequence of points: (1,3), (2,4). How can we find a polynomial that could represent it? \[ P(x) = \frac {(x - 2)}{(1-2)} \times 3 + \frac {(x - 1)}{(2-1)} \times 4 \] \[P(1) = 3\\P(2) = 4 \]

Suppose we have sequence of points: (1,3), (2,4), (7,11). How can we find a polynomial that could represent it? \[ P(x) = \frac {(x-2)(x-7)}{(1-2)(1-7)} \times 3 + \frac {(x-1)(x-7)}{(2-1)(2-7)} \times 4 + \frac {(x-1)(x-2)}{(7-1)(7-2)} \times 11 \] \[P(1) = 3\\P(2) = 4\\P(7) = 11 \] In a general form it looks like this: \[ P ( x ) = \frac { \left( x - x _ { 2 } \right) \left( x - x _ { 3 } \right) } { \left( x _ { 1 } - x _ { 2 } \right) \left( x _ { 1 } - x _ { 3 } \right) } y _ { 1 } + \frac { \left( x - x _ { 1 } \right) \left( x - x _ { 3 } \right) } { \left( x _ { 2 } - x _ { 1 } \right) \left( x _ { 2 } - x _ { 3 } \right) } y _ { 2 } + \frac { \left( x - x _ { 1 } \right) \left( x - x _ { 2 } \right) } { \left( x _ { 3 } - x _ { 1 } \right) \left( x _ { 3 } - x _ { 2 } \right) } y _ { 3 } \] \[ P(x) = \sum _1^3 P_i (x) y_i \]

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), there is a unique polynomial \(P\) with real coefficients satisfying \( P(x_i)=y_i\) for \( i \in \{ 1,2, \ldots, n \} \), such that \( \text{deg}(P) < n.\) \(_\square\)

This theorem can be viewed as a generalization of the well-known fact that two points uniquely determine a straight line, three points uniquely determine the graph of a quadratic polynomial, four points uniquely determine the graph of a cubic polynomial, and so on. (Two caveats: (1) the points are required to have different \(x\)-coordinates, and (2) the "quadratic polynomial" might actually be a linear or constant polynomial, the "cubic polynomial" might actually be a quadratic, linear, or constant polynomial, and so on.)

First, a proof that the polynomial \( P \) is unique: Suppose \( Q\) and \( R\) are polynomials with the above properties. Then \( Q-R\) vanishes on \( x_1,x_2,\ldots,x_n,\) but its degree is less than \( n.\) A nonzero polynomial of degree \( <n\) cannot have \(n\) roots, so \( Q-R\) must be the zero polynomial, i.e. \( Q=R.\)

Now, to show that \( P\) exists, let \[ P_1(x) = \frac{(x-x_2)(x-x_3)(\cdots)(x-x_n)}{(x_1-x_2)(x_1-x_3)(\cdots)(x_1-x_n)}. \] Then \( P_1(x_1)=1 \) and \( P_1(x_2)=P_1(x_3)=\cdots=P_1(x_n)=0.\)

Similarly construct polynomials \( P_2,P_3,\ldots,P_n\) such that \( P_j (x_j)=1\) and \( P_j (x_i)=0\) for all \( i \neq j\). (One way to write \(P_j(x)\) is \[ P_j(x) = \frac{f(x)}{(x-x_j)f'(x_j)}, \] where \( f(x) = (x-x_1)(x-x_2)(\cdots)(x-x_n).)\)

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 \} \). It is a sum of polynomials of degree \( n-1,\) so its degree is \( <n.\) \(_\square\)

Also note that the theorem still holds, with the same proof as above, if any field is substituted for the real numbers (e.g. the rational numbers, the complex numbers, the integers mod \( p,\) etc.).

Using Lagrange interpolation to find a polynomial \(P\) of degree \( <4\) satisfying

\[\begin{array} &P(1)=1, &P(2)=4, &P(3)=1, &P(4)=5,\end{array}\]

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, \[\begin{align} P(x) = &1\times \left(-\frac {1}{6}\right)(x-2)(x-3)(x-4) + 4\times \frac {1}{2} (x-1)(x-3)(x-4)\\ &+ 1\times \left(-\frac {1}{2}\right) (x-1)(x-2)(x-4)+ 5 \times \frac {1}{6} (x-1)(x-2)(x-3). \end{align}\]

Simplifying gives \( P(x) = \frac{13}6 x^3 -16x^2+\frac{215}6 x -21.\) \(_\square\)

Lagrange interpolation is related to the method of differences, which can also be used to solve some of the above problems.

• Method of Differences \(LaTeX\)