les méthodes directes

Rprésenté par :

Fadoua Elmengoug
Widad Atiq
Safaa Rhazouli

Encadrée par :
[Link]

November 22, 2023

 Introduction
Le problème consiste à trouver la solution du système d'équations :
a1,1 x1 + a1,2 x2 + · · · + a1,n xn = b1



a x + a x + · · · + a x = b

2,1 1 2 ,2 2 2,n n 2


 ...

an,1 x1 + an,2 x2 + · · · + an,n xn = bn
En notation matricielle, le problème s'énonce comme suit :
On cherche à résoudre le système Ax = b avec :
A matrice à coecients réels de taille n × n et supposée inversible (i.e.
det(A) ̸= 0);
b vecteur de Rn ;
x inconnue à chercher dans Rn .
Si b = 0, le système est dit homogène, donc il admet au moins une solution
x = 0 qui est la solution nulle ou triviale.
L'hypothèse d'inversibilité de A assure l'existence et l'unicité de la solution
du système.
Rprésenté par :Fadoua ElmengougWidad AtiqSafaales
RhazouliEncadrée
méthodes directes
par :[Link] November 22, 2023 2 / 12
Classication des méthodes de résolution

Il existe deux grandes familles de méthodes de résolution :

1 Les méthodes directes qui permettent d'obtenir la solution en un
nombre ni d'opérations soit par triangularisation soit par
décomposition de la matrice A. Les principales méthodes sont :
L'élimination de Gauss,

La décomposition LU,

La décomposition de Cholesky,
Methode d'élimination de Gauss
Le principe de la methode de Gauss

Méthode de Gauss :
Le principe de la méthode d'élimination de Gauss consiste alors à mettre le
système linéaire Ax = b sous la forme A′ x = b′ où la matrice A′ est
triangulaire supérieure, la résolution de ce nouveau système étant assez
simple. Attention : La matrice A′ n'est pas semblable à A. Autrement dit,
il ne faut pas croire que les matrices A et A′ ont les mêmes valeurs propres.
Rprésenté par :Fadoua ElmengougWidad AtiqSafaales
RhazouliEncadrée
méthodes directes
par :[Link] November 22, 2023 4 / 12
Methode d'élimination de Gauss
transformation du systéme linéeaire en sytéme triangulaire
Éliminons dans un premier temps la première inconnue, à savoir x1 : on part
de
 
a11 a12 ··· a1j ··· a1n
a21 a22 ··· a2j ··· a2n 
 .. .. ... .. ... .. 
 
(1)
 . . . . 
A =A=
 
a
 i1 a i2 ··· aij ··· ain 
 .. .
. .. .. 

 . . . . 
an1 an2 · · · anj ··· ann
 
b1
b2 
 .. 
 
.
b (1) =b=  bi 

 .. 
 
.
bn
Rprésenté par :Fadoua ElmengougWidad AtiqSafaales
RhazouliEncadrée
méthodes directes
par :[Link] November 22, 2023 5 / 12
On peut alors éliminer l'inconnue x1 de la deuxième équation en
retranchant de la deuxième ligne de A la première pré-multipliée par le
coecient aa , à condition que a11 soit non nul, ce que l'on supposera pour
21

11

le moment. Ceci conduit donc à remplacer

 
(1) (2) a21
a 2j = a2j → a 2j = a2j − a1j pour j = 1, 2, . . . , n
a11

et parallèlement
a21
 
(1) (2)
b 2 = b2 → b2 = b2 − b1 .
a11

En générale :
 
(1) (2) ai 1
a ij = aij → a ij = aij − a1j pour j = 1, 2, . . . , n
a11

ai 1
 
(1) (2)
b i = bi → bi = bi − b1 .
a11
Rprésenté par :Fadoua ElmengougWidad AtiqSafaales
RhazouliEncadrée
méthodes directes
par :[Link] November 22, 2023 6 / 12
Lorsqu'on a fait l'élimination jusqu'à la dernière ligne, on obtient un
système linéaire sous la forme A(2) x = b(2) avec
 
a11 a12 ··· a1j ··· a1n
(2) (2) (2) 
 0 a22 ··· a2j ··· a2n 

 0 ··· ··· ··· ··· ···
 

A(2)  0 ··· ··· ··· ··· ···

 
=
 0 (2) (2) (2)

 ai 2 ··· aij ··· ain 
· · · ··· ··· ··· ··· ···
 
(2) (2) (2)
0 an2 ··· anj ··· ann
 
b1
 (2) 
b2 
 . 
 .. 
 . 
 
b (2) . 
 . 
=
 (2) 
bi 
 . 
 . 
 . 
(2)
bn
On dit qu'on vient de réaliser la première étape de l'élimination de Gauss,
Rprésenté par :Fadoua ElmengougWidad AtiqSafaales
RhazouliEncadrée
méthodes directes
par :[Link] November 22, 2023 7 / 12
Methode d'élimination de Gauss
Résolution par la méthode de Gauss

le système linéaire Ax = b admet une unique solution si et seulement si A

est inversible .

Pour résoudre le systeme on suit les deux étapes suivantes:

Etape 1 : transformation du systéme linéeaire en sytéme triangulaire.
Etape 2 : Résolution le systéme triangulaire par la methode remonté.
Décomposition LU

Théorème

Si au cours de l'élimination de Gauss les pivots sont non nuls, alors il existe
une matrice triangulaire inférieure L et une matrice triangulaire supérieure
U,telles que l'on ait :
A = LU.
De plus si on impose à L d'avoir ses éléments diagonaux égaux à 1 alors la
factorisation est unique.
Décomposition LU
Démonstration :

Il reste à démontrer l'unicité. Soit donc une autre factorisation :

A = L'U',
L' ayant ses éléments diagonaux égaux à 1. On a donc :
LU = L'U',
et comme les matrices L et U sont inversibles, on peut écrire :
L1 ′ L = UU ′ 1
or L'1L est une matrice triangulaire inférieure qui a ses éléments diagonaux
égaux à 1, et UU' 1 est une matrice triangulaire supérieure. Ces deux
matrices ne peuvent être égales que si, d'une part, elles sont diagonales et
que, d'autre part, il y a égalité des éléments diagonaux (égaux à 1 pour
L'1L), d'où
L'1L = UU' 1 = I,
et donc L = L' et U = U'.
Décomposition LU

Dans certaines situations on a besoin de résoudre plusieurs fois le système

linéaire Ax = b avec la même matrice A mais pour plusieurs seconds
membres diérents. Il semble alors inutile de recommencer les opérations
d'élimination sur A qui est inchangée et l'on n'eectue celles-ci que sur le
second membre b. Ces opérations étant linéaires on doit pouvoir les mettre
sous forme matricielle. Reprenons le système :

Ax = b
Décomposition LU

Si l'on dispose d'une factorisation A = LU, telle que celle obtenue dans le
paragraphe précédent, mais que nous allons calculer directement dans les
paragraphes suivants, alors on peut récrire Ax = b sous la forme :

LUx = b
La solution de ce système s'obtient en résolvant successivement les deux
systèmes :
(
Ly = b
Ux = y
ce qui correspond à la résolution de deux systèmes triangulaires.