Interpolation de Lagrange

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 (x_i,y_i). On fixe Tⁱ₀ = y_i , polynome de degrée 0. Les T sont des polynomes. Donc on prend Tⁱ_{0 et} Tⁱ⁺¹₀ qui va nous donnée Tⁱ_1, polynome de degrée 1, interpolant les points i et i+1, grace à cette formule:
Tⁱ_j+1(x)= ( (x_i-x) * Tⁱ⁺¹_j(x) - (x_i+j+1-x) * Tⁱ_j(x) ) / x_i-x_i+j+1

Exemple: A(1,2) B(3,2) C(1,5)
On interpole y_A et y_B qui donne T⁰₁ idem y_B et y_C qui donne T¹₁. On interpole T⁰₁ et T¹₁ qui donne T_⁰2 = 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 T₁ à partir de celle des T_0, puis celle des T₂ à partir des T_1, 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=<P.degre;t++)
        { printf("%fx^%d",coeff[t],t)
        }
    };

Je vous remercie d'avoir tout lu, je m'excuse d'avoir abusé de votre patience et j'espère avec humilité qu'une bonne ame se penchera sur mon problème. Merci encore

salut

je ne connaissais pas ce truc !

j'ai été voir [ Lien ]

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 !

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