Discussion :

[john stedd]

Bonjour,

ma question est relativement simple (et générale), je n'ai pourtant pas trouvé de réponse sur le web et dans le forum...

j'ai 2 séries de points que l'on peut représenter sous la forme :
x0 y0
x1 y1
x2 y2
x3 y3
...
xn yn

Je sais comment utiliser l'interpolation de Lagrange pour déterminer y pour un x donné compris entre x0 et xn

Ce qui m'intéresse de faire c'est de calculer c'est :
- la valeur de x pour laquelle y est un extremum, et connaître la valeur de y (mais y est facile à calculer une fois qu'on connaît x)
- la valeur de x pour une valeur donnée de y (suffit-il d'inverser les tableaux x et y? j'ai essayé sur un exemple, mais ça n'a pas été concluant...)

Merci d'avance pour vos réponses

JS

[Zavonen]

Les formules pour calculer les polynômes de Lagrange sont données ici:
http://fr.wikipedia.org/wiki/Interpolation_lagrangienne
mais apparemment tu les as
Calculer y en fonction de x sera donc chose facile quand tu auras déterminé les coefficients des lagrangiens.
Mais en sens inverse cela risque d'être plus ardu, car le polynôme d'interpolation de Lagrange pour n+1 points est de degré n. Il te faudra donc résoudre une équation algébrique de degré n, on ne connait que des méthodes d'approximation (Newton & co.)
Pour ce qui concerne la recherche d'extrema , même problème car il faut dériver et calculer les racines d'un polynôme de degré n-1

[OliveK]

Attention avec les interpolations. Le polynôme de Lagrange va te donner une fonction qui passera exactement par les points (xi,yi).
Par contre, généralement ce polynôme fait un peu n'importe quoi entre les valeurs où il a été calé et il est souvent peu pertinent de l'utiliser pour d'autres valeurs que les xi de départ : c'est le phénomène de Runge.
Avec des méthodes du genre spline, tu pourras plus facilement inverse la fonction approximée qu'en passant par le polynôme de Lagrange.

[john stedd]

> Zavonen
ce que je voulais dire par inverser les tableaux x et y, c'est prendre
y0 x0
y1 x1
...
et calculer le polynôme interpolateur P(y). Après tout (dans mon cas), y est fonction de x, mais on peut dire que x est fonction de y.

Après vérification, cette méthode fonctionne sur l'exemple que j'avais pris (j'avais par mégarde pris une valeur en dehors de l'intervalle [y0; yn])

D'autre part, je calcule numériquement le polynôme de Lagrange par l'algo suivant (Java) :

Code :

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

1
2
3
4
5
6
7
8
9
y = 0.;
for(int i = 0; i < ytab.length; i++) {
    double c = 1.;
    for(int j = 0; j < xtab.length; j++) {
        if (i != j)
            c *= (x - xtab[j]) / (xtab[i] - xtab[j]);
    }
    y += c* ytab[i];
}

Je cherchais s'il y avait un algo similaire pour déterminer un extremum.

> OliveK
j'avais effectivement lu quelque part le phénomène de Runge, mais il n'y avait pas de graphiques. Je me rends compte avec l'allure de la courbe 1/(1+25x^2) que le calcul d'un extremum risque d'être très imprécis. Je fais faire quelques recherches sur les splines

merci

[Zavonen]

ce que je voulais dire par inverser les tableaux x et y, c'est prendre
y0 x0
y1 x1

Tout à fait possible, mais les fonctions ne sont pas réciproques l'une de l'autre (sauf sur les xi et les yi).

[Ehouarn]

Bonjour,

Pour trouver un extremum, on peut simplement procéder par dichotomie, à l'aide du polynôme de Lagrange, sur un sous-intervalle des xi préalablement identifié.

En ce qui concerne le vilain phénomène de Runge, il faut quand même nuancer un peu, sinon on en arrive à des conclusions erronées du type du

Le phénomène de Runge met en lumière le fait que l'interpolation polynomiale n'est pas bien adaptée à l'approximation de fonctions

de Wikiblabla.

L'émergence d'ocillations de Runge dépend de divers facteurs comme la présence de pôles (de la fonction que l'on cherche à interpoler, mais en général elle n'est pas connue) sur l'intervalle considéré et du choix des points de collocations (les xi, mais il arrive fréquemment qu'on n'ai pas la liberté pas les choisir); c.f. l'exemple décrit ici.

Ehouarn

[pseudocode]

Avec des méthodes du genre spline, tu pourras plus facilement inverse la fonction approximée qu'en passant par le polynôme de Lagrange.

Je suis d'accord avec cette remarque. En utilisant une spline cubique, le problème devient assez simple puisqu'entre chaque point la courbe est cubique par morceau, donc la dérivée est quadratique par morceau. La recherche des zéros d'une forme quadratique est simple.

[john stedd]

> Ehouarn

Ce que je cherche à faire, c'est trouver une méthode plus performante (plus rapide) pour calculer un extremum. La méthode par dichotomie, bien que très fiable, est aussi plus lente.


Je pense que je vais rester sur ma méthode actuelle (interpolation par différences avec 3 points), car le temps de calcul n'est pas pénalisant. Je chercherai ultérieurement si le besoin s'en fait sentir.

Merci de vos réponses

a++