Sujet Précédent Sujet Suivant

Interpolation de Lagrange

cs_highvoltage Messages postés 3 Date d'inscription jeudi 13 décembre 2007 Statut Membre Dernière intervention 9 janvier 2008 - 13 déc. 2007 à 20:14
Eregon Messages postés 17 Date d'inscription lundi 3 septembre 2007 Statut Membre Dernière intervention 26 octobre 2009 - 16 avril 2008 à 23:32
Bonjour à tous,
je viens solliciter votre aide à propos d'un programme que j'ai a réalisé pour un projet. Je vous passe les détails, c'est la première année qu'il instaure cette matière, alors qu'on a tout juste appris des bases de programmation (C++) l'an passé. Le tout en C, donc sans classe. La galère. Enfin, je tiens quand même à remercier d'avance tous ceux qui se pencherais sur mon problème, qui est quand même assez conséquent.

Bref, j'ai à coder un programme qui, à partir d'un nombre de points fixés par l'utilisateur, recrache un polynome, par la méthode de lagrange.Petite explication: on rentre n points de coordonnées (xi,yi). On fixe Ti0 = yi , polynome de degrée 0. Les T sont des polynomes. Donc on prend Ti0 et Ti+10 qui va nous donnée Ti1, polynome de degrée 1, interpolant les points i et i+1, grace à cette formule:
Tij+1(x)= ( (xi-x) * Ti+1j(x) - (xi+j+1-x) * Tij(x) ) / xi-x<sub>i+j+1

</sub>Exemple: A(1,2) B(3,2) C(1,5)
On interpole yA et yB qui donne T01 idem yB et yC qui donne T11. On interpole T01 et T11 qui donne T02 = P, le polynome que l'on cherche.

Les explications faites, passons au programme. Soyez indulgents envers mon code et mon niveau (au fait, je code sous solaris, vive printf et scanf )

Bon première idée, une structure pour un polynome:
struct poly
{ int degre;
  float coeff[degre+1];
};

Ensuite:
int n;
printf("A partir de combien de points voulez-vous interpoler le polynome?\n");
scanf("%d",&n);
float x[n];
float y[n];
for (int i=0;i<n;i++)
    {
     printf("Entrer le point "%d" sous la forme: x y\n",i+1);
     scanf("%f%f",x[i],y[i]);
    };

C'est la qu'arrive les problèmes: Je me doute que y'a une boucle dans une boucle: on calcule la deuxième colonne des T1 à partir de celle des T0, puis celle des T2 à partir des T1, ect... Mais ma question est: comment à partir de ma pauvre structure, appliqué la formule si dessus, lui faire calculer des polynomes ect... je bloque complêtement sur quoi mettre dans ces boucles. C'est la que j'aurais besoin de toutes vos suggestions et idées (aucune exigence dans le rouge, c'est pour les gens qui lirais en diagonnale) sur ce dont j'ai besoin pour le faire; peut être une autre classe, d'autres fonctions/procédures...

for (int j=0;j<n;j++)          
    {
     for(int k=j+1;k<n;j++)
        {
        }
    }

Bon, pour l'affichage du polynome, je devrais m'en sortir:
void affiche_poly(poly P)
    {printf("P(x)=")
     for(int t=0;t=

2 réponses

Réponse 1 / 2
acx01b Messages postés 280 Date d'inscription dimanche 7 septembre 2003 Statut Membre Dernière intervention 8 juillet 2014 6
14 déc. 2007 à 19:35
salut

je ne connaissais pas ce truc !

j'ai été voir http://sonia_madani.club.fr/Cloaque/Arithmurgistan/Interpolation/lagrange.html

il ne parlent pas de suite par récurrence pour recalculer l'interpolation avec un point de plus

sinon ta formule:
pour calculer T(i,j+1) il faut d'abord avoir calculé T(i+1,j) et T(i,j)
donc pour calculer
T(0,1) il faut  T(1,0) et T(0,0)
T(0,2) il faut T(1,1) et T(0,1)
sauf que pour calculer T(1,1) qu'on a pas calculé encore il faut
T(2,0) et T(1,0)
...

autrement dit cette méthode est très gourmande en calcul !
il s'agit ensuite de pouvoir représenter graphiquement tous les T(i,j) ?

dans ce ca tu connais au départ tous les T(i,0)
donc tu peux calculer tous les T(i,1) (il y en aura un de moins)
...
donc ta boucle sera
// on connait les T(i,0) pour i de 0 à n
for (j = 1; j <= n; j++) {
  for (i = 0; i < n - j; i++) {
     calculer le T(i,j)
  }
}

en tout cas pour avoir tous les T(i,j) c'est sûrement la meilleure formule, par contre pour avoir T(0,n) c'est une très mauvaise manière, la formule du lien que je t'ai donné est bien mieux !
0
Réponse 2 / 2
Eregon Messages postés 17 Date d'inscription lundi 3 septembre 2007 Statut Membre Dernière intervention 26 octobre 2009
16 avril 2008 à 23:32
J'ai récemment fait la même chose en php,
voici mon ptit bout de code qui devrait t'intéresser:
Tout d'abord, n est le nombre de points,
new Polynom(0) est le polynome P(x) = 0(aucun intérêt, c'est juste pour initialiser)
<?php
        $n = count($p);
        $result = new Polynom(0);
        for($k=0; $k<$n; $k++)
        {
            $t = new Polynom($p[$k]->y);
            for($i=0; $i<$n; $i++)
            {
                if($i != $k)
                {
                    $poly[$k][$i] = new Polynom(
                    1/($p[$k]->x - $p[$i]->x) ,
                    -$p[$i]->x/($p[$k]->x-$p[$i]->x) );
                    $t = $t->product($poly[$k][$i]);
                }
            }
            $result = $result->add($t);
        }
        return $result;
?>
Donc, une boucle pour additionner les polynomes entre eux (->add)
Et, à l'intérieur, une autre pour créer un polynome à partir des coordonnées du point: (px abcisse et py ordonnée du point)
polynome[k][i] = 1/(p[k]x - p[i]y) X - p[i]x/(p[k]x - p[i]x)
On multiplie ce polynome avec le polynome t(qu'on initialise avec t(x) = p[k]y) et ajoutons au résultat
0

Discussions similaires

Interpolation dans un tableau à 2 entrées
mitch40330 -
mitch40330 -

3 réponses
Interpolation de Lagrange
cs_raph123 -
Orohena -

6 réponses
Interpolation trilinéaire dans une Matrice 3D
narutokun66 -
ahmedba1 -

1 réponse
l'interpolation de lagrange
ahmedand -
ahmedand -

2 réponses
Interpolation linéaire
Tabouray38 -
ucfoutu -

5 réponses
Rejoignez-nous