Interpolation polynomiale (notes de cours) - Lamfa
Interpolation polynomiale (notes de cours)
(notes de cours) Jean-Paul Chehab Université de Picardie Jules Vernes LAMFA 2 Interpolation polynomiale - position du probl`eme et premiers résultats 3 |
Notes de cours -:: UMI E-Learning ::
Fabbri Notes de cours analyse numérique : Université de Tours France 6 j P Chehab Interpolation polynomiale Université de Picardie Jules Vernes LAMFA |
Chapitre II Interpolation et Approximation
Probl`eme de l'interpolation : on recherche des fonctions “simples” (polynômes polynômes par cours d'Analyse IIA ou le cours Math pour Info Chap VI |
Intégration numérique (notes de cours)
f ∈ C([a b]) On note pn le polynôme d'interpolation de f aux points (xi)n+1 i=1 On a ∫ b a pn(x)dx = n ∑ i=1 f(xi)wi avec wi = ∫ b a li(x) |
Interpolation polynomiale
Objectif : Approcher une fonction dont on ne connaıt les valeurs qu'en certains points Lorsqu'une fonction connue analytiquement est difficile `a évaluer |
Notes de cours -:: UMI E-Learning ::
Interpolation polynômiale 1 1 Introduction Dans ce chapitre nous nous donnons une fonction f supposée continue définie sur un |
Analyse numérique1 Par Pr DJEFFAL Lakhdar Université de
Ce Cours d'analyse numérique1 est destiné aux étudiants du 1er cycle 2eme ''La première forme générale d'interpolation polynômiale est bien celle de |
Feuille de TD 1 - Correction : Interpolation de Lagrange
Correction : Cet exercice fait l'objet d'une des preuves les plus importantes du cours Je vous renvoie donc au cours (ou au poly) Exercice 8 (examen 2016) ( |
DDOC_T_2018_0111_BRACHETpdf
Enfin j'adresse mes remerciements à l'équipe du LAMFA qui à travers les On note en particulier que la fonction f1 est polynomiale donc régulière et |
36 Congr`es National dAnalyse Numérique Résumés des
dt (note the polynomial increase in time) which is a vanishing contribution th`eme ont été obtenus par J Mathiaud et sont en cours de rédaction |
Th`ese - ResearchGate
LAMFA et LTI dont ils sont membres que j'ai eu la chance de travailler avec deux Le nombre de coordination noté Nc est le nombre de contact moyen par |
Processus électromagnétiques transfert de rayonnement et
des notes de cours Radiative Transfer in Astrophysics de C Dullemond [11] Le lecteur désireux d'ap Elle justifie la forme polynomiale de degré un en µ |
Congrès SMAI 2013 Seignosse le Penon (Landes) 27-31 Mai 2013
27 mai 2013 · 6 ? note < 10 : compétence en cours d'acquisition ; High-dimensional adaptive sparse polynomial interpolation and |
Exercices corrigés
sont des corrections plus détaillées que celles fournies durant le cours (si le temps a L'interpolation polynômiale sous forme lagrangienne noté L est une |
Ce document est le fruit dun long travail approuvé par le jury de
Enfin, j'adresse mes remerciements à l'équipe du LAMFA qui, à travers les enseignements, m'a grand cercle utilisée pour l'interpolation spline cubique On représente l'historique de l'erreur relative au cours du temps α En particulier, lorsque p = 1, on note τ l'opérateur de translation à droite : est polynomiale en λ |
1_DESSIN SM_TM_INFO_GLES - Université de Genève
87/88 ENSEIGNEMENT POSTGRADE EN MATHÉMATIQUES 89 NOTES 90 Les pages qui suivent présentent les cours de mathématiques Le programme des cours Interpolation et approximation 3 Résolution Transformations polynomiales 7 Problèmes Lamda-calcul, modèles d'évaluation et de substitution |
Analyse numérique1 Par Pr DJEFFAL Lakhdar Université de
Ce Cours d'analyse numérique1 est destiné aux étudiants du 1er cycle 2eme année licence la détermination du point fixe qu'on note par exemple par α tel que )( α α g = www lamfa u-picardie fr/chehab et quelques ouvrages : ''La première forme générale d'interpolation polynômiale est bien celle de Lagrange '' |
6 Polynômes dendomorphismes
Cours du jeudi 6 octobre 2016 Théorème 5 9 Soit K un corps unique polynôme unitaire noté mA(X) ∈ [X]; c'est le polynôme minimal de A Le polynôme |
Numéro 79 - [SMAI] - Emathfr
15 déc 2005 · cours 2006, ce qui reste bien en regard d'autres sections ( la mobilité vers l'uni- exemple, pour un opérateur d'interpolation ou de meilleure B-spline désigne une fonction spline polynômiale `a support borné mon ômes dans la base des B-splines (les monômes sont notés er(x) = xr, ∀r ≥ 0) : |
SMAI 2013 - Emathfr
6 mar 2006 · 6 ≤ note < 10 : compétence en cours d'acquisition ; 10 ≤ note < 14 Youcef Mammeri, LAMFA, Université de Picardie Jules Verne, 89039 Amiens, High- dimensional adaptive sparse polynomial interpolation and |
Lusage de calculatrices est interdit - Normale Sup
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur Dans cette partie on note αa la plus petite solution, si elle existe, de l' construction de l'interpolation d'une fonction par une fonction de classe C∞ polynomiale |
36 Congr`es National dAnalyse Numérique Résumés des
dt (note the polynomial increase in time), which is a vanishing contribution, provided N is th`eme ont été obtenus par J Mathiaud, et sont en cours de rédaction 2 4 Etude Ces interpolations introduisent des erreurs, en particulier dans l'équation de continuité ∂ρ LAMFA 1999 preprint, accepté `a J Math Anal Appl |
I. Interpolation
Cours de Claudia NEGULESCU
Le probl`eme de l"approximation d"une fonctionfintervient dans plusieurs situations, comme par exemple :1) la fonctionf(x) est connue, mais difficile `a manipuler. L"approximation a pour but de
remplacerfpar une fonction plus simple, ?(f), qui est plus accessible pour l"int´egration, la diff´erentiation, etc.2) la fonctionf(x) n"est pas connue, on ne connaˆ?t que les valeurs dans certains pointsxi.
Les quantit´es donn´eesf(xi) =yipeuvent ˆetre par example des mesures experimentales. Le but de l"approximation est alors de trouver une repr´esentation synth´etique (analytique) des donn´ees experimantales. Etant donn´en+ 1 couples (xi,yi),i= 0,···,n, le but de l"interpolation est de trouver une fonction ?(x), qui appartient `a une certaine classe et qui prend dans lesnoeuds d"interpolationxiles valeursyi, c.`a.d. ?(xi) =yi,?i. On dit que ?(x) interpole {yi}ni=0aux noeuds{xi}ni=0. On parle d"interpolation polynomialequand ?(x) est unpolynˆome, d"interpolation trigonom´etriquequand ?(x) est un polynˆome trigonom´etrique
et d"interpolation polynomiale par morceauxquand ?(x) est polynomiale par morceaux. Contrairement `a l"interpolation, l"approximation d"unefonction ne demande pas que la courbe recherch´ee passe par les points (xi,yi), mais plutot qu"un crit`ere d"approximation soit satisfait, comme par exemple le crit`ere de minimax, lecrit`ere des moindres carr´es, etc. Dans ce chapitre on pr´esentera plusieurs types d"interpolation polynomiale. Le chapitre III sera consacr´e `a l"approximation des fonctions. y x (xi, yi)?(x) xy (xi, yi) Figure 1: Interpolation polynomiale et approximation d"unnuage de points. valeurs correspondantes. Le probl`eme est de trouver un polynˆome de degr´e inf´erieur ou´egale `am, ?m? Pm, appel´e polynˆome d"interpolation, v´erifiant ?m(xi) =yi,?i. Pos´e
sous cette forme, ce probl`eme peut avoir un nombre infini de solutions, une seule solution ou aucune. Toutefois, il y a une et une seule solution, si on cherche cette solution dans l"espacePn(m=n). En effet, en d´efinissant les polynˆomes caract´eristiques de Lagrange l i? Pn, associ´es aux noeuds{xi}ni=0, (1)li(x) := ?nj=0,j?=ix-xj xi-xj, i= 0,···n, on remarque qu"ils forment une base dePn. Commeli(xj) =?ij, on peut d´eduire que le polynˆome d"interpolation recherch´e se laisse ´ecriresous la forme suivante (formule d"interpolation de Lagrange) et est unique : (2) ? n(x) :=n? i=0y ili(x). Th´eor`eme 1Etant donn´en+ 1points distinctsx0,···,xnainsi quen+ 1valeurs as- soci´eesy0,···,yn, il exitse un unique polynˆome?n? Pn, tel que?n(xi) =yipour i= 0,···,n. Soit?n+1le polynˆome nodal de degr´en+ 1 associ´e aux noeudsxiet d´efini par n+1(x) := ?ni=0(x-xi). Le prochain th´eor`eme donne l"erreur d"interpolation faite quand on remplace une fonction fpar son polynˆome d"interpolation ?nfassoci´e aux noeudsxi. f?Cn+1([a,b]). L"erreur d"interpolation au pointx?[a,b]est donn´ee par E n(x) :=f(x)-?nf(x) =f(n+1)(?) (n+ 1)!?n+1(x), avec??[a,b].Preuve....
Il est clair, qu"on ne peut rien dire sur l"erreur d"interpolationEnsi on ne connaˆ?t aucun renseignement sur la fonctionf, sauf ses valeurs dans les noeudsxi. Etudions maintenant plus en d´etail la convergence uniforme du polynˆome de Lagrange.2 Stabilit´e et convergence du polynˆome de LagrangeNotons la norme maximum d"une fonctionf?C([a,b]) par||f||?:= maxx?[a,b]|f(x)|. Le
polynˆome d"interpolation de Lagrange defassoci´e aux noeuds{xi}ni=0est donn´e par p n(x) =n? i=0f(xi)li(x). Si on remplace les valeursf(xi) par des valeurs approch´ees˜fi(par exemple due aux erreurs dans les mesures exp´erimentales ou aux erreurs d"arrondi) on aura une erreur sur le polynˆome d"interpolation ||pn-˜pn||?=||n? avec n:=||?n(x)||?, ?n(x) :=n? i=0|li(x)|.La constante ?
n, qui d´epend que den, de [a,b] et des pointsxiest appel´e constante de Lebesgue et joue le rˆole d"une constante de stabilit´e pourl"interpolation. On peut montrer en plus le th´eor`eme suivant de majoration de l"erreur d"interpolation Th´eor`eme 3Soitf?C([a,b])etpn? Pnson polynˆome d"interpolation associ´e aux noeudsx0,···,xn. Alors on aOn remarque que ?
ndepend que des noeudsxitandis queE?ndepend que def. Analysons ces deux termes.Notons
?nl"infimum des constantes de Lebesgue pour tous les choix possible de noeuds {xi}ni=0`anfix´e. On peut montrer que (3) ?n?2?log(n),c.`a.d. limn???n=?. Il est tr`es compliqu´e de trouver les noeuds qui m`enent vers la constante de Lebesgue minimale ?n. Par contre, les points d"interpolation de Chebyshev x i:=a+b2+b-a2cos?2i+ 12n+ 2??
, i= 0,···,n, qui sont les z´eros du polynˆome de Chebyshev de degr´en+ 1, sont quasi optimaux. En ce qui concerne le deuxi`eme terme, le th´eor`eme de Weierstrass montre que pour toute fonctionf?C([a,b]) on a limn??E?n(f) = 0. Il est important de remarquer maintenant que pour une fonctionf?C([a,b]) donn´ee, le choix des noeuds d"interpolation est crucial!!! Par contre on peut montrer, due `a la propri´et´e (3), que pour n"importe quel choix de noeudsx(n)0,···,x(n)npour chaque valeure
den, on trouvera toujours une fonctionf?C([a,b]), telle que le polynˆome d"interpolation pnne converge pas uniform´ement versf, pourn? ?. La propri´et´e (3) montre aussi que
l"interpolation de Lagrange peut devenir tr`es insatble pour des grandn. La figure suivante montre le ph´enom`ene de Runge. Il s"agit de l"interpolation de Lagrange de la fonction f(x) :=1 soit avec noeuds equir´epartis soit avec les noeuds de Chebyshev. Il est particuli`erement evident que dans ce cas (fonction r´eguil`ere!) le polynˆome d"interpolation avec noeuds equidistants ne converge pas uniform´ement versf, par contre le choix des points deChebyshev m`ene `a la convergence uniforme.
-5-4-3-2-1012345-1.5 -1 -0.5 0 0.5 1 1.5 X f(X) f(x)Lagrange
Chebyshev
Figure 2: Phenom`ene de Runge. Interpolation de Lagrange avec des noeuds equidistants (trait discontinu) ainsi que les noueds de Chebyshev (traitpointill´e).3 Forme de Newton du polynˆome d"interpolation
La forme de Lagrange (2) du polynˆome d"interpolation n"estpas la plus commode d"un point de vue pratique. Dans cette partie on introduira une autre expression du mˆeme polynˆome d"interpolation. Soient (xi,yi)ni=0,n+ 1 couples, o`u on noterayi=f(xi). Le but est de repr´esenter le polynˆome d"interpolation ? n? Pncomme la somme de ?n-1? Pn-1(associ´e aux noeuds x i, pouri= 0,···,n-1) et d"un polynˆomeqn? Pn. Donc n(x) = ?n-1(x) +qn(x), ce qui impliqueqn(xi) = ?n(xi)-?n-1(xi) = 0 pouri= 0,···,n-1 et doncqn? Pna la forme q n(x) =an(x-x0)···(x-xn-1).Le coefficientan, appel´en-i`eme diff´erence divis´ee de Newton, et not´e souventf[x0,···,xn],
a la forme suivante a n=f(xn)-?n-1(xn)?n(xn),
et se laisse calculer par r´ecurrence comme suit (4)f[x0,···,xn] :=f[x1,···,xn]-f[x0,···,xn-1] xn-x0. Il faut remarquer que?0?1 etyi=f(xi) =f[xi]. Le polynˆome d"interpolation deNewton est
(5) ? nf(x) =n? i=0? i(x)f[x0,···,xi].D"apr`es le th´eor`eme 1 d"existence et unicit´e du polynˆome d"interpolation, le polynˆome
d"interpolation de Newton (5) n"est rien d"autre qu"une autre forme du polynˆome de Lagrange. L"avantage de la formule de Newton est que les diff´erences divis´ees sont in- variantes par rapport `a la permutation des noeuds. Par consequent, pour rajouter un nouveau noeudxn+1, on n"a qu"`a rajouter au polynˆome ?nfle termean+1?n+1, ce quisignifie une considerable r´eduction du coˆut num´erique, par rapport `a l"impl´ementation de
la formule de Lagrange. L"algorithme suivant, obtenu `a partir de l"expression (4), permetde calculer d"une mani`ere r´ecursive, simple et pas du toutcoˆuteuse, les diff´erences divis´ees
de Newton. L"expression de l"erreur d"interpolation avec la formule de Newton est la suivante E n(x) =f(x)-?nf(x) =?n+1(x)f[x0,···,xn,x].4 Interpolation d"Hermite-Birkoff
On peut g´en´eraliser l"interpolation de Lagrange d"une fonctionfpour chercher un polynˆome (courbe) qui passe pas seulement par les points (xi,f(xi)), mais dont les d´eriv´ees coinci- dent `a certains points nodaux avec les d´eriv´ees de la fonctionf. On se donne donc (xi,f(k)(xi)), pouri= 0,···,netk= 0,···,mi. On notera souvent la k-i`eme d´eriv´ee def`a l"endroitxiparf(k)(xi) =y(k) i. SoitN:=?ni=0(1 +mi). Alors, on peut montrer qu"il existe un polynˆome uniqueHN-1? PN-1, le polynˆome d"interpolation de Hermite, tel que H (k)(xi) =y(k) i, i= 0,···,n k= 0,···,mi.Ce polynˆome s"´ecrit
HN-1(x) =n?
i=0m i? k=0y(k) iLik(x), avec les polynˆomes caract´eristiques d"HermiteLik? PN-1, d´efinis par d p dxpLik(xj) =?1,sii=jetk=p0,sinon.
L"erreur d"interpolation pour le polynˆome d"Hermite est donn´ee par f(x)-HN-1(x) =f(N)(?)N!?N(x),
avec??[a,b] et le polynˆome nodal ?N? PNN(x) := (x-x0)m0+1+···+ (x-xn)mn+1.
5 Interpolation de Lagrange par morceaux
On a vu par le ph´enom`ene de Runge, qu"on ne peut pas garantirla convergence uniforme du polynˆome d"interpolation de Lagrange ? n(f) vers la fonctionflorsquentend vers ?. Ce qu"on peut faire par contre, pour augmenter la pr´ecision, est d"introduire une sub-division de l"intervalle [a,b] enmsous-intervallesTj:= [zj,zj+1],j= 0,···,m-1, tel que [a,b] =?m-1 j=0Tj. Sur chaque sous-intervalleTjon utilise l"interpolation de Lagrange avecn+ 1 noeudsx(j) i,i= 0,···,n. Le polynˆome d"interpolation par morceaux, not´e (m)n(f), appartiendra alors `a l"espace X (m)n:=?g?C([a,b])/ g|Tj? Pn(Tj),j= 0,···,m-1?, et coincidera sur chaqueTjavec le polynˆome interpolant def|Tj, associ´e aux noeuds {x(j)i}ni=0. L"int´erˆet de cette approche est qu"on peut se limiter `a des polynˆomes d"interpolation
de bas degr´e, pour eviter les probl`emes li´es `a la stabilit´e et convergence de l"interpolation
de Lagrange. En effet, mˆeme pournpetit, on obtient une erreur suffissament petite, d`es quemest grand, comme le montre le th´eor`eme suivant Th´eor`eme 4Soitf?Cn+1([a,b]). Alors il existe un consantec >0telle que6 Splines
La m´ethode d"interpolation par splines consiste en une interpolation par morceaux, de- mandant `a la courbe interpolante plus de r´egularit´e globale. L"interpolation de Lagrange par morceaux a l"inconvenient, que le polynˆome d"interpolation ?(m)n(f) est continu, mais pas d´erivable. noeuds distincts. La fonctionsk?Ck-1([a,b])v´erifiant s k|[xi,xi+1]? Pk, i= 0,···,n-1, s"appelle une spline de degr´ek, correspondante aux noeuds{xi}ni=0. Une spline est donc une courbe r´eguli`ere, polynomiale parmorceaux et qui peut avoir desdiscontinuit´es `a lak-i`eme d´eriv´ee. Les conditions demand´ees `a la d´efinition pr´ec´edente
ne permettent pas de d´eterminer une spline de mani`ere unique. En effet, la restriction s ki(x) :=sk|[xi,xi+1]? Pkse laisse ´ecrire sous forme polynomiale (6)ski(x) =k? j=0? ij(x-xi)j, i= 0,···,n-1, ce qui requiert la connaissance de (k+1)ncoefficients?ij. Due a la r´egularit´e globale de la spline, on a (7)s(p) k,i-1(xi) =s(p) k,i(xi), i= 1,···,n-1, p= 0,···,k-1, ce qui montre qu"il reste (k+1)n-k(n-1) =k+ndegr´es de libert´e pour caract´eriser la spline. Si la spline doit interpoler une fonctionfaux noeuds{xi}ni=0, c.`a.d.sk(xi) =f(xi) ?i, il reste tout de mˆemek-1 degr´es de libert´e. Pour fixer la spline de mani`ere unique, on pourra poser les conditions suivantes :1)splines p´eriodiques(ont un sens sifest p´eriodique!), si
s (p) k(a) =s(p) k(b), p= 1,···,k-1.1)splines naturelles, si pourk= 2l-1,l?2
s (l+p) k(a) =s(l+p) k(b) = 0, p= 0,···,l-2. Une mani`ere de construire une spline a ´et´e donn´ee par lesformules (6),(7). Une autre mani`ere consiste `a d´ecomposer la spline `a l"aide d"une base de splines. En effet, en notant l"espace des splinesskpar S k:={sk?Ck-1([a,b])/ sk|[xi,xi+1]? Pk, i= 0,···,n-1}, on remarque quedimSk=n+k. L"approche consiste maintenant `a construire une base de splines{?l}k+n l=1? Sk.II. Int´egration num´erique
Si la fonctionf(x) est continue sur [a,b] et si on connaˆ?t sa primitiveF(x), on peut facilement calculer l"int´egrale `a l"aide de la formule deNewton-LeibnizI(f) :=?
b a f(x)dx=F(b)-F(a). Par contre, tr`es souvent on ne connaˆ?t pas la primitiveF(x) ou elle est trop compliqu´ee.Pour cette raison on fait appel `a des m´ethodes approch´eesde calcul d"int´egrales, appel´ees
formules de quadratureoud"int´egration num´erique. Le proc´ed´e usuel consiste `a remplacer
la fonction donn´ee sur [a,b] par une fonction d"interpolation ou d"approximationfn, qui sera plus facile `a int´egrer. On approche alorsI(f) par I n(f) :=I(fn) =? b a f n(x)dx.L"erreur de quadraturesera ainsi donn´ee par
b a ce qui montre qu"une bonne approximation de la fonctionfm`ene `a une bonne approxi- mation de l"int´egraleI(f). Ledegr´e d"exactituded"une formule de quadrature est d´efini comme le plus grand entierr?0 tel que I n(p) =I(p),?p? Pr. Dans les sections suivantes on pr´esentera des formules de quadrature interpolaires et dans le chapitre III des formules de quadrature approch´ees.7 Les formules de quadrature de Newton-Cotes
Ces formules sont bas´ees sur l"interpolation de Lagrange avec noeuds ´equidistants dans [a,b], soitxi:=x0+iH,i= 0,···,netH >0 le pas de discr´etisation. Dans le cas o`u les extr´emit´es de l"intervalle [a,b] font partie des noeuds, c.`a.d.x0=a,xn=bet H= (b-a)/n, on parle deformules ferm´ees. Sinon, c.`a.d. six0=a+H,xn=b-Het H= (b-a)/(n+ 2), alors on a desformules ouvertes. L"approche consiste maintenant `a prendre commefnle polynˆome d"interpolation de Lagrange ?nassoci´e aux noeuds{xi}.Ainsi on a
I n(f) =n? i=0f(xi)? b a l i(x)dx, o`uli? Pnest le polynˆome caract´eristique de Lagrange. Cette formule se laisse ´ecrire de fa¸con plus g´en´erale comme I n(f) =n? i=0? if(xi),avec?i:=? b a l i(x)dx. Les coefficients?is"appellent aussipoidset sont facilement calculables, vue que lesli sont des polynˆomes. On pr´esentra maintenant trois cas particuliers de cette formule pour n= 0,1 et 2. Formule du point milieu :n= 0,x0= (a+b)/2,H= (b-a)/2,l0? P0. I0(f) := (b-a)f?a+b
2? , E0(f) =H33f??(?), ??(a,b).
Formule du trap`eze :n= 1,x0=a,x1=b,H=b-a,l0,l1? P1. I1(f) :=b-a
2[f(a) +f(b)], E1(f) =-H312f??(?), ??(a,b).
Formule de Cavalieri-Simpson :n= 2,x0=a,x1= (a+b)/2,x2=b,H= (b-a)/2, l0,l1,l2? P2.
I2(f) :=b-a
6[f(a) + 4f?a+b2?
+f(b)], E2(f) =-H590f(4)(?), ??(a,b). En utilisant la th´eorie de l"interpolation, on note que lesformules d"int´egration inter- xf(x)a:=x0x1b:=x2 Figure 3: Int´egration num´erique avec la formule de Simpson.polaires, associ´ees `a une discr´etisation den+ 1 points, ont un d´egr´e d"exactitude au
moins ´egale `an. On verra dans le prochain chapitre que pour les formules d"int´egration approch´ees, comme la formule de quadrature de Gauss, on peut atteindre un degr´e d"exactitude ´egale `a 2n+ 1. L"ordre infinit´esimald"une formule de quadrature est le plus grand entierp?0, tel que|I(f)-In(f)|=O(Hp). Il mesure la pr´ecision de la formule, tandis que le degr´e d"exactitude d"une formule de quadrature mesure une sorte d"efficacit´e de la formule. Comme exemple pour la formule de Cavalieri-Simpson, l"ordre infinit´esimal est ´egale `a 5,