Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Systemes lineaires et matrices

12 pages
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?


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin