Polynomial Interpolation

We are given a set of \( n+1 \) points \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\). The central question is: Does there exist a polynomial \( p_n(x) \) of degree at most \( n \) that passes through all these points?

\[ p_n(x_i) = y_i \quad \text{for } i = 0, 1, \dots, n \, ? \]

Theorem — Existence and Uniqueness

If the interpolation nodes \( x_i \) are all distinct (that is, \( x_i \ne x_j \) for \( i \ne j \)), then there exists a unique polynomial \( p_n(x) \) of degree ≤ \( n \) such that:

\[ p_n(x_i) = y_i \quad \text{for all } i = 0, 1, \dots, n. \]

This fundamental result guarantees that the interpolation problem is well-posed: for any set of distinct points, one and only one polynomial can be found that exactly passes through them.

Lagrange Interpolation

The Lagrange interpolation formula provides a direct way to construct the interpolating polynomial without solving a system of linear equations. It expresses \( p_n(x) \) as a weighted sum of the data values \( y_i \):

\[ L(x) = \sum_{i=0}^{n} y_i \cdot \ell_i(x) \]

where each \( \ell_i(x) \) is a Lagrange basis polynomial defined by:

\[ \ell_i(x) = \prod_{\substack{j=0 \\ j \ne i}}^{n} \frac{x - x_j}{x_i - x_j} \]

• \( \ell_i(x_i) = 1 \)
• \( \ell_i(x_j) = 0 \) for \( j \ne i \)

This means that each basis polynomial \( \ell_i(x) \) takes the value 1 at its own node and 0 at all others, ensuring that the resulting sum exactly fits all data points.

Example 1 — Linear Interpolation (n = 1)

Consider two points: \( (x_0, y_0) = (1, 2) \) and \( (x_1, y_1) = (3, 4) \).

\[ p_1(x) = y_0 \frac{x - x_1}{x_0 - x_1} + y_1 \frac{x - x_0}{x_1 - x_0} \] \[ p_1(x) = 2 \frac{x - 3}{1 - 3} + 4 \frac{x - 1}{3 - 1} \] \[ p_1(x) = x + 1 \]

Thus, the interpolating polynomial is \( p_1(x) = x + 1 \), which exactly passes through both points.

Example 2 — Quadratic Interpolation (n = 2)

Given three points: \( (1, 2), (2, 3), (4, 1) \), we compute the Lagrange basis polynomials:

\[ \ell_0(x) = \frac{(x - 2)(x - 4)}{(1 - 2)(1 - 4)} = \frac{(x - 2)(x - 4)}{3} \] \[ \ell_1(x) = \frac{(x - 1)(x - 4)}{(2 - 1)(2 - 4)} = -\frac{(x - 1)(x - 4)}{2} \] \[ \ell_2(x) = \frac{(x - 1)(x - 2)}{(4 - 1)(4 - 2)} = \frac{(x - 1)(x - 2)}{6} \]

\[ p_2(x) = 2\,\ell_0(x) + 3\,\ell_1(x) + 1\,\ell_2(x) \]

This polynomial can be expanded to obtain its explicit form. The resulting curve smoothly passes through the three given data points.

Remarks

• The Lagrange formula is simple and elegant but becomes computationally expensive for large \( n \).
• It is mainly used for symbolic or theoretical interpolation.
• For numerical computation, the Newton form of interpolation is often preferred for efficiency.