Cours-Methodesdirectes

Description

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 ...

Informations

• Publié par: Asli
• Nombre de lectures: 55
• Langue: Français

Extrait

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:    a 1,1 . . .a 1,n b 1    . n A . ∈Gl(n,R) (⇔detA6=0)etb=  ∈R. X=bo`uA=  .  .  . . a n,1 . . .a n,n b n   x 1   n ou`X=   ∈Rest l'inconnue. On sait qu'il existe une unique solution. . x n Quelques rappels sur les permutations de lignes et de colonnes dans les matrices: n Soit la matriceP i,j qui permute leiie`me vecteur et lejeedquninocaseabaledruetcevemei`Ren fixant les autres vecteurs de base:   1 00 0 . . . . 0. . .0. . .1 0 0 10 P i,j ==. . . . . . 0. . .1 0. . .0   . .   . 0 0. . .0. . .0 1 Alors la matriceP i,j Aest obtenue a` partir deAaetnahgn´nceedansAla ligneiet la lignejsans changer les autres.La matriceAP i,j seottbrtirdeenue`apaAen e´changeant dansAla colonneiet la colonnejsans changer les autres.Remarquons que detP i,j =−1,i6=jet detP i,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 3 etb= 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 remplacelparl−l. Onrefait la 2 22 1 (1) (1) (1) meˆme chose avec la troisie`me ligne soit on remplacelparl−3l.On obtient: 3 31  (2)  x+2y+2z=2,l  1 (2) (2) (2) (⋆⋆) + y+z=0,l ⇔A 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.Icionremplacedonclparl−l. On 3 32 obtient le syste`me(⋆ ⋆ ⋆):  (3)  x+2y+2z=2,l  1 (3) ( 3) (3) (⋆ ⋆ ⋆) + y+z=0,l ⇔A X=b, 2   (3) +z=2.l 3 ou`:    1 2 22 (3) (3)    A=et 0 1 1 b= 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=b∀k∈ {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 b n    . .  (k) 0. . .0a. . .a n,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=0∀k∈ {1, ..,n}, sinon par multiplication par une matrice d'e´change de lig nes k,k (k) entre la lignei 0 ≥k(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 `a Ase fait en prenant pour pivota6=0: leskslignesdremi ` ereepAsont con- k,k (k+1) (k+1) serve´es dans A, puis on met des0dans la colonnekdeAde la lignek+1 a` 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,1 i, k i,n i ,1 i, k i,n i,i i,n b. Pourtoutidek+`1anon a: (k) a i,k(k+1) (k+1) (k+1) (k) (k) ligneideA=ligneideA−lignekdeA= (0, . . . ,0,a, . . . ,a), i,k+1 i,n (k) a k,k  (k+1) a=0∀j=1..k  i,j  (k) a ⇔ (k+1) (k)i,k(k) a=a−a∀j=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 deA a` Ale pivot esta6=0,pour toutk=1, ..,n−1.Posons: k,k   1 0. . .0 0 10 . . . . . . 0. . .0 10. (k) (k) (k) E= a . ,k=1, ...,n−1,det(E) =1. + . k1k .0− 1 . (k) a k,k . . . . 0  (k)   a  n,k 0. . .0−0. . .1 (k) a k,k Alors on peut constater que: (k+1) (k) (k) (k) (k−1) (1) A=E A=E E..E A.(∗) D'o`u: (n) (n−1) (1) (1) (n−1) (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`u∀i=k+1, ..,n,b=b−b=E b. (k+1)i i k (k) b k+1 a k,k   .  (k+1) b n ∗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. . .0a n,n (n) b=Mb, (n−1) (n−2) (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) (k−1) (k)   det(A) =a..adet  . .  1,1 k−1,k−1 (k) a. . .a n,n n,k (k) (k) (k) n´ecessairementundese´l´ements(a, ...,a)ulnnnostsconot.n´lmetee´eneta,i k ≥k+1. Alorsla matrice k+1,k n,k i,k k (k) (k) (k) Aneiggndelela´(ceahket de la ligneidansAequelluremeaa)`malAontisipotnnee´em´nleteos P i k ,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 (P i k ,k A), (k) (k) o `ula matriceEedrseocfe`sparaitruitemaientconste´cemmedllec´rpermfoueeqamalme`eP ficients d i k ,k A. Oncontinued'it´ererainsi.Alane´eti`emna:apeo (n) (n−1) (k) (1) =E P...E P.A A i n−1 ,n−1 i k ,k ..E P i 1 ,1 matrices 1...n−lignes. On1 sont l'ide o `ueventuellement lesP i k ,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.

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:     t 1,1 . . .t 1,n c 1 0t 2,2 . . .t 2,n   n T X=cou`T=  ∈Gl(n,R) (detT6=0)etc=   ∈R, . . .  . . .  c n 0. . .0t n,n   x 1   n o`uX=   ∈Rest l'inconnue. . x n  t 1,1 x 1 +. . .+t 1,n x n =c 1   t 2,2 x 2 +t 2,n x n =c 2 ⇔ . . . .   t n,n x n =c n

4