Cette publication est accessible gratuitement
Télécharger
UNIVERSITE DE BOURGOGNE
LM5: Analyse Nume´rique Ele´mentaire,
´ 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.
IISUAGM´Shoetdede:
1vsraailbse:d'´eliminationdeP´core´de
Exemple: Avantl'algorithmeg´ene´ral,commenc¸onsparunexemple.Lam´ethodedeGaussconsiste`aremplacerlesyst`eme initialparunsyst`emetriangulaire´equivalent.Soitlesyst`eme: (1) x+2y+2z=2,l 1 (1) (1) (1) A X=b, ()x+3y+3z=2,l 2 (1) 3x+7y+8z=8.l 3 ou`:   1 2 22 (1) (1)   A=1 3 3etb=2. 3 7 88
1
ime`Per:tapere´e (1) On conservel, la premie`re ligne du syste`me()lumnuetuledelpit,pjonasouilaaapremi`ereligne` 1 (1) (1) (1) (1) secondeleteleemrndacefn`¸onnaaerulx. Dansl'exemple on remplacelparll. Onrefait la 2 22 1 (1) (1) (1) meˆme chose avec la troisie`me ligne soit on remplacelparl3l.On obtient: 3 31 (2) x+2y+2z=2,l 1 (2) (2) (2) (⋆⋆) +y+z=0,lA X=b, 2 (2) +y+2z=2.l 3 ou`:   1 2 22 (2) (2)   A=0 1 1etb=0. 0 1 22 econde´etape:S On reprend le syste`me(⋆⋆)esotgienmelexu`iroisalatute`najovresnocnou`odeetre`emipeeselenme`igile (2) (2) (2) unmultipledelasecondelignedefa¸cona`annulerletermeeny.Icionremplacedonclparll. On 3 32 obtient le syste`me(⋆ ⋆ ⋆): (3) x+2y+2z=2,l 1 (3) (3) (3) (⋆ ⋆ ⋆) +y+z=0,lA X=b, 2 (3) +z=2.l 3 ou`:   1 2 22 (3) (3)   A=et0 1 1b=0. 0 0 12 Onobtientunsyste`metriangulairequel'onr´esoudfacilementparunermonte´ea`partirdeladerni`ere ´equation.Lasolutionest:   2   X=2. 2 e:gsaC:Pr´esen´en´eralrpcoe´´datitnoud Onrevientausyste`mege´ne´raletonappliquelemˆemeproc´ede´d'e´liminationdesvariablesquedansl'exemple pre´c´edent. (1) (1) On poseA=Aetb=bet on introduit la suite desnstsyssiue`emdsCeavtnr´eqramelentsu:iva (k) (k) A X=bk∈ {1, ..,n}   (k) (k) (k) a a. . .a 1,1 1,2 1,n (k) 0a. . . 2,2  (k) . .b . .1 . .. (k) (k) (k)n ou`A=Gl(n,R) (detA6=0)etb=R. (k) (k)..0a. . .a (k) k,k k,n bn   . .(k) 0. . .0a. . .an,n n,k (k) (k+1) amalcirtAeelamatriceA`aaPssgade: (k) (k) (k) Comme det[A]6=tseneml´´eesnd0ua, ..,aPour une simplification des notations ( et deest non nul. k,k n,k (k) la frappe!)supposons quea6=0k∈ {1, ..,n}, sinon par multiplication par une matrice d'e´change de lig nes k,k (k) entre la lignei0k(aveca6=0) et la lignekuorrtauoojrussreamener`acecassancsahgnre'llaulerdenpo i,k 0 (k) Amais il faudrait introduire une nouvelle matrice. (k) (k) (k+1) (k) Le passage deA`aAse fait en prenant pour pivota6=0: leskslignesdremi`ereepAsont con-k,k (k+1) (k+1) serve´es dansA, puis on met des0dans la colonnekdeAde la lignek+1a`nen utilisant la lignek (k) deA.
(k+1) (k) Plus pre´cisement,Aest construite a` partir deAde la fac¸on suivante:
2
a. Pourtoutide 1 a`kon a:
(k+1) (k) ligneideA=ligneideA (k+1) (k+1) (k+1) (k) (k) (k) (k) (k) (a, ..,a, ..a) = (a, ..,a, ..a) = (0, ..,0,a, ..a). i,1i,k i,n i,1i,k i,n i,i i,n b. Pourtoutidek+`1anon a: (k) a i,k(k+1) (k+1) (k+1) (k) (k) ligneideA=ligneideAlignekdeA= (0, . . . ,0,a, . . . ,a), i,k+1i,n (k) a k,k (k+1) a=0j=1..k i,j (k) a (k+1) (k)i,k(k) a=aaj=k+1...n i,j i,j k,j (k) a k,k (k+1) (k) (n) en fonction de A :et Aen fonction de AEcriture de A (k) (k) (k+1) On suppose toujours qu'au passage deAa`Ale pivot esta6=0,pour toutk=1, ..,n1.Posons: k,k   1 0. . .0 0 10 . . . . . . 0. . .0 10. (k) (k) (k) E=a.,k=1, ...,n1,det(E) =1. +. k1k .01 . (k) a k,k . . .. 0 (k)an,k 0. . .00. . .1 (k) a k,k Alors on peut constater que: (k+1) (k) (k) (k) (k1) (1) A=E A=E E..E A.() D'o`u: (n) (n1) (1) (1) (n1) (1) (n) A=E..E A=E..E A=MA,detA=detA6=0. (k) (k+1) Passage de b`a b: (k) (k) On fait sur la colonnebuqserumsel´emesop´erationsAsoit :   (k) b 1 . (k) (k) a (k+1)b(k+1) (k)i,k(k) (k) (k) k b=o`ui=k+1, ..,n,b=bb=E b. (k+1)i ik (k) b k+1a k,k .(k+1) bn Conclusion: A l' e´tapen:els'´ecritsyst`eme (n) (n) A X=bavec :
  (1) (1) (1) a a. . .a 1,1 1,2 1,n (2) 0a. . . 2,2 . . . . . .. (n) A=MA=, (k) (k) .0a. . .a k,k k,n . . . . . .   (n) 0. . .0an,n (n) b=Mb, (n1) (n2) (1) M=E E..E,detM=1.
3
(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) (k1) (k)   det(A) =a..adet . .1,1k1,k1 (k) a. . .an,n n,k (k) (k) (k) n´ecessairementundese´l´ements(a, ...,a)ulnnnostsconot.n´lmetee´eneta,ikk+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) (n1) (k) (1) =E P...E P.A Ain1,n1ik,k..E Pi1,1 matrices 1...nlignes. 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`1ou1tel que: MA=T ou` T est triangulaire. (k) Si dans la me´thode de Gauss aucun des coefficients a,k=1..n1n'est nul , alors : k,k (n1) (n2) (1) M=E E..E, ,detM=1.
Remarquezquedansl'´enonce´duthe´or`eme,iln'apas´et´esuppos´equedetA6=0.Pourquoi?
2´ee:laremontohteeded´M
(n) (n) Parleproc´ede´d'e´limination,onestpasse´dusyste`meinitialausyste`me´equivalentA X=b,avec une matrice triangulaire.Lam´ethodedelaremont´ees'appliqueausyst`emetriangulairedutype:     t1,1. . .t1,n c1 0t2,2. . .t2,n  n T X=cou`T=Gl(n,R) (detT6=0)etc= R, .. . ...cn 0. . .0tn,n   x1  n o`uX= Rest l'inconnue. . xn t1,1x1+. . .+t1,nxn=c1 t2,2x2+t2,nxn=c2 . . .. tn,nxn=cn
4