Résolution des syst`emes linéaires Méthode de Gauss
Aide : on cherchera d 'abord une relation de récurrence entre Nn et Nn?1. 3. Méthode de Gauss. Transformation de A en une matrice triangulaire supérieure.
1.3 Les méthodes directes
en détails la méthode de Choleski qui est adaptée aux matrices symétriques. 1.3.2 Méthode de Gauss
Chapitre V La méthode du pivot de Gauss et ses applications
Propriété : Un système de Cramer possède une unique solution que l'on détermine en partant de la dernière équation. … II – Technique du pivot de Gauss-Jordan. 1
Annexe 3 : Inversion de matrices par la méthode du pivot de Gauss
Dans le cas général on utilise la méthode du pivot de Gauss. Pour montrer qu'une matrice M est inversible : On applique les opérations élémentaires : •
Méthode du pivot de Gauss
Méthode du pivot de Gauss. Dédou. Octobre 2010 Pour appliquer la méthode du pivot `a un syst`eme on commence donc par y choisir une équation et une ...
METHODE DU PIVOT DE GAUSS
Dans tous les cas la méthode du pivot de Gauss permet de déterminer si le système a des solutions ou non (et notamment de savoir s'il est un système de Cramer
1 Méthode de Gauss et factorisation LU
(c) Résoudre le système (1) par l'algorithme de Gauss avec pivot partiel. (d) Calculer la factorisation ¯L¯U de PA (où P est la matrice produit des matrices de
Analyse Numérique
2.1.2 Méthode d'elimination de Gauss et décomposition LU.. . 6 2.2.3 Convergence des méthodes de Jacobi et de Gauss-Seidel. . 13.
Informatique en CPGE (2018-2019) Résolution dun système
12 mars 2019 Algorithme du pivot de Gauss. Utilisation de NumPy. Informatique en CPGE (2018-2019). Résolution d'un système linéaire inversible: méthode ...
Exercice 6 du TD 6. Méthode de réduction de Gauss. Cas 1 :Lorsqu
Méthode de réduction de Gauss. Cas 1 :Lorsqu'on a un x2 i dans l'expression de q : Exemple : q(x1x2
[PDF] Méthode du pivot de Gauss
La méthode du pivot permet d'associer `a tout syst`eme linéaire un syst`eme facile équivalent Elle consiste `a sélectionner une équation qu'on va garder
[PDF] METHODE DU PIVOT DE GAUSS - Toutes les Maths
La méthode du pivot de Gauss permet la résolution générale des systèmes d'équations linéaires à n équations et p inconnues Elle s'utilise notamment pour
[PDF] Résolution des syst`emes linéaires Méthode de Gauss - Normale Sup
Méthode de Gauss Méthodes numériques 2003/2004 - D Pastre licence de mathématiques et licence MASS 1 Résolution des syst`emes linéaires Notations
[PDF] Chapitre V La méthode du pivot de Gauss et ses applications
La méthode du pivot de Gauss et ses applications I – Présentation 1 Systèmes linéaires Problème : Résoudre les systèmes linéaires à n inconnues
[PDF] Résolution de systèmes linéaires par la méthode du pivot de Gauss
Méthode On résout les équations successivement en partant de la dernière On exprime les inconnues principales en fonction des inconnues secondaires
[PDF] Systèmes linéaires
Méthode du pivot de Gauss On va décrire la méthode du pivot de Gauss pour résoudre un système de la forme : diaporama_carres_magiques_ordre3 pdf
[PDF] 13 Les méthodes directes
en détails la méthode de Choleski qui est adaptée aux matrices symétriques 1 3 2 Méthode de Gauss méthode LU Soit A ? Mn(IR) une matrice inversible
[PDF] Systèmes linéaires - Exo7 - Cours de mathématiques
Résolution par la méthode du pivot de Gauss · Fiche d'exercices · Systèmes d'équations linéaires 1 Introduction aux systèmes d'équations linéaires
[PDF] TD n 1 Systémes linéaires Pivot de Gauss 1 Systémes linéaires
Exercice 5 Résoudre les deux probl`emes suivants par la méthode de votre choix (On commencera par poser correctement le probl`eme en termes de syst`eme
[PDF] Ift 2421 Chapitre 3 Résolution des systèmes déquations linéaires
Remarques sur la méthode de Gauss 1 Un pivot est une valeur par laquelle on doit diviser pour résoudre le système linéaire
Comment faire la méthode de Gauss ?
La méthode du pivot de Gauss est une méthode pour transformer un système en un autre système équivalent (ayant les mêmes solutions) qui est triangulaire et est donc facile à résoudre. Les opérations autorisées pour transformer ce système sont : échange de deux lignes. multiplication d'une ligne par un nombre non nul.Comment utiliser la méthode de pivot de Gauss ?
La méthode du pivot permet d'associer `a tout syst`eme linéaire un syst`eme facile équivalent. ? 2x + 3y + z = 1 ?7y + 7z = 1 ?7y ? 3z = ?2. on résout le syst`eme dérivé (par combinaison linéaire) et on conclut avec l'équation facile.Comment faire Gauss Jordan ?
L'élimination de Gauss-Jordan est un algorithme de transformation menant à un système équivalent d'équations linéaires Rx=d R x = d , où R est sous FER, qui n'utilise que des opérations élémentaires sur les lignes. En langage courant, on dit que la transformation d'une matrice en FER est une réduction.- Résoudre un système de trois équations d'inconnues x, y et z revient à chercher tous les triplets (x ; y ; z) qui vérifient ces trois équations. Un tel triplet de valeurs (x ; y ; z) est appelé « solution du système d'équations ».
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
1.3 Les méthodes directes
1.3.1 Définition
Définition 1.10(Méthode directe).On appelle méthode directe de résolution de (1.1) une méthode qui donne
exactementx(Aetbétant connus) solution de (1.1) après un nombre fini d"opérationsélémentaires(+,-,×,/).
Parmi les méthodes de résolution du système (1.1), la plus connue est laméthode de Gauss(avec pivot), encore
appeléeméthode d"échelonnementouméthode LUdans sa forme matricielle.Nous rappelons la méthode de Gauss et sa réécriture matricielle qui donne la méthodeLUet nous étudierons plus
en détails la méthode de Choleski, qui est adaptée aux matrices symétriques.1.3.2 Méthode de Gauss, méthodeLU
SoitA?Mn(IR)une matrice inversible, etb?IRn. On cherche à calculerx?IRntel queAx=b. Le principede la méthode de Gauss est de se ramener, par des opérations simples (combinaisons linéaires), à un système
triangulaire équivalent, qui sera donc facile à inverser.Commençons par un exemple pour une matrice3×3. Nous donneronsensuite la méthode pour une matricen×n.
Un exemple3×3
On considère le systèmeAx=b, avec
A=?? 1 0 1 0 2-1 -1 1-2?? b=?? 2 1 -2?? On écrit lamatrice augmentée, constituée de la matriceAet du second membreb.A=?Ab?=??10 1 2
0 2-1 1
-1 1-2-2?? Gauss et opérations matriciellesAllons y pour Gauss :La première ligne a un 1 en première position (en gras dans la matrice), ce coefficient est non nul, et c"est unpivot.
On va pouvoir diviser toute la première ligne par ce nombre pour en soustraire un multiple à toutes les lignes
d"après, dans le but de faire apparaître des 0 dans tout le basde la colonne.La deuxième équation a déjà un 0 dessous, donc on n"a rien besoin de faire. On veut ensuite annuler le premier
coefficient de la troisième ligne. On retranche donc (-1) fois la première ligne à la troisième3:
?10 1 20 2-1 1
-1 1-2-2?? ?3←?3+?1-→??10 1 202-1 1
0 1-1 0??
Ceci revient à multiplier
˜Aà gauche par la matriceE1=??
1 0 0 0 1 01 0 1??
La deuxième ligne a un terme non nul en deuxième position (2) :c"est un pivot. On va maintenant annuler le
deuxième terme de la troisième ligne; pour cela, on retranche 1/2 fois la ligne 2 à la ligne 3 :
3. Bien sûr, ceci revient à ajouter la première ligne! Il est cependant préférable de parler systématiquement de "retrancher" quitte à utiliser
un coefficient négatif, car c"est ce qu"on fait conceptuellement : pour l"élimination on enlève un multiple de la ligne dupivot à la ligne courante.
Analyse numérique I, télé-enseignement, L330Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
?10 1 202-1 1
0 1-1 0??
?3←?3-1/2?2-→??10 1 2
02-1 1
0 0-12-12??
Ceci revient à multiplier la matrice précédente à gauche parla matriceE2=?? 1 0 0 0 1 0 0-1 21??.On a ici obtenu une
matrice sous forme triangulaire supérieure à trois pivots :on peut donc faire la remontée pour obtenir la solution
du système, et on obtient (en notantxiles composantes dex) :x3= 1puisx2= 1et enfinx1= 1.On a ainsi résolu le système linéaire.
On rappelle que le fait de travailler sur la matrice augmentée est extrêmement pratique car il permet de travailler
simultanément sur les coefficients du système linéaire et sur le second membre.Finalement, au moyen des opérations décrites ci-dessus, ona transformé le système linéaire
Ax=benUx=E2E1b,oùU=E2E1A
est une matrice triangulaire supérieure.Factorisation LUTout va donc très bien pour ce système, mais supposons maintenant qu"on ait à résoudre
3089 systèmes, avec la même matriceAmais 3089 seconds membresbdifférents4. Il serait un peu dommage
de recommencer les opérations ci-dessus 3089 fois, alors qu"on peut en éviter une bonne partie. Comment faire?
L"idée est de "factoriser" la matriceA, c.à.d de l"écrire comme un produitA=LU, oùLest triangulaireinférieure
(lower triangular) etUtriangulaire supérieure (upper triangular). On reformulealors le systèmeAx=bsous la
formeLUx=bet on résout maintenant deux systèmes faciles à résoudre cartriangulaires :Ly=betUx=y.
La factorisationLUde la matrice découle immédiatement de l"algorithme de Gauss. Voyons comment sur l"exem-
ple précédent.1/ On remarque queU=E2E1Apeut aussi s"écrireA=LU, avecL= (E2E1)-1.
2/ On sait que(E2E1)-1= (E1)-1(E2)-1.
3/ Les matrices inversesE-11etE-12sont faciles à déterminer : commeE2consiste à retrancher 1/2 fois la ligne 2
à la ligne 3, l"opération inverse consiste à ajouter 1/2 foisla ligne 2 à la ligne 3, et donc
E -12=??1 0 00 1 001 21??Il est facile de voir queE-11=??1 0 00 1 0
-1 0 1?? et doncL=E-11E-12=??1 0 00 1 0 -11 21??La matriceLest une matrice triangulaire inférieure (et c"est d"ailleurs pour cela qu"on l"appelleL, pour "lower"
in English...) dont les coefficients sont particulièrementsimples à trouver : les termes diagonaux sont tous égaux à
un, etchaque terme non nul sous-diagonal?i,jest égal au coefficient par lequel on a multiplié la ligne pivot
iavant de la retrancher à la lignej.4/ On a bien doncA=LUavecLtriangulaire inférieure (lower triangular) etUtriangulaire supérieure (upper
triangular).La procédure qu"on vient d"expliquer s"appelleméthode LUpour la résolution des systèmes linéaires, et elle
est d"une importance considérable dans les sciences de l"ingénieur, puisqu"elle est utilisée dans les programmes
informatiques pour la résolution des systèmes linéaires.Dans l"exemplequenousavons étudié,toutse passait très biencarnousn"avonspas eude zéroenpositionpivotale.
Si on a un zéro en position pivotale, la factorisation peut quand même se faire, mais au prix d"une permutation.
4. Ceci est courant dans les applications. Par exemple on peut vouloir calculer la réponse d"une structure de génie civilà 3089 chargements
différents.Analyse numérique I, télé-enseignement, L331Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
a(1)1,1 a (i+1) i+1,i+1 a (i+1) i+2,i+1 a (i+1) N,Na (1) 1,N a (i+1)N,i+100
0 0A (i+1)= FIGURE1.3: Allure de la matrice de Gauss à l"étapei+ 1Le résultat général que l"on peut démontrer est que si la matriceAest inversible, alors il existe une matrice de
permutationP,unematricetriangulaireinférieureLetunematricetriangulairesupérieureUtelles quePA=LU:
voir le théorème 1.19.Le cas général d"une matricen×n
De manière plus générale, pour une matriceAcarrée d"ordren, la méthode de Gauss s"écrit :
On poseA(1)=Aetb(1)=b. Pouri= 1,...,n-1, on cherche à calculerA(i+1)etb(i+1)tels que lessystèmesA(i)x=b(i)etA(i+1)x=b(i+1)soient équivalents, oùA(i+1)est une matrice dont les coefficients
sous-diagonaux des colonnes 1 àisont tous nuls, voir figure 1.3 :Une fois la matriceA(n)(triangulaire supérieure) et le vecteurb(n)calculés, il sera facile de résoudre le système
A(n)x=b(n). Le calcul deA(n)est l"étape de "factorisation", le calcul deb(n)l"étape de "descente", et le calcul
dexl"étape de "remontée". Donnons les détails de ces trois étapes.Etape de factorisation et descentePour passer de la matriceA(i)à la matriceA(i+1), on va effectuer des
combinaisonslinéaires entre lignes qui permettrontd"annulerles coefficientsde lai-ème colonnesitués en dessous
de la lignei(dans le but de se rapprocher d"une matrice triangulaire supérieure). Evidemment, lorsqu"on fait ceci,
il faut également modifier le second membreben conséquence. L"étape de factorisation et descente s"écrit donc :
k,j=a(i) k,jetb(i+1) k=b(i) k.2. Pourk > i,sia(i)
i,i?= 0, on pose : a (i+1) k,j=a(i) k,j-a(i) k,i a(i) i,ia(i) i,j,pourj=i,...,n,(1.33) b (i+1) k=b(i) k-a(i) k,i a(i) i,ib(i) i.(1.34)La matriceA(i+1)est de la forme donnée sur la figure 1.3. Remarquons que le systèmeA(i+1)x=b(i+1)est bien
équivalent au systèmeA(i)x=b(i).
Si la conditiona(i)
i,i?= 0est vérifiée pouri= 1àn, on obtient par le procédéde calcul ci-dessus un système linéaire
A(n)x=b(n)équivalent au systèmeAx=b, avec une matriceA(n)triangulaire supérieure facile à inverser. On
verra un peu plus loin les techniques de pivot qui permettentde régler le cas où la conditiona(i)
i,i?= 0n"est pas vérifiée.Analyse numérique I, télé-enseignement, L332Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
Etape de remontéeIl reste à résoudre le systèmeA(n)x=b(n). Ceci est une étape facile. CommeA(n)est une
matrice inversible, on aa(i) i,i?= 0pour touti= 1,...,n, et commeA(n)est une matrice triangulaire supérieure, onpeut donc calculer les composantes dexen "remontant", c"est-à-dire de la composantexnà la composantex1:
x n=b(n)n a(n)n,n, x i=1 a(n) i,i?? b(n) i-? j=i+1,na(n) i,jxj?? ,i=n-1,...,1.Il est important de savoir mettre sous forme algorithmiqueles opérations que nous venons de décrire : c"est l"étape
clef avant l"écriture d"un programme informatique qui nouspermettra de faire faire le boulot par l"ordinateur!
Algorithme 1.11(Gauss sans permutation).
1. (Factorisation et descente)
Pour commencer, on poseui,j=ai,jetyi=bipour pouri,j? {1,...,n}. Puis, pouriallant de1àn-1, on effectue les calculs suivants : (a) On ne change pas lai-ème ligne (qui est la ligne du pivot) (b) On change les lignesi+ 1ànet le second membreyen utilisant la lignei.Pourkallant dei+ 1àn:
k,i=uk,i ui,i(siai,i= 0, prendre la méthode avec pivot partiel) pourjallant dei+ 1àn, u k,j=uk,j-?k,iui,jFin pour
y k=yk-?k,iyiFin pour
2. (Remontée) On calculex:
x n=yn un,nPouriallant den-1à1,
x i=yiPourjallant dei+ 1àn,
x i=xi-ui,jxjFin pour
x i=1 ui,ixiFin pour
Coût de la méthode de Gauss (nombre d"opérations)On peut montrer (on fera le calcul de manière détaillée
pourlaméthodedeCholeskidanslasectionsuivante,lecalculpourGauss estsimilaire)quelenombred"opérations
nécessairesnGpour effectuer les étapes de factorisation, descente et remontée est23n3+O(n2); on rappelle
lim n→+∞nG n3=23: lorsquenest grand, le nombre d"opérations se comporte comme(2/3)n3.En ce qui concerne la place mémoire, on peut très bien stockerles itérésA(i)dans la matriceAde départ, ce qu"on
n"a pas voulu faire dans le calcul précédent, par souci de clarté.Analyse numérique I, télé-enseignement, L333Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
DécompositionLUSi le systèmeAx=bdoit être résolu pour plusieurs second membresb, on a déjà dit qu"on
a intérêt à ne faire l"étape de factorisation(i.e.le calcul deA(n)), qu"uneseule fois, alors que les étapes de descente
et remontée (i.e.le calcul deb(n)etx) seront faits pour chaque vecteurb. L"étape de factorisation peut se faire en
décomposant la matriceAsous la formeLU. Supposons toujours pour l"instant que lors de l"algorithme de Gauss,
la conditiona(i) i,i?= 0est vérifiée pour touti= 1,...,n.La matriceLa comme coefficients?k,i=a(i) k,i a(i) i,ipourk > i,i,i= 1pour touti= 1,...,n, et?i,j= 0pourj > i, et la matriceUest égale à la matriceA(n). On peut vérifier
queA=LUgrâce au fait que le systèmeA(n)x=b(n)est équivalent au systèmeAx=b. En effet, comme
A (n)x=b(n)etb(n)=L-1b,on en déduit queLUx=b, et commeAetLUsont inversibles, on en déduit que A-1b= (LU)-1bpour toutb?IRn. Ceci démontre queA=LU.La méthodeLUse déduit donc de la méthode
de Gauss en remarquant simplement que, ayant conservé la matriceL, on peut effectuer les calculs surbaprès les
calculs surA, ce qui donne :Algorithme 1.12(LUsimple (sans permutation)).
1. (Factorisation)
On poseui,j=ai,jpour pouri,j? {1,...,n}.
Puis, pouriallant de1àn-1, on effectue les calculs suivants : (a) On ne change pas lai-ème ligne (b) On modifie les lignesi+ 1àn((mais pas le second membre) en utilisant la lignei.Pourkallant dei+ 1àn:
k,i=uk,i ui,i(siui,i= 0, prendre la méthode avec pivot partiel) pourjallant dei+ 1àn, u k,j=uk,j-?k,iui,jFin pour
2. (Descente) On calculey(avecLy=b)
Pouriallant de1àn,
y i=bi-?i-1 k=1?i,kyk(on a ainsi implicitement?i,i= 1)3. (Remontée) On calculex(avecUx=y)
Pouriallant denà1,
x i=1 ui,i(yi-?nj=i+1ui,jxj) Remarque 1.13(Optimisation mémoire).L"introduction des matricesLetUet des vecteursyetxn"est pasnécessaire. Tout peut s"écrire avec la matriceAet le vecteurb, que l"on modifie au cours de l"algorithme. A la
fin de la factorisation,Uest stockée dans la partie supérieure deA(y compris la diagonale) etLdans la partie
strictement inférieure deA(c"est-à-dire sans la diagonale, la diagonale deLest connue car toujours formée de
1). Dans l"algorithme précédent, on remplaçe donc "u" et "l" par "a". De même, on remplaçe "x" et "y" par
"b". A la fin des étapes de descente et de remontée, la solution duproblème est alors stockée dansb.
L"introduction deL,U,xetypeut toutefois aider à comprendre la méthode.Nous allons maintenant donner une condition nécessaire et suffisante (CNS) pour qu"une matriceAadmette une
décompositionLUavecUinversible et sans permutation. Commençons par un petit lemme technique qui va nous
permettre de prouver cette CNS. Lemme1.14(DécompositionLUdelamatriceprincipaled"ordrek).Soitn?IN,A?Mn(IR)etk? {1,...,n}. On appelle matrice principale d"ordrekdeAla matriceAk?Mk(IR)définie par(Ak)i,j=ai,jpouri=1,...,ketj= 1,...,k. On suppose qu"il existe une matriceLk?Mk(IR)triangulaire inférieure de coefficients
diagonaux tous égaux à 1 et une matrice triangulaire supérieureUk?Mk(IR)inversible, telles queAk=LkUk.
AlorsAs"écrit sous la forme "par blocs" suivante : A=?? L k0k×(n-k) C kIdn-k?? ?U kBk 0 (n-k)×kDk?? ,(1.35)Analyse numérique I, télé-enseignement, L334Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
où0p,qdésigne la matrince nulle de dimensionp×q,Bk?Mk,n-k(IR)etCk?Mn-k,k(IR)etDk? M n-k,n-k(IR); de plus, la matrice principale d"ordrek+ 1s"écrit sous la forme A k+1=?? L k01×k c k1?? ?U kbk 0 k×1dk?? (1.36)oùb?Mk,1(IR)est la première colonne de la matriceBk,ck?M1,kest la première ligne de la matriceCk, et
d kest le coefficient de la ligne 1 et colonne 1 deDk. DÉMONSTRATION- On écrit la décomposition par blocs deA: A=? AkEk F kGk? avecAk?Mk(IR),Ek?Mk,n-k(IR),Fk?Mn-k,k(IR)etGk?Mn-k,n-k(IR). Par hypothèse, on aAk=LkUk. De plusLketUksont inversibles, et il existe donc une unique matriceBk?Mk,n-k(IR)(resp.Ck?Mn-k,k(IR))telle queLkBk=Ek(respCkUk=Fk). En posantDk=Gk-CkBk, on obtient (1.35). L"égalité (1.36) en découle
immédiatement. Proposition 1.15(CNS pourLUsans permutation).Soitn?IN,A?Mn(IR). Les deux propriétés suivantes sont équivalentes.(P1) Il existe un unique couple(L,U), avecLmatrice triangulaire inférieure de coefficients égaux à 1 etUune
matrice inversible triangulaire supérieure, tel queA=LU. (P2) Les mineurs principaux5deAsont tous non nuls.
DÉMONSTRATION- SiA=LUavecLtriangulaire inférieure de coefficients égaux à 1 etUinversible triangulaire
supérieure, alorsAk=LkUkoù les matricesLketUkles matrices principales d"ordrekdeLetU, qui sont encore
respectivement triangulaire inférieure de coefficients égaux à 1 et inversible triangulaire supérieure. On a donc
det(Ak) = det(Lk)det(Uk)?= 0pour toutk= 1,...,n, et donc (P1)?(P2).Montrons maintenant la réciproque. On suppose que les mineurs sont non nuls, et on va montrer queA=LU. On va
en fait montrer que pour toutk= 1,...n, on aAk=LkUkoùLktriangulaire inférieure de coefficients égaux à 1
etUkinversible triangulaire supérieure. Le premier mineur estnon nul, donca11= 1×a11, et la récurrence est bien
initialisée. On la suppose vraie à l"étapek. Par le lemme 1.14, on a doncAk+1qui est de la forme (1.36), et donc une
Ak+1=Lk+1Uk+1Commedet(Ak+1)?= 0, la matriceUk+1est inversible, et l"hypothèse de récurrence est vérifiée à
l"ordrek+ 1. On a donc bien (P2)?(P1) (l"unicité deLetUest laissée en exercice).Que faireen cas de pivotnul :la technique de permutationLacaractérisationquenousvenonsde donnerpour
qu"une matrice admette une décompositionLUsans permutation est intéressante mathématiquement, maisde peu
d"intérêt en pratique. On ne va en effet jamais calculerndéterminants pour savoir si on doit ou non permuter. En
pratique, on effectue la décompositionLUsans savoir si on a le droit ou non de le faire, avec ou sans permutation.
Au cours de l"élimination, sia(i)
i,i= 0, on va permuter la ligneiavec une des lignes suivantes telle quea(i) k,i?= 0.Notons que si le "pivot"a(i)
i,iest très petit, son utilisation peut entraîner des erreurs d"arrondi importantes dans lescalculs et on va là encore permuter.En fait, même dans le cas où la CNS donnéepar la proposition1.15est verifiée,
la plupart des fonctions de libraries scientifiques vont permuter.Plaçons-nous à l"itérationide la méthode de Gauss. Comme la matriceA(i)est forcément non singulière, on a :
det(A(i)) =a(i)1,1a(i)
2,2···a(i)
i-1,i-1det((((a (i) i,i... a(i) i,n......... a (i) n,i... a(i)n,n)))) ?= 0.5. On rappelle que le mineur principal d"ordrekest le déterminant de la matrice prinicipale d"ordrek.
Analyse numérique I, télé-enseignement, L335Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
On a donc en particulier
det((((a (i) i,i... a(i) i,n......... a (i) n,i... a(i)n,n)))) ?= 0.On déduit qu"il existei0? {i,...,n}tel quea(i)
i0,i?= 0. On choisit alorsi0? {i,...,n}tel que|a(i)
i 0,i|= max{|a(i)k,i|,k=i,...,n}.Le choix de ce max est motivé par le fait qu"on aura ainsi moinsd"erreur d"arrondi.On
échange alors les lignesieti0(dans la matriceAet le second membreb) et on continue la procédure de Gauss
décrite plus haut.L"intérêt de cette stratégie de pivot est qu"on aboutit toujours à la résolution du système (dès queAest inversible).
Remarque 1.16(Pivot total).La méthode que nous venons de d"écrire est souvent nommée technique de pivot
"partiel". Onpeut vouloirrendrela normedu pivotencoreplus grandeenconsidéranttous les coefficientsrestants
et pas uniquement ceux de la colonnei. A l"etapei, on choisit maintenanti0etj0? {i,...,n}tels que|a(i)
i0,j0|=
max{|a(i) k,j|,k=i,...,n,j=i,...,n},et on échange alors les lignesieti0(dans la matriceAet le secondmembreb), les colonnesietj0deAet les inconnuesxietxj0. La stratégie du pivot total permet une moins grande
sensibilité aux erreurs d"arrondi. L"inconvénient majeurest qu"on change la structure deA: si, par exemple la
matrice avait tous ses termes non nuls sur quelques diagonales seulement, ceci n"est plus vrai pour la matrice
A (n).Ecrivons maintenant l"algorithme de la méthodeLUavec pivot partiel; pour ce faire, on va simplement remarquer
que l"ordre dans lequel les équations sont prises n"a aucuneimportance pour l"algorithme. Au départ de l"algo-
rithme, on initialise la bijectiontde{1,...,n}dans{1,...,n}par l"identité, c.à.d.t(i) =i; cette bijectiontva
être modifiée au cours de l"algorithme pour tenir compte du choix du pivot.Algorithme 1.17(LUavec pivot partiel).
1. (Initialisation det) Pouriallant de1àn,t(i) =i. Fin pour
2. (Factorisation)
Pouriallant de1àn, on effectue les calculs suivants : (a) Choix du pivot (et det(i)) : on cherchei?? {i,...,n}t.q.|at(i?),i|= max{|at(k),i|,k? {i,...,n}}(noter que ce max est forcément non nul car la matrice est inversible). On modifie alorsten inversant les valeurs det(i)ett(i?). p=t(i?);t(i?) =t(i);t(i) =p.On ne change pas la lignet(i):
u t(i),j=at(i),jpourj=i,...,n, (b) On modifie les lignest(k),k > i(et le second membre), en utilisant la lignet(i). Pourk=i+ 1,...,n}(noter qu"on a uniquement besoin de connaître l"ensemble , et pas l"ordre) : t(k),i=at(k),i at(i),iPourjallant dei+ 1àn,
a t(k),j=at(k),j-?t(k),iut(i),jFin pour
Fin pour
3. (Descente) On calculey
Pouriallant de1àn,
y t(i)=bt(i)-?i-1 j=1?t(j),kykFin pour
Analyse numérique I, télé-enseignement, L336Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
4. (Remontée) On calculex
Pouriallant denà1,
x (t(i)=1 ut(i),i(yi-?nj=i+1ut(i),jxj)Fin pour
NB : On a changé l"ordre dans lequel les équations sont considérées (le tableautdonne cet ordre, et donc la
matriceP). Donc, on a aussi changé l"ordre dans lequel interviennentles composantes du second membre : le
systèmeAx=best devenuPAx=Pb. Par contre, on n"a pas touché à l"ordre dans lequel interviennent les
composantes dexety.Il reste maintenant à signaler la propriété magnifique de cetalgorithme...Il est inutile de connaitrea priori
la bijection pour cet algorithme. A l"étapeide l"item1(et d"ailleurs aussi à l"étapeide l"item 2), il suffit de
connaîtret(j)pourjallant de1ài, les opérations de1(b)se faisant alors sur toutes les autres lignes (dans un
ordre quelconque). Il suffit donc de partir d"une bijection arbitraire de{1,...,n}dans{1,...,n}(par exemple
l"identité) et de la modifier à chaqueétape. Pour que l"algorithmeaboutisse, il suffit queat(i),i?= 0(ce qui toujours
possible carAest inversible).Remarque 1.18(Ordre des équations et des inconnues).L"algorithme se ramène donc à résoudreLUx=b, en
résolvant d"abordLy=bpuisUx=y. Notons que lors de la résolution du systèmeLy=b, les équations sont
dans l"ordret(1),...,t(k)(les composantes debsont donc aussi prises dans cet ordre), mais le vecteuryest
bien le vecteur de composantes(y1,...,yn), dans l"ordre initial. Puis, on résoutUx=y, et les équations sont
encore dans l"ordret(1),...,t(k)mais les vecteursxetyont comme composantes respectives(x1,...,xn)et (y1,...,yn).Le théorème d"existenceL"algorithme LU avec pivot partiel nous permet de démontrerle théorème d"existence
de la décomposition LU pour une matrice inversible.de permutationPtelle que, pour cette matrice de permutation, il existe un etun seul couple de matrices(L,U)où
Lest triangulaire inférieure de termes diagonaux égaux à 1 etUest triangulaire supérieure, vérifiant
PA=LU.
DÉMONSTRATION-
1.L"existencede la matricePet des matricesL Upeut s"effectuer en s"inspirant de l"algorithme "LUavec pivot partiel"
1.17). PosonsA(0)=A.
À chaque étapeide l"algorithme 1.17 peut s"écrire commeA(i)=E(i)P(i)A(i-1), oùP(i)est la matrice de permutation
qui permet le choix du pivot partiel, etE(i)est une matrice d"élimination qui effectue les combinaisons linéaires de lignes
permettant de mettre à zéro tous les coefficients de la colonneisitués en dessous de la lignei. Pour simplifier, raisonnons
sur une matrice4×4(le raisonnement est le même pour une matricen×n. On a donc en appliquant l"algorithme de
Gauss :
E (3)P(3)E(2)P(2)E(1)P(1)A=ULes matricesP(i+1)etE(i)ne permutent en général pas. Prenons par exempleE2, qui est de la forme
E (2)=???1 0 0 00 1 0 00a1 00b0 1???
SiP(3)est la matrice qui échange les lignes 3 et 4, alors P (3)=???1 0 0 00 1 0 00 0 0 10 0 1 0??? etP(3)E(2)=???1 0 0 00 1 0 00b0 10a1 0???
,alors queE(2)P(3)=???1 0 0 00 1 0 00a0 10b1 0???
Analyse numérique I, télé-enseignement, L337Université d"Aix-Marseille, R. Herbin, 8 septembre 2016
1.3. LES MÉTHODES DIRECTES CHAPITRE 1. SYSTÈMES LINÉAIRES
Mais par contre, comme la multiplicationà gaucheparP(i+1)permuteles lignesi+ 1eti+k, pour un certaink≥1,
et que la multiplicationà droitepermuteles colonnesi+ 1eti+k, la matrice?E(i)=P(i+1)E(i)P(i+1)est encore une
matrice triangulaire inférieure avec la même structure queE(i): on a juste échangé les coefficients extradiagonaux des
lignesi+ 1eti+k. On a donc P (i+1)E(i)=?E(i)P(i+1).(1.37) Dans l"exemple précédent, on effectue le calcul : Pquotesdbs_dbs14.pdfusesText_20[PDF] méthode pour apprendre à compter cp
[PDF] méthode pour apprendre à lire à 3 ans
[PDF] methode pour apprendre l'hebreu
[PDF] méthode pour apprendre l'histoire géographie
[PDF] methode pour apprendre la division
[PDF] methode pour apprendre les divisions
[PDF] methode pour apprendre les divisions en ce2
[PDF] méthode rapport de stage droit
[PDF] methode simple pour apprendre la division
[PDF] méthodologie commentaire composé pdf
[PDF] méthodologie de la dissertation économique
[PDF] méthodologie de rapport de stage
[PDF] méthodologie de recherche rapport de stage
[PDF] méthodologie de rédaction rapport de stage