[PDF] cours MAP : Mathématiques Appliquées DIIC 1ere année

View - Download cours MAP : Mathématiques Appliquées DIIC 1ere année

Previous PDF

Next PDF

cours MAP : Math´ematiques Appliqu´ees

DIIC 1ere ann´ee

Jocelyne Erhel

1

April 12, 2006

1 INRIA, UR Rennes, Jocelyne.Erhel@inria.fr, http://www.irisa.fr/aladin/perso/erhel/ 2

Contents

1 Introduction7

1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Objectif du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Application au calibrage d"un mod`ele . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Exemple : interpolation et approximation polynomiale . . . . . . . . . . . . . 8

1.4 Application `a un moteur de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Bases de l"alg`ebre lin´eaire 11

2.1 Matrices et vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Matrices particuli`eres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.2 Op´erations sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.3 Matrices carr´ees sym´etriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.4 Partitions par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Normes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Orthogonalit´e dansRn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4 Image, noyau, rang d"une matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5 Valeurs propres et vecteurs propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.6 Notions de complexit´e et de performances . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7 Biblioth`eques BLAS et LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.1 Op´erations BLAS1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.2 Op´erations BLAS2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.3 Op´erations BLAS3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.7.4 biblioth`eque LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Arithm´etique flottante 19

3.1 Erreurs de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.1 Sources d"erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Mesures de l"erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Arithm´etique flottante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.1 Format flottant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2.2 Arrondis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2.3 Op´erations arithm´etiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.4 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.5 Norme IEEE-754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2.6 Ph´enom`ene d"absorption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3

3.2.7 Ph´enom`ene de cancellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2.8 Extensions de la norme IEEE . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Stabilit´e des probl`emes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.1 Lien avec le r´esidu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.2 Exemple : effet papillon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4 Stabilit´e et ordre des sch´emas de discr´etisation . . . . . . . . . . . . . . . . . . . . . 27

3.5 Convergence des algorithmes it´eratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.6 Stabilit´e des algorithmes directs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.6.1 Exemple : produit scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.6.2 Exemple : produit ext´erieur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 R´esolution de syst`emes lin´eaires carr´es 31

4.1 Inverse d"une matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1.1 Matrices particuli`eres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2 R´esolution d"un syst`eme lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.1 Cas des matrices sym´etriques d´efinies positives . . . . . . . . . . . . . . . . . 33

4.3 Analyse des erreurs pour un syst`eme lin´eaire . . . . . . . . . . . . . . . . . . . . . . 34

4.3.1 Stabilit´e num´erique de Gauss et de Cholesky . . . . . . . . . . . . . . . . . . 34

4.3.2 Analyse de perturbation d"un syst`eme lin´eaire . . . . . . . . . . . . . . . . . . 35

4.3.3 Pr´ecision de la r´esolution d"un syst`eme lin´eaire . . . . . . . . . . . . . . . . . 37

5 Probl`emes aux moindres carr´es - cas du rang plein 39

5.1 Existence et unicit´e d"une solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.1.1 Existence d"une solution dans le cas g´en´eral . . . . . . . . . . . . . . . . . . . 39

5.1.2 Condition d"unicit´e de la solution . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2 Equations normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.3 Factorisation QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.4 Analyse d"erreur pour les probl`emes aux moindres carr´es de rang plein . . . . . . . . 42

5.4.1 Stabilit´e num´erique de la factorisationQR. . . . . . . . . . . . . . . . . . . . 42

5.4.2 Analyse de perturbation et conditionnement . . . . . . . . . . . . . . . . . . . 42

5.4.3 Pr´ecision d"une r´esolution de probl`eme aux moindres carr´es de rang plein . . 43

6 D´ecomposition en Valeurs Singuli`eres 45

6.1 Diagonalisation d"une matrice carr´ee . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.1.1 Diagonalisation des matrices sym´etriques . . . . . . . . . . . . . . . . . . . . 46

6.2 D´ecomposition SVD (Singular Value Decomposition) d"une matrice rectangulaire . . 46

6.2.1 SVD r´eduite. Rang, image et noyau . . . . . . . . . . . . . . . . . . . . . . . 48

6.3 Approximation de rang k et rang num´erique . . . . . . . . . . . . . . . . . . . . . . . 48

6.4 Calcul de la SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.1 Bidiagonalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.5 Analyse d"erreur du calcul de la SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.5.1 Stabilit´e num´erique du calcul d"une SVD . . . . . . . . . . . . . . . . . . . . 51

6.5.2 Analyse de perturbation des valeurs singuli`eres . . . . . . . . . . . . . . . . . 51

6.5.3 Pr´ecision du calcul des valeurs singuli`eres . . . . . . . . . . . . . . . . . . . . 51

4

7 Probl`emes aux moindres carr´es - cas g´en´eral 53

7.1 Probl`emes aux moindres carr´es - cas du rang plein . . . . . . . . . . . . . . . . . . . 53

7.1.1 SVD, ´equations normales et factorisationQR. . . . . . . . . . . . . . . . . . 53

7.1.2 SVD, inverse et pseudo-inverse . . . . . . . . . . . . . . . . . . . . . . . . . . 54

7.2 Probl`emes aux moindres carr´es - cas g´en´eral . . . . . . . . . . . . . . . . . . . . . . . 54

7.2.1 R´esolution d"un probl`eme aux moindres carr´es avec la SVD . . . . . . . . . . 56

7.3 SVD et conditionnement des matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 56

8 Conclusion57

5 6

Chapter 1

Introduction

1.1 Notations

On noteRnun espace vectoriel de dimensionn.

La base canonique deRnest (e1,...,en). Un vecteurx?Rn, de composantesx1,...,xn, est not´e x= (xi).

Une matriceA?Rm×nest not´eeA= (aij).

Lejemevecteur colonne deAestaj=Aej.

Un syst`eme denvecteursu1,...,un?Rmest not´e sous forme matricielleU= (u1...un)?Rm×n, avecujlejemevecteur colonne deU. On noteIm(U) ouV ect(U) le sous-espace vectoriel engendr´e par les vecteurs colonnes deU. Il est possible de d´efinir plusieurs normes dans l"espace vectorielRn. La norme vectorielle euclidienne est d´efinie par ?x?2= (? ix 2i)12

La norme vectorielle infinie est d´efinie par

?x?∞= maxi|xi|.

1.2 Objectif du cours

L"objectif de ce cours est la r´esolution de syst`emes lin´eaires avec soit autant de donn´ees que

d"inconnues, soit plus de donn´ees que d"inconnues (syst`eme sur-d´etermin´e), soit plus d"inconnues

que de donn´ees (syst`eme sous-d´etermin´e). Un syst`eme lin´eaire est un ensemble dem´equations

lin´eaires `aninconnues. Il s"´ecrit sous forme matricielle

Trouverx?Rn,tel queAx=b,

o`uA?Rm×netb?Rmsont donn´es. Selon les cas, un tel syst`eme peut ne pas avoir de solution,

avoir une solution unique, avoir une infinit´e de solutions. Pour ´etudier le cas g´en´eral et pour d´efinir

des algorithmes de r´esolution, on reformule le syst`eme sous la forme d"un probl`eme aux moindres

carr´es :

Trouverx?Rn,tel que?Ax-b?2soit minimum.

7 Ces probl`emes aux moindres carr´es interviennent dans beaucoup de domaines tels que le traite- ment du signal, le traitement d"images, l"analyse statistique, etc.

Les derniers chapitres sont consacr´es `a une notion qui g´en´eralise celle de valeur propre. Cela

permet de r´esoudre non seulement les probl`emes aux moindres carr´es, mais aussi beaucoup d"autres

probl`emes lin´eaires. Cette propri´et´e, appel´ee la D´ecomposition en Valeurs Singuli`eres, s"applique

dans des domaines vari´es comme les t´el´ecommunications, la r´ealit´e virtuelle, les moteurs de recherche,

etc.

Les mod`eles math´ematiques sont d´efinis dans l"ensembleRdes nombres r´eels. Mais les calculs

se font sur ordinateur, qui ne disposent que d"une m´emoire finie et ne peuvent donc pas stocker

l"infinit´e des nombres r´eels. Ce cours introduit les notions de calcul flottant et d"erreurs de calcul.

1.3 Application au calibrage d"un mod`ele

Une des premi`eres applications `a l"origine des probl`emes aux moindres carr´es est le calibrage d"un

mod`ele math´ematique. Ce mod`ele est une repr´esentation d"un ph´enom`ene que l"on ´etudie. Sup-

posons qu"il soit d´efini par une fonctionf(t), o`u la fonctionfest caract´eris´ee par un ensemble de

nparam`etresx?Rnque l"on ne connait pas. On dispose d"un ensemble demobservations ou mesuresbiaux "temps"ti, i= 1,...,m. La calibration du mod`ele consiste `a trouverxtel quebi soit proche deyi=f(ti). Une solution consiste `a rendre minimum la somme des carr´es des erreurs.

Math´ematiquement, cela s"´ecrit :

Trouverx?Rn,tel quem?

i=1(bi-yi)2soit minimum. Si la fonctionfest une fonction lin´eaire par rapport `ax, elle s"´ecrit f(t) =n? j=1x jΦj(t), etyi=?n j=1xjΦj(ti). Sous forme matricielle, on ay=Axet le probl`eme devient

Trouverx?Rn,tel que?b-Ax?2soit minimum.

1.3.1 Exemple : interpolation et approximation polynomiale

Dans l"interpolation ou l"approximation polynomiales, on cherchefsous la forme d"un polynˆome de degr´en-1, d´efini par f(t) =x1+x2t+...+xntn-1=n? j=1x jtj-1.

La matriceA= (aij) est d´efinie paraij=tj-1

i. Sim=n, on parle d"interpolation polynomiale, on obtient ainsi unsyst`eme lin´eaire Ax=b den´equations `aninconnues. Voir le chapitre et la section sur les syst`emes lin´eaires. 8 Sinon, on cherche uneapproximation polynomiale au sens des moindres carr´eset on r´esout leprobl`eme lin´eaire aux moindres carr´es min x?Ax-b?2. Voir les chapitres sur les probl`emes aux moindres carr´es.

1.4 Application `a un moteur de recherche

On dispose demtermes et dendocuments, avec des poidsaijdu termeidans le documentj. On construit la matriceA= (aij) qui est la base de recherche. Lajemecolonnedjest l"ensemble de poids attribu´es au documentj. Une requˆete est un ensemble de valeursq= (qi) attribu´ees aux termesi. L"objectif est de mesurer l"angle entre la requˆete et chaque documentj, autrement dit les quantit´es cos(θj) =dTjq?dj?2?q?2 o`udTjqest le produit scalaire des deux vecteurs.

Si l"angleθjest petit, autrement dit si cos(θj) est proche de 1, alors la probabilit´e que le

documentjcontienne des termes de la requˆeteqest ´elev´ee. Il faut obtenir une r´eponse rapide, mˆeme sur des bases gigantesques avec des milliers ou des millions de documents et de termes. Pour cela, on utilise une approximation de la baseApar une base beaucoup plus petiteAket on calcule une approximation des coefficients cos(θj) avec la base A

k. Voir le chapitre sur la d´ecomposition en valeurs singuli`eres et la section sur l"approximation

de rangk. 9 10

Chapter 2

Bases de l"alg`ebre lin´eaire

Ce chapitre introduit les op´erations de base sur l"alg`ebre des matrices. Dans le cas des matrices

carr´ees, il d´efinit les notions de matrice inversible et de matrice singuli`ere. Les notions de complexit´e

et de performances sont introduites. Le chapitre termine par la description des biblioth`eques BLAS et LAPACK.

2.1 Matrices et vecteurs

2.1.1 Matrices particuli`eres

Une matriceA?Rm×nest carr´ee d"ordrensin=m.

La matrice identit´e d"ordrek, dans?Rk×k, vautIk= (e1...ek).

Une matrice carr´eeDest diagonale si les seuls ´el´ements non nuls sont sur la diagonale ; elle est

not´eeD=diag(di).

Une matrice carr´eeLtriangulaire inf´erieure si les seuls ´el´ements non nuls sont dans le triangle

inf´erieur ; on d´efinit de mˆeme une matrice carr´eeUtriangulaire sup´erieure. Une matrice tridiagonale a trois diagonales non nulles, une matrice bidiagonale a deux diagonales non nulles.

2.1.2 Op´erations sur les matrices

L"ensemble des matricesRm×nest un espace vectoriel de dimensionmn. SoitA?Rm×netB?Rn×p; le produitC=AB?Rm×pest d´efini parcij=?n k=1aikbkj. L"ensemble des matrices carr´eesRn×nest un anneau. Attention, cet anneau n"est pas commu- tatif (il existeAetBtels queAB?=BA). Attention, l"anneau n"est pas int`egre, car il existe des diviseurs de z´ero. Le produit de deux matrices diagonales est une matrice diagonale. Le produit de deux matrices triangulaires est une matrice triangulaire.

2.1.3 Matrices carr´ees sym´etriques

La transpos´eeAT?Rn×md"une matriceA?Rm×nest la matrice obtenue en interchangeant les lignes et les colonnes.

Une matrice carr´eeAest sym´etrique siA=AT.

11

Les matricesATAetAATsont sym´etriques.

On a (AT)T=Aet (AB)T=BTAT.

2.1.4 Partitions par blocs

Une matrice par blocs est d´efinie par une partition o`u les ´el´ements scalaires sont regroup´es dans

des sous-matrices ; on noteA=Aij.

On d´efinit les mˆemes r`egles d"op´erations, en respectant les dimensions dans les produits. At-

tention `a l"ordre des blocs dans les produits.

2.2 Normes matricielles

La norme matricielle euclidienne est associ´ee `a la norme vectorielle euclidienne et est d´efinie par

?A?2= maxx?=0?Ax?2?x?2= max?x?2=1?Ax?2. La norme matricielle infinie est associ´ee `a la norme vectorielle infinie et est d´efinie par j=1|aij|. La norme matricielle de Frobenius est la norme prise au sens de l"espace vectoriel de dimension mnet est d´efinie par ?A?F= (? i,ja

2ij)12

Remarque 2.2.1La norme matricielle euclidienne n"est pas simple `a calculer, contrairement `a la norme infinie et la norme de Frobenius. Voir le chapitre sur la SVD.

Proposition 2.2.1

?ej?2= 1 ?I?2= 1 ?D?2=maxi|di|

2.3 Orthogonalit´e dansRn

D´efinition 2.3.1x?y?xTy= 0

D´efinition 2.3.2cos(angle(x,y)) =xTy?x?2?y?2

Proposition 2.3.1Th´eor`eme de Pythagore :

Six?y, alors?x+y?22=?x?22+?y?22.

U

TU=Ik.

12 Remarque 2.3.1Attention, sik < n, on aUUT?=In. Voir preuve plus loin. Proposition 2.3.2Un syst`eme orthonorm´e forme un syst`eme libre. Remarque 2.3.2(e1,...,en)est une base orthonorm´ee deRn. D´efinition 2.3.4SoitSun sous-espace vectoriel deRn. L"orthogonal deSest d´efini par S ?={y/yTx= 0,?x?S}. Proposition 2.3.3S?est un sous-espace vectoriel et les sous-espacesSetS?sont suppl´ementaires. Proposition 2.3.4Th´eor`eme de la base incompl`ete. SoitUun syst`eme orthonorm´e de taillek. On peut compl´eterUparU1de taillen-k, pour former une base orthonorm´ee deRn. Le syst`eme U

1est une base orthonorm´ee deU?. AlorsUT1U1=In-ketUTU1= 0. Tout vecteurxs"´ecrit

x=UUTx+U1UT1x. D´efinition 2.3.5Q?Rn×nest orthogonale ssiQTQ=In. AlorsQQT=In. Les colonnes deQ forment une base orthonorm´ee deRn. ?x?Rn,?Ux?2=?x?2.

A?Rm×n,U?Rp×msyst`eme orthonorm´e, alors

?UA?2=?A?2.

Q?Rn×nmatrice orthogonale, alors

?AQ?2=?A?2. Preuve.?Ux?22= (Ux)T(Ux) =xT(UTU)x=xTx=?x?22?UA?2= max?x?2=1?UAx?2= max?x?2=1?Ax?2=?A?2. ?AQx?2= max?x?2=1?AQx?2= max?y?2=1?Ay?2=?A?2carQest inversible (?y,?x,Qx=y) et?Qx?=?x?.? Remarque 2.3.3Attention, siU?Rn×porthonorm´e, on peut avoir?AU?2?=?A?2.

2.4 Image, noyau, rang d"une matrice

A?Rm×n.

D´efinition 2.4.1Im(A) ={y?Rm/y=Ax}=V ect(a1,a2,···,an) ker(A) ={x?Rn/Ax= 0} Proposition 2.4.1Im(A) est un sev deRmetker(A)est un sev deRn. 13

D´efinition 2.4.2rang(A) =dim(Im(A))

Proposition 2.4.2Im(A)?=ker(AT)etIm(AT) =ker(A)?.

Preuve.y?Im(A)?? ?x,(Ax)Ty= 0? ?x, xT(ATy) = 0?ATy= 0?y?ker(AT).?

Proposition 2.4.3rang(A) =rang(AT)

dim(ker(A)) +rang(A)) =n dim(ker(AT)) +rang(AT)) =m Preuve.Soitr=rang(AT), on va montrer querang(A)≥r. Par transposition, on en d´eduira quer=rang(A). SoitX={x1,...,xr}une base deIm(AT) etY=AX. Par construction,Y?Im(A). On va queY v= 0?v= 0. Y v= 0?AXv= 0?Xv?ker(A). Orker(A) =Im(AT)?doncXv?Im(AT)?. MaisX est une base deIm(AT) doncXv?Im(AT). DoncXv= 0 et puisqueXest une base,v= 0.

D"apr`es la proposition pr´ec´edente, on adim(ker(A)) +rang(AT) =n, on en d´eduit l"´egalit´e

avecrang(A).? Proposition 2.4.4rang(A) =n´equivaut `aker(A) ={0}.

Preuve.´evident.?

Proposition 2.4.6SoitU= (u1...uk)etV= (v1...vk)deux syst`emes libres deRmet deRn respectivement, alorsUVT?Rm×net ker(UVT) =V?, Im(UVT) =Im(U), rang(UVT) =k. R´eciproquement, siAest une matrice de rangk, il existeU= (u1...uk)base deIm(A)etV= (v1...vk)base deker(A)?tels queA=UVT. Preuve.SoitA=UVT, alorsx?ker(A)?UVTx= 0?VTx= 0?x?V?donc ker(A) =V?. On en d´eduit querang(A) =kcardim(V?) =n-k. D"autre part,Im(A)?Im(U) d"o`u, par ´egalit´e des dimensions,Im(A) =Im(U). R´eciproquement, soitV?Rn×kune base orthonorm´ee deker(A)?, compl´et´ee parV1dans ker(A). Alors?x, x=V VTx+V1VT1xetAx=AV VTx. SoitU=AV, alorsAx=UVTxdonc A=UVT. De plus,Uest un syst`eme libre carUy= 0?AV y= 0?V y?ker(A)∩ker(A)?? y= 0, doncUest une base deIm(A).? Remarque 2.4.1En particulier, les matrices de rang1sont de la formeuvT, o`uuetvsont deux vecteurs non nuls. D´efinition 2.4.3SoitA?Rm×nune matrice rectangulaire avecm≥n;Aest dite de rang plein sirang(A) =n. 14

2.5 Valeurs propres et vecteurs propres

Nous consid´erons ici des matrices carr´ees d"ordren. Avant de d´efinir la notion de valeur propre,

nous devons d´efinir le d´eterminant d"une matrice carr´ee. Nous choisissons une d´efinition r´ecursive.

D´efinition 2.5.1SoitA?Rn×nune matrice carr´ee. Le d´eterminant deAest d´efini par det(A) =n? j=1(-1)j+1a1jdet(A1j), o`uA1jest la matrice carr´ee d"ordren-1obtenue en supprimant la ligneiet la colonnejdans la matriceA. D"autre part,det(a) =apour une matricead"ordre 1.

Proposition 2.5.1det(AB) =det(BA)

det(AT) =det(A) det(αA) =αnA det(I) = 1 det(A)?= 0?rang(A) =n.

Proposition 2.5.2La fonction de la variable complexeλd´efinie pardet(A-λI)est un polynˆome

de degr´en. On l"appelle le polynˆome caract´eristique deA. D´efinition 2.5.2Le nombre complexeλest valeur propre de la matrice carr´eeAs"il existe un vecteurxnon nul tel queAx=λx. Proposition 2.5.3Les valeurs propres deAsont les racines du polynˆome caract´eristique. Il y a doncnvaleurs propres, distinctes ou non. Les valeurs propres deAet deATsont les mˆemes. Preuve.Ax=λx´equivaut `a (A-λI)x= 0 ´equivaut `ax?ker(A-λI). Doncxnon nul existe si et seulement sirang(A-λI)< nsi et seulement sidet(A-λI) = 0. Tout polynˆome de degr´endans l"ensemble des nombres complexes anracines complexes, compt´ees avec leur multiplicit´e.

On adet(A-λI) =det(AT-λI).?

D´efinition 2.5.3Le spectre deAest l"ensemble desnvaleurs propres deA. Le rayon spectral de Aest le plus grand module dans le spectre. La trace deAest la somme des ´el´ements diagonaux; c"est aussi la somme des valeurs propres.

2.6 Notions de complexit´e et de performances

Les algorithmes de calcul sont caract´eris´es par leur complexit´e arithm´etique, mesur´ee par le nombre

d"op´erations (additions, multiplications, etc) sur des r´eels, ainsi que par leur coˆut de stockage,

mesur´e par le nombre de variables r´eelles. Le stockage des entiers et les calculs entiers sont d"un

coˆut marginal, qui est ignor´e. En pratique, les op´erations arithm´etiques et le stockage se font sur

des nombres flottants (voir chapitre sur l"arithm´etique flottante). Les performances d"un algorithme se mesurent par sa vitesse de calcul. Celle-ci d´epend de la

complexit´e mais aussi de l"exploitation de l"architecture de l"ordinateur, notamment du parall´elisme

interne et de la hi´erarchie des m´emoires. 15 Pour la complexit´e, on donnera souvent le terme pr´edominant, du plus grand ordre, sous la formeO(cnk). Cela signifie que le nombre d"op´erations divis´e parcnktend vers 0 quandntend

vers l"infini. Par exemple, pour une complexit´e polynomiale enn, le terme pr´epond´erant est celui

du plus grand degr´e dans le polynˆome.

2.7 Biblioth`eques BLAS et LAPACK

Les op´erations de base d"alg`ebre lin´eaire sont regroup´ees dans une biblioth`eque num´erique appel´ee

BLAS : Basic Linear Algebra Subroutines. Cette biblioth`eque est souvent fournie par le construc-

teur et optimis´ee pour une architecture donn´ee. Les op´erations sont divis´ees en trois niveaux,

appel´es BLAS1, BLAS2, BLAS3. L"optimisation concerne l"ordre des op´erations et l"acc`es `a la

m´emoire, pour exploiter au mieux la hi´erarchie (m´emoire principale, m´emoire cache, etc). Les

performances (vitesse de calcul) sont d"autant meilleures que le niveau est ´elev´e.

Les op´erations plus complexes sont regroup´ees dans la biblioth`eque num´erique appel´ee LA-

PACK : Linear Algebra Package. Les op´erations de LAPACK utilisent au maximum les op´erations BLAS, surtout BLAS3, qui est le plus performant en temps de calcul.

2.7.1 Op´erations BLAS1

Ce niveau concerne les op´erations entre vecteurs. Quelques exemples : •combinaison lin´eaire de vecteursz=a?x+b?y, •produit scalaire de vecteursa=xTy.

Toutes les op´erations BLAS1 ont une complexit´e enO(n) op´erations arithm´etiques (sur les

nombres r´eels) et un acc`es m´emoire enO(n) mots (r´eels).

Il n"y a qu"un niveau de boucle.

2.7.2 Op´erations BLAS2

Ce niveau concerne les op´erations entre matrices et vecteurs. Quelques exemples : •produit matrice-vecteury=a?y+b?Ax, •produit ext´erieur de vecteursA=xyT. Toutes les op´erations BLAS2 ont une complexit´e enO(n2) et un acc`es m´emoire enO(n2). Il y a deux niveaux de boucle imbriqu´es, ce qui permet de construire deux variantes suivantquotesdbs_dbs47.pdfusesText_47

[PDF] math autour de moi

[PDF] math c urgent

[PDF] math calcul

[PDF] math calcul temps

[PDF] math calculator solver

[PDF] math calcule fractionnaire

[PDF] math cned

[PDF] Math cned n3 ! Merci SECONDE

[PDF] Math cned seconde année

[PDF] MATH COMMENT FAIRE POUR CONSTRUIRE UN TRIANGLE OU ON NOUS DONNE LA MESURE DE 3 ANGLE ET DEUX COTES

[PDF] Math compléter

[PDF] Math complexes

[PDF] Math consultez et repondez

[PDF] Math conversion 5°

[PDF] math correction DS