[PDF] Interpolation et intégration numérique

View - Download Interpolation et intégration numérique

Previous PDF

Next PDF

InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Interpolation et integration numerique

Pr. Lacroix

SEATECH

Universite de Toulon

12 mai 2014

1/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

1Interpolation

Calculs

Lagrange

Neville-Aitken

Dierences nies

Newton

2Erreur, choix, convergence

Erreur

Choix des points

Convergence

3Hermite et autresHermite

Autres

4Splines

Bernstein - Bezier

Courbe de Bezier

Splines

Splines cubiques

5Quadrature

Quadrature simple

Quadrature composite

Gauss 2/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Soitfune fonction de la variable reelle. On suppose que l'on conna^t les valeurs de (f(x0);:::;f(xn) et l'on cherche un polyn^omePtel que

P(xi) =f(xi);0in:

On appelle un tel polyn^ome unpolyn^ome d'interpolationdef aux pointsx0;:::;xn.Theoreme Une condition necessaire et susante pour qu'il existe un unique polyn^ome P de degre au plus n qui interpole f aux points x

0;:::;xnest que les abscisses x0;:::;xnsoient deux a deux

distinctes. 3/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Une premiere methode pour construire un tel polyn^ome est de considerer labase de Lagrangeassociee aux pointsx0;:::;xn: L i(x) =nY j=0; j6=i(xxj)=(xixj);0in; et alors d'ecrire P=nX i=0L i(x)f(xi): L'inconvenient ici est que lesLidependent denet donc si l'on veut ajouter de nouveaux points d'interpolation il faut recommencer les calculs. 4/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Une alternative est d'utiliser leSchema de Neville-Aitken: appelonsT(i) kle polyn^ome de degre au pluskqui interpolefaux pointsxi;:::;xi+k. Alors on demontre qu'a partir des premieres valeurs T(i)

0=f(xi);0in;

on peut calculer recursivement les autres polyn^omesT(i) kpar le schema T (i) k+1(x) =(xi+k+1x)T(i) k(x)(xix)T(i+1) k(x)x i+k+1xi;

0kn1;0ink1.

Schema en arbre

5/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Une autre methode consiste a utiliser lesdierences divisees: elles sont denies recursivement par 8< :[xi]f=f(xi) i+kxi et permettent ensuite d'exprimer le polyn^ome d'interpolation P(x) = [x0]f+ (xx0)[x0;x1]f+ (xx0)(xx1)[x0;x1;x2]f +:::+ (xx0):::(xxn1)[x0;:::;xn]f: Cette methode permet aussi d'ajouter des points d'interpolation facilement. 6/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Dans le cas des points equidistants, on denit

0f(xi) =f(xi) puis

k+1f(xi) = kf(xi+1)kf(xi). Alors puisquexi=x0+ih, on a k!hk[xi;:::;xi+k]f= kf(xi); et alors le polyn^ome d'interpolationPs'exprime a l'aide de la formule de Newton

P(x) =f(x0) + (xx0)f(x0)1!h+ (xx0)(xx1)2f(x0)2!h2

+:::+ (xx0):::(xxn1)nf(x0)n!hn 7/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature On suppose que les points d'interpolationx0;:::;xn, parfois appeles lesnoeuds, appartiennent a un intervalleIola fonctionf est denie.Theoreme Si f est n+ 1fois derivable sur I, alors il existe(x)2I tel que f(x)P(x) =v(x)(n+ 1)!f(n+1)((x));v(x) =nY i=0(xxi):

Et donc

max

x2Ijf(x)P(x)j 1(n+ 1)!maxx2Ijv(x)jmaxx2Ijf(n+1)(x)j:On observe donc que pour optimiser l'erreur independamment de

f, on peut jouer sur le choix des pointsxi. 8/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature On suppose, quitte a faire un changement de variable ane, que I= [1;+1]. Pour minimiser maxx2[1;+1]jv(x)j, il faut choisir pourxiles zeros despolyn^omes de Tchebytchev: T

0(x) = 1;T1(x) =x;

T n+1(x) = 2xTn(x)Tn1(x);n1:

On montre queT

nest de degrenet sur [1;+1],Tn(x) = cos(narcos(x));parmi les les polyn^omes de degren+ 1 ayant un coecient de

plus haut degre egal a 1, et toutes leurs racines reelles et distinctes dans [1;1],Tn(x)=2nest celui qui minimise max jxj1jv(x)j.le choix optimal des points d'interpolation consiste donc a prendre les racines deTnqui sont les x i= cos2i+ 12n+ 2 ;Oin: 9/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Theoreme

Quelles que soient les choix successifs(x(n)

i)0in, il existe f continue sur I telle que max x2Ijf(x)Pn(x)j90: Quelle que soit f continue sur I, il existe un choix de ((x(n) i)0in)n1tel que max x2Ijf(x)Pn(x)j !0:

Si f a en outre une derivee k

iemecontinuesur[1;+1], k1, alors si l'on choisit les zeros des polyn^omes de Techbytchev, max jxj1jf(x)Pn(x)j=oln(n)n k 10/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature On appellepolyn^ome d'interpolation d'Hermitedefaux noeudsx0;:::;xnun polyn^omePde degr 'e au plus 2n+ 1 satisfaisant a

P(xi) =f(xi);P0(xi) =f0(xi);0in:Theoreme

Il existe un unique polyn^ome d'interpolation d'Hermite ssi x

0;:::;xnsont deux a deux distincts. Alors

P(x) =nX

i=0H i(x)f(xi) +nX i=0V i(x)f0(xi); avecH i(x) = (12(xxi)L0i(xi))L2i(x);V i(x) = (xxi)2L2i(x);L i(x) =Q j6=i(xxj)=(xixj).11/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Theoreme

Si f est2n+ 2fois contin^ument derivable sur I, alors il existe (x)2I tel que f(x)P(x) =v2(x)(2n+ 2)!f(2n+2)((x));v(x) =Y i(xxi):12/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature }Interpolation par des fractions rationnelles(dierences reciproques) : (i)

1= 0 et(i)

0=f(xi);

(i) k+1=(i+1) k1+xi+k+1xi (i+1) k(i) k;A

1(x) = 1;A0(x) =(0)

0;B1(x) = 0;B0(x) = 1;A

k+1(x) = ((0) k+1(0) k1)Ak(x) + (xxk)Ak1(x);B k+1(x) == ((0) k+1(0) k1)Bk(x) + (xxk)Bk1(x). AlorsA2k;A2k+1;B2k+1sont des polyn^omes de degre au plusk, etB2kde degre au plusk1 sous certaines conditions d'existence, et R n(x) =An(x)=Bn(x) interpolefenx0;:::;x2n. 13/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature |Interpolation par des fonctions quelconques : Mulbach: on se donneg0(x);:::;gn(x) et on cherche g(x) =a0g0(x) +:::+angn(x) telle quef(xi) =g(xi);0in:

On generalise l'algorithme de Neville-Aitken :P

(i)

0(x) =f(xi)g0(x)=g0(xi),i= 0:::;g

(i)

0;j(x) =gj(xi)g0(x)=g0(xi)gj(x),i= 0:::;j= 1:::;P

(i) k+1(x) =g(i+1) k;k+1(x)P(i) k(x)g(i) k;k+1(x)P(i+1) k(x)g (i+1) k;k+1(x)g(i) k;k+1(x),i;k0;g (i) k+1;j(x) =g(i+1) k;k+1(x)g(i) k;j(x)g(i) k;k+1(x)g(i+1) k;j(x)g (i+1) k;k+1(x)g(i) k;k+1(x), i;k0;jk+ 2.

Si aucune division par 0 n'appara^t, on aura

P(x) =P(0)n(x):

14/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Plut^ot que d'augmenter le degre du polyn^ome d'interpolation pour ameliorer l'approximation de la fonction, on peut proceder en subdivisant l'intervalleIet en choisissant sur chacun des sous-intervalles un polyn^ome d'interpolation de faible degre, en demandant aux polyn^omes choisis ainsi qu'a leurs derivees jusqu'a un certain ordre de se raccorder aux points de la subdivision. On parle alors desplines. 15/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Lespolyn^omes de Bernsteinsont donnes par

B nk(x) =Cknxk(1x)nk;0kn:

Ils forment une base deRn(X) et satisfontP

kBnk(x) = 1. Un polyn^ome de degre au plusnse represente donc sous la formePn i=0biBni(x) : on l'appelle larepresentation de Bezier deP, les coecients etant les coecients de Bezier deP. On calcule les polyn^omes de Bernstein par recurrence gr^ace a la formule B n+1 k(x) = (1x)Bnk(x) +xBnk1(x): 16/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Six= (xn)0npest une suite, on pose x= (xn+1xn)0np1.

SiP(x) =Pn

i=0aixi=Pn k=0bkBnk(x), alors sib

0=a0;a

(i) k=bk, 0kLes points ( in ;bi) sont lespoints de Bezieroupoints de contr^oleet la ligne polygonale qui les relie s'appelle le polygone de Bezier deP. Le deplacement de ces points permet de modier l'allure de la courbe deP: utilisation en CAO. 17/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature L'algorithme de De Casteljau permet de calculer recursivement les valeurs et les derivees dePen tout point :b r;s(x) =Ps i=rbiBsr ir(x);on abr;r(x) =br;b r;s(x) = (1x)br;s1(x) +xbr+1;s(x);r0;n(x) =P(x);P(k)(x) =n!(nk)!kb0;n(x); le portant sur le premier indice. Le representation de Beziers et l'algorithme de De Casteljau s'etendent aux courbes parametrees et aux surfaces. 18/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature On appelle courbe de Bezier associee aux pointsP0;:::;Pn2R2 la courbe parametree t7!nX k=0B nk(t)Pk:

Elle s'obtient recursivement parB

0(Pk)(t) =Pk;B

k(Pi;:::;Pi+k)(t) = (1t)Bk1(Pi;:::;Pi+k1)(t) +tBk1(Pi+1;:::;Pi+k)(t). Son image est contenue dans l'enveloppe convexe deP0;:::;Pn.19/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature A l'aide de l'algorithme de De Casteljau, on peut interpoler une fonctionfen des points d'un intervalle [a;b], et sur chaque sous-intervalle ainsi deni, approcherfpar une courbe de Bezier de faible degre, avec des conditions de raccord aux points d'interpolation. On peut aussi sur chacun des sous intervalles inserer des points de contr^olePiqui permettent ensuite de modier l'allure de la courbe en CAO tout en gardant les conditions de raccord et d'interpolation... 20/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

SoitD=fx0;:::;xn+1gune subdivision de [a;b]

(x0=a;xn+1=b). Une fonctionS: [a;b]!Rest unefonction spline de degrekpar rapport aDssi elle est polynomiale de degre au plusksur chaque sous intervalle de la subdivision, et de classeCk1sur [a;b]. Elle est ditespline naturelle de degre2k1 par rapport aDsi c'est un poly^ome de degre 2k1 au plus sur chaque ]xi;xi+1[,

1in1, et de degre au plusk1 sur [a;x1[ et ]xn;b], et si

elle est de classeC2k2sur [a;b].

On montre que ceci equivaut a ce que

S(x) =p0(x) +nX

i=1a i(xxi)2k1+ oup0est un polyn^ome de degre au plusk1,y+= max(y;0), etPn i=1aixj i= 0, 0jk1. 21/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Les splines cubiques correspondent ak= 3 ou 2k1 = 3. Pour les splines cubiques naturelles, sihi=xi+1xi, 1in1, alors

S(x) =pi(x) =zi+1h

i(xxi)3+zi6hi(xi+1x)3 yi+1h ihi6 zi+1)(xxi) + (yih ihi6 zi)(xi+1x) sur [xi;xi+1], 1in1, etSest ane sur [a;x1[ et determinee pary1etp01(x1), idem sur [xn;b]. La theorie se developpe en produisant une base de splines pour une partition donnee et un degre donne, ditesB-splines. 22/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

On va chercher a obtenir une valeur approchee de

I=Rb af(x)w(x)dxouw(x)>0 sur [a;b]. On peut proceder en remplacantfpar un de ses polyn^omes d'interpolation, on parle alors dequadrature de type inerpolation. On subdivise [a;b] enn+1 intervalles [xi;xi+1] et on notePn(x) le polyn^ome d'interpolation defaux noeudsxi. Alors f(x) =Pn(x) +En(x), et Z b a f(x)w(x)dx=Z b a P n(x)w(x)dx+Z b a E n(x)w(x)dx:

CommePn(x) =Pn

i=0f(xi)Li(x), il vient

I=In+Rn;In=nX

i=0f(xi)Z b a L i(x)w(x)dx |{z} A (n) i;Rn=Z b a E n(x)w(x)dx: 23/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Le calcul desA(n)

ipeut se faire autrement, en resolvant le systeme de Van der Monde : n X i=0A(n) ixki=Z b a tkdt;0kn1:Proposition

Si f est un polyn^ome de degre au plus n, alors I

n=I.On dit que la quadrature estexactepour les polyn^omes de degre n. Sonordreest egal a l'entierm+ 1 le plus grand tel que la formule soit exacte pour tous les polyn^omes de degrem. Choisissonsh= (ba)=netxi=a+ih. Il s'agit pour determiner la quadrature associee de calculer lesA(n) i. 24/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature Lorsquew(x) = 1 ces coecients sont donnes dans des tables. On appelle les quadratures associees lesformules de Newton-Cotes. Plusieurs questions se posent : celle de laconvergenceIn!I pour certaines classes de fonctionsf, et celle de lastabilite: supposons que l'ordinateur genere des erreurs et que l'on caclculePn i=0A(n) i(f(xi) +i), alors l'erreur vaut n X i=0A(n) ii:Denition On dit que la quadrature eststablesi il existe M telle que pour tout n eti,nX i=0A(n) iij Mmax0injij:25/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Theoreme

Une CNS pour qu'une methode de quadrature soit convergente sur C

1[a;b]est quea) elle soit convergente lorsque f est un polyn^ome;

b) il existe M telle que pour tout n, n X i=0jA(n) ij M:26/39 InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature

Theoreme

Une CNS de stabilite est que la condition b) precedente soit satisfaite.Theoreme La methode de Newton-Cotes n'est ni stable ni convergente sur C

1[a;b].27/39

InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature |Methode du trapeze. Pour palier a la non convergence de

Newton-Cotes, on ecritZb

a f(x)dx=Z x1 x

0f(x)dx+:::+Z

xn x n1f(x)dx et on calcule separement chacune des integrales par une approximation. C'est une methodecomposite. Le methode du trapeze consiste a calculer chacune de ces integrales par la formuleZxi+1 x if(x)dx=xi+1xi2 (f(xi) +f(xi+1)): Si l'on choisit les abscisses equidistantes, on obtient I n=h2 f(a) + 2n1X i=1f(a+ih) +f(b)!

On montre queI

nI=(ba)312n2f00(); 2[a;b]; 28/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature etA(n)

0=A(n)n=h=2,A(n)

i=hsi 1in1, et donc n X i=0jA(n) ij=ba:Proposition La methode des trapezes est stable et convergente. On peut aussi appliquer sur chaque sous-intervalle la methode de

Simpson, qui est Newton-Cotes a trois noeuds :

Z b a g(t)dtba6 f(a) + 4fa+b2 +f(b) ~I:

Alors l'erreur vautI~I=f(4)()2880

(ba)5. Elle est egalement stable et convergente. 29/39
InterpolationEr reur,ch oix,c onvergenceHer miteet au tresSp linesQu adrature On va chercher a accelerer la convergence dans la methode des trapezes. C'est l'objet de la methode de Romberg. On noteT(h) la valeur approchee deIpar la methode desquotesdbs_dbs19.pdfusesText_25

[PDF] interpolation d'hermite démonstration

[PDF] interpolation d'hermite matlab

[PDF] interpolation d'hermite pdf

[PDF] interpolation de lagrange en langage c

[PDF] interpolation de lagrange en ligne

[PDF] interpolation de lagrange exercice corrigé

[PDF] interpolation de lagrange matlab

[PDF] interpolation de lagrange python

[PDF] interpolation entre deux valeurs

[PDF] interpolation et approximation polynomiale

[PDF] interpolation formule

[PDF] interpolation graphique

[PDF] interpolation image

[PDF] interpolation lagrangienne

[PDF] interpolation linéaire casio graph 35+