Systemes lineaires et matrices

Publié par

CHAPITRE XVIII Systemes lineaires et matrices Systemes lineaires. Considerons un systeme d'equations lineaires : ? ? ? ? ? ? ? ? ? a11x1 + a12x2 + · · ·+ a1nxn = y1 a21x1 + a22x2 + · · ·+ a2nxn = y2 . . . am1x1 + am2x2 + · · ·+ amnxn = ym En algebre lineaire on developpe la theorie de ces systemes sur un corps ou un anneau K, et on apprend certaines methodes pour leur resolution, notamment la methode de Gauss rappelee plus bas. Ici les donnees ai j et yi sont des coefficients dans K et les x j sont les inconnues, a determiner dans la suite. Pour K = Z ou K = Q ou K un corps fini, on peut effectuer ces calculs de maniere exacte sur ordinateur. Lorsque K = R ou K = C, par contre, on fait recours au calcul numerique arrondi : les donnees initiales, les calculs intermediaires et les resultats finaux ne sont que des valeurs approchees. Structuration du probleme. Comme vous en avez l'habitude, la matrice A = (ai j)i=1,...,mj=1,...,n et les vec- teurs x = (x j) j=1,...,n et y = (yi)i=1,...,m permettent d'ecrire ce systeme plus succinctement comme Ax = y.

  • depend du cout respectif de la multiplication et de l'addition des coefficients

  • multiplication

  • structuration des donnees

  • question de la representations des donnees et du choix des algorithmes

  • ligne après ligne

  • cout

  • calcul numerique

  • matrice vn de taille n?


Publié le : mardi 19 juin 2012
Lecture(s) : 80
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 12
Voir plus Voir moins
CHAPITRE XVIII
Systemesline´airesetmatrices
Systemeslin´eaires. Consid´eronsun systemed'´equationslin´eaires : a 11 x 1 + a 12 x 2 +    + a 1 n x n = y 1 a 21 x 1 + a 22 x 2 +    + a 2 n x n = y 2 . a m 1 x 1 + a m 2 x 2 +    + a mn x n = y m ´ Enalgebrelineaireond´eveloppelathe´oriedecessysetmessuruncorpsouunanneau K , et on apprend certainesm´ethodespourleurr´esolution,notammentlam´ethodedeGaussrappele´eplusbas.Icilesdonne´es a i j et y i sont des coefcients dans K et les x j sontlesinconnues,ad´eterminerdanslasuite.Pour K = Z ou K = Q ou K un corps ni, on peut effectuer ces calculs de maniere exacet sur ordinateur. Lorsque K = R ou K = C ,parcontre,onfaitrecoursaucalculnum´eriquearrondi:lesdonne´esinitiales,lescalculs interme´diairesetlesre´sultatsnauxnesontquedesvaleursapproch´ees. Structuration du probleme. Comme vous en avez l'habitude, la matrice A = ( a i j ) ij == 11 mn et les vec-teurs x = ( x j ) j = 1  n et y = ( y i ) i = 1  m permettentd'´ecrirecesystemeplussuccinctementcomme Ax = y C'estbienplusqu'unenotationcommode.Cettestructurationdesdonn´eesestlepointdede´partdetous lesalgorithmespourlare´solutiondesystemeslin´eaires.Ayantx´elesdonne´es A et y , il s'agit de trouver les solutions x ve´riant Ax = y .Or,lesproblemesli´esalare´solutiondessystemense´laiiressontdivers. Ilyad'abordlaquestiondelarepre´sentationsdesdonn´eesetduchoixdesalgorithmesadapt´es(petites matrices denses, grandes matrices creuses, matrices trigonales, en blocs, en bandes, etc.). Il y a d'une part desquestionshabituellesdelacomplexit´ealgorithmique.Ilyad'autrepart,lorsducalcul num´erique , les problemes lie´s au conditionnement du systeme et a la p raogation d'erreurs. Re´solutiond'unsystemelin´eaire. Si A est une matrice inversible, de taille n × n , le systeme Ax = y est´equivalenta x = A 1 y . C'est cette me´thode qui est souvent utilise´e dans les pet its exemples, disons n = 3 ou n = 4. On de´veloppera cette de´marche au § 1 pour les matrices de petite taille, disons n 10, par lam´ethodedeFaddeev.Soulignonsdeuxavertissements: + Le calcul de la matrice inverse A 1 est e´quivalent a la re´solution de n systemes lin´ ires A ea v i = e i . Ceci peut ˆetre assez co ˆuteux, a savoir d'ordre O ( n 3 ) op´erationssi A est dense, c'est-a-dire, ne comporte que peu de coefcients nuls. Ce n'est pas toujours la meilleure solution. + LaformuledeCramerquin´ecessitelecalculde n + 1d´eterminants,soit ( n + 1 ) ! ope´rations, est, quant a elle totalement inexploitable. (Calculer 10! ou 20! voire 50! pour vous en convaincre.) Aussiimportantequ'ellesoitpourlath´eorie,nesongezpasal'utilisersurordinateur. Cechapitrerappelleetimple´mentequelquesm´ethodese´l´ementaires,notammentl'e´liminationde Gauss,permettantder´esoudredessystemesdetaillemoyenne,disons n 100. Nous n'indiquerons qu'en passantdesproblemespossiblesetdesvariantesquireme´dientauxinconv´enientslesplusfr´equents. Sommaire 1.Impl´ementationdematricesenC++. 1.1.Matricesdensesvscreuses.1.2.Uneimpl´ementation faite maison. 1.3. Multiplication d'apres Strassen. 1.4.Inversion d'apres Faddeev. 2 L ´thode de Gauss. 2.1. L'algorithme de Gauss. 2.2. Conditionnement. 2.3. Fac torisation . a me LU . 2.4. Me´thode de Cholesky. 327
328
ChapitreXVIII—Systemeslin´eairesetmatrices
1.Impl´ementationdematricesenC++ 1.1. Matrices denses vs creuses. Commen¸conle´el´ementsdebasedetouttraitementalgorith-s par s mique:larepr´esentationdesdonne´esetlesope´rationse´le´mentaires.Cettepremiere´etapeestdegrande importance,carlamode´lisationd´ependfortementduchampsd'applicationenvisage´: –Veut-onmod´eliserdesmatrices denses , c'est-a-dire comportant peu de coefcients nuls ? S'agi-til desmatricesge´n´eriques?ousyme´triques?Ont-ellesdespropri´ete´sparticulieres?... –Veut-onmod´eliserdesmatrices creuses , c'est-a-dire comportant beaucoup de ze´ros ? S'agit-il des matrices concentre´es autour de la diagonale ? Ou des matrices triangulaires ? Ou en blocs ? . . . Question 1.1 (a titre d'exemple) . Une matrice dense de taille m × n n´ecessitelestockagede mn coef-cients,cequipeutfacilementde´borderlam´emoiredisponible.Discutersil'onpeutstockerpuisadditionner et multiplier des matrices denses de taille 100 × 100, 1000 × 1000, ou 10 4 × 10 4 , ou 10 5 × 10 5 , etc. Jusqu'ouest-cepossiblepourdesmatricescreuses?Pr´ecisezquelgenredematricescreusesvous conside´rez puis esquissez comment les stocker et comment les additionner et multiplier. 1.2.Uneimpl´ementationfaitemaison. Dans ce chapitre on conside´rera des matrices denses, alors que le projet annexe sur Google traitera un cas de matrices creuses. Exercice/P 1.2. Le chier matrix.cc impl´ementeuneclasseg´ene´rique Matrix<T> pour stocker des matrices denses de taille m × n dont les coefcients sont d'un type T etindex´espar ( i j ) avec i ∈ { 1      m } et j ∈ { 1      n } .Essayezdecomprendrelecodede´jaimpl´emente´.Ajouterlesope´rationsusuelles: Matrix<T> operator + ( const Matrix<T>& a, const Matrix<T>& b ) Matrix<T> operator - ( const Matrix<T>& a, const Matrix<T>& b ) Matrix<T> operator * ( const Matrix<T>& a, const Matrix<T>& b ) Conseil. — Quand vous utilisez des constantes, il vaut mieux e´crire T(0) et T(1) au lieu de 0 et 1 de type int :laconversionexpliciteassureralebonr´esultat,quelquesoitletype T utilis´e.Sanscette pr´ecaution,vousobligezlecompilateuradevinerlui-meˆmelaconversion,cequin'estpastoujourspossible. Mˆemesic'estpossible,laconversionimplicitechoisien'estpasforc´ementcellequevoussouhaitez. Gestion d'exceptions. — Quand les dimensions de a et b correspondent, l'imple´mentation ne pose pas deprobleme.Sinon,ilfautd´ecidercommentge´rercetteexception.Onpeutrenvoyerlamatricevide,de dimension 0 × 0, pour signaler l'erreur ou bien afcher un message d'erreu r et abandonner le calcul. On pourrait aussi « tronquer » convenablement les matrices, ou bien les « stabiliser » c'est-a-dire les e´largir convenablementenajoutantdescoefcientsz´eros. Remarque 1.3 (complexite´) . Pour estimer le co ˆut des calculs ulte´rieurs il est important de connaˆtre d'abordlacomplexit´edesope´rationse´le´mentaires.Onconsiderelesmatrices n × n et on compte le nombre d'op´erationseffectu´surlescoefcients. ees (1) Pour l'addition C = A + B on parcourt toutes les paires ( i j ) pardeuxbouclesimbriqu´eespour i = 1      n et j = 1      n . Pour chaque ( i j ) on calcule c i j a i j + b i j . Ceci fait n 2 additions. (2) Pour la multiplication scalaire C = l A on utilise deux boucles imbriquees et calcule c i j l a i j ´ pour chaque ( i j ) . Ceci ne´cessite n 2 multiplications, et on ne peut pas espe´rer de faire mieux. (3) La multiplication C = A B , par contre, est plus complexe. Le calcul directe de c i j å nk = 1 a ik b k j ne´cessite trois bouclesimbriqu´ees,pour i et j et k . Cet algorithme de multiplication ne´cessite donc n 3 multiplication et n 2 ( n 1 ) additions, au total donc presque 2 n 3 ope´rations. 1.3. Multiplication d'apres Strassen. Lad´enitionduproduit C = A B par la formule c i j = å nk = 1 a ik b k j donneimm´ediatementlieuaunalgorithmedemultiplicatoindematrices.Sicetalgorithmeestsatisfaisant pour les matrices de petite taille, le co ˆut cubique se fait sentir pour les grandes matrices. En 1969 V. Strassen de´couvrit une multiplication plus rapide. Puisquelesmultiplicationssontpluscoˆuteusequelesadditions,onessaierad'´economiserlesmulti-plications—mˆemeauprixdequelquesadditionssuppl´ementaires.Concretement,pourcalculer C = A B on suppose A B C de taille n × n avec n = 2 m . On les de´compose en blocs de taille m × m : A = AA 2111 AA 2122 B = BB 2111 BB 1222 C = CC 2111 CC 2122 MAE 22 juin 2009
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.