Systemes lineaires et matrices

Description

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?

Sujets

• multiplication
• exercice
• mathe
• cours
• exercices
• cours de

Informations

• Publié par: pefav
• Nombre de lectures: 50
• Langue: Français

Extrait

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 ´ 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 ) i j = = 1 1           m n 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'unsyste  melin ´ 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