Discussion :

[nhella22]

bonjour

Je suis débutante et j'aurai besoin d'aide pour coder l'interpolation de lagrange et celle de neuville:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct{
int degre;
double* coefficients;
}polynome;
 
polynome* polynome_lagrange(double* points, int n, int j){
 
}
 
double interpolation_lagrange(double* donnees, int n, double x){
 
}
 
double interpolation_neuville(double** donnees, int n, double x){
 
}

franchement si vous pouviez m'aider parce que la je comprend plus rien .

Merci beaucoup

[jeroman]

Salut

franchement si vous pouviez m'aider parce que la je comprend plus rien .

Qu'est-ce que tu ne comprends plus ?

[nhella22]

je ne sais comment codés ces méthodes

[Invité]

Mathématiquement parlant, tu sais quels calculs faire, quelles formules utiliser? Et que sais-tu du C ?

[nhella22]

j'ai les formules mais je ne sais pas comment les codés. En faite j'ai du mal a voir ou a transformer les formules en codes

[mikhailo]

Donne les formules et on va voir ça

[nhella22]

Polynômes de Lagrange
Étant donnés n points (x0,y0),(x1,y1),...,(xn-1,yn-1) les polynomes de la grange sont n polynômes lj(X) (pour 0  j < n) tels que lj(xj) = 1 et lj(xi) = 0 si i 6= j. Ils sont définis par :

lj(X) = X-x0/xj-x0*...*X-xj-1/xj-xj-1*X-xj+1/xj-xj+1*...*X-xn-1/xj-xn-1


Polynôme interpolateur
Il est alors aisé de définir un polynôme L(X) tel que pour tout 0<=j<n L(xj)=yj
Il suffit de choisir la combinaison linéaire suivante de polynômes de Lagrange :
L(X)=y0l0(X)+y1l1(X)+...+yn-1ln-1(X)

Polynome de neuville
Étant donnés n points (x0; y0), (x1; y1),...(xn-1,yn-1) d’abscisses deux à deux distincts, on note di,j(X) le polynôme minimal de degré inférieur à j-i qui passe par les points (xi; yi); (xi+1; yi+1); ... ; (xj ; yj).
d0,n-1(X) passe par tous les points. Il est donc identique au polynôme d’interpolation T (X).
Le principe de l’algorithme de Neuville consiste à calculer T (x) = d0; n-1(x) par l’algorithme récursif suivant :
– si 0  i < n :
di,i(x) = yi
– si 0  i < j < n :
di;j(x) =(x - xj) di,j-1(x) + (xi - x) di+1;j(x)/xi - xj

[mikhailo]

Pour ma part, je ne ferais pas ça avec les struct. Puisqu'un polynôme est un vecteur, voilà ce que je ferais:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
double lagrange[n][n+1];//n polynomes de degre n, donc avec n+1 monomes chacun: chaque ligne du tableau représente un des polynomes
 
double** make_lagrange(double** lagrange, int n)
{
	int i;
	int j;
 
	for (i = 0; i < n; i++)//pour chaque ligne du tableau
	{
		for (j = 0; j < n+1; j++)//on parcourt la ligne du début à la fin
		{
			lagrange[i][j] = //calcul du coefficient selon les règles que tu utilises
		}
	}
	return lagrange;
}

Ensuite, tout dépend de comment tu récupères les données que tu utilises (les coordonnées). Tu peux par exemple les stocker dans un tableau à deux colonnes: double points[n][2].
Pour les polynômes interpolateur et de neuville, c'est pareil, sauf que comme il n'y a qu'un polynôme, ben ce sera un tableau à une dimension au lieu de deux: s'ils sont de degré n aussi, ils seront du type double interpolateur[n+1] et double neuville[n+1]. Et tu peux les calculer soit à partir de ceux de lagrange, soit à partir de tes données initiales. J'espère ne pas avoir fait de bourde dans le peu de code que voilà, mais en tout cas, algorithmiquement c'est à ça que ça doit ressembler =)

[nhella22]

Merci je vais essayé

[mikhailo]

Sinon, j'ai regardé un peu...

http://fr.wikipedia.org/wiki/Interpolation_lagrangienne

http://www.google.fr/url?sa=t&source...7sq_dsTdeuMBLQ

Ces deux liens sont pas mal; surtout le deuxième qui explique bien comment ça marche au niveau algorithmique. Le problème, c'est que je n'ai vu nulpart de formule donnant explicitement les coefficients du polynôme de Lagrange. Du coup, il faut peut-être que tu commences par faire toi-même une fonction qui multiplie deux polynômes, en calculant les coefficients, puis ensuite, l'appeler n fois pour calculer chacun des Lj, et de là construire le tableau que j'ai décrit plus haut.

Autre solution: puisque tu connais les racines du polynôme de Lj, tu peux peut-être voir s'il n'est pas plus simple pour toi de les représenter par
a) la liste de leurs racines,
b) le coeff devant le produit des (X-xj): ce sera le produit des 1/(xj - xi).
Tu peux regarder si tu trouves des idées intéressantes dans ce TP: http://www.perso.univ-rennes1.fr/phi...linalg/TP4.pdf

Implémentation en C++ sur le wiki en anglais: http://en.wikipedia.org/wiki/Lagrang...ion_in_C.2B.2B

Sinon, tu as aussi la solution d'écrire ton programme en Maple, qui gère déjà les polynômes, du coup tu n'auras presque plus qu'à transcrire les formules du Wiki.

Voilà, s'il y a une piste que tu préfères aux autres ^^

[nhella22]

j'ai deja ecrit le produit de deux polynomes et la somme esque je doit les utilisés

[mikhailo]

Ouip, tu peux utiliser ça pour calculer tes polynômes de Lagrange:

lagrange = produit(lagrange, (X - xi)/(xj - xi))

Tu fais ça pour chaque i entre 0 et n-1, et le résultat sera le Lj(X). Tu fais ça pour chaque j avec une autre boucle, comme dans mon premier post, et tu as tous les Lj

T'en es où avec ton programme?

[nhella22]

je sui entrain d'essayer de le codé merci encore pour ton aide

[mikhailo]

De rien, j'espère que tu vas y arriver! Bonne chance =)