Special thanks to Alistair Stewart for the helpful discussions

In this research article, I review the barycentric interpolation method$^{[1]}$ as a more efficient form for working with Lagrange bases especially when paired with nth roots of unity.

First we define $\ell(x)$ as the product of terms:

$$\ell(x) = \prod^n_{i=0} (x - x_i)$$

Next we define the barycentric weight $w_i$ as:

$$w_i = \prod^{n}_{j=0, j \ne i} (x_i -x_j) ^{-1}$$

Such that the Lagrange base $\mathcal{L}_i(x)$ can be written as:

$$\begin{equation} \mathcal{L}_i(x) = \ell(x) \frac{w_i}{x-x_i} \tag{1} \end{equation}$$

This works because:

$$\mathcal{L}_i(x) = \delta_{ij} = \prod\limits_{j = 0, { i \ne j}}^{n} (\frac{x-x_j}{x_i - x_j}) = \frac{\prod^n_{i=0} (x - x_i)}{\prod^{n}_{j=0, j \ne i} (x_i -x_j)(x-x_i)}$$

(The $(x - x_i)$ term in the numerator and denominator both cancel out)

Where $\delta_{ij}$ is the Kronecker delta function. And so our new Lagrange polynomial becomes:

$$\phi(x) = \sum^{n}_{i = 0} \frac{\ell(x) \cdot w_i}{x-x_i} \cdot v_i$$

Since $\ell(x)$ is a common term we can factor it out such that we have:

$$\begin{equation} \phi(x) = \ell(x) \sum^{n}_{i = 0} \frac{ w_i}{x-x_i} \cdot v_i \tag{2} \end{equation}$$

This form allows us to precompute $\ell(x)$ and only have to compute the individual barycentric weights for each $i$-th term. This gives us a much better complexity than the naive Lagrange interpolation polynomial.

Equation $(2)$ is also known as the “First form of the barycentric interpolation formula”.

But we’re not done, we need to re-write the barycentric weight $w_i$ as a function, rather than an expression. Notice that we can rewrite $w_i$ as:

$$\begin{align*} w_i &= \frac{1}{\prod^{n}_{j=0, j \ne i} (x_i -x_j)} \\ &= \frac{1}{\ell^{\prime}(x_i)} \end{align*}$$

Where $\ell^{\prime}(x)$ is the derivative of $\ell(x)$. In order to understand how we arrived at this derivative expression, Let’s examine an example for $n = 4$

$$\ell(x) = \prod^{4}_{i = 0}(x - x_i)$$

In order to compute the derivative of this function we leverage the product rule:

$$(u \cdot v)^{\prime} = u^{\prime} \cdot v + u \cdot v^{\prime}$$

Thus the derivative becomes:

$$\begin{split} \ell^{\prime}(x) &= (x - x_2)(x - x_3)(x - x_4)\\&+(x - x_1)(x - x_3)(x - x_4)\\&+(x - x_1)(x - x_2)(x - x_4) \\&+(x - x_1)(x - x_2)(x - x_3)\\ \end{split}$$

Evaluating the derivative $\ell^{\prime}(x)$ at $x_1$ gives us:

$$\ell^{\prime}(x_1) = (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)$$

From observing how the derivative behaves at other coordinates $x_1, x_2 \dots x_n$, we can generalise the derivative as:

$$\ell^{\prime}(x) = \sum^{n}_{i = 0} (\prod^{n}_{j = 0, i \ne j} (x -x_j))$$

So we see now how our barycentric weight $w_i$ can be re-written as a function of $x_i$:

$$\begin{split} w_i &= \prod^{n}_{j = 0, i \ne j} (x_i -x_j)^{-1} \\ &= \ell^{\prime}(x_i)^{-1} \end{split}$$

nth Roots of Unity

Another optimisation we can make here is to reduce the computation time for the terms $\ell(x)$ and $\ell^{\prime}(x_i)$ to be logarithmic, by leveraging the $n$th roots of unity. The $n$th Roots of unity are simply the solutions to the equation:

$$X^n = 1$$

For example, the solutions to the equation at $n = 2$, are $x = 1, -1$. This is because, $1^2 = (-1)^2$. At $n=4$, we run into a problem, the first two solutions are $1$ & $-1$ same as before, but other what two numbers raised to $4$ will give us $1$? Well logically that would be $\sqrt{1}$ and $\sqrt{-1}$ but there are no solutions for this expression in the real numbers. Instead, they are referred to as $-i$ and $i$, imaginary units which lie in the complex plane. Usually we’d be working in finite fields or cyclic groups where there are indeed solutions to these expressions. The fundamental theorem of algebra states that any $n$th degree polynomial has $n$ roots. What this means is that we can factor the equation above into the form:

$$\begin{equation} \ell(x) = X^n - 1 = \prod^{n}_{i = 0}(x - \omega^i) \tag{3} \end{equation}$$

Where $\omega$ is some primitive root of unity such that $\omega^n = 1$. This primitive root of unity has an order $n$, that is to say that $\omega$ generates a multiplicative group of order $n$. It’s worth noting that this group is an Abelian group. Equation $(3)$ is also referred to as the Zero or Vanishing Polynomial. We can show this is true by recalling basic group theory, for any positive integer $k < n$:

$$\omega^{k^n} = (\omega^k)^n = (\omega^n)^k = 1^k = 1$$

So this means equation $(3)$ will “vanish” on all powers of $\omega^i \space \forall i\in [n]$. Finally, the barycentric weight, is just the derivative of equation $(3)$:

$$\ell^{\prime}(x) = nx^{(n-1)}$$

So our new Lagrange base becomes:

$$\begin{split} \mathcal{L}_i(x) &= \frac{x^n - 1}{n\omega^{i(n-1)}(x - \omega^i)} \\ &= \frac{\omega^i(x^n - 1)}{n(x - \omega^i)} \end{split}$$

References

$^{[1]}$ Barycentric Lagrange Interpolation