[PDF] Analyse Numérique Analyse Numérique. Radhia Bessi &

View - Download Analyse Numérique

Previous PDF

Next PDF

Analyse Numerique

Radhia Bessi & Maher Moakher

2015{2016

Table des matieres

1 Methodes directes pour la resolution des systemes lineaires 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Principe des methodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.1 Rappels et notations sur les vecteurs et les matrices . . . . . . . . . . . . . . .

3

1.2.2 Resolution d'un systeme triangulaire . . . . . . . . . . . . . . . . . . . . . . .

4

1.3 Factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.1 Rappel sur la methode de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.2 Factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.4 Factorisation de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.4.1 Rappels sur les matrices symetriques . . . . . . . . . . . . . . . . . . . . . . .

14

1.4.2 Factorisation des matrices symetriques . . . . . . . . . . . . . . . . . . . . . .

16

1.4.3 Factorisation de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2 Methodes iteratives pour la resolution des systemes lineaires 19

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2 Rappels sur les normes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2.1 Normes matricielles subordonnees . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.3 Methodes iteratives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.3.1 Methode deJacobi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

2.3.2 Methode de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.3.3 Methode deGauss-Seidel. . . . . . . . . . . . . . . . . . . . . . . . . . . . .29

2.3.4 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.3.5 Critere ou test d'arr^et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.4 Conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3 Optimisation sans contraintes 37

3.1 Optimisation surRn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

3.1.1 Existence et unicite d'un minimum . . . . . . . . . . . . . . . . . . . . . . . .

38

3.1.2 Conditions d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.1.3 Probleme d'optimisation quadratique . . . . . . . . . . . . . . . . . . . . . . .

43

3.1.4 Probleme aux moindres carres . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.2 Algorithmes de descente et methodes du gradients . . . . . . . . . . . . . . . . . . . .

45

3.2.1 Methodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45
i

TABLE DES MATI

ERES3.2.2 Methodes du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46

3.2.3 Methode du gradient a pas xe . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.2.4 Methodes du gradient a pas optimal . . . . . . . . . . . . . . . . . . . . . . .

47

3.2.5 Methodes du gradient conjugue . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.2.6 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.2.7 Methodes du gradient et preconditionnement . . . . . . . . . . . . . . . . . . .

53

4 Optimisation avec contraintes lineaires 55

4.1 Problemes d'optimisations sous contraintes . . . . . . . . . . . . . . . . . . . . . . . .

55

4.1.1 Existence et unicite de minimum . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.1.2 Condition d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.1.3 Cas de contraintes d'egalites et d'inegalites lineaires . . . . . . . . . . . . . . .

61

4.1.4 Probleme quadratique avec contraintes lineaires . . . . . . . . . . . . . . . . .

61

4.2 Quelques algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

4.2.1 Methode du gradient projete . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

4.2.2 Methode d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65
ii

Chapitre 1

Methodes directes pour la resolution des

systemes lineaires

1.1 Introduction

La resolution des systemes lineaires de grandes tailles est l'un des plus importants problemes en analyse numerique. Le but de ce chapitre est d'etudier des methodes de resolution numerique d'un lineaireAx=b, ouAest une matrice carree inversible. Pour motivation, commencons par citer le probleme mecanique classique suivant qui conduit a la resolution d'un systeme lineaire. La deformationxd'une corde elastique, xee aux bords et soumise a un champ de forcef, peut se traduire par l'equation dierentielle suivante x00(t) =f(t); t2[0;1] x(0) =x(1) = 0;(1.1)

pourfune fonction continue sur [0;1]. En general, il n'est pas possible d'expliciter la solution exacte

de ce probleme. L'idee donc est de chercher une solution approcheexhdexen prenant une subdivision

0 =t0t1 tn+1= 1, avecti=ih,i= 0;:::;n+ 1 eth=1n+ 1. On se limitera a calculer

x h(ti) =xi'x(ti), pouri= 0;:::;n+1 et par interpolation par exemple, on peut avoirxhsur tout l'intervalle [0;1]. Si on suppose que notre solutionxest de classeC2, alors on a les deux developpement de Taylor suivants : x(ti+1) =x(ti+h) =x(ti) +x0(ti)h+x00(ti)h22 +O(h3); et x(ti1) =x(tih) =x(ti)x0(ti)h+x00(ti)h22 +O(h3):

Si on fait la somme de deux egalites on obtient

x

00(ti) =x(ti+h)2x(ti) +x(tih)h

2+O(h):

1 Chapitre 1. Methodes directes pour la resolution des systemes lineaires Si on neglige les termes d'ordreO(h) dans l'expression de la derivee seconde, le probleme discretise pour resoudre notre equation devient xi+12xi+xi1h

2=f(xi); i= 1;:::;n

x

0=xn+1= 0(1.2)

qui est equivalent au systeme lineaireAhx=bh, ou A h=1h 20 B

BBBBB@21 00

1 21...

0 .........0...1 21

001 21

C

CCCCCAx=0

B @x 1... x n1 C

Aetbh=0

B @f(t1)... f(tn)1 C A: La solution approchee est d'autant plus proche de la solution exactexlorsquenest grand. On rappele que la solution uniquex= (x1;:::;xn) d'un systemeAx=b, pourA= (aij)1i;jn une matrice inversible etb= (b1;:::;bn)Test donnee par les formules deCramersuivantes : x i=detAidetA; i= 1;:::;n; ou det designe le determinant etAiest la matrice d'ordrenobtenue a partir deAen remplacant sa colonneipar le vecteur de second membreb. Donc la resolution d'un systeme lineaire d'ordren, par les formules de Cramer fait intervenir le calcul den+ 1 determinants dont chaque determinant necessite de l'ordre den! multiplications. La methode de Cramer devient trop co^uteuse m^eme pour des matrices de tailles assez petites. D'ou l'idee de concevoir des methodes qui en general donnent la solution a une valeur pres, mais avec un nombre raisonnable d'operations. Pour simplier, on se limitera a resoudre numeriquement un systeme lineaire reel sachant qu'un systeme lineaire complexe est equivalent a deux systemes lineaires reels representants ses parties reelles et imaginaire. On distinguera deux methodes numeriques pour resoudre un systeme lineaire. Les methodes

directes, dont certaines font l'objet de ce chapitre et les methodes iteratives qui seront developpees

dans les chapitres suivants.

1.2 Principe des methodes directes

On appelle methode directe pour resoudre un systeme de typeAx=b, une methode qui donne xapres un nombre ni d'operations elementaires. Le principe de ces methodes est de se ramener a un systeme lineaire equivalent, mais qui est plus simple a resoudre. C'est le cas par exemple ou la matrice du systeme est diagonale, triangulaire ou orthogonale. 2

1.2 Principe des methodes directes

1.2.1 Rappels et notations sur les vecteurs et les matrices

Tout au long de ce cours on utilisera les notations suivantes : Pournun entier naturel non nul xe, on note parRnl'espace vectoriel des vecteurs colonnes a coecients reelsx=0 B @x 1... x n1 C A. Le vecteur lignexT= (x1;:::;xn) designe la transposee du vecteur x2Rn. Le produit scalaire dansRnsera note (;) et est deni par (x;y) =nX i=1x iyi; et la norme associee est la norme euclidienne donnee par kxk2= nX i=1jxij2! 12 = (x;x)12 On notera l'espace vectoriel des matrices anlignes etpcolonnes et a coecients dansRpar M n;p(R) et parMn(R) l'ensemble des matrices carrees d'ordrena coecients dansR. La transposee d'une matriceA= (aij)1in;1jp2 Mn;p(R) par A

T= (aji)1ip;1jn2 Mp;n(R):

La matrice transposee verie

(Ax;y) = (Ax)Ty=xTATy= (x;ATy) pour toutx2Rpety2Rn: Denition 1.2.1SoitA= (aij)1i;jn2 Mn(R): Aest dite : diagonale siaij= 0pour touti6=j. triangulaire inferieure siaij= 0pour touti < j. triangulaire superieure siaij= 0pour touti > j. inversible si son determinant est non nul ou s'il existe une matriceB2 Mn(R)telle que

AB=BA=In

ouInest la matrice unite d'ordrendonnee par I n=0 B @1 11 C A: La matriceBest appelee inverse deAet sera noteeA1. 3 Chapitre 1. Methodes directes pour la resolution des systemes lineaires semblable a une matriceD2 Mn(R)s'il existe une matrice inversiblePtelle queD=P1AP. diagonalisable si elle est semblable a une matrice diagonale.

On peut verier facilement que

Proposition 1.2.1

1. L epr oduitde deux matric estriangulair essup erieures(r epectivementinf erieures)est une ma- trice triangulaire superieure (respectivement inferieure). 2. Une matric eA= (aij)1;i;jn2 Mn(R)triangulaire est inversible si et seulement siaii6= 0, pour touti= 1;:::;n. De plusA1est de m^eme type queAet(A1)ii=1a ii, pour tout i= 1;:::;n.

1.2.2 Resolution d'un systeme triangulaire

Soit le systeme trianglaire superieur8>>><

>>:u

11x1+u12x2+u1nxn=b1

u

22x2+u2nxn=b2......

u nnxn=bn:(1.3) SiUest la matrice triangulaire superieure suivante :quotesdbs_dbs22.pdfusesText_28

[PDF] M33 Analyse numérique - Gloria FACCANONI

[PDF] Exercices de Licence - Analyse numérique 1 Normes matricielles

[PDF] Cours Analyse Numérique

[PDF] Analyse Numérique : SMA-SMI S4 Cours, exercices et examens

[PDF] Recueil d exercices pour les cours MTH2210x

[PDF] Méthode d 'analyse structurée pour la mise au point de logiciels

[PDF] positionner mon entreprise : l analyse pestel - Formasup

[PDF] Analyse du marché des produits biologiques en - Agri-Réseau

[PDF] Secteur des textiles, de l 'habillement et du cuir - Europa EU

[PDF] Consommateurs et consommation de fromages de chèvre en France

[PDF] Le marché des produits laitiers - ANIMA Investment Network

[PDF] Secteur de l hôtellerie et de la restauration - Europa EU

[PDF] ANALYSE DE L 'ENVIRONNEMENT DE L 'INDUSTRIE DU TEXTILE

[PDF] Première approche phonologique, morpho-syntaxique - (DDL), Lyon

[PDF] Procédés et analyses en chimie et agroalimentaire