Condition sur f'(x) pour une interpolation par spline cubiqu

[coqp-ox]

Bonjour, étant donné que ce post est mon premier sur le forum je vais commencer par une courte présentation. Je suis actuellement en école d'ingénieur :zen: et je travaille en ce moment sur un (petit) projet pour une entreprise (une présentation TRES courte).

Une partie du projet consiste à interpoler des points répartis inégalement sur un intervalle. Pour se faire j'ai donc utilisé la méthode des splines cubiques qui marche relativement bien (puisque j'étudie des mouvements "simples" ). Cependant, j'étais parti pour travailler avec des splines naturelles (càd f''(x0)=f''(xn)=0) mais il s'avère que les conditions pour réaliser l'interpolation dont j'ai besoin sont f'(x0)=f'(xn)=0. :mur:

En fait, concrètement, il s'agit d'un moteur qui doit prendre les valeurs de la courbe qui représente la vitesse donc il impératif que la vitesse initiale soit nulle et que la vitesse finale aussi pour que le moteur puisse réaliser un cycle. :dodo:

Donc ma question est la suivante, comment modifier la méthode des splines cubiques pour qu'elle puisse convenir à ces conditions ?

Je m'étais basé sur ce document (très bien expliqué) pour réaliser l'interpolation :
http://asi.insa-rouen.fr/enseignement/siteUV/ananum/11interpol.pdf

Merci d'avance pour votre réflexion.

Edit : En cherchant sur internet j'ai réussi a trouver une methode susceptible de m'aider (page 5, equations 11) le problème étant que je n'arrive pas à repérer quelles sont les autres equations nécessaire...
http://www.giref.ulaval.ca/~afortin/mat17442/documents/splines.pdf

[DamX]

Bonjour et bienvenue à toi,

on a besoin de deux conditions aux bords et on peut prendre ce que l'on veut, comme par exemple ce que tu proposes, des dérivées nulles. Ca complique un tout petit peu mais il n'y a rien de sorcier il faut juste de pas se mélanger. C'est presque la même solution.

Je te lance :

En repartant du cas simplifié de ton premier lien, tu as :

et


si au lieu de prendre m_0 et m_n =0 qui donnent direct l'équation matricielle, tu veux prendre la nullité de la dérivée, ça te donne :

ce qui en injectant dans la première équation te donne :

On a donc récupéré m0 qui ne nous reste plus qu'à injecter dans la deuxième équation :


Tu vois que ça modifie donc très légèrement la première ligne de ta matrice (7/2,1,0,...,0)ainsi que le 1er élément du vecteur colonne.

Et puis il faut faire de même pour l'autre bord g'(x_n) = 0 avec a_n et m_n !

Damien

[Sylviel]

Le cours proposé à l'air bien construit (je ne l'ai que survolé). Les splines cubiques sont effectivement souvent utilisées en interpolation si tu sais que la fonction est "smooth". En effet elles permettent d'avoir une fonction C^1 déterminées avec 1 coeff par point. Avoir f"(x0)=0 ou f'(X0)=0 ne change pas grand chose. Il suffit de suivre pas à pas la démarche pour aboutir à l'équation matricielle.

Attention l'hypothèse derrière l'utilisation d'une spline c'est que la valeur en chaque point est parfaitement connu, ou autrement dit qu'on veut "absolument" que la courbe interpolée y passe.
S'il y a une incertitude sur les points on aura plutôt tendance à préférer une fonction plus globale
(si possible d'une forme issue de la physique du problème) et effectuer une minimisation d'erreur (typiquement une méthode des moindres carrés).

Effectivement la page 5 de ton second lien te donne explicitement les équation utiliser.

P.S : voici un petit site qui réponds un peu à "pourquoi les splines cubiques" plutôt que "des arcs de parabole"

P.P.S : C'est bizarre, mais sur Google Scholar je ne trouve pas de publication de Jean Jacquelin avec des mots comme interpolations estimation ou splines.

[Dlzlogic]

Bonjour Sylviel

P.S : voici un petit site qui réponds un peu à "pourquoi les splines cubiques" plutôt que "des arcs de parabole"

Peux-tu me dire où je peux trouver ce site ?

P.P.S : C'est bizarre, mais sur Google Scholar je ne trouve pas de publication de Jean Jacquelin avec des mots comme interpolations estimation ou splines.

http://www.scribd.com/JJacquelin/documents
Il y a plusieurs documents qui concernent ce sujet.
Jean Jacquelin est un membre assez discret de Math-Forum (pseudo JeanJ). Je pense que le meilleur moyen de savoir pourquoi il n'est pas référencé sur Google Scholar est de lui demander.

[coqp-ox]

Merci pour vos explications. Je suis un peu plus éclairé (même si évidemment il faut que je travaille avec la forme qui n'est pas simplifiée :mur: ).
Quoiqu'il en soit, voila ce que j'obtiens pour mn :

m[SIZE=1]n=-[(yn-yn-1)/hn-1+(hn-1*mn-1)/6]/(hn-1/3)[/SIZE]

Pouvez-vous me dire si vous obtenez la même chose ?

J'ai aussi croisé quelques sites sites qui parlaient de spline encastré, après avoir analysés quelques exemples je me rends compte que cette méthode traduit exactement mon problème cependant le document (.ppt) qu'on m'a fourn iest en anglais donc j'ai un peu de mal (pas pour l'anglais, plus pour les maths en anglais :hum: )

[Dlzlogic]

P.S : voici un petit site qui réponds un peu à "pourquoi les splines cubiques" plutôt que "des arcs de parabole"

Je viens de lire le sujet, je n'ai pas vu où il est dit que les polynômes cubiques sont à préférer aux paraboles.
Très nettement ce sujet évoque une lissage de courbe avec une grande participation de l'opérateur, voire totale.
Que fera-t-il avec des milliers de points et des centaines de courbes ?
Par ailleurs, la parabole a des propriétés intéressantes qui sont particulièrement efficaces en matière de traçage de courbe, avec lissage d'une ligne brisée.
Enfin, dans les dessins présentés, la courbe passe bien loin des points élémentaires.
Ce sujet a déjà été évoqué il y a un bout de temps, mais n'a pas bénéficié d'une discussion.

[DamX]

Merci pour vos explications. Je suis un peu plus éclairé (même si évidemment il faut que je travaille avec la forme qui n'est pas simplifiée :mur: ).
Quoiqu'il en soit, voila ce que j'obtiens pour mn :

m[SIZE=1]n=-[(yn-yn-1)/hn-1+(hn-1*mn-1)/6]/(hn-1/3)[/SIZE]

Pouvez-vous me dire si vous obtenez la même chose ?

J'ai aussi croisé quelques sites sites qui parlaient de spline encastré, après avoir analysés quelques exemples je me rends compte que cette méthode traduit exactement mon problème cependant le document (.ppt) qu'on m'a fourn iest en anglais donc j'ai un peu de mal (pas pour l'anglais, plus pour les maths en anglais :hum: )

Oui c'est bien Ca pour m_n (Meme si on peut le simplifier un poil pour qu'il ait une meilleure tête)
Il ne reste plus ensuite qu'à le remplacer dans l'equation m(n-2)+4m(n-1)+m(n) = f(n-1) pour obtenir la dernière ligne de la matrice ainsi que le dernier élément du vecteur colonne.

A présent tout y est, reste plus qu'à inverser la matrice comme dans ton lien.

En ce qui concerne les splines encastrées, de ce que j'ai vu c'est exactement ce qu'on vient de faire puisque ça correspond aux splines avec conditions aux bords sur la dérivée.


PS :
Je rejoins les autres sur le fait qu'au delà de la calibration, il faille bien réfléchir au préalable sur le problème (valeurs exactes/approchées, réalité physique orientant une fonctionnelle/modélisation, etc) pouvant permettant de peser le pour et le contre des diverses méthodes à disposition.

Toutefois, cette personne venant avec un problème bien défini (ce qui est loin d'être toujours le cas), il conviendrait selon moi de répondre en priorité à sa question, tout en ouvrant si besoin le champ de la réflexion si nécessaire) plutôt que de retomber dans un conflit de personne dont je suis bien trop jeune ici pour en avoir connu la genèse mais qui parfois pollue des sujets et ternis la qualité de ce forum par ailleurs remarquable.


Bonne soirée à tous,
Damien

[Ben314]

... interpoler des points répartis inégalement sur un intervalle...

Attention : ça fait deux post que je vois où apparait la formule "m(n-2)+4m(n-1)+m(n) = f(n-1)" qui n'est valable que dans le cas de points "également répartis" sur l'intervalle.

[DamX]

Attention : ça fait deux post que je vois où apparait la formule "m(n-2)+4m(n-1)+m(n) = f(n-1)" qui n'est valable que dans le cas de points "également répartis" sur l'intervalle.

Oui en effet c'etait pour expliquer la méthode de gerer l'equation aux bords dans le cas simplifié comme dit plus haut. Dans le cas général Ca change le résultat mais pas les substitutions à opérer.

Damien

[coqp-ox]

Bon après un week-end reposant, je dois me remettre dans mes calculs! Donc, voila ce que je trouve pour résumer :

m[SIZE=1]n=3*(yn-yn-1)/hn-1²+mn-1/2[/SIZE]

m[SIZE=1]o=3*(y1-y0)/h0²-m1/2[/SIZE]

Cependant, pour modéliser les fonctions trouvées pour m0=mn=0 j'utilisais excel (avec 5 points) puisqu'on pouvait trouver une formule assez simple pour mi 0<i<n
Pensez-vous qu'il y ait un moyen plus simple pour calculer les mn qu'un tableau excel, je pense à un algorithme du style de celui présent dans le lien que je vous ai fourni mais il ne me semble pas très clair.
Pour l'instant je vais essayer de prendre simplement 3 points et de représenter les courbes que j'obtiens sur excel a nouveau ^^

Merci d'avance et bonne journée!

Edit : Bon j'ai donc essayé en prenant trois points quelconques et leur image suivant une fonction basique (polynomiale), le résultat est plutot concluant, j'ai une vitesse nulle au départ et à la fin, la courbe (même avec 3 points) relativement bien les variations de la fonction.

Maintenant, il faudrait que je trouve un algorithme capable d'effectuer les calculs de m avec une trentaine de points, pensez-vous que cela est possible ? :help:

[DamX]

Bonjour,

La résolution matricielle ne te conviens pas ? A priori excel sait inverser une matrice et peut aller théoriquement jusqu'à une matrice (57*57) (je dis théoriquement parce que je n'ai jamais testé en pratique).

Damien

[coqp-ox]

Je n'ai jamais été très doué en matrice, j'arrive à peine à comprendre les comment l'utiliser dans mon problème alors que j'y travaille depuis un petit moment.

Si c'est possible avec excel je vais essayer de me débrouiller pour pouvoir faire des essais en "conditions réelles" mais cet algorithme doit pouvoir être utilisé par un "programme" afin de transmettre les valeurs au moteur. Autant il est facile pour un utilisateur d'entrer des valeurs sur excel autant, je pense, un programme n'est pas capable de comprendre le langage d'excel, si ?

Je dévie un peu du sujet initial puisque maintenant il s'agit de son application mais j'espère que vous pourrez quand même me venir en aide :ptdr:

Merci d'avance

Edit : Après une petite recherche sur google, je pense avoir trouvé comment résoudre mon système sur excel de facon matricielle.

[Dlzlogic]

Bonjour,
Si la résolution d'un système linéaire de n équation à n inconnues vous pose un problème, je vous donnerai volontiers une fonction en C et/ou la même en PHP.

[coqp-ox]

Bonjour,
Si la résolution d'un système linéaire de n équation à n inconnues vous pose un problème, je vous donnerai volontiers une fonction en C et/ou la même en PHP.

Merci beaucoup pour votre proposition, je ne connais pas encore le langage utilisé "par le moteur" donc je ne vous dérangerai pas pour l'instant, mais s'il s'avère que c'est bien du C alors je reviendrai vers vous !
Pour l'instant je vais deja essayer d'illustrer la solution du problème sur excel.

Merci!

[Sylviel]

Il existe de très nombreuses librairies d'algèbre linéaire (linear algebra) qui ont été développées pour résoudre de manière efficace des systèmes linéaires (et plein d'autres choses). Il est fortement recommandé de les utiliser (plutôt qu'un solveur fait soit même). Reste à savoir le langage utilisé pour commander le robot et trouver bibliothèque adéquate.

[coqp-ox]

Dlzlogic, après une discussion avec le responsable du projet. Il s'avère que l'algorithme doit bien être réalisé en C, cependant le problème possède une petite particularité, serait-il possible de continuer en privé (puisqu'on touche à de la programmation et non à des maths) ?

Merci d'avance de votre réponse.

[leon1789]

...et cela malgré les sages recommandations de Sylviel :ptdr:
Avoir des algorithmes sûrs et efficaces ne relève pas de l'amateurisme. Traiter de l'algèbre linéaire avec Dlzlogic est à vos risque et périls (moult exemples sur ce forum et ailleurs). Let's go and see...

[Ben314]

Même remarque que léon....
Je rajouterais aussi que vu que la matrice à inverser est particulièrement "creuse" (au plus 3 valeurs non nulles par ligne/colonnes), il n'est pas complètement évident qu'un algo. "trés général" de résolution de systèmes linéaires soit le plus adapté dans ce cas là (i.e. on risque de pouvoir se contenter de bibliothèque d'algébre linéaires "trés basiques" qui risquent d'être aussi performantes pour des systèmes aussi "creux")

Je sais que perso, j'aurais peut-être refait un algo spécifique, mais c'est parce que je suis un vieux qui a connu l'époque où la mémoire des ordi était limitée, donc de trimbaler une matrice de 50x50 (=2500 valeur) alors qu'il y en a moins de 150 de non nulles, je continue à avoir du mal et j'aurais plutôt stocké les coeffs dans une matrice 50x3...
Mais bon, les temps ont changés...

[Dlzlogic]

Rien de tel qu'un test numérique.
A vous la main.

[coqp-ox]

Même remarque que léon....
Je rajouterais aussi que vu que la matrice à inverser est particulièrement "creuse" (au plus 3 valeurs non nulles par ligne/colonnes), il n'est pas complètement évident qu'un algo. "trés général" de résolution de systèmes linéaires soit le plus adapté dans ce cas là (i.e. on risque de pouvoir se contenter de bibliothèque d'algébre linéaires "trés basiques" qui risquent d'être aussi performantes pour des systèmes aussi "creux")

Je sais que perso, j'aurais peut-être refait un algo spécifique, mais c'est parce que je suis un vieux qui a connu l'époque où la mémoire des ordi était limitée, donc de trimbaler une matrice de 50x50 (=2500 valeur) alors qu'il y en a moins de 150 de non nulles, je continue à avoir du mal et j'aurais plutôt stocké les coeffs dans une matrice 50x3...
Mais bon, les temps ont changés...

J'ai regardé en diagonal quelques sujets qui traitaient de ces bibliothèques et j'avoue ne pas avoir compris grand chose, je m'y remets de ce pas pour essayer d'en comprendre l'utilisation!

Edit : Après quelques recherches, j'ai plus ou moins compris comment utiliser ces librairies cependant je ne suis pas capable de les intégrer dans un programme en C étant donné que je ne connais que les bases de ce langage (24h de cours :+: ) :/