Evaluation, interpolation

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

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

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

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

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

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

Definition 2   For i = 0 ^... n - 1 mathend000# the i mathend000#-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}}}$$ (37)

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}$$ (38)

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

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

Moreover this polynomial is given by

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

Proof. Clearly the polynomial f mathend000# 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 mathend000# and
• n mathend000# roots

hence is the zero polynomial. $\qedsymbol$

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

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

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

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

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

leading to 2 i mathend000#. Hence computing p₂,..., p_n = m mathend000# amounts to

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

(42)

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

Computing f mathend000# from the L_i(u) mathend000#'s requires

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

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

Remark 5   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}$$ (43)

This is just the map corresponding to evaluation of polynomials of degree less than n mathend000# at points u₀,..., u_n-1 mathend000#. It is obvious that E mathend000# is $\bf k$ mathend000#-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)$$ (44)

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