# 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 following theorem:

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

Let \(f(x)\) be a quintic polynomial such that

\[ \begin{array} { r l } f(1) & = 1 \\ f(2) & = 1 \\ f(3) & = 2 \\ f(4) & = 3 \\ f(5) & = 5 \\ f(6) & = 8. \\ \end{array} \]

Determine \( f(7)\).

**Note:** Many people are answering this incorrectly because they think it is the Fibonacci sequence, but this problem is asking about a **quintic polynomial** that passes through those points. That does not necessarily mean the next term behaves as the Fibonacci sequence would.

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

**Cite as:**Lagrange Interpolation.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/lagrange-interpolation/