Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

Stef Graillat

Description

Modélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB(MODEL)oCours n 7 : Calcul matriciel (1/2)Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) MODEL (cours n˚7) 1 / 24Résumé du cours précédentPrésentation de l’arithmétique à virgule flottanteIntroduction au logiciel MATLABIntroduction à la Symbolic Math Toolbox de MATLABS. Graillat (Univ. Paris 6) MODEL (cours n˚7) 2 / 24ObjectifsOn considère des calculs utilisant des matrices denses (c’est à dire avec peud’éléments nuls)Nous avons besoin de1 manipuler efficacement ces matrices sur un ordinateur2 choisir la décomposition adéquate pour résoudre un problème donnéS. Graillat (Univ. Paris 6) MODEL (cours n˚7) 3 / 246Problèmes classiques en calcul matricielRésolution de systèmes linéaires : étant donné une matrice A de taille nnet un vecteur b de taille n, trouver x tel queAx = bRésolution de problèmes de moindres carrés : étant donné une matrice A detaille mn (avec m> n) et un vecteur b de taille m, résoudreminkb AxkxRésolution de problèmes aux valeurs propres : étant donné une matrice Ade taille n, trouver un vecteur x = 0 et un scalaire tels queAx =xS. Graillat (Univ. Paris 6) MODEL (cours n˚7) 4 / 24Plan du cours1 Manipulation des matrices1 comment sont stockées les matrices en machine?2 outils de base pour la manipulation de matrice : les BLAS2 Décomposition de matrice et applications1 LU2 QR3 Réduction ...

Informations

• Publié par: Ornui
• Nombre de lectures: 48
• Langue: Français

Extrait

.S

Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB (MODEL)

rGaillat(Univ.Pa

Cours n o 7 : Calcul matriciel (1/2)

ris6)

Stef Graillat

Université Pierre et Marie Curie (Paris 6)

MODELc(uosr˚n)71/24

Résumé du cours précédent

.S

Présentation de l’arithmétique à virgule flottante

Introduction au logiciel MATLAB

Introduction à la Symbolic Math Toolbox de MATLAB

rGalialtU(in.vParis)6OMEDL(cours˚n)72/42

Objectifs

On considère des calculs utilisant desmatrices denses(c’est à dire avec peu d’éléments nuls)

Nous avons besoin de 1 manipulerefficacementces matrices sur un ordinateur 2 choisir ladécompositionadéquate pour résoudre un problème donné

S.Gralilat(Univ.aPirs)6OMEDLc(oursn˚7)3/24

Problèmes classiques en calcul matriciel

Résolution de systèmes linéaires: étant donné une matriceAde taillen×n et un vecteurbde taillen, trouverxtel que

Ax=b

Résolution de problèmes de moindres carrés: étant donné une matriceAde taillem×n(avecm>n) et un vecteurbde taillem, résoudre

minkb−Axk x

Résolution de problèmes aux valeurs propres: étant donné une matriceA de taillen, trouver un vecteurx6=0 et un scalaireλtels que

.SrGaillat(Univ.aPirs)6M

Ax=λx

DOEL(coursn˚7)4/24

Plan du cours

1

2

3

S.

Manipulation des matrices 1 comment sont stockées les matrices en machine ? 2 outils de base pour la manipulation de matrice : les BLAS

Décomposition de matrice et applications 1 LU 2 QR 3 Réduction (diagonalisation, etc.) 4 SVD (décomposition en valeurs singulières)

Logiciels

Graillat(Univ.Paris)6MODELc(uosrn˚7)5/42

Bibliographie

S.

Scientific Computing with Case Studies, D. O’Leary, SIAM, 2009 Applied Numerical Linear Algebra, J. Demmel, SIAM, 1997 Numerical Linear Algebra, L. N. Trefethen et D. Bau, SIAM, 1997 Matrix Computations, G. Golub et C. Van Loan, Johns Hopkins University Press, 1996 Analyse numérique matricielle, L. Amodei et J.-P. Dedieu, Dunod, 2008 Algèbre linéaire numérique, G. Allaire et S. M. Kaber, Ellipses, 2002 Introduction à l’analyse numérique matricielle et à l’optimisation, P. G. Ciarlet, Dunod, 2006 Analyse numérique matricielle appliquée à l’art de l’ingénieur, P. Lascaux et R. Théodor, Dunod, 2004

Graillat(Univ.aPirs)6OMEDLc(uorsn˚7)6/24

Notations

.S

les vecteurs sont des vecteurs colonnes les matrices sont notées en majuscule et les vecteurs et scalaires en minuscule les éléments d’une matriceAen position(i,j)sont notésa ij ouA(i,j) Iest lamatrice identitéete i lei-èmevecteur unité B=A T signifie queBest latranposéede A :b ij =a ji B=A ∗ signifie queBest latransconjuguéedeA:b ij =a ji on utilise aussi la notation MATLAB. Par exempleA(i:j,k:l) représente la sous-matrice deAavec les lignes deiàjet les colonnes dekàl unematrice orthogonaleUvérifieU T U=I unematrice unitaireUvérifieU ∗ U=I deux matricesAetBsont ditessemblabless’il existeXinversible telle queB=XAX −1

rGalialt(Univ.Paris6)MODELc(uosr˚n)77/42

Normes vectorielles et matricielles

Définition 1 Unenorme vectorielleest une fonctionk ∙ k:C n →R + vérifiant 1 kxk=0ssi x=0 2 kαxk=|α|kxkpour toutα∈Cet x∈C n 3 kx+yk ≤ kxk+kykpour tout x,y∈C n

Exemple 1

.S

n kxk 1 =|x 1 |+∙ ∙ ∙+|x n |= X |x i | i=1 n kxk 2 = (|x 1 | 2 +∙ ∙ ∙+|x n | 2 ) 1/2 = ( X |x i | 2 ) 1/2 i=1

kxk ∞ = 1 m ≤i a ≤ x n |x i |

Graillat(Univ.aPris6)MODELc(oursn˚7)8/42

Normes vectorielles et matricielles (suite)

Définition 2 Unenorme matricielleest une fonctionk ∙ k:C m×n →R + vérifiant les mêmes propriétés que pour les normes vectorielles

Exemple 2

kAxk Norme subordonnéeà une norme vectorielle :kAk=s x6 u = p 0 kxk

.S

kAk 1 =s x6 u = p 0 k k x xA k k 1 1 = 1 m ≤j a ≤ x i n = m X 1 |a ij | n kAk ∞ = x s 6 u = p 0 k k Ax x k k ∞ ∞ = 1≤ m i a ≤ x m j= X 1 |a ij | kAxk 2 kAk 2 =s x6 u = p 0 kxk 2

rGaillat(Univ.aPirs)6OMEDL(cours˚n7)9/24

y i =A(i,:)x

Étant donnés un matriceAde taillem×net un vecteurxde longueurn, on veut calculery=Ax Le vecteuryest défini par des produits scalaire entre les lignes deAet x

Exemple:produit matrice-vecteur

→Pourprogrammer efficacementdes algorithmes sur les matrices, il est très important de savoir comment sontstockéesles matrices enmémoire!

Stockage des matrices

42/01ir6s.vaPU(inlltan˚7)oursEL(c)MOD ,i(Ax∗)jy=)i+)i( S. nd aiGr );(j d e en 1,;) ofir z=resom( j=1:n, y( =1:m, for zi(e)A y ;[,m]ns=

Stockage des matrices (suite)

S.

On peut exprimerAxen utilisant plutot les colonnes deA

Ax=x 1 A(:,1) +x 2 A(:,2) +∙ ∙ ∙+x n A(:,n)

[ m, n ]=s i z e(A ) ; y =z e r o s(m, 1 ) ; f o rj =1: , n f o ri =1:m, y ( i ) = y ( i ) + A( i , j )∗ j ) ;x ( end end

GralilatU(in.vaPirs)6OMEDL(coursn˚7)11/42