Discussion :

[User]

Bonjour,

Voila je dispose d'une série de double valeurs (xi, yi)
et je souhaiterai à partir de ces valeurs obtenu expérimentalement obtenir 1 polynôme ou 1 fonction qui me permette de tracer la courbe correspondante pour n'importe quel valeurs de x.

J'ai pensé à une méthode d'interpolation mais je n'arrive pas à trouver une méthode assez précise...

Alors je sollicite votre aide précieuse

@ +

[Guigui_]

Pour une interpolation, c'est à toi de définir la forme général de ton polynôme (donc le degré) ou de ta fonction

Dans le cas d'un polynôme, une fois que le degré est choisi, ca te fait un système d'équation linéaire du type M équations (le nombre de valeurs expérimentales que tu as) à N inconnus (dépendant du degré du polynôme que tu as choisi)

yi = a(n).xi^n+a(n-1).xi^(n-1)+...+a(1).xi+a(0) ou les (xi, yi) sont les valeurs expérimentales à trouver et les a(j) les paramètres inconnus de ton polynôme à déterminer

Donc pour la résolution comme ce n'est pas un système carré, il faut regarder du côté des matrices pseudo-inverses.
Tu peux regarder ce post: http://www.developpez.net/forums/vie...110&highlight=

[j.p.mignot]

Le problème est trivial avec n'mporte quel algorithme de moindre carré. Bien entendu le nombre de points doit être au moins égal au nombre de paramrètres de modèle à ajuster.
Si on considère un fit polynômial de degré d pour n points ( n >= d+1) , le problème est encore plus simple car si on note P(x) = Somme Ai * x^i (i=0..d) alor prenons comme ecart pour chaque point ( Xa, Ya) a = 1.. N

Ea = Ya - P(Xa)

notons alors R le résidu à minimiser comm R = Somme Ea^2 a= 1..N

on écrit alors d+1 équations correspondant à @R@Ap=0 (p=0..d). Ceci conduit à un système de kramer de D+1 équations à D+1 inconnues. Un tel système se solutionne sans problème ( triangularisation ) d'où la solution au probème ( si Det(M) <> 0 !! si non il y a indetermination dont les origines ont une interprepation géométrique facile ) .

ATTENTION : Un fit polynômiala facilement tendance à osciller et à diverger sérieusement hors des points où il a été ajusté!

Si nécessaire je pourrais joinde du code en C ou Pascal pour résoudre ce problème (polynôme &/ou moindre carré"standard" par approximations succéssives). Il est tout de même à noter qu'1 moindre carré nécessite de partir d'1 jeu de paramètres pas trop "éloignés" de la solution si non il y a risque de divergence ou de se faire trapper dans des minimums locaux qui peuvent être fort loin de la solution réelle.

[User]

Merci pour ces réponses !

Je vais étudier les étudier !

@+

[User]

Pour une interpolation, c'est à toi de définir la forme général de ton polynôme (donc le degré) ou de ta fonction

Excusez moi mais mes connaissances sont assez imprécise sur le sujet:

Questions:

Comment je détermine le degré de mon polynôme
car en fait je n'ai aucune idée de l'allure de ma courbe ou de la forme de mon polinôme a priori (je souhaiterai générer 1 courbe à partir du polynome obtenu pour ensuite la comparé à une fonction connu..)

Existe-t-il 1 algo déja connu (sur developpez ou autre) pour la résolution d'1 système de n équations à n inconnus (système cramer ou autre) dont je pourrais m'inspirer pour programmer... (sinon triangulation: google ?)

N'existe t'il pas déja des méthodes d'interpolation (Newton..)
Quels sont les avantages de vos méthodes (résolution d'1 système) par à ces autres méthodes.

ATTENTION : Un fit polynômiala facilement tendance à osciller et à diverger sérieusement hors des points où il a été ajusté!

C'est justement le problème car je souhaiterai pour faire simple obtenir 1 polynôme à partir de la série de valeurs (xi,yi) i 1..n
Puis tracer la courbe correspondante sur 1 intervalle plus large

ex: x de 0, 0.1 ,0.2,.. 100 ou 0,0.5,1 .. 1000

et là j'ai bien peur que la courbe soit imprécise (oscillation) et ceci quelquesoit la méthode employé

Qu'en dites vous,

et merci encore pour vos contributions

@+

[j.p.mignot]

C'est justement le problème car je souhaiterai pour faire simple obtenir 1 polynôme à partir de la série de valeurs (xi,yi) i 1..n
Puis tracer la courbe correspondante sur 1 intervalle plus large

ex: x de 0, 0.1 ,0.2,.. 100 ou 0,0.5,1 .. 1000

et là j'ai bien peur que la courbe soit imprécise (oscillation) et ceci quelquesoit la méthode employé

Si on veut extrapoller, on DOIT avoit un modèle qui va justifier du fit. Sans modèle, il est impossible de faire une prédiction sur les points à venir.Si le modèle est correct il doit fitter raisonnablement les points déjà connus. Ces points pourraient être entachés de bruit autel cas, il peut être souhaitable d'effectuer un filtrage préalable pour supprimer les composantes fréquentielles non significatives.
A défaut de modèle, si on sait que les points doivent tout de même répondre à une fonction une fois le bruit supprimé on peut alors:
-1- Supposer que la fonction f est suffisament simple pour admettre des dérivées et alors utiliser un fit polynomial qui correspondrait au 1er éléments de sont développement en série de Taylor
2- Limiter au faibles degrés ( je dirais <= 2 ou 3 ) car les dérivées d'ordre plus élevées peuvent devenir très variables.
3- Une telle hypothèse en tout état de cause ne pourra conduire qu'à des prédictions à court terme et devra être réajustée dans le temps dès l'acquisition de nouveaux points de mesure

[diogene]

Si on veut interpoler, la fonction d'interpolation doit passer par les points de la courbe, ce qui exclut une méthode des moindres carré ou tout autre méthode de fit
Guigui_ :

Pour une interpolation, c'est à toi de définir la forme général de ton polynôme (donc le degré) ou de ta fonction

Dans le cas d'un polynôme, une fois que le degré est choisi, ca te fait un système d'équation linéaire du type M équations (le nombre de valeurs expérimentales que tu as) à N inconnus (dépendant du degré du polynôme que tu as choisi)

Dans le cas d'interpolation, ce n'est pas si complexe : utilise le polynome d'interpolation de Lagrange : Si le polynome doit passer par les point (Xi,Yi)

P(x) = Somme sur i ( Yi * Produit pour j#i ( (x-Xj)/(Xi-Xj) ) )

Mais, ceci donne des résultats catastrophiques en dehors de l'intervalle des points. cf remarque de j.p.mignot (et quelquefois des bizarreries entre les points).
Il serait peut être préférable de faire une interpolation plus "locale" avec un degré de polynome plus faible

[j.p.mignot]

FAUX!
On peut trés bien estimer des résultats en tout point à partir de fits. Il est d'ailleur bien souvent assez inopportum "d'interpoller" directement entre les points si ceux-ci sont bruités ( errur de mesure, bruit thermique, incertutude du les f max après FFT, ... )

[diogene]

j.p.mignot :

FAUX!
On peut trés bien estimer des résultats en tout point à partir de fits.

Ce n'est plus de " l'interpolation ". C'est supposer un modèle théorique et essayer de trouver les paramètres les plus probables de ce modèle compte tenu des mesures entachées de bruit compte tenu des caractéristiques statistiques (supposées connues) de ce bruit. C'est un autre problème à la base.

Sans modèle, il est impossible de faire une prédiction sur les points à venir.

Je suis bien d'accord. C'est également vrai d'ailleurs si on veut une interpolation qui justifie les valeurs obtenues et ne soit pas un simple "lissage"

Il est d'ailleur bien souvent assez inopportum "d'interpoller" directement entre les points si ceux-ci sont bruités

Je suis d'accord puisque les points eux-mêmes ne sont pas sûr. Dans le problème présenté (points expérimentaux) une méthode basée sur un fit semble être la meilleure si il dispose d'un modèle justifié théoriquement (sinon, pourquoi un polynome et pas autre chose ?)

[j.p.mignot]

Le fit polynômial peut tout de même se justifier.

Si il existe une loi qui justifie une évolution des points et que cette loi soit développable en série de taylor alors
f(x) = f(x0) + (x-x0) f'(x0) + (x-x0)^2 / 2! f''(x0) + (x-x0)^3/3! f'''(x-x0) + ...
soit
f(x) = A + Bx + Cx^2 + ...

un fit avec un degré de faible valeur ( disons <= 2 ) permet au moins d'accéder à la valeur moyenne, la pente et à la courbure moyenne locale. Ne possédanrt pas tous les termes du développement, il est peut prédictif et doit être réactualiser avec l'apport de nouveaux points.

[diogene]

j.p.mignot :

Si il existe une loi qui justifie une évolution des points et que cette loi soit développable en série de taylor alors
f(x) = f(x0) + (x-x0) f'(x0) + (x-x0)^2 / 2! f''(x0) + (x-x0)^3/3! f'''(x-x0) + ...

Bien sur. Et, comme en général ceci n'est précis qu'au voisinage de x0, ta remarque suivante en découle justement :

un fit avec un degré de faible valeur ....ne possédant pas tous les termes du développement, il est peu prédictif et doit être réactualiser avec l'apport de nouveaux points.

ce qui revient à essayer un developpement d'ordre plus faible au voisinage des points donc à actualiser les coefficients du polynome.
C'est ce que j'entendais en disant

Il serait peut être préférable de faire une interpolation plus "locale" avec un degré de polynome plus faible

C'est sans doute la meilleure méthode en l'absence d'un modèle physique exploitable. Mais, en l'absence de ce modèle, l'extrapolation .....

[j.p.mignot]

Ce n'est pas sur que cela soit LA meilleur méthode. pour avoir les 3 approximations valeur pente et courbure moyenne cela est probable. Mais les fits polynômiaux ne se racordent pas ( ou en des points angulaux) ce qui peut être source de problèmes pour certains calculs exigeant des fonctions de clasee C2, C3 voir même C infini.
Dans ce cas l'approche par spline m'a tres souvent amené de meilleurs stabilités dans les calculs.

[User]

Merci pour tous ces renseignements !

[User]

Bonsoir à tous,

J'ai pu mettre en place les Algos (en vb) pour la résolution d'1 système de n équations à n inconnus (pivot de Gauss)

et l'algo de la méthode d'interpolation de Lagrange:

Et après test sur quelques fonctions

Résultat globale, comme on pouvait si attendre:

Ces deux méthode donne des résultats semblables !!!

Dans l'intervalle des valeurs données les résultats sont assez bon en dehors de cette intervalle (pour de grande valeurs par ex.) les résultats sont mauvais.


Donc mon problème reste entier:
Je peux tracer ma courbe sur l'intervalle des valeurs, mais sinon pas moyen.

En fait je devrais plutot parler d'extrapolation,

merci pour vos informations mais j'ai peut-être pas saisie vos propositions:

j.p.mignot:

On peut trés bien estimer des résultats en tout point à partir de fits. Il est d'ailleur bien souvent assez inopportum "d'interpoller" directement entre les points si ceux-ci sont bruités ( errur de mesure, bruit thermique, incertutude du les f max après FFT, ... )

j.p.mignot:

Si on veut extrapoller, on DOIT avoit un modèle qui va justifier du fit. Sans modèle, il est impossible de faire une prédiction sur les points à venir.Si le modèle est correct il doit fitter raisonnablement les points déjà connus.

Excuse moi j.p.mignot mais je n'ai pas tout pigé:
A priori je ne possède pas de modèle:
Quand bien même: Quand tu parles de modèle, il s'agit bien d'avoir une idée générale de l'allure de la courbe à tracer ou de la fonction...

Mais comment incorporer ce modèle à mon algorythme ???
Ou comment faire en sorte que mon algo prenne en compte ce modèle ???

@+ User

[j.p.mignot]

Si vous avez N points et que vous y faites passer un polynôme de degré N-1, il passera exactement par les N points ( si le système de kramer N X N à un déterminant non nul ) : On l'y force!
Mais alors entre les points il oscille fortement et hors des points il diverge complètement.

En l'absence de tout modèle il est en général préférable de limiter le degré du polynôme à 2 ou 3 et calculer PAR MOINDRE CARRE le "meilleur" plolynôme. Bien entendu il NE PASSERA PAS NECESSAIREMENT pas tous les points mais les coefficients comme Ao,A1,A2 permment d'estimer les valeurs moyenne, pente et courbures dans l'intervalle. Un tel FIT n'est que PEU PREDICTIF et l'utiliser pour prévoir les points hors intervalle peut se réveler douteux!

Pour obtenir un courbe ayant une chance de pouvoir prédir les points suivants, IL FAUT que les points connus répondent à un modèle y=f(x). Peut importe la fonction f (qui doit tout de même être dérivable ) mais elle doit être connue comme polynôme de degré donné, exp, erf, trigo, ... et peut avoir un certain nombre de paramètres comme une constante de temps dans y(t)=A*exp(-t/TAU)+B ou phase et fréquence comme y(t)=A*cos(t/T+phi)+B, Offet, amplification, ...

Connaissant le'propotype de fonction', on ajuste par MOINDRE CARRE la valeur du/des paramètre(s) pour que la fonction passe au mieux parmis les N points expérimentaux. ( Il est bien entendu NECESSAIRE que N soit >= nombre de paramètre(s) à ajuster. de plus une convergeance necessite de connaitre une valeur approximative des paramètres pour eviter une divergeance du moindre carrés). Suivant le cas on peut aussi filtrer les données avant le fit moindre carrés pour eviter d'y introduire des composantes fréquencielles non significatives.

Un algorithme se passe alors comme suit

a- Acquisition de N couples ( Xi, Yi)
b- Filtre (Xi, Yi) --> (X'i, Y'i) <optionnel>
c- Définition des valeurs initiales A1, ...Ap ( p <=N) du modèle à partir des couples(Xi, Yi) ou (X'i,Y'i).
d- Affinement de Aj j=1..p par une méthode de moindres carrés. ( on doit en général limiter le nombre d'itération et les seuils de convergences à atteindre)
e- Vérification que le fit est acceptable ( écarts entres points observés et fit < tolérance que l'on veut atteindre). Si quelques points sont manifestement mals atteints par le modèle, que le modèle passe correctement par tous les autres et que l'on a une raison de croire qu'ils puissent être douteux, les supprimer et retourner au point b.
f- Maintenant la fonction f ainsi ajustée à un aspect prédictif et peut être utilisés (dans une certaine mesure ) en lieu et place des points experimentaux.

[User]

Bonjour,

D'abord merci beaucoup j.p.mignot pour toutes des infos,
qui montre bien que tu maitrise le sujet !

Mais j'ai quelques problèmes pour la méthode des moindres Carrés:
(Je comprends vite mais faut m'expliquer longtemps lol)

si j'ai une idée de ma fonction (modèle) disons: f(x)=a*Exp(-bx)

Je cherche donc a et b tels que:

S=Somme( (yi-f(xi))^2 ) (i 1..n) soit minimum

Soit:

S(a,b)=Somme( (yi-a*Exp(-bxi))^2 ) (i 1..n) soit minimum

donc on doit avoir:

d(S(a,b))/da = 0 (dérivée de S par rapport à a)

d(S(a,b))/db = 0 (dérivée de S par rapport à b)

Donc la dérivation c'est 1 travail qui doit être fait à la main,

Comment puis-je faire pour simplifier et résoudre ce système de façon algorythmique.

Existe t'il une formule générale, compréhensible par l'ordi applicable quelque soit la fonction f .

En gros comment (connaissant f) puis-je résoudre le système:

d(S(a,b))/da = 0
d(S(a,b))/db = 0

de façon algorythmique ...

(si f est 1 polynôme de degré p < N il doit y avoir 1 moyen...)

Je sais tu m'as donné la démarche général (qui m'est bien utile) mais comment puis-je automatiser cette méthode (moindre carré) au niveau algorythmique..

Merci encore

@+ User

[j.p.mignot]

Il existe quelques cas où il est possible de ramener le moindre carré à un calcul "one shot" pour avoir les paramètres comme pour le fit polynômial dont j'ai brièvement parrelé l'approche dans 1 précedant message. Quelques autres cas s'y ramènent moyenant des changements de variables + ou - tordus. C'est le cas par exemple du fit des paramètres de maille en diffraction X pour lea mailles autres que triciliniques.
Dans la plus part des cas il faut utiliser un moindre carré "standard" qui est basé sur des approximations succéssives, les ajustements des paramètres cycle à cycle se faisant via les dérivées ( d'où la nécessité de fonction dérivables par rapport à chacun de ses paramètres). Le cas échéant je pourrais fournir du code en C ou pascal pour un tel calcul mais il est très commun et devrait aussi pouvoir se trouver sur le WEB.


Dans Votre exemple Yi = a * exp( -b Xi )


soit log(Yi) = log(a) - b * Xi


si on fit par un polynome de degré 1 les couples ( Xi, Ln ( Yi) ) on va trouver A0 = ln ( a ) et A1 = b d'où a = exp(A0). Une méthode "directe" est ici possible mais cela est le hazard de ce modèle.

[User]

Bonsoir

Merci encore j.p.mignot !

J'ai pu mettre en place l'algo simple (moindre carré appliquée à 1 polynôme):

je dispose d'une série de n valeurs expérimentales (xi,yi)
je choisi au mieux le degré d de mon polynôme (d+1<=n)

je pose mon problème système d+1 equation à d+1 inconnus:

Je détermine les coefficients de ma matrice par la méthode des moindre carrée (trouvé sur le net..)
J'obtient une matrice d+1 sur d+1

et je résous le système (pivot..)

L'avantage de la méthode (comme tu l'as dit) est que si je dispose d'1 info sur le degré du polynôme sensé suivre les valeurs expérimentales
j'obtiens une plus grande précision que dans les méthodes classiques (Interpolation Lagrange ..)

Mais fort est de constater (comme vous l'avez indiqué) que ca diverge toujours pour des valeurs en dehors de l'intervalle..

Par la suite je souhaiterai trouver l'algo pour appliquer la moindre carré à une fonction f (Log, Exp, Trigo) sensée être 1 modèle pour mes valeurs.

Mais la au niveau algorythmique je ne vois vraiement pas comment m'en sortir:

Immaginez que mon modèle à priori soit une fonction du style:
f(x)=a*sin(bx)*Exp(-cx)

Excusez moi pour mon amateurisme !!!

mais là je fais comment pour que la bestiole (mon ordi) trouve les coefficients (a,b et c) à partir de la série (xi,yi) et de la fonction f

Pour faire plus simple:

j'ai une procedure Moindre_Carre(xi,yi,f,resultat)

ou xi est 1 tableau qui contient les valeurs xi (i de 1 à n)
yi est 1 tableau qui contient les valeurs yi (i de 1 à n)

et ou f est la fonction f(x)=a*sin(bx)*Exp(-cx) par exemple
(ca peut être un string)

et je veut qu'en résultat il me sorte les coefficients optimums a,b,c
pour ma fonction f.


Je sais c'est tordu mais bon il doit bien y avoir 1 méthode algorythmique
et non pas manuel !!!

Voila,
merci encore pour vos efforts !

Allez sur ce,

A bientôt

User

[j.p.mignot]

1- fit polynâmial:

Comme vous avez du le remarquer les coefs de la matrice font intervenir des sommes du type Apq = Sima( (i=1..Npoint ) Xi^p+q où p et q varient de 0 à d ( degré du polynôme ) cela peut conduire à des chiffres TRES grands et donc de gros problèmes numériques. Il est eb gémnéral préférable d'applique une honotétie sur les points pour les ramener dans de petits intervalles compris en générakl entre -2, 2 une fois le fit fait, corriger les coefficients trouvés via l'homotétie inverse.

2- Moindre carrés

Je ne vois pas où il y a 1 problème.
une méthode moindre carré nécessite
1- la fonction modèle dérivable ( numériquement) par rapport à chacun de ses paramètres
2- un jeu de paramètres de départ sensé

Il est en général préférable de fitter un 1er lieu les paramètres significatifs et de 'libere' les autres que plus tard. On peut aussi mettre un système de pondération automatique pour rejeter les points faux'.


Si vous avez une routine qui résoud le moindre carré que voulez vous de +??
Par contre j'ai un certain doute sur le passage d'une fonction comme string?!?
Cela me parrait hautement incertain et extrçmement limitatif...

Si vous souhaitez que je vous fasse parvenir un code pour du moindre carré ( C ou Pascal ) faites le moi savoir clairement. Cela est possible mais ne pourrai pas être fait avant une dizaine de jours car je devrais alors l' extraire de l'environnement d'1 des programmes que j'ai développés et qui l'inclue pour en faire une classe ou un module indépendant.

[Matthieu Brucher]

Tout à faut d'accord avec JP, un fit trop précis, et on va droit dans le mur -> over-fitting.
Il peut aussi être intéressant de calculer le meilleur modèle par maximum d'entropie sur le spectre des données.