Evaluation, interpolation

Let ${\bf k}$ be a field and let $u=(u_0, \ldots, u_{n-1})$ be a sequence of pairwise distinct elements of ${\bf k}$ .

Remark 4   A polynomial in ${\bf k}[x]$ with degree $n-1$ , say

$$f \ = \ f_0 + f_1 x + \cdots + f_{n-1} x^{n-1}$$ (35)

can be evaluated at $x = x_0$ using Horner's rule

$$f(x_0) \ = \ ( \cdots ( f_{n-1} x_0 + f_{n-2}) x_0 + \cdots + f_1) x_0 + f_0$$ (36)

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

Definition 2   For $i = 0 \cdots n-1$ the $i$ -th Lagrange interpolant is the polynomial

$$L_i(u) \ = \ {\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}$$ (37)

with the property that

$$L_i(u_j) = \left\{ \begin{array}{rcl} 0 & {\rm if} i \neq j \\ 1 & {\rm otherwise} & \end{array} \right.$$ (38)

Proposition 6   Let $v_0, \ldots, 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 \ \ {\rm for} \ \ i = 0 \cdots n-1.$$ (39)

Moreover this polynomial is given by

$$f \ = \ {\Sigma}_{0 \leq i < n} \ v_i \ L_i(u).$$ (40)

Proof. Clearly the polynomial $f$ of Relation (40) satisfies Relation (39). 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 7   Evaluating a polynomial $f \in {\bf k}[x]$ of degree less than $n$ at $n$ distinct points $u_0, \ldots, u_{n-1}$ or computing an interpolating polynomial at these points can be done in ${\cal O}(n^2)$ operations in ${\bf k}$ .

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

$$L_i(u) \ = \ \frac{q_i}{q_i(u_i)}$$ (41)

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_0 m_1 \cdots 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$ 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$ . Hence computing $p_2, \ldots, p_n = m$ amounts to

$$\begin{array}{rcl} {\Sigma}_{1 \leq i \leq n-1} \, 2 \, i & =... ...1} i \ \\ & = & 2 \, n \, (n-1)/2 \\ & = & n (n-1). \end{array}$$ (42)

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 $2 n - 2$ operations in the base field ${\bf k}$ (from Remark 4). Then computing all $q_i(u_i)$ 's amounts to $2 n^2 - 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 (n+1) + 2 \, n^2 + 2 n^2 - 2 n + n^2 = 6 n^2 - n$ .

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^2$ 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^2 - n$ . Finally the total cost is $6 n^2 - 2n -1 + 2 \, n^2 - n = 8 \, n^2 - 2 \, n$ . $\qedsymbol$

Remark 5   We consider the map

$$E: \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}$$ (43)

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

$$VDM(u_0, \ldots, u_{n-1}) \ = \ \left( \begin{array}{lllll} 1 & u... ...dots \\ 1 & u_{n-1} & u_{n-1}^2 & \cdots & u_{n-1}^{n-1} \\ \end{array} \right)$$ (44)

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.