[PDF] Cours danalyse numérique de licence L2 MATH

View - Download Cours danalyse numérique de licence L2 MATH

Previous PDF

Next PDF

Cours d'analyse numerique de licence L2 MATH

Roland Masson

Annee 2018-2019

1IntroductionCalendrier du cours

Evaluation

Objectifs

Plan du cours

Exemples d'applications du calcul scientique

Debouches

2Quelques rappels d'algebre lineaire en dimension nieEspaces vectoriels

Applications lineaires

Matrices

Transposition de matrices et matrices symetriques

Determinants

Normes matricielles

3Methodes iteratives

Calendrier du cours

Cours le mercredi de 13h00 a 15h00 en Amphi Informatique

TPs ou TDs

Groupe 1: PV201 le mercredi de 15h15 a 17h15 avec Roland Masson Groupe 2: PV202 le mercredi de 15h15 a 17h15 avec Samira Amraoui Groupe 3: PV314 le jeudi de 10h15 a 12h15 avec Samira Amraoui Groupe 4: PV314 le jeudi de 13h00 a 15h00 avec Boniface Nkonga

Evaluation

Un examen partiel de TD: notePartielUn examen partiel de TP: noteTPUn examen nal: noteEF

Note nale: 0:4EF+ 0:3Partiel+ 0:3TP

Analyse numerique: objectifs

Analyse numerique: concoit et analyse mathematiquement les algorithmes de simulation sur ordinateurs de modeles mathematiquesObjectifs du cours Introduction a quelques algorithmes de bases en calcul scientique Fondements mathematiques (complexite, stabilite, convergence, consistance, ...)Exemples d'applications et mise en oeuvre informatique sous scilab en TP

Plan du cours

Resolution des systemes lineairesAx=b,A2 Mn,b;x2RnMethodes iteratives: methode de Richardon, preconditionnement, Jacobi,

Gauss Seidel, SOR, SSORResolution des systemes non lineairesf(x) = 0,f:Rn!RnMethodes de point xe et de Newton

Resolution des systemes lineairesAx=b,A2 Mn,b;x2RnMethodes directes: methode d'elimination de Gauss, factorisation LU

Calcul des valeurs propres d'une matriceA2 MnMethode des puissances iterees

References

Site web: http://math.unice.fr/massonr/L2MATH/L2MATH.html Cours d'analyse numerique de Raphaele Herbin (Universite de Provence): Livre de P.G. Ciarlet: Introduction a l'analyse numerique matricielle et a l'optimisation. Livre de Quateroni et al: \Methodes numeriques, algorithmes, analyse et applications", Springer, 2007.

Domaines d'applications du calcul scientique

EnergieNucleaire

Petrole

Fusion nucleaire

Eolien, hydrolien, solaire, ...

Transport

Aeronautique

Spatial

Automobile

Environnement

Meteorologie

Hydrologie

Geophysique

Climatologie

Finance, Economie, Biologie, Sante, Telecommunications, Chimie, materiaux, ... Exemple de la simulation des reservoirs petroliers

Petrole = huile de pierreBassin de paris

Exemple de la simulation des reservoirs petroliers

Reservoir: piege geologique rempli

d'hydrocarbures Exemple de la simulation des reservoirs petroliers

Enjeux de la simulation

Prediction de la production

Optimisation de la production (ou du rendement economique)

Integration des donnees

Evaluation des incertitudes sur la production

Debouches

Competences

Analyse numerique

Modelisation

Informatique

Metiers

Developpements de codes de calculs scientiques

Etudes en modelisation numerique

Ingenieur de recherches en calcul scientique

Chercheur academique en mathematiques appliquees

Employeurs

SSII en calcul scientique

EPIC: CEA, ONERA, IFPEN, BRGM, IFREMER, INRA, CERFACS, ... Industrie: EDF, EADS, Dassault, Michelin, Areva, Total, CGGVeritas, Thales, Safran, Veolia, Rhodia, ...Academique: Universites, CNRS, INRIA, Ecoles d'ingenieurs, ...

Espaces vectoriels

Denition d'un e.v. surK=RouC: ensemble E muni d'une loi de composition interne notee + et d'une loi d'action deKsurEnotee:tels

que:(E;+) est un groupe commutatif1:x=x, ():x=:(:x) (associativite)(+):x=:x+:x,:(x+y) =:x+:y(distributivite)Exemple:Rne.v. surR(Cne.v. surC):x=0

B @x 1 x n1 C

A,x+y=0

B @x 1+y1 x n+yn1 C

A,:x=0

B @x1 xn1 C A

Familles libres, generatrices, base, dimension

Famille libre demvecteursv1;;vmdeE:P

m

i=1ivi= 0)i= 08i= 1;;mFamille generatrice demvecteursv1;;vmdeE:E= Vectfv1;;vmgBase: famille libre et generatrice

Dimension (supposee nie): toutes les bases ont m^eme dimension appelee

dimension de l'espace vectorielEnoteenUne famille libre denvecteurs est generatrice, c'est une baseUne famille generatrice denvecteurs est libre, c'est une base

Espaces vectoriels normes

Denition: e.v. muni d'une norme, ie une application deE!R+, notee

x! kxksatisfaisant les proprietes suivanteskxk= 0)x= 0k:xk=jjkxkkx+yk kxk+kykUne norme denit surEune topologie d'espace metrique avec

d(x;y) =kxykLimite de suite de vecteurs:limk!+1vk=v,limk!+1kvkvk= 0Exemples de normes surRnkxk1=Pn i=1jxij;kxk2=Pn

i=1jxij21=2;kxk1= maxi=1;;njxij.En dimension nie toutes les normes sont equivalentes ie il existec;C>0

telles queckxk kxk?Ckxk(attentioncetCdependent den).

Espaces vectoriels euclidiens

e.v. muni d'un produit scalaire ie une forme bilineaire symetrique denie positive noteeh:;:iSurRnle produit scalaire canonique esthx;yi=Pn i=1xiyikxk=hx;xi1=2est une norme appelee norme euclidienne

Applications lineaires

f:E!F,f(:x) =:f(x),f(x+y) =f(x) +f(y)L(E;F) espace vectoriel des applications lineaires deEdansFL(E) espace vectoriel des applications lineaires deEdansEou

endomorphismes deE

L(E);+;:;

algebre non commutative munie de la loi de composition

des applicationsfg(x) =f(g(x))Noyau def, Ker(f) =fx2Etels quef(x) = 0g(sous e.v. deE)Image def, Im(f) =ff(x);x2Eg(sous e.v. deF)Endomorphismes deEinversibles:Application bijective ssi il existef12 L(E) telle queff1=f1f=Idfbijective,finjective: Ker(f) =f0gfbijective,fsurjective: Im(f) =E

Matrice d'une application lineaire

Bases e j;j= 1;;n deEet f i;i= 1;;m deFf2 L(E;F) telle quef(ej) =Pm i=1Ai;jfix=Pn j=1xjej2Ey=f(x) =Pm i=1 Pn j=1Ai;jxj f iX=0 B @x 1... x n1 C

A2Rn,Y=0

B @y 1... y m1 C

A2Rm,Y=AXRetenir que lesncolonnesjdeAsont donnees par les imagesf(ej)Espace vectoriel des matrices de dimensionm;n:Mm;n(a coecients dans

K=RouC)Matrices remarquables: diagonale, symetrique, triangulaires inferieure ou superieure

Exercice: produit de matrices versus composition

d'applications lineairesSoientE;F;Gdes e.v de dimensions resp.n,m,p,f2 L(E;F) et g2 L(F;G)Des bases etant donnees,fa pour matriceA2 Mm;netga pour matrice

B2 Mp;mgfa pour matrice le produitBA2 Mp;ntel que

(BA)i;j=mX k=1B

i;kAk;jProduit de matrices:Mp;m Mm;n! Mp;nproduit matrice vecteur:Mm;n Mn;1! Mm;1produit scalaire de deux vecteurs: ligne . colonneM1;n Mn;1! M1;1produit tensoriel de deux vecteurs: colonne. ligneMn;1 M1;n! Mn;n

Exercice: changements de base pour les vecteurs et les matricesP: matrice de passage d'une base dans une autre~ej=Pn k=1Pk;jek

(colonnes de la nouvelle base dans l'ancienne)Changement de base pour les coordonnees des vecteurs:X=P~X.Changement de base pour les matrices des applications lineaires:X=P~X,

Y=Q~Yet~Y=~A~X,Y=AXimplique que

A=Q1AP:

Matrices carres inversibles

A2 Mn;n=Mnest inversible ssi l'une des proprietes suivantes est verieeIl existeA12 Mn;ntel queAA1=A1A=IAest injective ieAX= 0)X= 0Aest surjective ie Im(A) =fAX;X2Rng=RnA;B2 Mninversibles

(AB)1=B1A1

Transposition de matrices

A2 Mm;n, on denittA2 Mn;mpar

tA)i;j=Aj;ipour tousi= 1;;n;j= 1;;mProduit scalaire canonique de deux vecteurs (colonnes)X;Y2Rn: t XY=nX i=1X iYiMatrice carreeA2 Mnest symetrique ssi t A=A

Diagonalisation d'une matrice carree symetriqueA2 MnLes valeurs propres surCd'une matrice reelle symetriqueAsont reelles et il

existe une base orthonormee de vecteurs propresFi2Rn,i= 1;;ntelle que AF

i=iFiet (tFi)Fj=i;jpour tousi;j= 1;;nSiPest la matrice de passage de la base canonique dans la baseFi,

i= 1;:::;n, alors on a P 1=tP et t PAP=0 B 10 0n1 C A Determinants denvecteurs dans un e.v.Ede dimensionn pour une base donneeUnique forme n-lineaire alternee surEvalant 1 sur la baseDet v

1;;v;;v;;vn

= 0 (alternee)Antisymetrie: Det v

1;;vi;;vj;;vn

=Det v

1;;vj;;vi;;vnOn a donc aussi pour toute permutationdef1;;ng,

Det v 1;;vn = sign()Det v (1);;v(n)Determinant d'une matrice carreeA= determinant des vecteurs colonnes Det A = Det A :;1;;A:;n =X 2nn Y i=1sign()A(i);i

Proprietes du determinant

Les vecteurs colonnes deAsont libres ssi Det(A)6= 0DoncAest inversible ssi Det(A)6= 0Det(AB) = Det(A)Det(B) = Det(BA)Det(

tA) = Det(A)Developpement par rapport aux lignes ou aux colonnes

Det(A) =nX

i=1(1)i+jAi;jDet(A(i;j)) =nX j=1(1)i+jAi;jDet(A(i;j))

Normes matricielles

Une norme matricielle sur l'e.v.Mnest une norme telle que kABk kAkkBkUne norme matricielle induite par une normek:ksurRnest la norme matricielle denie par kAk= sup X6=0kAXkkXkOn a pour une norme matricielle induite:kAXk kAkkXkpour tout X2Rn

Exercice: exemples de normes induites

kAk1= SupX6=0kAXk1kXk1= maxi=1;;nPn j=1jAi;jjkAk1= SupX6=0kAXk1kXk1= maxj=1;;nPn i=1jAi;jjkAk2= SupX6=0kAXk2kXk2=(tAA)1=2

Norme et rayon spectral

Spectre de A:

spec(A) =f2Ctel qu'il existeu2Cnnon nul tel queAu=ugRayon spectral(A) = max2spec(A)jjC. On admettra le lemme suivant qui montre la proximite entre norme et rayon

spectral (voir preuve dans le livre de Ciarlet ou le cours de Raphaele Herbin)(A) kAkquelle que soit la norme matricielle surMnQuels que soientA2 Mnet >0 il existe une norme induitek:kA;telle

que kAkA;(A) +: Theoreme: convergence de la suiteAkpourA2 MnLes propositions suivantes sont equivalentes

(1)limk!+1Ak= 0(2)limk!+1Akx= 0 quel que soitx2Rn(3)(A)<1(4) Il existe une norme induitek:ktelle quekAk<1.

Theoreme: convergence de la suiteAkpourA2 Mn

Preuve:(1))(2): carkAkxk kAkkkxk(2))(3): par la contraposee non (3))non (2):(A)1 implique qu'il existe un vecteuru2Cnnon nul et2Ctels queAu=uetjj 1.

Ceci implique queAku=kuet donc (2) ne peux ^etre verie.(3))(4): decoule du lemme ci-dessus(4))(1): on akAkk kAkkaveckAk<1 d'ou (1)

Corollaire: suiteAket rayon spectralRayon spectral et suite des puissances d'une matrice: on demontre la

propriete suivante:(A) =limk!+1kAkk1=kquelle que soit la norme matricielle surMn Preuve: on a tout d'abord(A)k=(Ak) kAkkd'ou(A) kAkk1=k Soit >0. On considereB=A(A)+, telle que(B)<1. D'apres le theoreme precedent lim k!+1(B)k= 0, donc il existeNtel que pour toutkNon a k(B)kk=kAkk((A) +)k1: On deduit que(A) kAkk1=k(A) +ce qui prouve le corollaire.

Matrices de la formeI+AouIASi(A)<1 alors les matricesI+AetIAsont inversiblesLa serie de terme generalAkconverge (vers (IA)1ssi(A)<1Preuve:

PN

k=0Ak(IA) =IAN+1et utiliser le lemme precedentSikAk<1 pour une norme matricielle, alorsIAest inversible et on a

k(IA)1k 11kAk(idem pourI+A)

Conditionnement

Soitkkla norme induite dansMnpar une normekksurRn

Conditionnement deAinversible : Cond(A) =kAkkA1k

8 :Cond(A)1

Cond(A) = Cond(A)

Cond(AB)Cond(A)Cond(B)

SoitAinversible et1,nles vp min et max detAA, on a pour la normekk2 Cond

2(A) =n

1 1=2

On en deduit que Cond

2(A) = 1 ssiA=QouQmatrice orthogonale

PourASDP de vp min et max1etn, on a pour la normekk2 Cond

2(A) =n

1

Erreur d'arrondi

SoitAune matrice inversible, on cherche a estimer l'in uence sur la solution du systemeAx=bd'une erreur d'arrondi sur le second membreb Ax=b

A(x+x) =b+b

implique kxkkxk kAkkA1kkbkkbk

Methodes iteratives: motivations

Matrice creuse:O(n) termes non nulsMethodes iteratives: calcul d'une suitexnfaisant intervenir que des

produits matrice - vecteurPour une matrice creuse, une iteration co^uteO(n) operations ottantesLe probleme a resoudre est la ma^trise de la convergence de la suitexnvers xet du nombre d'iterationsCo^ut pour une matrice creuse et une convergence ennititerations

O(n:nit)

matrices creuses: exemple du Laplacien 2D sur maillage

Cartesien

Maillage cartesien uniforme (n+1)(n+1) du carre

= (0;1)(0;1) de pas x=1n+1Laplacien avec conditions limites homogenes: @2u@x2@2u@y2=fsur u(x) = 0 sur@

Discretisation:

1(x)2(4ui;jui+1;jui1;jui;j+1ui;j1=fi;jpouri;j= 1;;n

u i;j= 0 pouri= 0;n+ 1;j= 0;;n+ 1 etj= 0;n+ 1;i= 0;;n+ 1 Systeme lineaire: numerotation des inconnuesk=i+ (j1)nde 1 aN=n2 AU=FavecAmatrice pentadiagonale de largeur de bandeq=n

Co^ut d'une methode directeLU: 2Nn2= 2N2

Co^ut d'une methode iterative convergente ennititerations: 10N:nit

Methode de Richardson

SoitA2 Mninversible etb2Rn. Soitx2Rnsolution de

Ax=b: Methode de Richardson: soit2R, on construit une suite de solutionxkde la forme x k+1=xk+(bAxk):

On a donc

(xk+1x) = (IA)(xkx); (xk+1x) = (IA)k(x1x); B= (IA)Convergence: ssi(B)<1Taux de convergence:kBkk1=k!(IA)

Methode de Richardon pour les matrices SDP

SoitA2 MnSDP (Symetrique Denie Positive) eti>0;i= 1;;nses valeurs propres par ordre croissant (IA) =max j11j;j1nj opt=argmin2Rmax j11j;j1nj opt=2

1+n; (IoptA) =n1

1+n=1+ 1<1

Probleme: on ne connait pas les valeurs propres deA Voir Exercice: Methode de Richardson a pas variable

Methode de Richardon pour les matrices SDP

Nombre d'iterations pour une precision xee:

kxk+1xk2 (IoptA) kkx1xk2; kxk+1xk21+ 1 kkx1xk2; On cherche le nb d'iterationkpour atteindre une precision, ie 1+ 1 k; kln(1 )ln( 1+1 11

Pourgrand:

k >2 ln(1 Methode de Richardon a pas variable pour les matrices SDP

SoitA2 MnSDP (Symetrique Denie Positive).

On poseek=xxk;rk=Aek=bAxk;

quotesdbs_dbs10.pdfusesText_16

[PDF] cours maths mp

[PDF] cours maths mpsi pdf

[PDF] cours maths pcsi

[PDF] cours maths pcsi pdf

[PDF] cours maths sup pdf

[PDF] cours maths terminal e&s

[PDF] cours maths terminal e&s pdf

[PDF] cours maths terminale s pdf

[PDF] cours maths terminale stmg

[PDF] cours mecanique bac technique tunisie

[PDF] cours mécanique du point

[PDF] cours mécanique quantique mp

[PDF] cours mécanique quantique pdf mp

[PDF] cours mecanique rationnelle usthb pdf

[PDF] cours messagerie électronique pdf