Systemes lineaires et matrices
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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.
Voir
- 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?
CHAPITRE XVIII
Syste mesline´airesetmatrices
Syste meslin´eaires. Consid´eronsun syste med'´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 ´ Enalg ebrelineaireond´eveloppelathe´oriedecessysetm essuruncorpsouunanneau 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 mani ere exacet sur ordinateur. Lorsque K = R ou K = C ,parcontre,onfaitrecoursaucalculnum´eriquearrondi:lesdonne´esinitiales,lescalculs interme´diairesetlesre´sultatsnauxnesontquedesvaleursapproch´ees. Structuration du proble me. 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'´ecrirecesyst emeplussuccinctementcomme Ax = y C'estbienplusqu'unenotationcommode.Cettestructurationdesdonn´eesestlepointdede´partdetous lesalgorithmespourlare´solutiondesyst emeslin´eaires.Ayantx´elesdonne´es A et y , il s'agit de trouver les solutions x ve´riant Ax = y .Or,lesprobl emesli´es alare´solutiondessyst emense´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 probl emes lie´s au conditionnement du syst eme et a la p raogation d'erreurs. Re´solutiond'unsyste melin´eaire. Si A est une matrice inversible, de taille n × n , le syst eme Ax = y est´equivalent a 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 syst emes 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,nesongezpas al'utilisersurordinateur. Cechapitrerappelleetimple´mentequelquesm´ethodese´l´ementaires,notammentl'e´liminationde Gauss,permettantder´esoudredessyst emesdetaillemoyenne,disons n ≤ 100. Nous n'indiquerons qu'en passantdesprobl emespossiblesetdesvariantesquireme´dientauxinconv´enientslesplusfr´equents. Sommaire 1.Impl´ementationdematricesenC++. 1.1.Matricesdensesvscreuses.1.2.Uneimpl´ementation faite maison. 1.3. Multiplication d'apr es Strassen. 1.4.Inversion d'apr es 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
