- The Lagrange polynomial basis .
- The Lagrange interpolation polynomial .
- The multivariate Horner scheme

We must find a new polynomial which is somewhat ''perpendicular'' to the with respect to the points . Any multiple of added to the previous must leave the value of this unchanged at the points . We can see the polynomials as ``vectors'', we search for a new ``vector'' which is ``perpendicular'' to all the . We will use a version of the Gram-Schmidt othogonalisation procedure adapted for the polynomials. The original Gram-Schmidt procedure for vectors is described in the annexes in Section 13.2.

We define the scalar product with respect to the dataset of points between the two polynomials and to be:

(3.19) |

We have a set of independent polynomials . We want to convert this set into a set of orthonormal vectors with respect to the dataset of points by the Gram-Schmidt process:

**Initialization**k=1;**Normalisation**

**Orthogonalisation**

For to , do:(3.21)

We will take each and remove from it the component parallel to the current polynomial .**Loop**increment . If go to step 2.

The initial set of polynomials can simply by initialized with the monomials of a polynomial of dimension . For example, if , we obtain: , , , , , , , ,

In the Equation 3.22, there is a division. To improve the stability of the algorithm, we must do ``pivoting''. That is: select a salubrious pivot element for the division in Equation 3.22). We should choose the (among the points which are still left inside the dataset) so that the denominator of Equation 3.22 is far from zero:

If we don't manage to find a point such that , it means the dataset is NOT poised and the algorithm fails.

After completion of the algorithm, we have:

The Lagrange interpolation polynomial .

is a matrix which represents the way the monomials are ordered inside the polynomial. Inside our program, we always use the ``order by degree'' type. For example, for , we have: . We have the following matrix :

We can also use the ``inverse lexical order''. For example, for , we have: . We have the following matrix (the is to indicate that we are in ``inverse lexical order'') :

and

The ``inverse lexical order'' is easier to transform in a multivariate horner scheme. For example: for the polynomial , we have:

- Set
- Set
- Set
- Set
- Set
- Return

Let us define the function . This function takes, as input, the index of a monomial inside a polynomial ordered by ''inverse lexical order'' and gives, as output, the index of the same monomial but, this time, placed inside a polynomial ordered ''by degree''. In other words, This function makes the

We can now define an algorithm which computes the value of a multivariate polynomial ordered by degree by multivariate horner scheme:

**Declaration**

: dimension of the space

: number of monomial inside a polynomial of dimension and degree .

: registers for summation ()

: counters ()

: the coefficients of the polynomial ordered by degree.**Initialization**

Set

set**For**- Determine
- Set
- Set
- Set
- Set

**Return**