7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
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