## Evaluation, interpolation

Let be a field and let be a sequence of pairwise distinct elements of .

Remark 4   A polynomial in with degree , say

 (35)

can be evaluated at using Horner's rule

 (36)

with additions and multiplications leading to operations in the base field . The proof is easy by induction on .

Definition 2   For the -th Lagrange interpolant is the polynomial

 (37)

with the property that

 (38)

Proposition 6   Let be in . There is a unique polynomial with degree less than and such that

 (39)

Moreover this polynomial is given by

 (40)

Proof. Clearly the polynomial 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 and
• roots
hence is the zero polynomial.

Proposition 7   Evaluating a polynomial of degree less than at distinct points or computing an interpolating polynomial at these points can be done in operations in .

Proof. We saw in Remark 4 that evaluating the polynomial of degree at one point costs operations in . So evaluating at amounts to . Let us prove now that interpolating a polynomial at can be done in operations in . We first need to estimate the cost of computing the -th interpolant . Consider , , ... where is the monic polynomial . Let and for . We have

 (41)

To estimate the cost of computing the 's let us start with that of . Computing the product of the monic polynomial of degree by the monic polynomial of degree costs
• multiplications (in the field ) to get plus
• additions (in the field ) to add (of degree ) to (of degree but without constant term)
leading to . Hence computing amounts to

 (42)

Computing implies a division-with-remainder of the polynomial of degree by the polynomial of degree . This division will have steps, each step requiring operations in . Hence computing all 's amounts to . Since has degree computing each 's amounts to operations in the base field (from Remark 4). Then computing all 's amounts to . Then computing each from the 's and 's costs . Therefore computing all 's from scratch amounts to .

Computing from the 's requires

• to multiply each (which is a polynomial of degree ) by the number leading to operations in and
• to add these leading to additions of polynomials of degree at most costing operations in
amounting to . Finally the total cost is .

Remark 5   We consider the map

 (43)

This is just the map corresponding to evaluation of polynomials of degree less than at points . It is obvious that is -linear and it can be represented by the Vandermonde matrix

 (44)

From the above discussion, this matrix is invertible iff for all . To conclude observe that both evaluation and interpolation are linear maps between coefficients and value vectors.

Marc Moreno Maza
2008-01-07