Evaluation, interpolation

Let $\bf k$ be a field and let u = (u₀,..., u_n-1) be a sequence of pairwise distinct elements of $\bf k$.

Remark 7   A polymomial in $\bf k$[x] with degree n - 1, say

f  =  f₀ + f₁x + ^... + f_n-1x^n-1 (26)

can be evaluated at x = x₀ using Horner's rule

f (x₀)  =  ( ^... (f_n-1x₀ + f_n-2)x₀ + ^... + f₁)x₀ + f₀ (27)

with n - 1 additions and n - 1 multiplications leading to 2n - 2 operations in the base field $\bf k$. The proof is easy by induction on n $\geq$ 1.

Definition 2   For i = 0 ^... n - 1 the i-th Lagrange interpolant is the polynomial

$$\Pi_{{{\mbox{\begin{scriptsize}$\begin{array}{c} 0 \leq j < n \\ j \neq i\end{array}$\end{scriptsize}}}}}^{{}} {\frac{{x-u_j}}{{u_i-u_j}}}$$ (28)

with the property that

$$\left\{\vphantom{ \begin{array}{rcl} 0 & {\rm if} i \neq j \\ 1 & {\rm otherwise} & \end{array} }\right. \begin{array}{rcl} 0 & {\rm if} i \neq j \\ 1 & {\rm otherwise} & \end{array}$$ (29)

Proposition 5   Let v₀,..., v_n-1 be in $\bf k$. There is a unique polynomial f $\in$ $\bf k$[x] with degree less than n and such that

f (u_i) = v_i  for  i = 0 ^... n - 1. (30)

Moreover this polynomial is given by

$$\Sigma_{{{0 \leq i < n}}}^{{}}$$ (31)

Proof. Clearly the polynomial f of Relation (31) satisfies Relation (30). Hence the existence is clear. The unicity follows from the fact that the difference of two such polynomials has

• degree less than n and
• n roots

hence is the zero polynomial. $\qedsymbol$

Proposition 6   Evaluating a polynomial f $\in$ $\bf k$[x] of degree less than n at n distinct points u₀,..., u_n-1 or computing an interpolating polynomial at these points can be done in $\cal {O}$(n²) operations in $\bf k$.

Proof. We saw in Remark 7 that evaluating the polynomial f of degree n at one point costs 2n - 2 operations in $\bf k$. So evaluating f at u₀,..., u_n-1 amounts to 2n² - 2n. Let us prove now that interpolating a polynomial at u₀,..., u_n-1 can be done in $\cal {O}$(n²) operations in $\bf k$. We first need to estimate the cost of computing the i-th interpolant L_i(u). Consider m₀m₁, m₀m₁m₂, ... m = m₀ ^... m_n-1 where m_i is the monic polynomial m_i = x - u_i. Let p_i = m₀m₁ ^... m_i-1 and q_i = m/m_i for i = 1 ^... n. We have

$${\frac{{q_i}}{{q_i(u_i)}}}$$ (32)

To estimate the cost of computing the L_i(u)'s let us start with that of m. Computing the product of the monic polynomial p_i = m₀m₁ ^... m_i-1 of degree i by the monic polynomial m_i = x_-u_i of degree 1 costs

• i multiplications (in the field $\bf k$) to get - u_i p_i plus
• i - 1 additions (in the field $\bf k$) to add - u_i p_i (of degree i) to x p_i (of degree i + 1 but without constant term)

leading to 2 i - 1. Hence computing p₂,..., p_n = m amounts to

$$\Sigma_{{{2 \leq i \leq n}}}^{{}}$$ 2 i - 1	=	$$\Sigma_{{{1 \leq i \leq n-1}}}^{{}}$$ 2 i + 1
	=	2$$\Sigma_{{{1 \leq i \leq n-1}}}^{{}}$$i  +  n - 1
	=	2 n (n - 1)/2  +  n - 1
	=	(n - 1)(n + 1)

(33)

Computing q_i implies a division-with-remainder of the polynomial m of degree n by the polynomial m_i of degree 1. This division will have n - 1 + 1 steps, each step requiring 2 operations in $\bf k$. Hence computing all q_i's amounts to n 2 n. Since q_i has degree n - 1 computing each q_i(u_i)'s amounts to 2n - 2 operations in the base field $\bf k$ (from Remark 7). Then computing all q_i(u_i)'s amounts to 2n² - 2n. Then computing each L_i(u) = q_i/q_i(u_i) from the q_i's and q_i(u_i)'s costs n. Therefore computing all L_i(u)'s from scratch amounts to (n - 1)(n + 1) + 2 n² + 2n² - 2n + n² = 6n² - 2n - 1.

Computing f from the L_i(u)'s requires

• to multiply each L_i(u) (which is a polynomial of degree n - 1) by the number v_i leading to n² operations in $\bf k$ and
• to add these v_i L_i(u) leading to n - 1 additions of polynomials of degree at most n - 1 costing (n - 1)n operations in $\bf k$

amounting to 2 n² - n. Finally the total cost is 6n² - 2n - 1 + 2 n² - n = 8 n² - 3 n - 1 $\qedsymbol$

Remark 8   We consider the map

$$\begin{array}{lll} {\bf k}^n & \rightarrow & {\bf k}^n \\ (f_0, ... ...eq j < n} f_j u_0^j, \ldots, {\Sigma}_{0 \leq j < n} f_j u_{n-1}^j) \end{array}$$ (34)

This is just the map corresponding to evaluation of polynomials of degree less than n at points u₀,..., u_n-1. It is obvious that E is $\bf k$-linear and it can be represented by the Vandermonde matrix

$$\left(\vphantom{ \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & ... ...s \\ 1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\ \end{array} }\right. \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & u_0^{n-1} \\ 1 &... ...& & \vdots \\ 1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\ \end{array} \left.\vphantom{ \begin{array}{lllll} 1 & u_0 & u_0^2 & \cdots & ... ...s \\ 1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\ \end{array} }\right)$$ (35)

From the above discussion, this matrix is invertible iff u_i $\neq$ u_j for all 0 $\leq$ i < j $\leq$ n - 1. To conclude observe that both evaluation and interpolation are linear maps between coefficients and value vectors.