[PDF] Chapitre II Interpolation et Approximation
Chapitre II Interpolation et Approximation Le probl`eme de l'interpolation consiste `a chercher des fonctions “simples” (polyn?mes poly-
[PDF] Chapitre II Interpolation et Approximation
Interpolation et Approximation Cotes le publia comme dernier chapitre II 2: Fac-similé du calcul de Newton pour le probl`eme de l'interpolation
[PDF] I Interpolation - Institut de Mathématiques de Toulouse
Figure 1: Interpolation polynomiale et approximation d'un nuage de points Page 2 1 Forme de Lagrange du polynôme d'interpolation Soit a = x0
[PDF] Chapitre 2 Interpolation polynomiale
Pourquoi les polynômes ? 1 Théor`eme d'approximation de Weierstrass : pour toute fonction f définie et continue sur l'intervalle [a b]
[PDF] Chapitre II Interpolation et Approximation - PolytechnicEcom
Chapitre II Interpolation et Approximation Le probl`eme de l'interpolation consiste `a chercher des fonctions “simples” (polynômes poly-
[PDF] CHAPITRE II : Inroduction `a linterpolation
forme (xi ;f (xi )) 0 ? i ? n peut-on construire une approximation ? (polynômes polynômes par morceaux polynômes trigonométriques )
[PDF] annales scientifiques de léns - Numdam
Approximation et interpolation des fonctions différentiables de plusieurs variables Dans le chapitre II nous démontrons tout d'abord quelques résultats
[PDF] Interpolation et Approximation Polynômiale - Unblogfr
Plan du Chapitre 1 Introduction 2 Polynômes de Lagrange 3 Polynômes de Newton 4 Erreur d'interpolation 5 Conclusion
[PDF] Interpolation polynomiale - mathuniv-paris13fr
Chapitre 2 : Interpolation polynomiale 2 1 Approximation d'une fonction par son polynôme de Taylor au voisinage d'un point
[PDF] CHAPITRE 4 INTERPOLATION ET APPROXIMATION
?i p(xi) ? fi2 soit minimal • On cherche `a calculer une intégrale dont on ne conna?t pas explicitement sa valeur Par exemple on approche cette comme
Chapitre II Interpolation et Approximation
Chapitre II Interpolation et Approximation Probleme de l’interpolation :` on recherche des fonctions “simples” (polynoˆmes polynoˆ mes par morceaux polynoˆmes trigonome´triques) passant par (ou proche) des points donne´s (x0y0)(x1y1) (xnyn) (0 1) c -a`-d on cherchep(x) avec p(xi) = yipour i= 01 n
Université de Genève - Université de Genève
Learn the basics of interpolation and approximation with this chapter from a course on numerical analysis featuring examples and exercises (PDF)
Chapitre IIInterpolation et ApproximationProbl`eme de l'interpolation :on recherche des fonctions "simples" (polynˆomes, polynˆomes par
morceaux, polynˆomes trigonom´etriques) passant par (ou proche) des points donn´es (x0,y0),(x1,y1),...,(xn,yn),(0.1) c.-`a-d., on cherchep(x)avecp(xi) =yipouri= 0,1,...,n. Si les valeurs deyisatisfontyi=f(xi)o`uf(x)est une fonction donn´ee, il est alors int´eressant d'´etudier l'erreur de l'approximation
f(x)-p(x) = ?(0.2)Bibliographie de ce chapitre
J.H. Ahlberg, E.N. Nilson & J.L. Walsh (1967):The Theory of Splines and Their Applications.Academic Press, New York. [MA 65/4]
C. de Boor (1978):A Practical Guide to Splines. Springer-Verlag. [MA 65/141] G.D. Knott (2000):Interpolating Cubic Splines.Birkh¨auser. [MA 65/431] H.J. Nussbaumer (1981):Fast Fourier Transform and Convolution Algorithms. Springer-Verlag. H. Sp¨ath (1995):One Dimensional Spline Interpolation.AK Peters. [MA 65/362]II.1 Diff
´erences divis´ees et formule de Newton
``...tho' I will not undertake to prove it to others." (Newton, letter to Collins, Nov. 8, 1676 ; publ. Cotes 1711, p. 38) Probl `eme (Newton 1676).´Etant donn´es lesn+ 1points (0.1), chercher un polynˆome p(x) =axn+bxn-1+cxn-2+...(1.1) de degr´enqui satisfasse p(xi) =yipouri= 0,1,...,n.(1.2)Pour un exemple voir la fig.II.1.
Interpolation et Approximation25
2 4 6 8 10
-50510 p(x) FIG. II.1:Polynˆome d'interpolation de degr´e5 Solution.En ins´erant les conditions (1.2) dans (1.1), le probl`eme se transforme en un syst`eme lin´eaire (`a matrice du type Vandermonde; ici ´ecrit pourn= 2) c+bx0+ax20=y0 c+bx1+ax21=y1 c+bx2+ax22=y2soustraire et diviserb+a(x1+x0) =y1-y0 x1-x0 b+a(x2+x1) =y2-y1 x2-x1(1.3) et, si on soustrait et divise une deuxi`eme fois, on trouve a=1 x2-x0? y2-y1x2-x1-y1-y0x1-x0?.(1.4)Le mˆeme calcul a ´et´e effectu´e pourn= 4dans un manuscript de Newton datant de 1676; comme `a
l'accoutum´ee, Newton refusa de le publier (voir citation). Cotes le publia comme dernier chapitre
Methodus differentialisdu livreAnalysis per quantitatum series, fluxiones, ac differentias, Londini1711 (voir fac-simil´e en figure II.2
1). FIG. II.2:Fac-simil´e du calcul de Newton pour le probl`eme de l'interpolation Dans tous ces calculs apparaissent les "diff´erences divis´ees" :1On peut observer que Newton maˆıtrise les ´eliminations de variables dans un syst`eme lin´eaire avec brio ; plus tard,
toute la gloire pour cette m´ethode reviendra `a Gauss.26Interpolation et Approximation
D ´efinition 1.1 (diff´erences divis´ees)Pour(xi,yi)donn´es (xidistincts) on d´efinit y[xi] :=yiδy[xi,xj] :=y[xj]-y[xi]
xj-xi2y[xi,xj,xk] :=δy[xj,xk]-δy[xi,xj]
xk-xi3y[xi,xj,xk,xl] :=δ2y[xj,xk,xl]-δ2y[xi,xj,xk]
xl-xietc. tion (voir citation) : Th ´eor`eme 1.2 (formule de Newton)Le polynˆome d'interpolation de degr´enqui passe par les n+ 1points(x0,y0),(x1,y1),...,(xn,yn), o`u lesxisont distincts, est unique et donn´e par p(x) =y[x0] + (x-x0)δy[x0,x1] + (x-x0)(x-x1)δ2y[x0,x1,x2] +...+ (x-x0)(x-x1)·...·(x-xn-1)δny[x0,x1,...,xn].(1.5) D´emonstration.Nous utilisons deux id´ees :
1. On proc
`ede par r´ecurrence.Pourn= 1, et en tenant compte des premiers deux points, nous avons p(x) =y0+ (x-x0)y1-y0 x1-x0.(1.6)Il s'agit d'une formule bien connue des G´eom`etres (voirΓ?ωμ?τρ´ια, figure II.1.8).
Puis, pourn= 2, en rajoutant le point(x2,y2), on essaie de bˆatir l`a dessus un polynˆome de degr´e 2, qui ne change plus les valeurs dey0et dey1. Il est donc de la forme p(x) =y0+ (x-x0)y1-y0 x1-x0+a·(x-x0)(x-x1) 2 405 (1.7)o`u le coefficientaest `a d´eterminer. Mais il s'agit du coefficient dex2dep(x): nous savons d´ej`a
(voir (1.4)) que celui-ci est la deuxi`eme diff´erence divis´eeδ2y[x0,x1,x2]. Pour d´emontrer le cas g´en´eral, nous supposons que p1(x) =y[x0] + (x-x0)δy[x0,x1] +...+ (x-x0)·...·(x-xn-2)δn-1y[x0,x1,...,xn-1]
soit le polynˆome unique de degr´en-1qui passe par(xi,yi)pouri= 0,1,...,n-1. Alors, comme auparavant, le polynˆomep(x)a n´ecessairement la forme p(x) =p1(x) +a·(x-x0)(x-x1)·...·(x-xn-1), o`uaest d´etermin´e parp(xn) =yn.2.L'id
´eedeAitken-Neville.Pourmontrerquea=δny[x0,x1,...,xn], cequiach`evelad´emonstra- tion, nous consid´erons ´egalement le polynˆome de degr´en-1 p2(x) =y[x1] + (x-x1)δy[x1,x2] +...+ (x-x1)·...·(x-xn-1)δn-1y[x1,x2,...,xn],
Interpolation et Approximation27
2 4 6 8 10
-10-50510 p(x) p 2(x)p 1(x) FIG. II.3:Les polynˆomesp1(t),p2(t)etp(t)de l'algorithme d'Aitken-Neville qui passe par(xi,yi)pouri= 1,...,n(voir figure II.3). Ensuite, on pose (Aitken - Neville, 1929, 19322) p(x) =1 xn-x0?(xn-x)p1(x) + (x-x0)p2(x)?.(1.8)
Il s'agit d'un polynˆome de degr´en, qui satisfait la condition (1.2) pour le pointx0(ici, le facteur
(x-x0)est nul), pour le pointxn(ici, le facteur(x-xn)est nul), et pour les pointsx1,...,xn-1(ici, les deux polynˆomesp1etp2sont ´egaux `ayi). Le polynˆome d´esir´e est donc trouv´e.
En consid´erant le coefficient dexndans (1.8), nous obtenons a=1 ce qui d´emontre la formule (1.5). TAB. II.1:Diff´erences divis´ees pour les donn´ees de la fig.II.1 xiyiδy δ2y δ3y δ4y δ5y0-1121 3/85/2-77/12046-17/6 167/960-6 3/4-287/960050 5/3-1/82/3-1/482 1/63/2105
Exemple 1.3Pour les donn´ees de la fig.II.1, les diff´erences divis´eessont pr´esent´ees dans le
tableau II.1. Le polynˆome d'interpolation est alors donn´e par p(x) =-1 +x+x(x-2)3 -x(x-2)(x-4)(x-5)(x-8)287 9600.ou mieux encore pour la programmation (ou le calcul `a la main) p(x) =-1 +x?1 + (x-2)?3
8+ (x-4)?-77120+ (x-5)?167960-(x-8)2879600????.
2Il fallait plus de deux si`ecles pour avoir cette id´ee !...
28Interpolation et Approximation
Remarque.L'ordre des{xi}n'a aucune importance pour la formule de Newton (1.5). Si l'onpermute les donn´ees(xi,yi), on obtient ´evidemment le mˆeme polynˆome. Pour l'exempleci-dessus
et pour les{xi}choisis dans l'ordre{4,5,2,8,0,10}, on obtient ainsi p(x) = 6 + (x-4)?-6 + (x-5)?-176+ (x-2)?34+ (x-8)?167960-x2879600????.
En observant queδny[xi0,...,xin]est une fonction sym´etrique de ses arguments (par exemple,2y[x2,x3,x1] =δ2y[x1,x2,x3], voir exercices), on peut utiliser les valeurs calcul´ees dans le
tableau II.1. Sixest entre4et5, les deux facteursx-4etx-5dans laformulepr´ec´edente sont relativement petits, ce qui favorise la diminution des erreurs d'arrondi.II.2 Erreur de l'interpolation
Supposons que les points(xi,yi)soient sur le graphe d'une fonctionf: [a,b]→IR, c.-`a-d., y i=f(xi), i= 0,1,...,n,(2.1)´etudions alors l'erreurf(x)-p(x)du polynˆome d'interpolationp(x). Deux exemples sont donn´es
dans la fig.II.4. A gauche, on voit un polynˆome d'interpolation pour la fonctionf(x) = sinx, et`a droite pour la fonction1/(1 +x2). Pour mieux rendre visible l'erreur, on a dessin´e la fonction
f(x)en une courbe pointill´ee.0 2 4 6 8
-101 -4 -2 0 2 401 f(x) = sinxf(x) =11 +x2 FIG. II.4:Polynˆome d'interpolation poursinx(gauche) et pour1/(1 +x2)(droite) Lesr´esultatssuivantssontdus `aCauchy(1840,Surlesfonctionsinterpolaires,C.R. XI,p. 775-789,Oeuvresser. 1, vol. V, p. 409-424). Commenc¸ons par une relation int´eressante entre les diff´erences
divis´ees pour (2.1) et les d´eriv´ees de la fonctionf(x). Lemme 2.1Soitf(x)n-fois diff´erentiable etyi=f(xi)pouri= 0,1,...,n(xidistincts). Alors, il existe unξ?(minxi,maxxi)tel que ny[x0,x1,...,xn] =f(n)(ξ) n!.(2.2) D ´emonstration.Soitp(x)le polynˆome d'interpolation de degr´enpassant par(xi,yi)et notons d(x) =f(x)-p(x). Par d´efinition dep(x), la diff´erenced(x)s'annule enn+ 1points distincts : d(xi) = 0pouri= 0,1,...,n.Interpolation et Approximation29
Commed(x)est diff´erentiable, on peut appliquernfois le th´eor`eme de Rolle (voir le cours d'Analyse I) et on en d´eduit que d ?(x)anz´eros distincts dans(minxi,maxxi).Le mˆeme argument appliqu´e `ad?(x)donne
d ??(x)an-1z´eros distincts dans(minixi,maxixi), et finalement encore d (n)(x)a1z´ero dans(minixi,maxixi).Notons ce z´ero ded(n)(x)parξ. Alors, on a
f (n)(ξ) =p(n)(ξ) =n!·δny[x0,x1,...,xn].(2.3)La deuxi`eme identit´e dans (2.3) r´esulte du fait queδny[x0,x1,...,xn]est le coefficient dexndans
p(x).Th´eor`eme 2.2Soitf: [a,b]→IR(n+ 1)-fois diff´erentiable et soitp(x)le polynˆome d'interpo-
lation de degr ´enqui passe par(xi,f(xi))pouri= 0,1,...,n. Alors, pourx?[a,b], il existe unξ?(min(xi,x),max(xi,x))tel que
f(x)-p(x) = (x-x0)·...·(x-xn)·f(n+1)(ξ) (n+ 1)!.(2.4) D ´emonstration.Six=xipour un indicei? {0,1,...,n}, la formule (2.4) est v´erifi´ee car p(xi) =f(xi). Fixons alors un¯xdans[a,b]qui soit diff´erent dexiet montrons la formule (2.4) pourx= ¯x.L'id´ee est de consid´erer le polynˆome¯p(x)de degr´en+ 1qui passe par(xi,f(xi))pouri=
0,1,...,net par(¯x,f(¯x)). La formule de Newton donne
¯p(x) =p(x) + (x-x0)·...·(x-xn)·δn+1y[x0,...,xn,¯x].(2.5)Si l'on remplace la diff´erence divis´ee dans (2.5) parf(n+1)(ξ)/(n+ 1)!(voir le lemme pr´ec´edent)
et si l'on posex= ¯x, on obtient le r´esultat (2.4) pourx= ¯xcar¯p(¯x) =f(¯x). Comme¯xest
arbitraire, la formule (2.4) est v´erifi´ee pour toutx. Exemple 2.3Dans la situation de la fig.II.4, on an+ 1 = 7. Comme la7`emed´eriv´ee desinxest born´ee par1, on a que 7!, par exemple Pour le deuxi`eme exemple,f(x) = 1/(1 +x2), la7`emed´eriv´ee est donn´ee par f (7)(x) =-8!·(x+ 1)(x-1)x(x2-2x-1)(x2+ 2x-1) (1 +x2)8, qui est maximale pourx≈ ±0.17632698. On obtient ainsi ?p(x)-1 Alors, l'erreur peut ˆetre4392fois plus grande que pour l'interpolation desinx.30Interpolation et Approximation
Convergence de l'interpolation.
Une grande surprise en math´ematiques fut la d´ecouverte, d'abord par Riemann (1854), puis par Weierstrass (1872), de l'incroyable complexit´e qu'ont certaines fonctions continues, p.ex., de n'ˆetre nulle part diff´erentiables; puis la deuxi`eme grande surprise: toutes ces fonctions, aussi compliqu´ees qu'elles puissentˆetre, peuvent ˆetre approch´ees, aussi pr`es qu'on le veutet uniform´ement, par les fonctions les
plus simples qui existent, des polynˆomes (Weierstrass 1885; voir [HW96],§III.9); personnenepensait alorsque lespolynˆomesd'interpolation,si on prend seulementles points suffisamment proches les uns des autres, ne convergeaient pas vers la fonction donn´ee. Lad´ecouverte que cela n'est mˆeme pas assur´e pour les fonctions rationnelles, les deuxi`emes
fonctions les plus simples, (voir dessin de figure II.5), a choqu´e ´enorm´ement les math´emati-
ciens vers 1900 (en particulier E. Borel).Carl David Tolm´e Runge (1856-1927), premier prof de maths appliqu´ees de l'histoire et, en tant
qu'´el`eve de Weierstrass, ayant aussi une solide formation en maths pures, fut certes l'hommeid´eal pour expliquer ce ph´enom`ene de mani`ere claire et ´el´egante (1901,Zeitschr. Math. u. Physik
vol. 46).quotesdbs_dbs7.pdfusesText_13[PDF] H3 anc Millikan
[PDF] Correction de l 'exercice ONDES SISMIQUES
[PDF] Dureté d 'une eau - Dosage complexométrique - Nicole Cortial
[PDF] exercices sur les pyramides - euclidesfr
[PDF] limites de suites - Maths-et-tiques
[PDF] Statistiques - Logamathsfr
[PDF] EXERCICES DE CHIMIE GÉNÉRALE
[PDF] I Effectif et fréquence II Représentations graphiques - college
[PDF] exercices - euclidesfr
[PDF] I) Détermination de la capacité thermique d 'un calorimètre: Un
[PDF] calculer un angle a partir de la loi de descartes - Physagreg
[PDF] Cours 5 : ESTIMATION PONCTUELLE
[PDF] Calcul des coûts
[PDF] chiffre d 'affaires, panier moyen, et - L 'Etudiant