Interpolation en 3D

[RoBeRTo-BeNDeR]

Bonjour,

je cherche depuis peu des choses sur les interpolations de points par des polynômes. Par exemple ayant trouvé par moi même celle en 2D de Lagrange j'ai cherché pour la 3D une méthode, mais en 3D tout ce complique car si l'on choisit un polynôme à deux indéterminées alors l'interpolation est en générale pas unique.

Soit un ensemble A de points que l'on range sous cette forme :


On peut donc interpoler ces points par un polynômes que je dirai prédominant en X car le rôle joué par X et Y n'y est pas en général unique (c'est à dire que si l'on fait la méthode prédominante en Y on ne trouvera pas le même polynôme):



Et à priori l'interpolation est unique si l'ensemble des points projeté sur xOy forme un "quadrillage", je m'explique c'est à dire que pour tout il y a n et pour tout il y a n ce qui "symétrise" la distribution.

Ai-je bien conjecturé ou quelqu'un aurait un contre argument ?

Et y aurait t'il un nom pour deux polynômes tel que l'un décrive les composantes de l'autre? C'est à dire si et Q soit tel que pour

Dans le cas de symétrie j'ai tenté de l'appliquer aux matrices mais hormis que c'est une bijection... j'y vois peu d'intérêt mis à part "différencier" et "intégrer" ces polynômes, et étudier les matrices résultantes, si quelqu'un y trouverai un quelconque intérêt autre qu'il me le dise. Par ailleurs la formule devrait se simplifier sous cette forme pour les matrices :




Si quelqu'un trouverai quelque chose sur ce sujet ce serait fort aimable à lui de me le soumettre car je tourne en rond dessus.
(Ou même sur l'interpolation en dimension 2)
Car hormis l'utiliser pour trouver des suites de matrices ayant même déterminant mais divergentes fortement je n'en ai eu encore aucune utilité. On peut certes approximer une fonction de R² par ce procédé mais comme tout approximation polynomiale, elle reste souvent utile et proche uniquement dans le pavé d'interpolation. Merci pour toute réponse

RoBeRTo
-----

[KerLannais]

Bonjour,

Oui l'interpolation 2D et 3D sont bien connues puisque c'est la base des calculateur à éléments finis tels que comsol ou freefem++ ou ... Il est effectivement pas facile de trouver un bon cours d'interpolation sur internet (enfin en tout cas j'ai rien trouvé de satisfaisant) mais tous les livres qui parlent de la méthode des éléments finis de façon suffisamment pratique pour se poser la question de leur implémentation en parle. Il y aurait pas mal de chose à dire sur le sujet je crois et comme je n'ai pas l'intention de taper une réponse de 6 pages je vais me contenter de remarques générales, j'espère que cela pourra t'éclairer. Dans tout ce qui suit je vais me placer en 2D, puisque quand on comprends les subtilités qui apparaissent en dimension 2 on comprends celles qui se produisent lorsque l'on passe à une dimension strictement supérieure à 1.

Première remarque : Avant de commencer à faire de l'interpolation il faut bien sûr se poser la question : pour un nombre de points donné quel degré de polynôme choisir au minimum ? ou inversement : pour un degré de polynôme donné combien de point d'interpolation peut on avoir au maximum ? Si on ne le fait pas on peut soit tomber sur des impossibilité s'il y a trop de point pour un degré donné, soit sur une non unicité de fonction interpolatrice s'il le nombre de point n'est pas assez élevé pour le degré en question. Ne surtout pas croire que le nombre de point nécessaire en dimension n est égal au nombre de point en dimension 1 à la puissance n. C'est totalement faux et forcément si on pense ça alors on se casse un peu les dents Exemple pour le degré 1 en dimension 2, quand on réfléchi bien il s'agit de fonctions affines de la forme

dont les images sont donc des plans (en dimension 1 ce sont des droites) un plan est uniquement déterminé par trois points (non alignés) et donc que le bon nombre de point est 3 et non pas 4.

Deuxième remarque : On voit dans l'exemple précédent que les points ne peuvent être choisi n'importe comment (dans l'exemple il faut que les points soient non alignés). Si les points sont en position "pathologique" alors on s'en sort avec du degré supérieur mais il n'y a plus unicité. La détermination des ensembles de points pathologique n'est pas sympathique, pour le degré 1 ça va, les points ne doivent pas être alignés, en degré 2 ils ne doivent pas être alignés sur des coniques et en degré supérieur ils ne doivent pas être alignés sur des courbes algébriques de degré supérieur. Sans parler de ce qui se passe en dimension supérieur ou il s'agit alors de surfaces ou d'hypersurfaces algébriques. Le plus simple est de se donner un système de points non pathologique et l'on sait alors que toutes les déformations de ce système de point par des transformations affines sont non pathologiques puisque une déformation affine d'un polynôme reste un polynôme. Il y a par ailleurs des façon de choisir des points d'interpolation pour faire de l'intégration numérique en optimisant la position des points pour avoir un résultat le plus précis possible (L'équivalent des méthodes de Gauss-Legendre et ... en dimension supérieure).

Pour répondre à ces remarques raisonnons de façon générale. Soit et deux ensembles, , un ensemble fini de points de et un ensemble de fonction de dans . On dira que résout le problème d'interpolation en les points si pour tout fonction de dans il existe une fonction de qui coïncide avec sur les . On dira que résout le problème d'interpolation de façon unique si la fonction est unique.

Le principe d'interpolation de Lagrange est le suivant. Mettons que soit un corps même si au point où on en est un anneau suffirait (de toute façon en général ) alors un condition nécessaire pour que résolve le problème est que pour chaque compris entre et il existe une fonction qui vaut en et sur les autres (c'est une condition très général puisque elle est valable dès que l'ensemble contient deux éléments notés et et est forcément satisfaite dès que résout le problème d'interpolation pas nécessairement de façon unique). Il est facile de voir alors que si l'on prend une fonction de dans alors la fonction définie par

coïncide avec (c'est que l'on a besoin du fait que soit un anneau si on veut additionner et multiplier ses éléments et donner un sens à la définition de , on utilise pas tous les axiomes de la définition d'anneau, juste le fait que l'on ai deux loi et de neutres respectifs et )
Ainsi, la condition nécessaire est suffisante si appartient à et donc si est contient toutes les combinaisons linéaires des . Il suffit que soit stable par combinaisons linéaires et donc est alors un sous--module (si est un anneau) ou un sous--espace vectoriel (si est un corps) puisque il est bien entendu non vide et que l'ensemble des fonctions de dans est alors naturellement un -module ou un -espace vectoriel. Je vais maintenant utiliser l'hypothèse que est un corps pour pouvoir parler de dimension (c'est tout de suite moins pratique de travailler dans des modules). Il est clair que la famille des est une famille libre puisque si

est une relation de dépendance linéaire alors il suffit de l'évaluer en les pour conclure que chacun des est nul. Ainsi, doit être de dimension au moins avec le nombre de points d'interpolation. Si l'on veut que résolve de façon unique le problème d'interpolation alors il faut que ne contienne pas d'autres fonctions que les combinaisons linéaires des et est alors l'espace engendré par cette famille qui en est donc une base, sa dimension est donc exactement le nombre de points . Le fait que résolve le problème de façon unique résulte alors simplement de la décomposition unique d'un vecteur dans une base d'un espace vectoriel. Cette condition est naturel.

Dans ton cas et les ensembles de polynômes avec un degré maximal donné sont des espace vectoriels. Pour résoudre de façon unique le problème d'interpolation il faut donc que
1- le nombre de points soit égal à la dimension de ton espace de polynôme
2- la répartition des points ne soit pas pathologique au sens où tu peut trouver des fonction

avant de continuer, un petit exercice pour toi
Quel est la dimension de l'espace des polynômes de degré au plus à variables?

un indication: ce n'est pas

[RoBeRTo-BeNDeR]

Merci pour cette réponse complète.

Pour ton exercice je répondrais ce soir (sachant que je ne rentre pas avant 00h, j'ai ma petite idée quand même) juste pour précision X^n*Y^m est de degré n+m ou max(n,m), je dirai n+m.

Pourrais tu m'expliquer pour les coniques en dimension 3 car là je ne vois pas, privilégiant xOy je dirais que les car pathologiques sont lorsque des point ont même abcisse et même ordonnées.

Merci, RoBeRTo

[KerLannais]

Re

Oui, le degré c'est bien . Déterminer les ensembles de points pathologiques me semble pas évident et pas très utile. En fait j'aurais tendance à penser que lorsque l'on prends des points au hasard on a une probabilité nulle de tomber sur un cas pathologique. En tout cas il y a une méthode simple pour construire de façon générique suffisamment d'ensembles de points non pathologique pour convenir à toute utilisation pratique. D'ailleurs dans ton premier message tu as des intuitions correctes et tu t'approchais de cette méthode, c'est juste que tu considères trop de points d'interpolation. Ne t'inquiète pas je peux te parler de cette méthode mais chaque chose en son temps et puis ça te donnerait la solution de l'exercice par la même occasion ce ne serait pas drole

Pour ce qui est des ensembles pathologiques de points je ne connaîs pas la réponse et je ne sais pas s'ils ont été caractérisés. Pour le degré 2 en dimension 2, ont peut interpoler en 6 points sauf si ces 6 points sont sur une même conique (une conique est par définition l'ensemble des zéro d'un polynôme de degré 2 à 2 variables, de même qu'une droite est l'ensemble des zéros d'un polynôme de degré 1 à 2 variables) puisqu'alors si on cherche un polynôme qui s'annule en 5 point sur 6, on sait que par cinq points il ne passe qu'une et une seule conique et donc l'ensemble des zéros de qui est une conique est forcément cette conique qui contient les six points et il s'annule forcément au sixième point. Exemple on considère six points sur le cercle de rayon 1 et centré en zéro, les points de coordonnées

Tu prends un polynôme de degré deux générique

En injectant les coordonnées des 6 points tu obtient un système à 6 équations et 6 inconnues (les six coefficients), je te laisse t'amuser à résoudre, on doit trouver



avec les 5 équations dont le second membre est nul et en déduire que le polynôme P s'annule sur le cercle tout entier. (en espèrant que je me trompe pas j'ai eu la flemme de vérifier mais il me semble que c'est correct)

Enfin j'espère que cet exemple peut te convaincre que la situation n'est pas simple

[A voir en vidéo sur Futura]

[RoBeRTo-BeNDeR]

oui il me convient bien
Bon çà fait 5 fois que je recommence pour la dimension de l'espace... je t'avoue je m'y perd... je ne suis pas un pro du dénombrement , j'ai cru avoir réussi mais il me manqué les triples les quadruples etc produits.

je dirai donc une truc cool sous la forme de 2 sommes imbriquées l'un dans l'autre l'une pour la vième variable et l'autre pour compter les simple produits, double, triple etc jusqu'au min(d,v) youpi!

Je t'avoue j'ai trouvé dim(1,1)=2 donc avec une variable et de degré
1. Je plaisante, bien plus. pourrais tu me donner ta solution bien expliquée çà ne me fera pas de mal de revoir n peu le dénombrement.

[KerLannais]

D'accord,

Commençons par le cas de la 2D. Il est intuitif que la dimension d'un espace vectoriel est le nombre de paramètres qui permettent de définir un vecteur, et dans le cas des polynômes il s'agit du nombre de leurs coefficients. La preuve est simple, un polynôme de degré est par définition une combinaison linéaire de monômes unitaires de degré inférieur ou égal à (d'où le nom polynôme) et la famille des monômes unitaires est d'évidence libre puisque un polynôme n'est nul que lorsque chacun de ses coefficients est nul de sorte que, toute relation de dépendance linéaire, puisqu'elle se traduit par la nullité d'un polynôme, est forcément triviale. Dans le cadre où on travaille on peut identifier allégrement polynômes et fonctions polynomiale. La question est donc de compter les monômes

En dimension , pour le degré

la dimension est , il faut donc points d'interpolation.

En dimension , pour le degré



...




On voit qu'il s'agit des nombres triangulaires

Il comprend alors que, en notant le nombre de monômes unitaires de degré au plus en variables alors

où dans ce cas est la puissance de la ème variable dans le monômes qui peut prendre toutes les valeurs de à le reste du monôme étant alors un monôme de degré au plus à variables.
Cette somme peut se réécrire

par le changement d'indice . On a bien entendu (il y a un monôme unitaire sans variable c'est ) et égale (il n'y a qu'un seul monôme unitaire constant quel que soit le nombre de variables c'est encore une fois )
A l'aide de cette formule je te laisse vérifier que

On a donc tendance à conjecturer que

Montrons par récurrence sur que

Pour on a

en supposant le résultat vrai pour on a






(où on pose )

Soit


d'où l'hérédité. On peut alors montrer la conjecture par récurrence
Pour

et

D'où le résultat


La méthode d'interpolation en 2d est donc basée sur des triangles et non des carrés, de même qu'en 3d on utilise des tétraèdres et non des cubes.

[KerLannais]

Cela dit je suis en train de me rendre compte que en utilisant la définition du degré comme un max de degrés plutôt qu'une somme alors le nombre de points d'interpolation est bien
en prenant , ... , des réels deux à deux distincts on a

qui est un ensemble de points non pathologique et on peut prendre

Ce qui permet de faire de l'interpolation en dimension sur un hypercube sans se casser la tête

La méthode que j'ai vu et que je t'ai suggéré est par contre bien utile pour intégrer numériquement des fonctions à deux variables sur un certain domaine. Il est facile de trianguler (plus que de quadranguler un domaine) un domaine de façon régulière, on peut alors interpoler par des fonctions polynomiales par morceaux (polynomiales sur chaque triangle).

Mais bon tout dépends de ce que tu veux faire ensuite.

[RoBeRTo-BeNDeR]

bien plus que necessaire mais c'est sympa.
je cherchai juste à comprendre un peu plus que mon interpolation 3D sur un quadrillage pour qu'elle soit unique.

Merci pour toutes ces explications si tu sa des liens a me passer ne te gène pas ^^