emre-ozer.github.io

Lagrange polynomial interpolation

Consider the following problem: given a set of nodes \( \{ x_k \} \) and a corresponding set of values \( \{ y_k \} \), find the lowest order interpolating polynomial \( L(x) \). An interpolating polynomial is defined through the set of relations:

$$ L(x_i) = y(x_i) $$

for all nodes \( x_i \in \{ x_k \} \).

The solution is very straightforward if one first considers the simpler problem: given a node \( x_i \in \{ x_k \} \), what is the lowest order polynomial \( \ell_i(x) \) such that:

$$ \ell_i(x_k) = \begin{cases} 1 & k = i, \\ 0 & k \neq i.\end{cases} $$

Such polynomials are called the Lagrange basis, as any interpolating polynomial can be decomposed into a weighted sum of them. Explicitly, it is given by

$$ L(x) = \sum_{i=0}^{n} y_i \ell_i(x) \quad\Rightarrow\quad L(x_i) = y(x_i) \quad\forall i. $$

The expressions for the basis polynomials are as follows:

$$ \ell_i(x) = \prod_{j \neq i} \frac{(x-x_j)}{(x_i - x_j)}, $$

arranged such that they have zeros at \(x_j\) for \( j \neq i \), and normalised such that \( \ell_i(x_i) = 1 \).

Equivalence to Newton-Cotes methods

Upon closer inspection, it turns out that Newton-Cotes integration is nothing but Lagrange interpolation in disguise. This should be intuitive, as in both cases we evaluate the function on a set of nodes and minimize errors using polynomials.

On the Newton-Cotes side, the number of nodes used is determined by the error order, which arises from going further in the Taylor expansion. On the interpolation side, the order of the interpolating polynomial is determined by the number of nodes.

To be more explicit, the map between the two is given through:

$$ \int_a^b f(x) dx \approx \int_a^b L(x)dx = \sum_{i=0}^m f_i \int_a^b \ell_i(x) dx = \sum_{i=0}^m \alpha_i f_i. $$

It only remains to show that the coefficients \( \alpha_i \) determined from the basis polynomial integrals match the Newton-Cotes coefficients.

Recall, the coefficients in the Newton-Cotes method are determined through

\begin{align*} 1 &= \alpha_0 + \dots + \alpha_m \\ \frac{1}{2} &= \alpha_0 (0/m) + \alpha_1 (1/m) + \dots + \alpha_m (m/m) \\ \vdots& \\ \frac{1}{m+1} &= \alpha_0 (0/m)^{m} + \alpha_1 (1/m)^{m} + \dots + \alpha_m (m/m)^{m}, \end{align*}
Here, the nodes are set to be \( x_k = k / m \) These equations follow directly from:
$$ \frac{1}{n+1} = \int_0^1 x^n dx = \sum_{i=0}^m \Big( \frac{i}{m} \Big)^n \int_0^1 \ell_i(x) dx. $$
The only thing left to show is the independence of the basis integrals on the integration range (noting to also shift the nodes accordingly). I think this would be a good exercise.