Discussion :

[evariste_galois]

bonjour a tous,
voila j'ai des données et j'aimerais pouvoir faire passer un polynome de degres n ( dans un premiertemp de degres 2) qui passe le plus pres possible de tous les points.
je sais le faire pour une droite ( avec la droite de regression linéaire) mais je n'ai aucune idée de la maniere avec laquelle je dois m'y prendre pour un degres superieur... je connais bien les interpolateurs de Lagrange mais je ne pense pas que ce soit tres utile :'(.
bref si quelqu'un a une idée...

d'avance merci

Evariste Galois

[KORTA]

OUPS

[Totsira]

Si ton système est linéaire => interp. polynômiale

- choisis n+1 points x0, x1, ... , xn
- calcule y0 = f(x0), y1 = f(x1), ... , yn = f(xn)
- cherche un polynôme de degré n tel que Pn(xi) = yi avec i = 0 , 1 , ... , n
de la forme P(x) = anx^n + ... + a0

Puisque tu connais Lagrange, utilise les coeff d'interpolation, sachant que
P(x) = y0L0(x) + y1L1(x) + ... + ynLn(x) = Sum [ ykLk(x) ]

Sinon transpose sous forme matricielle (type Vandermonde) et résous...

Bon courage.

Ps : ton nick est bien choisi !

[grishka]

le problème est de choisir le degrès de son polynome quel que soit le nombre de points or le polynome interpolateur de Lagrange est de degrès n pour n+1 points....

Si tu veux commencer par du degrès 2 ou 3, regardes du coté des splines : ce sont des courbes polynomiales par morceau (degrès 2 ou 3 le plus souvent, mais tu peux généraliser). Je pense notament aux courbes de Hermite qui se calculent matriciellement.
Sinon pour trouver le polynome de degrès n qui minimise la distance aux points, c'est un problème d'optimisation qui ne doit pas être différent de la régression linéaire sauf dans la complexité des calculs. Regarde du coté de la régression polynomiale...

[Teuchteu]

Lagrange te permet d'obtenir une erreur nulle en chaque point d'interpolation. En revanche c'est vrai que le degré de ton polynome est régi par le nombre de point que tu as. Tu peux chercher du côté des polynomes de Bezel aussi...

[evariste_galois]

je me permet d'aporter une petite precision...

en faite j'ai par exemple 50 points et je desire faire passer un unique polynome de degres 2 le plus pres possible de tous c'est point ... je cherche une methode car la je rame c'est horrible..... j'ai entendu parler de la methode des moindre carrées mais je ne trouve rien de bien sensationnelle (sur le net en tous cas) alors si quelqu'un la connais ou peut me tuyeuter dessus ou une methode comparable.....
Merci pour vos reponses :-) :-)

Evariste Galois

[grishka]

méthode polynomiale avec la méthode des moindres carrés :

soit ton ensemble de points (xi, yi) et un polynome modèle p(x) = ax²+bx+c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
soit S = som( [yi - p(xi)]² ) le carré de la norme
 
=> S(a,b,c) = som( [yi - (axi²+bxi+c)]² )

(a,b,c) tel que S(a,b,c) minimale? résoudre le système :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
dS/da = 0
dS/db = 0
dS/dc = 0

donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
som(-2yixi^2+axi^4+bxi^3+cxi^2) =0
som(-2yixi + axi^3+bxi^2+cxi) = 0
som(-2yi+axi^2+bxi+c)=0

donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
|som(xi^4) som(xi^3) som(xi^2)|  |a|    |2*som(yixi²)|
|som(xi^3) som(xi^2) som(xi)   |*|b| = |2*som(yixi) |
|som(xi^2) som(xi)     som(1) |  |c|    |2*som(yi)    |

soit :
M*X = Y

un petit pivot de gauss et le tour est joué...Vérifie les calculs quand même....

PS : La méthode est facilement adaptable à n'importe quel degrès de polynome modèle
PS2 : est-ce forcément LE minimum? il faudrait calculer la signature de S(a,b,c) qui est une forme quadratique... je laisse le faire...

[grishka]

j'chuis c** S est une norme donc forcément définie positive, et la signature est (3,0) (vive la France) donc c'est un minimum!

[Metal Tom]

Il y a eu un post récemment sur l'interpolation.

[evariste_galois]

j'chuis c** S est une norme donc forcément définie positive

errare humanum est.... et qui plus est l'erreur etait négligeable devant toute l'information que tu as distillé vu que j'ai la methode et si je veux je peux faire passer une autre fonction dutype ln ou sin ;-)....
encore merci...... :-)

[rouxel10]

c'est pour faire de la prévision de cours de bourse?

[j.p.mignot]

J'ai fournis des source codes pour résoudre du moindres-carrés et faire des fits polynômiaux sur ce même forum. Cette discussion a été initialisée le
28/10/2005
sous le nom
Méthode d'interpolation a partir dune série de valeurs
On résoud exactement ce problème par plusieurs technique dont celle citée ci-dessus

Lien:
http://www.developpez.net/forums/showthread.php?t=63949

[Nemerle]

Quelques remarques supplémentaires:

1. Si les différentes valeurs de ta séquence sont "peu" nombreuses, tu peux utiliser l'algorithme de Berlekamp-Massey (il n'y a pas "mieux")

2. Effectivement, en fct de ce que TU cherches, ton modèle choisira l'algo. le + approprié: Neville, NURBS, Aitken... ou les classiques Lagrange, Chebyshev, Newton...

Donc à toi de définir ce que tu veux (par exemple, si tu te fous du comportement aux extremes, si tu veux minimiser les variations entre 2 pts consécutifs...)

[Razgriz]

euh j'ai un stress je résous à la main et j'ai pas la même chose que toi :
(je suppose qu'on ait des données xi, yi avec i = 0 ... n )
et qu'on cherche le pol de degré k = sum[0<= j <= k] (aj * x^j)

Rq : sum[i] (f(x)) = sum[0 <= i <= n] f(f(x))

Après

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
dS/da = 0
dS/db = 0
dS/dc = 0

(ici a = a2, b = a1 et c = a0)

On a que

dS/daj = sum[i] ( 2 * ( yi - sum[j](aj * xi^j) ) * (- aj xi^j ) )

et donc

dS / daj = -2 aj * sum[i]( ( xi^j ) * ( yi - sum[j](aj * xi^j) ) )

Ce qui n'est pas ce que tu as écrit.
Je me trompe peut-être bien sur, si qqn voit une faute, qu'il le dise

[j.p.mignot]

Vous Notez
dS/daj = sum[i] ( 2 * ( yi - sum[j](aj * xi^j) ) * (- aj xi^j ) )
ce qui n'est pas correct!

Prenons un polynôme de degré n coef A0.. An
et prenons N points (N >= n+1) 1..N
Sima note implicitement Sigma ( p=0 à n )
Somme note implicitement Somme ( i=1 à N )

On minimise
R = Somme [( Yi - Sigma(Ap.(Xi)^p) ] ^2
on souhaite donc que
@R/@aq=0 pour tout q=0..n

@R/@Aq = 2 * Somme [( Yi - Sigma(Ap.(Xi)^p) * ( -Xi^q) ] =0
=>
Somme [( Yi - Sigma(Ap.(Xi)^p) * Xi^q) ] =0
=>
Somme ( Yi * Xi^q) ] =Somme [ Sigma(Ap.(Xi)^(p+q) ]
=>
Somme ( Yi * Xi^q) ] =Sigma [ Ap * Somme ((Xi)^(p+q)) ]

Ce qui est bien un système de Kramer de n+1 équations à n+1 inconnues avec

M*A = B

Bq = Somme ( Yi * Xi^q) ] q=0..n
Mpq= Mqp = Somme ((Xi)^(p+q)) p,q = 0..n,0..n

Bien entendu, il est préférable de faire une homotétie pour ramener X dans [1,2] et corriger en conséquence la solution. Si non, Somme ((Xi)^(p+q))
peut devenir gigantesque!

[Razgriz]

OK désolé pour la faute
Pouvez-vous donner une forme explicite sous forme matricielle du système?
(Et ne me vousvoyez pas, je suis pas prof lol )

[j.p.mignot]

1- Vous demandez:
Pouvez-vous donner une forme explicite sous forme matricielle du système?

Je ne comprends pas:
j'ai écrit

M*A = B
Bq = Somme ( Yi * Xi^q) ] q=0..n
Mpq= Mqp = Somme ((Xi)^(p+q)) p,q = 0..n,0..n

Ce qui est exactement la réponse à votre question.
précisons peut-être M matrice carrée (n+1)X(n+1), B matrice colonne (n+1)
A matrice colonne (n+1) représentant les inconnues du système

2- J'avais donné du source code pour résoudre ce système:
voir
http://www.developpez.net/forums/showthread.php?t=63949

[vietdung]

Et si x(i) est un vecteur de dimension d (pas scalaire), comment on peut transformer des variables x(i) de d-dimensions a 1-dimension ? , vecteurs x(i) contient d variables sous la distribution Normal(0,1)

Merci bcp
VD

méthode polynomiale avec la méthode des moindres carrés :

soit ton ensemble de points (xi, yi) et un polynome modèle p(x) = ax²+bx+c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
soit S = som( [yi - p(xi)]² ) le carré de la norme
 
=> S(a,b,c) = som( [yi - (axi²+bxi+c)]² )

(a,b,c) tel que S(a,b,c) minimale? résoudre le système :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
dS/da = 0
dS/db = 0
dS/dc = 0

donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
som(-2yixi^2+axi^4+bxi^3+cxi^2) =0
som(-2yixi + axi^3+bxi^2+cxi) = 0
som(-2yi+axi^2+bxi+c)=0

donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
|som(xi^4) som(xi^3) som(xi^2)|  |a|    |2*som(yixi²)|
|som(xi^3) som(xi^2) som(xi)   |*|b| = |2*som(yixi) |
|som(xi^2) som(xi)     som(1) |  |c|    |2*som(yi)    |

soit :
M*X = Y

un petit pivot de gauss et le tour est joué...Vérifie les calculs quand même....

PS : La méthode est facilement adaptable à n'importe quel degrès de polynome modèle
PS2 : est-ce forcément LE minimum? il faudrait calculer la signature de S(a,b,c) qui est une forme quadratique... je laisse le faire...