[PDF] Résolution numérique des Équations Différentielles Ordinaires

View - Download Résolution numérique des Équations Différentielles Ordinaires

Previous PDF

Next PDF

Résolution numérique des Équations

Différentielles Ordinaires

L3 Mapi

3

Christophe Besse

Copyright

c

2016 Christophe BesseLicensed under the Creative Commons Attribution-NonCommercial 3.0 Unported License (the "License").

You may not use this file except in compliance with the License. You may obtain a copy of the License

athttp://creativecommons.org/licenses/by-nc/3.0. Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an"as is" basis, without warranties or conditions of any kind, either express or implied. See the License for the specific language governing permissions and limitations under the License.

First printing, November 2016

Table des matières

1Interpolation polynomiale.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1 Interpolation de Lagrange

5

1.2 Étude de l"erreur d"interpolation et stabilité

6

1.3 Calcul pratique du polynôme d"interpolation de Lagrange

9

1.3.1 Différences divisées

10

1.3.2 Algorithme de Horner

11

1.4 Exercices12

2Intégration numérique.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1 Formules de quadrature et leur ordre

15

2.2 Étude de l"erreur

19

2.3 Formules d"ordre supérieur

23

2.4 Polynômes orthogonaux de Legendre

24

2.5 Formule de quadrature de Gauss

24

2.6 Exercices25

3EDO - Introduction.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4La méthode d"Euler.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.1 Exemples35

4.2 Le cas général

37

4.3 Analyse de la méthode

38

4.4 Le schéma d"Euler implicite

44

4.4.1 Consistance

44

4.4.2 Stabilité

44

4.4.3 Convergence

45

4.5 Étude générale de l"erreur des méthodes à un pas45

4.6 Les méthodes de prédicteur-correcteur

47

4.7 Exercices49

5Les méthodes multi-pas.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.1 Introduction55

5.1.1 La règle des trapèzes

56

5.1.2 Méthode de Adams-Bashforth à 2 étapes AB(2)

56

5.2 Les méthodes à deux pas

56

5.2.1 Consistance

57

5.2.2 Construction

57

5.3 Méthodes àkétapes58

5.4 Convergence et (zéro)-stabilité

59

5.5 Familles classiques

60

5.5.1 Adams-Bashforth 1883

60

5.5.2 Famille Adams-Moulton 1926

61
61

5.5.4 Milne-Simpson 1926

61

5.5.5 Backward Differentiation Formulas (BDF) 1952

61

5.6 Exercices61

6Stabilité.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.1 Stabilité absolue - motivations

65

6.2 Stabilité absolue

67

6.3 Méthode de localisation de la frontière

70

6.4 A-stabilité71

6.5 Extension aux systèmes d"EDO

71

6.6 Exercices74

7Les méthodes de Runge-Kutta.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

7.1 Description de la méthode

77

7.2 Consistance79

7.2.1 Méthodes RK à une étape

79

7.2.2 Méthodes RK à deux étapes

80

7.2.3 Méthodes RK à trois étapes

81

7.2.4 Méthodes RK à quatre étapes

81

7.2.5 Méthodes implicites

81

7.3 Stabilité absolue

82

7.4 Méthodes implicites

83

7.5 Exercices85

Bibliographie.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Livres87

Index.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

1. Interpolation polynomialeOn dispose d"une série de couples de points(xi;fi),i2 f0;;ng. Le but de l"interpolation est de

contruire un polynômepqui prenne les valeursfiaux pointsxi. Si on suppose que les valeursfisont issues de l"évaluation d"une fonctionfenxi, nous tenterons de quantifier l"erreurjf(t)p(t)j.x 1x 2x 3x 4x 5

On ne présente ici que l"interpolation de Lagrange. Il en existe d"autres comme par exemple l"interpolation

de Hermite qui outre les valeursfis"interesse également aux valeurs de la dérivée enxi.

Notations

On notePnl"ensemble des polynômes d"une variable (réelle ou complexe) de degrén.Pnest un espace vectoriel de dimensionn+ 1 Soit [a;b]2R. On noteC0([a;b])l"ensemble des fonctions continues sur[a;b]et kfk1= sup x2[a;b]jf(x)j On n oteCm([a;b])l"ensemble des fonctions de classeCmsur[a;b]. 1.1

Inter polationde Lagrange

On considèren+ 1points distincts, pas nécessairement ordonnés(x0;x1;;xn)de[a;b]et on considère une fonctionf2C0([a;b]). Nous souhaitons répondre à la question Existe-t-il un polynômep2Pntel quep(xi) =f(xi),0in?

6Chapitre 1. Interpolation polynomialeDéfinition 1.1.1 - Polynômes de Lagrange.On définit les polynômes de Lagrange associés aux

points(x0;;xn)par l i(x) =(xx0)(xxi1)(xxi+1)(xxn)(xix0)(xixi1)(xixi+1)(xixn);0in; Y

0jn;j6=i(xxj)(xixj):(1.1)

On ali(xj) =ij8(i;j)2 f0;;ngoùijest le symbole de Kronecker, et degré(li) =n.

Proposition 1.1.1(l0;;ln)est une base dePn.

Preuve

Cette famille est évidemment génératrice. Le point clé est de savoir si elle est libre. Soit

(a0;;an)2Rn+1etx2R. Alors, siPn i=0aili(x)pour toutx, on a pour toutj,Pn i=0aili(xj) = 0.

Commeli(xj) =ij, cela impliqueaj= 0pour toutj.

Ainsi, la famille est libre et génératrice et c"est donc une base.Théorème 1.1.2 Le problème : trouverp2Pntel quep(xi) =f(xi),80inadmet une unique solution donnée par p(x) =nX i=0f(xi)li(x):(1.2) ps"appelle le polynôme d"interpolation de Lagrange, notépn.

Preuve

Existence : on vérifie aisément que le polynômepdonné par (1.2) répond à la question.

Unicité : soitq2Pntel queq(xi) =f(xi),80inetr=pq2Pn. On a ainsir(xi) = 0

80in. Il existe donc un polynômeAtel que

r(x)|{z} d n=A(x)(xx0)(xx1)(xxn)|{z} d (n+1):

Donc, siA6= 0,rdevrait être de degrén+ 1. La seule possibilité est queA0et doncr= 0.ROn posen+1(x) = (xx0)(xx1)(xxn). Alors

l i(x) =n+1(x)(xxi)0n+1(xi):(1.3) 1.2 Étude de l"err eurd"inter polationet sta bilité En pratique, on commet systèmatiquement des erreurs car un ordinateur ne travaille qu"avec un

nombre limité de chiffres significatifs. Il est donc important de connaître l"influence sur le résultat final

des erreurs commises sur les données. On remplace (ici volontairement) les vraies valeursf(xi)par des

valeurs approchéesfiet on regarde l"incidence surpn. On note ce nouveau polynôme d"interpolation

~pn(x) =Pn i=0fili(x). L"erreur commise est donc j~pn(x)pn(x)j= n X i=0(fifi(x))li(x) nX i=0jfifi(x)j jli(x)j maxijfifi(x))jnX i=0jli(x)j:

1.2 Étude de l"erreur d"interpolation et stabilité 7

On note la constante de Lebesgue associée aux pointsx0;;xn n= maxx2[a;b]n X i=0jli(x)j:

Ainsi,

k~pn(x)pn(x)k1nmaxijfifi(x)j: L"erreur commise sur lesf(xi)est donc amplifiée (ou atténuée) par la constante de Lebesgue. Proposition 1.2.1On introduit l"application linéaire L n:C0([a;b])!Pn f7!pnqui àf2C0([a;b])associe son unique polynôme d"interpolation de Lagrange aux pointsx0;;xn.

Alors, la norme deLnestn, c"est à dire

jjjLnjjj:= sup f2C0([a;b]) f6= 0kLn(f)kkfk1= n:

Preuveon commence par montrerjjjLnjjj n. On a

jLn(f)(x)j=jpn(x)j= n X i=0f i(x)li(x) nX i=0jfi(x)j jli(x)j kfk1n X i=0jli(x)j nkfk1: Pour obtenir l"égalité, on se demande s"il existe une fonctionf2C0([a;b])telle quekLn(f)k1= nkfk1. Il n"est pas du tout sur qu"une telle fonction existe car lesuppeut ne pas être atteint.

Supposons que c"est le cas. Cela impliquerait

1.kfk1n

X i=0jli (x)j= nkfk1signifie quexest un point de maximum de la fonctiony7!P ijli(y)j. Or, un tel point existe car cette fonction est continue sur[a;b], intervalle fermé borné deR. 2. nX i=0kfk1 nX i=0jfi(x)j jli (x)jsignifie quejf(xi)j=kfk1pour touti. On peut supposer que kfk1= 1. 3. nX i=0jfi(x)j jli (x)j= n X i=0f i(x)li(x) signifie que lesfi(x)li(x)ont tous le même signe. On peut supposer que toutes ces quantités sont positives. En combinant(2)et(3), on voit qu"on peut prendref(xi) = 1sili(x)0etf(xi) =1sili(x)<0. De plus, si on suppose les points ordonnésx0< x1<< xn, on peut choisirfaffine par morceaux

(c"est à dire affine sur chaque intervalle[xi;xi+1]) et constante pourxx0etxxn. Alors, on vérifie

aisément quefsatisfaitekLn(f)k1= nkfk1.

Notre première estimation de l"erreur est donnée parThéorème 1.2.2Pour toute fonctionf: [a;b]!R, on a

kfLn(f)k1(1 + n)d(f;Pn)

8Chapitre 1. Interpolation polynomialeoùd(f;Pn) = infq2Pnkfqk1.

Preuve: par unicité du polynôme d"interpolation, on aLn(q) =q,8q2Pn. On écrit alors kfLn(f)k1=kfq+LnqLn(f)k1 kfqk1+kLn(qf)k1 kfqk1+ nkfqk1:

Le résultat en découle en prenant l"infimum.RCe théorème est une forme indeterminée car on verra quelimn!1n= +1et quelimn!1d(f;Pn) =

0. En effet, d"après le théorème de Weierstrass, toute fonction continue sur[a;b]est limite uniforme

de polynômes.

Exemple 1.1-

points équidistants :xi=a+i(ba)=n,i= 0;1;;n. Alors, sixi2[1;1], on a l"estimationn2n+1enlog(n). p ointsde Cheb yshev: xi=a+b2 +ba2 cos(2i+ 1)2n+ 2 . Alors,n2 log(n).

Exemple 1.2

Effet de Runge. Dans le cas des fonctions du typega(x) =11+a2x2ouha(x) =1a

2+x2, on

constate que l"interpolation via les points équidistants ne donne pas un résultat proche de la fonction

interpolée. On constate des oscillations de grandes amplitudes près des bord (voir figure ci-dessous).10:750:50:2500:250:50:75110:500:51

xf(x) = (1 + 25x2)1Fonctionf(x) = 1=(1 + 25x2)et son interpolée.

Il est naturel de penser que l"erreur est meilleure dans le cas d"une fonction régulière (même si le

phénomène de Runge existe aussi). C"est l"objet du résultat suivantThéorème 1.2.3 Soitf: [a;b]!Rune fonction(n+ 1)fois dérivable sur]a;b[telle quef,f0,, f(n)soient continues sur[a;b]. Alors,8x2[a;b],9x2]a;b[telle que f(x)pn(x) =n+1(x)(n+ 1)!f(n+1)(x):R-

On voit que ce résultat dépend des valeurs des dérivées def: c"est assez intuitif car plus une

fonction oscille, plus elle est difficile à interpoler.

1.3 Calcul pratique du polynôme d"interpolation de Lagrange 9

1(n+ 1)!est de plus en plus petit quandn! 1.

-On peut interpréter la quantitén+1comme une " mesure » de répartition des points x0;;xndans[a;b]. La meilleure interpolation est donc celle pour laquellekn+1k1est minimale.

Pour démontrer le théorème précédent, on a besoin du lemme de RolleLemme 1.2.4 - (Rolle).

Sif2C1([a;b])etf(a) =f(b) = 0,a6=b, alors92[a;b]telle que f0() = 0.

Preuve du théorème:

Si xest l"un desxi, les deux membres de l"égalité sont nuls et donc le résultat est acquis. Si x6=xi. La preuve se fait par récurrence surn. n= 0soitx6=x0. Le théorème fondamental de l"analyse nous dit que92]x0;x[tel que f(x) =f(x0)|{z} p

0(x)+(xx0)f0():

Pourn= 0,l0(x) = 1,1(x) = (xx0)etp0(x) =f(x0). Ainsi f(x) =p0(x) = (xx0)f0() = 1(x)f0(): n >0 Soitpnle polynôme de Lagrange associé à(x0;;xn). On considère la fonction (y) = f(y)pn(y)An+1(y)oùAest une constante à déterminer. On a : - (xi) = 0,0incarn+1(xi) = 0etf(xi) =pn(xi)

On choisitAtelle que (x) = 0. Ainsi,A=f(x)pn(x)

n+1(x). Cela est possible car comme x6=xi,n+1(x)6= 0.

Ainsi, s"annule(n+ 2)fois.x

0x 1x 2x 3xx n1x n On a donc (y) = 0siy=xouy=xi,0in. Si on applique le lemme de Rolle à l"intervalle[x0;x1], alors il existe un pointx0< 01< x1tel que 0(01) = 0. En appliquant Rolle à chaque sous intervalle, on a que 0s"annule en(n+1)points. En répétant ce processus,

00s"annule ennpoints. Et ainsi de suite pour en conclure que (n+1)s"annule en1point :

9xtel que (n+1)(x) = 0. Mais, on a

(n+1)(y) :=f(n+1)(y)p(n+1)n(y)A(n+1) n+1(y):

Commepn2Pn,p(n+1)n(y) = 0et on a(n+1)

n+1(y) = (n+ 1)!. En évaluant (n+1)enx, on obtient

0 =f(n+1)(x)A(n+ 1)!

et donc

A=f(n+1)(x)(n+ 1)!:

En comparant les deux expressions deA, on a le résultat. 1.3 Calcul pra tiquedu polynôme d"inter polationde Lagrange Soitp(x) =a0+a1x++anxn. Lors de l"évaluation de ce polynôme, si on calcule chaque terme

indépendemment, cela conduit à(n1)multiplications pour calculer successivement lesxkpuis encore

(n1)multiplications pour effectuer les produits avec les coefficientsaketnadditions ce qui au final

10Chapitre 1. Interpolation polynomialefait2(n1)multiplications etnadditions. Une autre méthode consiste en l"utilisation de l"algorithme

d"Horneru

0=anx+an1

u

1=xu0+an2

u

2=xu1+an3...

etun1=pn(x). On fait doncnmultiplications etnadditions et on a donc un gain d"un facteur2. 1.3.1

Dif férencesdivisées

On se donne une subdivision de[a;b]parx0;;xn. On va calculer successivementp0;p1;;pn oùpk2Pkest le polynôme associé àx0;;xk. On définit doncp0(x) =f(x0). On notef[x0;;xk]le coefficient de plus haut degré depk. Commepkpk1est de degréket s"annule enx0;;xk1, on a (pkpk1)(x) =f[x0;;xk] k(x) d okCtedo(k):

Ainsip1(x)p0(x) =f[x0;x1]1(x)et donc

p

1(x) =p0(x) +f[x0;x1]1(x) =f(x0) +f[x0;x1]1(x):

De même,p2(x)p1(x) =f[x0;x1;x2]2(x)et donc

p

2(x) =f(x0) +f[x0;x1]1(x) +f[x0;x1;x2]2(x):

Par récurrence, on obtient laformule de Newton

p n(x) =f(x0) +nX k=1f[x0;;xk]k(x):

Il reste à calculer lesf[x0;;xk]de manière efficace.Lemme 1.3.1Pour tout0in, on af[xi] =f(xi)et pour1kn,

f[x0;;xk] =f[x1;;xk]f[x0;;xk1]x kx0: Ainsi, dès que l"on sait calculer desf[]àktermes, on calcule facilement desf[]àk+ 1termes.

Preuve

: Soitqk12Pk1l"unique polynôme d"interpolation aux pointsx1;;xk. Par définition, le coefficient du terme dominantxk1estf[x1;;xk]. Soit ~pk(x) :=(xx0)qk1(x)(xxk)pk1(x)x kx0: Mais,pk1etqk1appartiennent àPk1. Ainsi,~pk2Pket ~pk(x0) =(x0xk)pk1(x0)x kx0=f(x0); ~pk(xk) =(xkx0)qk1(xk)x kx0=f(xk); et pour1jk1, ~pk(xj) =(xjx0)qk1(xj)(xjxk)pk1(xj)x kx0; (xjx0)f(xj)(xjxk)f(xj)x kx0; =f(xj)(xjx0)(xjxk)x kx0=f(xj):

1.3 Calcul pratique du polynôme d"interpolation de Lagrange 11

Par unicité du polynôme d"interpolation, on a~pk=pk. Mais p k(x) =akxk+ p k1(x) =ak1xk1+ q k1(x) =bk1xk1+ ~pk(x) =ak1+bk1x kx0xk+ et doncak= (bk1ak1)=(xkx0)et on en conclut f[x0;;xk] =f[x1;;xk]f[x0;;xk1]x kx0: 1.3.2

Algor ithmede Hor nerPour calculerpken pratique, on calcule lesf[]puis on utilise la formule de Newton. On utilise le

lemme pour déterminer la valeur de tous lesf[x0;;xk]qui sont obtenus en bout de lignes dans le tableau suivant. On les notesT[k]

T[0]f(x0)&

T[1]f(x1)!f[x0;x1]& &

T[2]f(x2)!f[x1;x2]!f[x0;x1;x2]

T[n2]f(xn2)!f[xn3;xn2]!f[xn4;xn3;xn2]& &

T[n1]f(xn1)!f[xn2;xn1]!f[xn3;xn2;xn1]& &

T[n]f(xn)!f[xn1;xn]!f[xn2;xn1;xn]

et on reconstruit enfin le polynôme de Lagrange par la suite

U[n] =T[n]

U[n1] =T[n1] + (xxn1)U[n]

U[k] =T[k] + (xxk)U[k+ 1]

U[0] =pn(x):

Exemple 1.3

On souhaite calculer le polynôme d"interpolation de la fonctionf(x) =x2+ 1évaluée enf(0) = 1,f(1) = 2etf(2) = 5. Bien entendu, par unicité du polynôme d"interpolation de Lagrange, il faut quep2=f. Le tableau de calcul desf[]est

T[0]f(x0) =1 &

T[1]f(x1) = 2!f[x0;x1] =211

1 & &

T[2]f(x2)!f[x1;x2] =521

= 3!f[x0;x1;x2] =312 1 : On a alorsU[2] =T[2] = 1, puisU[1] =T[1] + (xx1)U[2] = 1 + (x1)et enfin U[0] =T[0] + (xx0)U[1] = 1 +x(1 + (x1)) =x2+ 1 =p2(x):

12Chapitre 1. Interpolation polynomiale1.4Ex ercices

Exercice 1.1On noteli(x) =

nY j=0;j6=ixxjx ixj ,0inles polynômes de Lagrange relatifs aux pointsx0;x1;;xnetk+1(x) =kY j=0(xxj). Montre que80in,8x2Retx6=xi l i(x) =n+1(x)(xxi)0n+1(xi):

Exercice 1.2Interpolation de Lagrange

Soitf(x) = cos(x).

1. Calculer le polynômep1d"interpolation de Lagrange defrelativement aux pointsx0= 0et x1=. 2. Calculer le polynômep2d"interpolation de Lagrange defrelativement aux pointsx0= 0, x2=2 etx1=. 3.

Mon trerque 8x2[x0;x1],

jf(x)p1(x)j 28 jf(x)p2(x)j p33216

Exercice 1.3Interpolation de Hermite

L"objectif est de contruire un polynôme d"interpolation d"une fonctionfen utilisant des valeurs de

fet de sa dérivéef0aux points(xi)0ind"un intervalle[a;b]. 1. On définit les polynômesHi(x) = (12l0i(xi)(xxi))l2i(x)et~Hi(x) = (xxi)l2i(x). Montrer queHi(xj) =i;j,H0i(xj) = 0, et~Hi(xj) = 0"~H0i(xj) =i;j. 2. Soit pnle polynôme de degré2n+ 1qui s"écrit p n(x) =nX i=0f(xi)Hi(x) +nX i=0f

0(xi)~Hi(x):

Montrer quepnainsi défini est l"unique polynôme d"interpolation (dit de Hermite) qui vérifie

pn(xi) =f(xi)etp0n(xi) =f0(xi),0in. Exercice 1.4Symétrie des différences divisées Soientx0;x1;;xndes points distincts d"un intervalle[a;b]. 1.

Démon trerl"id entité

f[x0;;xn] =nX j=0f(xj)nY k=0;k6=j1x jxk: 2.

En déduire que la différence diviséef[x0;;xn]est une fonction symétrique, c"est à dire que

pour toute permutation f[x(0);x(1);;x(n)] =f[x0;x1;;xn]:

1.4 Exercices13Exercice 1.5Convergence de l"interpolation de LagrangeSoient >1, une foncitonfdéfinie sur[1;1]parf(x) = 1=(x)etpnle polynôme d"interpolation

de Lagrange defauxn+ 1points distinctsxi=1 +ih,i2 f0;;ngeth= 2=n. 1.

Mon trerque si >3, alorslimn!1kfpnk1= 0.

2.

Dans la pratique, nous préférons utiliser des polynômes de degré peu élevé sur chaque intervalle

[xi;xi+1],i2 f0;;n1g. Notonsfnla fonction continue tel quefnj[xi;xi+1]est un polynômes de degré1etfn(xi) =f(xi)pour tout0in. On suppose ici que =2[1;1]. (a) Soiti= 0;;n1. Écrire l"approximation de Lagrange de degré1p(i)

1defsur l"intervalle

[xi;xi+1]. (b) Montrer quekffnk1C=n2et donc quefnconverge uniformément versflorsquen tend vers l"infini.

2. Intégration numériqueL"objectif de ce chapitre est connaissant une fonctionf2C0([a;b])réaliser un calcul approché deZb

a f(x)dx. 2.1

For mulesde quadra tureet leur or dre

On introduit une subdivision de[a;b]en sous intervalles a=x0< x1< x2<< xn=b et on utilise la relation de Chasles Z b a f(x)dx=N1X j=0Zquotesdbs_dbs10.pdfusesText_16

[PDF] consommation marqueur social

[PDF] les differentes finalités d'une entreprise

[PDF] les finalités de l'entreprise management

[PDF] les finalités de l'entreprise cours

[PDF] les finalités de l'entreprise pdf

[PDF] les finalités de l'entreprise cours ofppt

[PDF] objectif entreprise 2016 complet

[PDF] classement des pays consommateur d'alcool en afrique 2017

[PDF] les pays qui consomment le plus d'alcool en afrique

[PDF] classement des pays consommateur d'alcool en afrique 2016

[PDF] top 10 des pays consommateur d'alcool en afrique

[PDF] le pays le plus grand consommateur de biere en afrique

[PDF] statistiques consommation alcool france 2016

[PDF] consommation alimentaire définition

[PDF] consommation alimentaire mondiale