[PDF] Chapitre 1 : Polynôme dinterpolation de Lagrange & son utilisation

Chapitre 1 : Polynôme d'interpolation de Lagrange & son utilisation1.polynôme de Lagrange 2.calcul de dérivées : différences finies 3.calcul d'intégrales : quadrature d'interpolation 4.intégration temporelle d'EDO's

Dans tous les cas, nous avons besoin de construire une fonction d'interpolation f(x) Interpolation : qu'est-ce que c'est et à quoi ça sert ? Vous êtes astronome dans le 15ième siècle et vous étudiez le mouvement des étoiles à l'aide d'un télescope. Chaque nuit pas forcément à la même heure vous mesurez la position d'une même étoile de manière précise, ce qui vous donne un tableau de points de mesure instantpositionSous forme graphiqueavec . A partir de ces mesures, on souhaite obtenir une idée de la positionde l'étoile f(x) à tout instant x. Extrapolation :Interpolation :Selon la position de x, on parle de

Cette fonction d'interpolation n'est pas unique. On peut interpoler des données d'une infinité de manières différentes, un exemple fonction d'interpolationfonction d'interpolationCertains choix sont plus précis que d'autres ou plus facile à mettre en oeuvre. Le but est toujours de calculer les coefficients d'expansion à l'aide des données dont on dispose. Puis on reconstruit la fonction où on veut. base générale base polynomiale simpleUne fonction d'interpolation est toujours proposée comme une 'décomposition' sur une base connue de fonctions. base FourierQuelques exemples :

Une fonction d'interpolation ne sert pas juste à reconstruire la fonction entre des points où on connait la valeur.ou pour une intégrale Ceci nous donne des formules très utiles, qui constituent le point de départ d'un très grand nombre de méthodes numériques utilisées en physique pour résoudre des EDO, EDP, équation intégrales ... Dans ce cours, on se limitera à l'interpolation polynomiale de Lagrange et son utilisation. On peut également l'utiliser afin de trouver une approximation pour une dérivée

1. Polynôme d'interpolation de Lagrange 1.1. Une formule assez intuitive polynôme unique d'ordre 4, passant par les 5 pointsOn dispose de (n+1) couples Le polynôme d'interpolation de Lagrange est le polynôme unique d'ordre n, qui passe exactement par ces (n+1) pointsComment trouver les (n+1) coefficients ?

On peut définir un système linéaire, qui exprime que le polynôme passe effectivement par les points=Comme les points sont différents, nous avons toujours ce qui implique qu'il existe en effet une solution unique à ce problème Trouver cette solution ne semble pas si facile que ça en pratique, mais Lagrange remarque que le polynôme a une propriété intéressante.

car en effet, on voit facilement que ce polynôme passe exactement par tous les pointsEn conséquence le polynôme d'interpolation de Lagrange ne peut être que Remarque : on comprend ici que les fonctions forment une base alternative aux monômes . Les coefficients d'expansion , sont directement les valeurs de la fonction sur les points ce qui est facile à retenir. Ce polynôme prend la valeur 1 dans le point , et zéro ailleurs, ou encore utilisant le symbole de Kronecker delta.

1.2. Quelques exemples simplesLe polynôme de Lagrange, passant par 2 points, est une droite Le polynôme de Lagrange, passant par 3 points, est un paraboleQ : le polynôme de Lagrange passant par 1 point ??

1.3 Estimation de l'erreur polynôme d'interpolationla vraie fonctionSi on approche une fonction f(x) par un polynôme d'interpolation, on fera évidemment des erreurs : On aimerait être capable d'estimer ces erreurs afin de mesurer la "qualité" de l'approxima- tion polynomiale

Théorème (sans preuve)avecThéorèmel'erreur diminue en prenant plus de points et sera d'autant plus petite que x est proche d'un point d'interpolationf ne varie pas trop brusquementSi f(x) est un polynôme d'ordre alors l'erreur s'annule caralors l'erreur sera un polynôme d'ordre n+1 Soit f(x) une fonction n+1 fois continûment dérivable sur l'intervalle [a,b] et n+1 points où la fonction prends les valeurs Si on note P (x) le polynôme d'interpolation passant par ces (n+1) points

1.3 Estimation de l'erreur polynôme d'interpolationla vraie fonctionSi on approche une fonction f(x) par un polynôme d'interpolation, on fera évidemment des erreurs : On aimerait être capable d'estimer ces erreurs afin de mesurer la "qualité" de l'approxima- tion polynomiale Ce théorème permet de borner l'erreur commeRq : l'erreur = 0, si on interpole f(x) un polynôme d'ordre n à l'aide de n+1 points.

Exemple interpolation Matlab & mot d'attention !Interpolation d'un trajet de RER B connu (code interpol_rerb)Méfiez-vous : augmenter l'ordre d'un polynôme n'augmente pas forcément la précision de l'interpolation, bien au contraire. Mieux faut-il interpoler par morceauxutilisant des polynômes de bas ordre.

2. Dérivation numérique par différences finiesinstantposition2.1 Contexte simpleVous êtes expérimentateur et vous mesurez la position d'un mobile au cours du temps à des instants successifsOn sait déjà qu'on peut approcher la fonction par un polynôme d'interpolation. Les dérivées d'une fonction peuvent être approchées par les dérivées d'un polynôme d'interpolation = > formules différences finies Comment calculer la vitesse et l'accélération du mobile ? instantvitesseaccélérationSera très utile dans le chapitre suivant

2.2 Différences finies suivant votre intuitionLa dérivée d'une fonction f(x) par rapport à x est définie commeOn fait donc la différence entre une fonction en un point et en un point infiniment proche et on divise par cette petite distance. Est-ce la seule formule que l'on puisse imaginer ?Pas besoin de chercher très loin : en enlevant la limite, on remplace une dérivée par une différence finie F = forwardOn comprend intuitivement que plus que les soient rapprochés, plus que l'erreur sera petite.

Non, aucune raison pour préférer une direction "forward'' par rapport à "backward'' . B = backwardce qui mène par le même procédé à une formule alternativeOn peut en effet définir la dérivée commeCette formule ne semble pas mieux que la précédente (F). Même remarque sur l'erreur d'ailleurs. On peut encore aller plus loin

En effet, pourquoi ne pas prendre encore une autre formule comme définition de la dérivée Cette formule peut alors mener à C = centeredVisuellement on a l'impression de plus de précision, mais est-ce que c'est le cas ?Que faire des dérivées d'ordre supérieur ?

Peut-on proposer une procédure un peu + systématique ? Pour les dérivées d'ordre supérieur on peut procéder de la même manièrepeut mener à par une application successive des formules B et F. si pts. équidistantsMais on a du mal à estimer la précision de telles formules. Par exemple, pour une dérivée d'ordre 2

2.3 Systématique = en utilisant le polynôme de LagrangePour obtenir une approximation différences finie des dérivées en un point...on fixe d'abord un ensemble d'indices autour de jque l'on veut voir apparaitre dans les formules différences finiesNous choisissons ces points !On calcule ensuite le polynôme de Lagrange passant par ces points où on utilise les fonctions introduites dans la section 2

Construit sur (p+1) points, ce polynôme de Lagrange sera d'ordre p. On peut donc le dériver p fois. Exercice : utilisant les indicescalculer ces approximations diff. finies de Bonne idée pour p > 2,3 ??nous approchons les dérivées de la fonction par la dérivée d'un polynôme d'interpolation. ...En exprimant : Cette procédure nous donne des formules d'approximation différences finies, qui auront d'ailleurs toutes le même niveau de précision, en théorie. Dangereux, pense à l'exemple RER B.

Solution généraleCas particulier : maillage régulierRemarque : il faut plus que 3 points pour des dérivées d'ordre sup.

2.4 Consistance & ordre des approximationsOn comprend que nous avons de très nombreuses approximations différences finies pour les dérivées.Q2. Qu'elle est le degré de précision, l'ordre de ces formules ? Q1. Est-ce que ces formules sont consistantes, c.a.d. qu'elles tendent bien vers les bonnes dérivées dans la limite ?Pour répondre, une seule méthode : appliquer la formule sur une fonction continûment différentiable et faire des développements limités autour d'un point choisi. Quelques rappels sur les DL ? que l'on suppose obtenue en travaillant avec des pas d'espace constantSoit des formules données

Développement limité d'une fonction dans un voisinage de xParfois, nous avons envie de limiter un DL à un certain ordre. Par exemple : où nous utilisons le symbole O. Rappels sur les développements limités avec A un nombre. Ce symbole nous informe que les termes oubliés décroissent au moins aussi rapide que la quantité spécifié. Nous avons donc : Quelques règles de calcul :

On remplace par un DL autour de Dans le coté droit de la formuleexact résiduDans la limite l'approximation tend vers la formule exacte, ce qui démontre sa consistance. L'erreur, le résidu décroit comme avec p=1 iciOn dit que l'approximation est d'ordre 1 Formule forward (F) Quelques exemples pour illustrer la notion de consistance et d'ordre

Formule centrée (C)On remplace et par des DL autour de ce qui donneexact résiduOn dit que cette formule centrée est consistante et d'ordre 2. Dans la limite l'approximation tend encore vers la formule exacte, ce qui démontre sa consistance. L'erreur, le résidu décroit comme avec p=2 ici

Pour résumer : afin de tester la consistance et afin de trouver l'ordre d'approximation d'une formule différence finie, il faut remplacer les termes par des DL autour du point dans lequel on souhaite calculer la dérivée. On remplace à droiteSi la formule est consistante, on trouvera après avoir collecté les différents termes où le résidu doit aller vers 0, avec . Pour une formule différence finie de la forme avec A une constante non-nulle, ce qui signifie que On définit ordre comme l'exposant p

Attention : si vous trouvez à l'issue de vos calculs querésidu = Note : les formules différences construites sur le polynôme de Lagrange à (p+1) points, sont d'ordre p, toujours.L'ordre peut être et on ne peut alors pas conclure. Il faudra alors recommencer et inclure plus de termes dans les DL utilisés pour remplacer à l'aide de la procédure mentionnée. Testez-le en calculant l'ordre des formules différences finie

3. Intégration numérique : quadrature d'interpolation à évaluer la superficie sous la courbe f(x). Graphiquement, on cherche par l'intégrale 3.1 Principe générale

3. Intégration numérique : quadrature d'interpolation Graphiquement, on cherche par l'intégrale à évaluer la superficie sous la courbe f(x). Dans une formule de quadrature de d'interpolation on remplace la fonction dans l'intégrandum par un polynôme d'interpolation de Lagrangemènera à une formule de la forme cstvaleurs nodales3.1 Principe générale

Les coefficients de la formule de quadrature d'interpolation à (n+1) points sont doncavecComme il s'agit d'intégrales de polynômes, ces coefficients ne sont pas très difficiles à évaluer.avecPour calculer les coefficients on rappelle que le polynôme d'interpolation de Lagrange basé sur (n+1) points est et on remplace donc

3.2 Quelques exemplesPour calculer l'intégrale, on remplace la fonction par le polynôme d'interpolation qui passe par les deux points d'extrémitéméthode du trapèzeOn approche l'intégrale, l'aire sous la courbe, par l'aire du trapèze

méthode de SimpsonPour calculer l'intégrale, on remplace la fonction par le polynôme d'interpolation qui passe par les deux points d'extrémité et le point du milieudonneOn approche l'intégrale, par l'aire sous une parabole

3.3 Analyse d'erreurOn peut calculer l'erreur comme?Ici . Appliqué au deux exemples précédentméthode du trapèze (2 points, n=1)méthode de Simpson (3 points, n=2)

3.4 Méthodes compositesSur des grands intervalles [a,b], on peut en principe appliquer la méthode avec des polynômes d'interpolation d'ordre de plus en plus élevé (formules de Newton-Cotes)Un seul polynômed'ordre nMéthode composite des trapèzesInterpolation linéaire par morceauEn pratique, on utilise très souvent des méthodes composites. L'idée est ici de diviser l'intervalle [a,b] en sous-intervalles où on interpole avec des polynômes de bas ordre. Ceci n'est pas conseillé, les formules ne deviennent pas forcément plus précises.

3.4 Méthodes compositesSur des grands intervalles [a,b], on peut en principe appliquer la méthode avec des polynômes d'interpolation d'ordre de plus en plus élevé (formules de Newton-Cotes)Un seul polynômed'ordre nEn pratique, on utilise très souvent des méthodes composites. L'idée est ici de diviser l'intervalle [a,b] en sous-intervalles où on interpole avec des polynômes de bas ordre. Ceci n'est pas conseillé : les formules ne deviennent pas forcément plus précises.Interpolation quadratique par morceauMéthode composite de Simpson

Méthode composite du trapèzeOn coupe l'intégrale e termes où on applique à chaque fois la méthode du trapèzeL'erreur commise sera bornée comme Souvent on prends les points équidistants entre a et b, pour On note . La formule se simplifie alors à-1

Méthode composite de SimpsonOn introduit de nouveau n+1 points dans l'intervalle [a,b]. L'intégrale ne sera divisé en seulement n/2 termes et n doit donc être pair soit ...Sur chacun des n/2 segments, on applique la méthode de Simpson. on fait donc une interpolation, quadratique par morceau. Avec des points équidistants, ceci donne

Méthode composite de SimpsonOn introduit de nouveau n+1 points dans l'intervalle [a,b]. L'intégrale ne sera divisé en seulement n/2 termes et n doit donc être pair Sur chacun des n/2 segments, on applique la méthode de Simpson. on fait donc une interpolation, quadratique par morceau. Avec des points équidistants, ceci donneL'erreur sera alors bornée par

...CI :...4. Intégration temporelle de systèmes d'EDOOn considère un système général de p équations différentielles ordinaires d'ordre 1 :4.1 Problème aux conditions initialesOn dispose de exactement p fonctions que l'on connait et on cherche à identifier des solutions , , ... , qui passent par un état initial bien spécifié sous forme vectoriellesous forme vectorielleCI = condition initiale, différent d'une condition limite, par le fait qu'on impose des valeurs à un seul "instant".1 point de départpentes à tout temps

selon des méthodes + ou - précisesConnaitre la solution sur tous les temps sera difficile et n'est pas nécessaire. En pratique, il suffit de connaitre la solutions sur des temps discretsL'idée générale d'une intégration temporelle numérique, peut être illustré comme ci-dessous :Le pas de temps peut être fixe ou variable. S'il est fixe, on le notera on calculera la solution donc pas par pas...notation

4.2 Méthode intuitivesPourquoi ne pas utiliser ce que nous connaissons sur l'approximation des dérivées(formule F)On adoptera la notation vectorielleCI :donne directement Méthode d'Euler expliciteOn continue le long de la tangente sur un intervalle de temps Explicite = connaissant l'état précédent, on calcule directement l'état suivant

Mais pourquoi préférer une formule "forward'' par rapport à "backward". (formule B)donne ou encoreMéthode d'Euler impliciteComme f peut être une fonction compliquée, on ne résolve pas si facilement cette équation "implicite". (On peut utiliser la méthode de Newton...) Implicite = connaissant l'état précédent, on ne peut pas directement calculer l'état suivant. Plus difficile à utiliser, mais ça peut avoir un intérêt : la stabilité.

4.3 + Systématique = utilisant le polynôme de LagrangeNotre problème d'EDO + CICI := polynôme de Lagrange passant par Euler expliciteAdams-Bashfort 1 Dans les méthodes de Adams-Bashfort, on remplace par un polynôme de Lagrange, qui interpole des points déjà connus, pour les temps Ceci donne des formules explicites, dont la précision dépend du dégrée du polynôme. Quelques exemples :peut s'écrire sous forme intégraleet on peut utiliser les règles de quadrature d'interpolation pour approcher les intégrales.

= polynôme de Lagrange passant par Adams-Bashfort 2 Un petit calculPour calculer l'état en temps n+1, on utilise les deux précédents états n et n-1. Ces méthodes sont plus précises et explicites. On peut continuer la même procédure pour trouver des formules d'ordre plus élevé Si on remplace

Dans les méthodes de Adams-Moulton, on remplace par un polynôme de Lagrange, qui interpole f pour les temps Ceci donne des formules implicites, dont la précision dépend du dégrée du polynôme. Quelques exemples : = polynôme de Lagrange passant par Euler impliciteAdams-Moulton 1 = polynôme de Lagrange passant par Le calcul mène à Adams-Moulton 2 Crank-Nicolson Trapèzes ?

4.4 Autre méthode : Runge-Kutta On peut encore construire d'autres formules, basées sur d'autres formules de quadrature d'interpolation. Les méthodes de Runge-Kutta sont les plus souvent utilisées en physiqueRK4 : Runge-Kutta ordre 4On évalue successivementRK2 : Runge-Kutta ordre 2 (point du milieu)En deux pas