Approximation polynomiale d'un ensemble de points

Version imprimable

23/06/2008, 10h56
ealrann

Approximation polynomiale d'un ensemble de points

Bonjour,

je cherche un algorithme permettant, à partir d'un ensemble de points, de trouver une fonction polynomiale assez proche des ces points.

les contraintes sont (je suis en milieu professionnel, j'ai pas trop le choix):

-cet algorithme doit déterminer une fonction polynomiale d'un degré fixé (pour le moment compris entre 1 et 7).
-il doit être rapide, il y a environ 75 points.
-il faut pouvoir fixer une valeur d'origine (il faut en tout cas que ce soit la même valeur de départ (à t=0)).
-à part pour la valeur initiale, le polynôme recherché n'a pas besoin de passer précisément par tout les points.
il faut pouvoir calculer le coefficient de détermination (la marge d'erreur je crois?).

C'est un phénomène physique qui est observé.

Voila, si quelqu'un pouvait m'aider ça serait vraiment sympa. J'ai déjà pas mal cherché mais c'est pas évident, et puis je dois trouver une solution assez rapidement.
23/06/2008, 14h49
pseudocode

Pour imposer la valeur a t=0, tu ecris le polynome recherché P(t) sous la forme:

P(t) = a0 + t*Q(t)

ou a0 est la valeur à t=0.

Tu peux ensuite utiliser les moindres carrés pour determiner le meilleur polynome t*Q(t) passant par les points (x_i , y_i-a0)
23/06/2008, 14h55
ealrann

merci pour ta réponse :) je vais voir ça
23/06/2008, 21h27
FR119492

Salut!

Ce n'est pas très compliqué:

Tu as 75 paires de valeurs t01 à t75 et f01 à f75. Chaque paire te donne une information, donc une équation. Si tu veux approximer ta fonction par un polynôme, disons de degré 3, soit f=A0+A1*t+A2*t^2+A3*t^3, tu as 3 inconnues A1, A2 et A3, car A0 est déjà connu, car égal à f(0). Tu as donc un système de 75 équations à 3 inconnues, donc largement surdéterminé. Pour trouver la "moins mauvaise solution", au sens des moindres carrés, la solution la plus simple consiste à utiliser la pseudoinverse de Moore-Penrose (fonction pinv dans MatLab. Il est équivalent, mais un peu plus compliqué, de passer par la décomposition en valeurs singulières (routine DSVDC dans LinPack). Pour plus de détails, va voir dans Numerical Recipes.

Jean-Marc Blanc
25/06/2008, 09h24
ealrann

Merci pour vos réponses, au moins je sais vers ou chercher maintenant.

FR119492: je pense que c'est ce genre de choses qu'il me faut, cependant je ne trouve pas d'algo pour calculer la pseudo-inverse. J'essaye d'installer des librairies qui le font (un dérive de matlab, je code en C++), mais bon, c'est tellement plus marrant quand on arrive même pas a l'installer ... J'ai pourtant pas mal cherché (mais les sites de maths en anglais ne m'aident pas beaucoup :cry: ).

Sinon, j'aurais peut être du préciser que le but est de lisser les courbes, et non d'avoir une courbe passant par tout les points.
25/06/2008, 13h04
FR119492

Salut!
J'ai pondu récemment un cours sur les diverses méthodes de résolution des systèmes linéaires. Il est déjà sur le site, à l'adresse ftp://ftp-developpez.com/jmblanc, mais pas encore officiellement annoncé. Quand tu auras tout lu et tout compris, tu trouveras les sous-programmes dont tu as besoin dans la bibliothèque LAPack++, qui est téléchargeable gratuitement de www.netlig.org
Jean-Marc Blanc
03/07/2009, 10h56
Nukix

bonjour, je cherche à faire la même chose avec excel VBA, le problème c'est queje en trouve pas le code sur internet, je pense pourtant ne pas être le seul à chercher un code vba de regression polynomiale.
Si quelqu'un a une piste c'est génial !
Merci d'avance
04/07/2009, 17h58
FR119492

Salut!
Il te suffit de l'écrire (par exemple sous la forme d'une macro).
Jean-Marc Blanc
07/07/2009, 10h50
velkouby

Courbes de Bezier

Ce genre de polynomes ont des solutions analytiques connues. Pas besoin de passer par des moindres carrés. Ca s'appelle une courbe de Bezier.

vous trouverez les équations directement applicables à vos problèmes ici:

Par contre pour ce qui est du degrés tu ne le contrôleras pas, mais ce sera rapide.
07/07/2009, 11h25
pseudocode

Citation:

Envoyé par velkouby

Ce genre de polynomes ont des solutions analytiques connues. Pas besoin de passer par des moindres carrés. Ca s'appelle une courbe de Bezier.

hum... Contraindre une courbe de Bezier à passer "au plus proche" d'un ensemble de points, c'est pas gagné.

bon, d'accord, c'est vrai qu'à 75 points ca risque de partir un peu en vrille et de faire sauter les limites numériques ( factoriel de 75 ca fait combien? ;-) ), mais bon ca marche si les points pris pour le fit ne sont pas trop bruités.

Pour faire pardonner :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
function fit=fitPolinomialAvecPointsDeControle(x,y,deg,xc1,yc1,xc2,yc2)
% model : Q(n)(t)=a0+a1.t+a2.t^2.......+an.t^n
% on cherche :
% Pn(t)=(t-xc1)(t-xc2)Q(n-2)(t)+yc1*(t-xc2)/(xc1-xc2)+yc2*(t-xc1)/(xc2-xc1)
 
if deg>=2
    alfa=y./((x-xc1).*(x-xc2));
    beta=(yc2*(x-xc1)-yc1*(x-xc2))./((x-xc1).*(x-xc2).*(xc2-xc1));
    gama=alfa-beta;
    Q=fitPolinomial(x,gama,deg-2)';
 
    fit=(x-xc1).*(x-xc2).*Q+yc1*(x-xc2)./(xc1-xc2)+yc2*(x-xc1)./(xc2-xc1);
 
else
    fit=zeros(size(y));
end
 
 
 
%% demo
x=0:0.01:2;
y=2*x.*x+4.8*cos(pi*x/3);
yf=y+0.1*randn(size(x));
xc1=0;
yc1=y(1);
xc2=2;
yc2=y(end);
 
x=x(2:(end-1));
y=y(2:(end-1));
yf=yf(2:(end-1));
 
yp=fitPolinomialAvecPointsDeControle(x,yf,6,xc1,yc1,xc2,yc2);
figure(1)
subplot 311
plot(x,y,'r--')
hold on
plot(x,yf)
hold off
title('Courbe originale + bruit')
subplot 312
plot(x,yp,'r--')
hold on
plot(x,yf)
plot([xc1 xc2],[yc1 yc2],'og')
hold off
title('Courbe bruitee + fit')
subplot 313
bar(x,100*abs(yp-y)./y)
title('erreur relative du fit en %')

Attention à ce que les points de contrôles ne fassent pas partie des données sinon, il va y avoir de la division par zéros... :-(

j'ai oublié la fonction fitPolinomial :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function fit=fitPolinomial(x,y,deg)
% model : y=a0+a1.x+a2.x^2.......+an.x^n
if deg>=0
    A=ones(length(x),deg+1);
    for i=1:deg
        A(:,i+1)=(x').^i;
    end
    B=y';
 
    % on minimise J=|AX-B|
    coef=(((A'*A)^-1)*A')*B;
 
    fit=A*coef;
else
    fit=zeros(size(y));
end

10/07/2009, 15h06
FR119492
Salut!

Citation:

Ce genre de polynomes ont des solutions analytiques connues. Pas besoin de passer par des moindres carrés. Ca s'appelle une courbe de Bezier.

Il me semble y avoir une confusion entre deux notions:
- Dans le cas d'une interpolation, on cherche une courbe qui passe exactement par tous les points. Les courbes de Bézier en sont un exemple.
- Dans le cas d'une approximation, on cherche une courbe qui passe "le moins loin possible" des points. On peut, par exemple, faire une approximation au sens des moindres carrés.
Jean-Marc Blanc
10/07/2009, 23h13
Invité

Citation:

Envoyé par Nukix

bonjour, je cherche à faire la même chose avec excel VBA, le problème c'est queje en trouve pas le code sur internet, je pense pourtant ne pas être le seul à chercher un code vba de regression polynomiale.
Si quelqu'un a une piste c'est génial !
Merci d'avance

Dans excel, et pour des polynomes de faible degré, le solveur fera pour toi des merveilles... Tu calcules explicitement les carrés des écarts en fonction des paramètres des courbes, tu sommes ca et tu lances le solveur...

Idéalement, tu commences par évaluer les sommes des moindres carrés en un certain nombre de valeurs fixes (c'est une boucle en VBA), pour approcher la solution et garantir que le solveur ne perde pas les pédales (sur des degrés un peu élevés, ca arrive)

Ah oui, aussi, le solveur d'excel a tendance à déraper quand les valeurs deviennent grandes, si tu peux réduire des polynomes de facon a ne résoudre le problème qu'avec de petites valeurs de x, ca ira mieux...

Francois
01/01/2011, 11h17
olibara

Bonjour

Je me greffe un peu tard sur cette discussion car elle correspond exactement a ce que je cherche : trouver la courbe de tendance approchant d'une suite de point fort "bruitée"
Pour cela je voudrais ecrire l'algorithme en C#
Mais contrairement a ce qui est dit il n'est pas du tout facile de trouver des modeles de code appliquant une formule de régresion polynomiale

En connaissez-vous ?
Merci de votre aide
Bonne année

N.B. : J'ai déja un post sur le sujet avec une illustration du graph de point et sa regresion linéaire

http://www.developpez.net/forums/d10...nt-dinflexion/
01/01/2011, 22h20
Nebulix

Je sors des limites de l'épure mais je tiens à te dire que si ta fonction n'a pas de raison précise d'être un polynôme, tes résultats n'auront aucune signification ( en particulier pour des interpolations ou des extrapolations )