Sur une généralisation de l’interpolation de Newton

Olivier Ruatta

26 mars 2003

1 Introduction

Dans ce document, nous traitons des problèmes d’interpolation polynomiaux multivariés. Dans toute la suite du texte, R = 𝕂[x_{1}, …, x_{n}] est l’anneau des polynômes en n variables, Z = {ζ_{1}, …, ζ_{d}} ⊂ 𝕂^{n} un ensemble de points et E = {α_{1}, …, α_{n}} ⊂ ℕ^{n} un ensemble de multi-indices. On note x^{E} = {x^{α}|α ∈ E} et R_{E} le 𝕂-espace vectoriel engendré par l’ensemble de monomes x^{E}. On suppose que E est connexe à 1, c’est-à-dire qu’on peut passer de 1 à tout monome de x^{E} est restant dans x^{E} par multiplication une suite de multiplications par des variables. Avec ces notation, le problème d’interpolation auquel nous nous intéressons se formule comme suit :

Problme 1 Soit v = (v_{1}, …, v_{d}) ∈ 𝕂^{d}, existe-t-il un polynôme f ∈ R_{E} tel que f(ζ_{i}) = v_{i} pour tout i ∈ {1, …, d}.

Nous proposons une approche à se problème qui construit explicitement le polynôme f, c’est-à-dire qui résout le problème suivant :

Problme 2 Si la réponse au problème 1 est positive, donner explicitement un (le) polynôme f.

Les analogues univariés de ces deux problèmes. L’analogue de Z est alors un ensemble de valeurs {z_{1}, …, z_{d}} et l’analogue de R_{E} est 𝕂[x]_{d}, l’ensemble des polynômes de degré strictement inférieur à d. Dans ce cas, le problème 1 univarié admet une solution si et seulement si le déterminant de Vandermonde suivant :

| \begin{matrix}1 & 1 & … & 1 \\ z_{1} & z_{2} & … & z_{d} \\ ⋮ & ⋮ & ... & ⋮ \\ z_{1}^{d−1} & z_{2}^{d−1} & … & z_{d}^{d−1} \end{matrix} |

est non nul. La solution du problème 2 est alors unique est elle est donnée par des schémas d’interpolation comme celui de Lagrange ou celui de Newton. Dans la suite de ce document, nous présentons une extension de ces résultats dans le cas multivarié de dimension 0 (c’est-à-dire que l’ensemble des points d’interpolation est fini). Notre cadre de travail est issue d’une interprétation algébrique est à ce titre, nous commençons par présenter rapidement ce cadre. Dans une deuxième partie nous présentons les réponses aux problèmes qui nous intéresse en terme d’interpolation de Lagrange qui est la plus naturelle dans ce cadre. Nous introduisons dans une troisième partie un schéma d’interpolation généralisant l’interpolation de Newton. Nous finissons par discuter de l’extension de certaines propriétés de l’interpolation de Newton univarié dans le cadre que nous aurons préalablement introduit.

2 Cadre algébrique

Le cadre dans le lequel nous nous plaçons est celui de la géométrie algébrique effective en dimension 0. Soient f_{1}, …, f_{m} ∈ R (m > n) des polynômes, on note (f_{1}, …, f_{m}) = I ⊂ R l’idéal engendré par ces polynômes. On suppose que Z_{I} = {ζ ∈ 𝕂^{n}|p(ζ) = 0, ∀p ∈ I} ∈ 𝕂^{n} est un ensemble fini {ζ_{1}, …, ζ_{d}} et de plus on suppose que toutes les racines sont simples, i.e. ζ_{i} ≠ ζ_{j} si i ≠ j ∈ {1, …, d}. On note A = R/I la 𝕂-algèbre quotient de R par l’idéal I. Le résultat suivant est un théorème classique de géométrie algébrique :

Thorme 1 Si I définit un ensemble de racines simples {ζ_{1}, …, ζ_{d}}, alors A est un 𝕂-espace vectoriel de dimension fini d.

Dfinition 1 Pour tout p ∈ A, on a un application linéaire M_{p} : \{ \begin{matrix}A → A \\ f ↦ p ∗ f \end{matrix} .

On a alors le théorème suivant :

Thorme 2 Sous les même hypothèses que le théorème 1, pour tout p ∈ A, les valeurs propres de l’application linéaire M_{p} sont p(ζ_{1}), …, p(ζ_{d}).

Proposition 1 Il existe une famille de polynômes de A, {e_{1}, …, e_{d}} ⊂ A formant une base de A comme 𝕂-espace vectoriel, appelée système fondamentale d’idempotents vérifiant les conditions suivantes :

• e_{i}(ζ_{j}) = δ_{i,j}, où δ_{i,j} est le symbole de Kroneker, pour tout i, j ∈ {1, …, d},

• e_{i} ∗ e_{j} = δ_{i,j}e_{i} = δ_{i,j}e_{j}, pour touti et j ∈ {1, …, d},

• ∑_{i=1}^{d} e_{i} = 1 ∈ A. Le polynôme e_{i} est appelé idempotent associé à ζ_{i}.

Remarque 1 Les idempotents forment une partition de l’unité de l’anneau des fonctions sur Z. L’analogie avec l’analyse ne s’arrête pas là, bien que je la développerai pas plus dans ce document.

On a le théorème suivant :

Thorme 3 Pour tout p ∈ A, on a p(x) = ∑_{i=1}^{d} p(ζ_{i})e_{i}(x).

Autrement dit, les formes linéaires 1_{ζ_{i}} : \{ \begin{matrix}A → 𝕂 \\ p ↦ p(ζ_{i}) \end{matrix} est une base de l’es-

pace vectoriel dual de A et dans le système fondamentale d’idempotents est la base de A dans laquelle les matrices de multiplication par un polynômes sont diagonales. C’est de dernier théorème, connu sous le nom de théorème de Cauchy qui nous permettra de développer notre approche. Le premier objectif que nous cherchons à atteindre est de trouver un bon ”espace de représentation” de A. En fait il en existe plusieurs en général. La réduction par rapport à une base de Gröbner de l’idéal I nous dit qu’il existe E ∈ ℕ^{n} de cardinal d et connexe à 1 tel que x^{E} soit une base de A. Une telle base base est appelée base monomiale de A. On peut remarquer que toutes les bases monomiales ne s’obtiennent pas de cette façon.

Le problème 1 se reformule en termes algébriques de la façon suivante : soit Z ⊂ 𝕂^{n} un ensemble de d points distincts {ζ_{1}, …, ζ_{d}}, et soit E ∈ ℕ^{n} un ensemble de multi-indice de cardinal d, x^{E} est-il une base monomiale de Z vu comme ensemble algébrique, ou encore R_{E} est-il une réalisation (une représentation) de l’anneau des coordonnées de Z pris comme ensemble algébrique. C’est le premier objectif de la section suivante.

3 Interpolation de Lagrange multivariée

Note 1 Dans toute la suite du document, si on considère un ensemble de points distincts Z = {ζ_{1}, …, ζ_{d}} ⊂ 𝕂^{n}, on note A_{Z} l’anneau des coordonnées de Z, i.e. si I(Z) est l’idéal des fonctions qui s’annulent pour tous les points de Z, on a A_{Z} = R/I(Z).

Dans le cas univarié, les polynômes de Lagrange sont les idempotents de l’algèbre des coordonnées. Dans cette section nous présentons la généralisation du déterminant de Vandremonde qui nous permettra de donner des formules explicites pour les idempotent de l’algèbre des coordonnées comme dans le cas univarié.

Dfinition 2 Avec le notations et les hypothèses utilisées ci-dessus, on définit la matrice de Vandermonde associé à un ensemble Z et un ensemble de multiindices comme suit :

V_{Z,E} = ( \begin{matrix}ζ_{1}^{α_{1}} & … & ζ_{1}^{α_{d}} \\ ⋮ & ... & ⋮ \\ ζ_{d}^{α_{1}} & … & ζ_{d}^{α_{d}} \end{matrix} )

le déterminant de Vandermonde est alors définit comme v_{Z,E} = det(V_{Z,E}).

Remarque 2 On remarque que la définition précédente est exactement celle de la matrice et du déterminant de Vandermonde classique s’il n’y a qu’une seule variable.

Proposition 2 Soit Z un ensemble de points distincts et E un ensemble de multi-indices, alors x^{E} est une base monomiale de l’anneau des coordonnées A_{Z} de Z si et seulement si le déterminant de Vandermonde v_{Z,E} est non nul.

Dmonstration On sait que A_{Z} est un espace vectoriel de dimension d, de plus les évaluations aux racines 1_{ζ_{i}} forment une base du duale de A_{Z} duale de la base des idempotents (formule de Cauchy), la matrice V_{Z,E} est donc la matrice matrices dont les lignes sont les coordonnées des monomes de x^{E} dans la base des idempotents. Donc si cette matrice est inversible, alors x^{E} forme une base de A_{Z} et V_{Z,E} est la transposée de la matrice de changement de bases allant de la base des monomes dans la base des idempotents. □

Remarque 3 L’interprétation de R_{E} comme espace de représentation de A_{Z} est particulièrement intéressante est elle peut mener à des développement intéressant : la théorie des systèmes de formes normales.

Dfinition 3 Soient Z un ensemble de points distincts et E un ensemble de multi-indice tel que v_{Z,E} ≠ 0, on définit alors, pour tout i ∈ {1, …, d}, le polynôme suivant :

e_{ζ_{i}}(x) = (−1)^{δ_{1,i}+1} | \begin{matrix}x^{α_{1}} & ⋯ & x^{α_{d}} \\ ζ_{1}^{α_{1}} & ⋯ & ζ_{1}^{α_{d}} \\ ⋮ & & ⋮ \\ ζ_{i−1}^{α_{1}} & ⋯ & ζ_{i−1}^{α_{d}} \\ ζ_{i+1}^{α_{1}} & ⋯ & ζ_{i+1}^{α_{d}} \\ ⋮ & & ⋮ \\ ζ_{d}^{α_{1}} & ⋯ & ζ_{d}^{α_{d}} \end{matrix} | /v_{Z,E}.  (1)

Proposition 3 Soient Z un ensemble de points distincts et E un ensemble de multi-indice tel que v_{Z,E} ≠ 0, on a alors e_{ζ_{i}} qui est l’idempotent associé à ζ_{i}, en d’autres termes, pour tout i ∈ {1, …, d}, on a e_{ζ_{i}} = e_{i} dans A_{Z}.

Dmonstration Il suffit de constater que ces polynômes vérifient la caractérisation des idempotents, i.e. e_{ζ_{i}}(ζ_{j}) = δ_{i,j} pour tout i et j ∈ {1, …, d}. □

Remarque 4 Ces polynômes sont une généralisation des polynômes de Lagrange, d’ailleurs leur spécialisation dans le cas univarié redonne bien les polynômes de Lagrange classiques.

En corollaire de la formule de Cauchy, on obtient le théorème suivant qui résout le problème 2 explicitement si on connaît une base monomiale de A_{Z} :

Thorme 4 Soient Z un ensemble de points distincts et E un ensemble de multiindice tel que v_{Z,E} ≠ 0 et soit v = (v_{1}, …, v_{d}) ∈ 𝕂^{d}, alors la solution (unique) au problème 2 est donné par :

f(x) = ∑_{i=1}^{d} v_{i}e_{i}(x).  (2)

C’est la généralisation que nous proposons pour le schéma d’interpolation de Lagrange. Encore une fois on retrouve bien le schéma classique si on ne considère qu’une seule variable.

4 Base de Newton multivariée

On considère Z = {ζ_{1}, …, ζ_{d}} ⊂ 𝕂^{n} et suppose qu’on connaît E = {α_{1}, …, α_{d}} ⊂ ℕ^{n} tel que x^{E} = {x^{α}|α ∈ E} est une base monomiale de A_{Z} = 𝕂[x]/I(Z). On suppose de plus que x^{α_{1}} = 1, i.e. α_{1} = 0 ∈ ℕ^{n}. Pour tout j ∈ {1, …, d}, on considère :

N_{j}(x) = | \begin{matrix}x^{α_{1}} & x^{α_{2}} & ⋯ & x^{α_{j}} \\ ζ_{1}^{α_{1}} & ζ_{1}^{α_{2}} & ⋯ & ζ_{1}^{α_{j}} \\ ⋮ & ⋮ & & ⋮ \\ ζ_{j−1}^{α_{1}} & ζ_{j−1}^{α_{2}} & ⋯ & ζ_{j−1}^{α_{j}} \end{matrix} |  (3)

on vérifie facilement que N_{1}(x) = 1.

Note 2 On suppose que pour tout i ∈ {1, …, d}, N_{i}(ζ_{i}) ≠ 0.

Thorme 5 La famille (N_{j})_{j∈{1,...,d}} forme une base de A_{Z}. Cette base est appelé base de Newton.

Remarque 5 On l’appel base de Newton car la spécialisation au cas univarié redonne la base des polynômes de Newton habituelle.

Avant de démontrer ce théorème nous allons montrer le lemme suivant :

Lemme 1 Soit j ∈ {2, …, d}, alors pour tout i ∈ {1, …, j}, on a N_{j}(ζ_{i}) = 0.

Dmonstration Pour tout i < j, on a :

N j(ζ_{i}) = | \begin{matrix}ζ_{i}^{α_{1}} & ⋯ & ζ_{i}^{α_{j}} \\ ζ_{1}^{α_{1}} & ⋯ & ζ_{1}^{α_{j}} \\ ⋮ & & ⋮ \\ ζ_{i}^{α_{1}} & ⋯ & ζ_{i}^{α_{j}} \\ ⋮ & & ⋮ \\ ζ_{j−1}^{α_{1}} & ⋯ & ζ_{j−1}^{α_{j}} \end{matrix} |

sous cette forme on remarque que la première ligne et la i-ème ligne sont identiques, d’où le lemme.

□

Dmonstration (du théorème) Les évaluations aux racines forment une base du dual Â_{Z} de A_{Z} qui est duale de la base des idempotents, ainsi la matrice

H(Z, E) = ( \begin{matrix}N_{1}(ζ_{1}) & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ N_{1}(ζ_{d}) & ⋯ & N_{d}(ζ_{d}) \end{matrix} )

est inversible, puisque c’est une matrice triangulaire dont les coefficients diagonaux sont non nuls d’après le lemme 3. C’est donc une matrice de changement de bases, c’est la transposée de la matrice de passage de la base de Newton dans la base de Lagrange. □

Corollaire 1 Tout polynôme p ∈ A_{Z} s’écrit sous la forme p(x) = ∑_{i=1}^{d} c_{j}N_{i}(x) et on a c_{1} = p(ζ_{1}).

Dans la preuve du théorème, on a vu que H(Z, E) est la matrice de passage de la base de Newton dans la base des idempotents. On obtient immédiatement la proposition suivante :

Proposition 4 Les coefficients c_{1}, …, c_{d} sont les coordonnées de la solution du système linéaire suivant :

H(Z, E) ( c_{1} ; ⋮ ; c_{d} ) = ( p(ζ_{1}) ; ⋮ ; p(ζ_{d}) ) .  (4)

Dmonstration C’est immédiat en remarquant que les p(ζ_{i}) sont les coordonnées de p dans la base des idempotents. □

Cette proposition permet déjà d’avoir un algorithme pour calculer les coefficients d’un polynôme dans la base Newton. La complexité de cette algorithme est d’ailleurs acceptable (O(d^{2}) une fois toutes les expressions évalué) puisque la matrice de changement de base est triangulaire.

5 Calcul des coefficients dans la base de Newton

Dans cette section ont fait un peu de prospective. Elle concerne le calcul des coefficients dans la base de Newton. Dans le cas univarié, l’algorithme le plus utilisé pour le calcul de ces coefficients est basé sur le lemme d’Aitken (ces sous cette dénomination que je l’ai trouvé le plus souvent dans la littérature, mais je ne sais pas si c’est justifié) qui exprime ces coefficients en termes de différences divisées. Nous donnons ici un calcul qui illustre notre propos à partir de la matrice H(Z, E) dans le cas univarié. Nous commençons néanmoins par faire le calcul avec un formalisme qui reste valable pour le cas multivarié. Puis nous reviendrons sur une question ouverte au sujet de ce calcul.

5.1 Un calcul communs aux cas univarié et multivarié

On considère un ensemble de points points distincts Z = {ζ_{1}, …, ζ_{d}} ⊂ 𝕂^{n}, on suppose qu’on connaît un ensemble de multi-indice E = {α_{1}, …, α_{d}} ⊂ ℕ^{n} connexe à 1 et tel que x^{E} soit une base de l’anneau des coordonnées de Z. On suppose de plus que pour tout i ∈ {1, …, d}, N_{i}(ζ_{i}) ≠ 0. 0n note (c_{1}, …, c_{d}) ∈ 𝕂^{n} le vecteur des coordonnées d’un polynôme f ∈ A_{Z}. Par définition des N_{i}(x) et par la formule (4), on a :

• N_{1}(ζ_{1})c_{1} = f(ζ_{1}), d’où c_{1} = f(ζ_{1}).

• N_{1}(ζ_{2})c_{1} + N_{2}(ζ_{2})c_{2} = f_{2}(ζ_{2}), d’où finalement c_{2} = \frac{f(ζ_{2})−f(ζ_{1})}{N_{2}(ζ_{2})}.

• N_{1}(ζ_{3})c_{1}+N_{2}(ζ_{3})c_{2}+N_{3}(ζ_{3})c_{3} = f(ζ_{3}), d’où c_{3} = \frac{f(ζ_{3})−f(ζ_{1})}{N_{3}(ζ_{3})}−\frac{N_{2}(ζ_{3})}{N_{2}(ζ_{2})N_{3}(ζ_{3})}(f(ζ_{2})− f(ζ_{1})).

• …

C’est formule s’obtiennent simplement en prenant ligne à ligne les égalités correspondant au système (4). Il est assez facile de tirer une récurrence du calcul qui précède. Néanmoins, l’expression obtenue est assez compliquées. Il est assez difficile de voir sous cette forme qu’on va retrouver les différences divisées dans le cas d’une variable. C’est l’objet de ce qui suit.

5.2 Dans le cas univarié

Dans le cas de polynômes d’une variable, les polynômes de Newton sont N_{i}(x) = ∏_{j=1}^{i}(x − ζ_{j}), pour tout i ∈ {1, …, d}. En sachant cela si on reprend les calculs précédents on obtient :

• c_{1} = f(ζ_{1}).

• c_{2} = \frac{f(ζ_{2})−f(ζ_{1})}{N_{2}(ζ_{2})} = \frac{f(ζ_{2})−f(ζ_{1})}{ζ_{2}−ζ_{1}}.

• c_{3} = \frac{f(ζ_{3})−f(ζ_{1})}{N_{3}(ζ_{3})}−\frac{N_{2}(ζ_{3})}{N_{2}(ζ_{2})N_{3}(ζ_{3})}(f(ζ_{2})−f(ζ_{1})) = \frac{1}{ζ_{2}−ζ_{3}} (\frac{f(ζ_{2})−f(ζ_{1})}{ζ_{2}−ζ_{1}}−\frac{f(ζ_{1})−f(ζ_{3})}{ζ_{1}−ζ_{3}}).

• …

Autrement dit on retrouve bien les formules des différences divisées qui sont définies comme suit :

Considérons l’ensemble des points d’interpolation comme un alphabet. On définit les différences divisées ∂_{i} comme des opérateurs sur les fonctions en les variables ζ_{1}, …, ζ_{d} comme suit :

∂_{i} : f → \frac{f − f^{s_{i}}}{ζ_{i} − ζ_{i+1}} , i ∈ \{1, …, d\},

en notant s_{i} la transposition échangeant ζ_{i} et ζ_{i+1}. Si on prend une fonction d’une variable, alors :

f^{∂}, f^{∂∂}, f^{∂∂∂}, …

représentent respectivement :

∂_{1}(f(ζ_{1})), ∂_{2}(∂_{1}(f(ζ_{1}))), ∂_{3}(∂_{2}(∂_{1}(f(ζ_{1})))), …

Avec ces notations, la formule d’interpolation de Lagrange s’écrit :

f(x) = f(ζ_{1})N_{1}(x) + f^{∂}N_{2}(x) + f^{∂∂}N_{3}(x) + ⋯

La question est alors de donner une expression analogue dans le cas multivarié. Une réponse a été donnée par A. Lascoux et M.P. Schützenberger en termes de polynômes de Schubert. Les formule qu’ils donnent sont très élégantes, mais quelle est alors le rapport avec les formules que nous donnons dans le cas multivarié pour les coefficients ?