Interpolation polynomiale (notes de cours) - Lamfa


PDF
List Docs
PDF 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

PDF 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

PDF 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 

PDF 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) 

PDF 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 

Share on Facebook Share on Whatsapp











Choose PDF
More..












CMI, Universit´e de ProvenceAgr´egation de Math´ematiques Ann´ee 07-08Option Calcul scientifique et mod´elisation

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 un

polynˆ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 a

On 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+b

2+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 p

nne 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 de

Chebyshev 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 de

Newton 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 qui

signifie 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), permet

de 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

H

N-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=p

0,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? PN

N(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 que

6 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 des

discontinuit´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-Leibniz

I(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. I

0(f) := (b-a)f?a+b

2? , E

0(f) =H33f??(?), ??(a,b).

Formule du trap`eze :n= 1,x0=a,x1=b,H=b-a,l0,l1? P1. I

1(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, l

0,l1,l2? P2.

I

2(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,
TP interpolation polynomiale Série d 'exercices no5/6 Interpolation polynomiale TP5 : Les fonctions sous MATLAB et l 'interpolation - Institut de Chapitre II Interpolation et Approximation Python et les math (n 3) - Free Pautas y ejemplos de informe - Universidad de Concepción 29 El análisis sensorialpdf - Inta El Estudio de las Narraciones en las Técnicas Proyectivas Verbales

PDFprof.com Search Engine
Images may be subject to copyright Report CopyRight Claim

Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement


Interpolation polynomiale (notes de cours) - PDF Téléchargement

Interpolation polynomiale (notes de cours) - PDF Téléchargement

Politique de confidentialité -Privacy policy