66UNIVERSITE DE BOURGOGNE L3-MATHEMATIQUESLM5: Analyse Nume´rique Ele´mentaire,´Un exemple de Me´thode directe: METHODE de GAUSSI IntroductionOn se propose de re´soudre le syste`me de Cramer suivant: a ... a b1,1 1,n 1 . . . n.AX = b ou` A= . . . ∈ Gl(n,R) (⇔ detA= 0) et b= . ∈R . .. . .a ... a bn,1 n,n n x1 . n.ou` X = ∈R est l’inconnue. On sait qu’il existe une unique solution. .xnQuelques rappels sur les permutations de lignes et de colonnes dans les matrices:nSoit la matrice P qui permute le i ie`me vecteur et le j ie`me vecteur de la base canonique deR en fixant les autresi, jvecteurs de base: 1 0 0 0 . .. . . . 0 ... 0 ... 1 0 0 1 0 P == . i, j . ... . . .. . 0 ... 1 0 ... 0 .. . 00 ... 0 ... 0 1Alors la matrice P A est obtenue a` partir de A en e´changeant dans A la ligne i et la ligne j sans changer les autres. Lai, jmatrice AP est obtenue a` partir de A en e´changeant dans A la colonne i et la colonne j sans changer les autres.Remarquonsi, jque detP =−1,i= j et detP = 1.i, j i,iII Me´thode de GAUSS:1 Proce´de´ d’e´limination des variables:∗ Exemple:Avant l’algorithme ge´ne´ral , commenc¸ons par un exemple. La me´thode de Gauss consiste a` remplacer le syste`meinitial par un syste`me triangulaire e´quivalent. Soit le syste`me:(1) x +2y +2z = 2, l 1(1) (1) (1)(⋆) ⇔ A X = b ,x +3y +3z = 2, l2 (1)3x +7y +8z = 8. l3ou`: 1 2 2 2(1) (1) A = 1 3 3 et b = 2 .3 ...
´ Un exemple de Me´thode directe: METHODE de GAUSS
L3-MATHEMATIQUES
I Introduction Onseproposeder´esoudrelesyst`emedeCramersuivant: a1,1. . .a1,nb1 .n A.∈Gl(n,R) (⇔detA6=0)etb=∈R. X=bo`uA=.. . . an,1. . .an,nbn x1 n ou`X= ∈Rest l'inconnue. On sait qu'il existe une unique solution. . xn Quelques rappels sur les permutations de lignes et de colonnes dans les matrices: n Soit la matricePi,jqui permute leiie`me vecteur et lejeedquninocaseabaledruetcevemei`Ren fixant les autres vecteurs de base: 1 00 0 . . .. 0. . .0. . .1 0 0 10 Pi,j==. . . ... 0. . .1 0. . .0 . . . 0 0. . .0. . .0 1 Alors la matricePi,jAest obtenue a` partir deAaetnahgn´nceedansAla ligneiet la lignejsans changer les autres.La matriceAPi,jseottbrtirdeenue`apaAen e´changeant dansAla colonneiet la colonnejsans changer les autres.Remarquons que detPi,j=−1,i6=jet detPi,i=1.
(k) (k+1) Ne pas oublier que dans le passage deA`aA, leskpremie`res lignes sont conserve´es, d'ou` l'indice(1)en haut dans la premie´re ligne, puis(2)dslanecasednongil...esenO-ugnairtrae´´n`eacemdtno`emesystreunsoud laire e´quivalent. (k) ∗`usoCavitoas'lnuedpsulestn: k,k (k) (2) (k) (k) Supposons que l'on ait pu construire(A, ..,Atetneuqde´cemmemeom´eprcaest nul.Comme det(A) k,k est non nul et que: (k) (k) a. . .a k,k k,n (1) (k−1) (k) det(A) =a..adet . . 1,1k−1,k−1 (k) a. . .an,n n,k (k) (k) (k) n´ecessairementundese´l´ements(a, ...,a)ulnnnostsconot.n´lmetee´eneta,ik≥k+1. Alorsla matrice k+1,k n,k i,k k (k) (k) (k) Aneiggndelela´(ceahket de la ligneidansAequelluremeaa)`malAontisipotnnee´em´nleteos Pik,k k (k,k)lpqieua`ecttneuovellematricelepre´code´dle´'nimiioat´endlove´epp´cderpe´tn,meemstepanosrolA.lunnon defa¸con`amettredesze´rosdanslakilocome`eaarealpred`tnink+1 ie`me ligne.On a: (k+1) (k) (k) A=E (Pik,kA), (k) (k) o `ula matriceEedrseocfe`sparaitruitemaientconste´cemmedllec´rpermfoueeqamalme`eP ficients dik,kA. Oncontinued'it´ererainsi.Alane´eti`emna:apeo (n) (n−1) (k) (1) =E P...E P.A Ain−1,n−1ik,k..E Pi1,1 matrices 1...n−lignes. On1 sont l'ide o `ueventuellement lesPik,k,k='ylndianqu´eitntedegnahce´'dsapa d´eduitlethe´ore`mesuivant: Th´eor`eme: SoitAunematricere´elled'ordren.AlorsilexisteunematriceMdede´terminant´egala`1ou−1tel que: MA=T ou` T est triangulaire. (k) Si dans la me´thode de Gauss aucun des coefficients a,k=1..n−1n'est nul , alors : k,k (n−1) (n−2) (1) M=E E..E, ,detM=1.