Analyse numérique

Chapitre 2 : Resolution du systeme lineaire Ax = b

Dr. Imed MAHFOUDHI

mahfoudhi.imed5@[Link]

21 octobre 2024
1/13
Imed MAHFOUDHI 2024-2025 ENIM
 PLAN

1 Introduction
Méthode d’élimination de Gauss
Méthode de décomposition LU
Méthode de Cholesky

2/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

M ÉTHODE DIRECTE (G AUSS , LU, C HOLESKY )

Dans ce chapitre, on va étudier quelques méthodes directes

permettant de résoudre le système

AX = b (1)

Avec A ∈ Mn (R), et b ∈ Rn . Les méthodes suivantes seront

abordées :
▶ Méthode d’élimination de Gauss
▶ Méthode de décomposition LU
▶ Méthode de Cholesky

3/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode d’élimination de Gauss

E XEMPLE - É LIMINATION DE G AUSS

L’idée de cette méthode est de se ramener à un système linéaire dont
la matrice est triangulaire supérieure on obtient ensuite la solution
par simple remontée. On cherche à résoudre le système suivant :


 2x + 3y + 3z + t = 15
−4x − 6y + 3z + 2t = 3

(S) :

 −x + y + z + t = 5
−2x − y + z + t = 1


La méthode de Gauss, consiste à éliminer x des lignes 2,3 4, puis y des

lignes 3,4, puis z de la ligne 4. On obtient alors la valeur de t et on en
déduit les autres valeurs on remontant. Le système (S) s’écrit sous
forme matricielle Ax = b.
    
2 3 3 1 x 15
 −4 −6 3 2   y   3 
 −1 1 1 1   z  =  5 
     (2)
−2 −1 1 1 t 1
4/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode d’élimination de Gauss

M ATRICE SOUS FORME TRIANGULAIRE

On pose A1 = A et on note a1i,j , 1 ≤ i, j ≤ 4 l’élément (i, j) de la
matrice A. Lorsqu’il est non nul. On effectue alors pour toute
ligne Li , 2 ≤ i ≤ 4 :
a1i,1
Li ← Li − 1 L1
a1,1
On obtient, après une suite des transformations, le système
devient :
    
2 3 3 1 x 15
 0 5 5 3   y   25 
2 2 2    2 
 0 0 9 4   z  =  33 


0 0 0 −4 45
t −4
3

La matrice est maintenant triangulaire, on peut résoudre le

système par remontée.
5/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode d’élimination de Gauss

A LGORITHME M ÉTHODE DE G AUSS

Algorithme Méthode de Gauss

De l’exemple précédent on peut tirer l’algorithme suivant :
▶ Pour k allant de 1 à n − 1 Si tous les éléments sous le pivot dans
la colonne k est nulle, passer à la colonne suivante.
▶ Si l’élément ak,k est nul, et s’il existe un élément non nul, sous le
pivot, dans la colonne k permuter la ligne i avec la ligne k où i est
le plus petit entier supérieur à k tel que ai,k soit non nul.
▶ Ensuite, pour tout i > k, effectuer l’opération

ai,k
Li ←− Li − Lk
ak,k

6/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de décomposition LU

M ÉTHODE DE D ÉCOMPOSITION LU

La méthode de décomposition LU consiste à factoriser la

matrice A en un produit de deux matrices triangulaires A = LU.
Le système Ax = b se résout par deux systèmes : Ly = b et
Ux = y.
où L est triangulaire inferieure (lower) et U est triangulaire
superieure (upper).

Theorem (Méthode de décomposition LU)

Soit A une matrice dont toutes les sous-matrices diagonales sont
inversibles. Alors Il existe un unique couple (L, U), avec U triang.
sup., et L triang. inf. à diagonale unité tel que A = LU

7/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de décomposition LU

E XEMPLE D ’ APPLICATION

Soit A la matrice définie par :

 
4 2 2
A= 2 10 7 
2 7 21

1 Justifier l’existence d’une décomposition LU de A.

2 Effectuer la factorisation LU de la matrice donnée.
 
8
3 Soit b =  16 , en déduire la solution du système linéaire
44
AX = b.

8/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de Cholesky

M ÉTHODE DE C HOLESKY
Cette méthode s’applique aux matrices réelles symétriques définies
positives. Elle consiste en une factorisation A = BBT , où B est une
matrice triangulaire inférieure.
Théorème(Méthode de Cholesky)
Soit A une matrice réelle symétrique définie positive. Alors il existe
une unique matrice réelle B triangulaire inférieure, telle que tous ses
éléments diagonaux soient positifs et qui vérifie : A = BBT

Le but de ramener la résolution de l’équation linéaire Ax = b à la

résolution de deux équations By = b et BT x = y.
Théorème(Critère de Sylvester)
Soit A = (aij )1≤i,j≤n une matrice réelle symétrique. A est définie
positive si et seulement si les n sous-matrices principales de A,
c’est-à-dire les matrices Ap = (aij )1≤i,j≤p pour p = 1, . . . , n, ont des
déterminants strictement positifs.
9/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de Cholesky

E XERCICE DE D ÉCOMPOSITION C HOLESKY

Soit A la matrice définie par :

 
4 2 2
A= 2 10 7 
2 7 21

1 Justifier l’existence d’une décomposition Cholesky de A.

2 Effectuer la factorisation Cholesky de la matrice donnée.
 
8
3 Soit b =  16 , en déduire la solution du système linéaire
44
AX = b.

10/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de Cholesky

E XERCICE

Soit A la matrice définie par

 
1 1 1
A = 2 3 4
2 5 7

1 Justifier pourquoi la matrice A admet une décomposition LU.

2 Donner la décomposition LU de la matrice A.
3 En déduire la solution du système linéaire Ax = b où
b = (1.5, 4, −6.5)T .
4 Soit C = UT ALT . Sans calculs supplémentaires, donner une
décomposition LU de la matrice C.

11/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de Cholesky

E XERCICE
On considère la matrice suivante
 
α 1 2
A = 1 3 1
2 1 3

1 Déterminer les valeurs de α pour les quelles la matrice A est

définie positive.
2 Pour α = 0. Proposer une méthode directe de résolution du
système Ax = b où b ∈ R3 ; quelle factorisation de la matrice A
envisagiez-vous ? Justifier votre réponse.
3 En considérant α = 2, donner la factorisation de Cholesky
A = BBT .
4 En supposant que b = (1, 1, 1)T , résoudre le système linéaire
Ax = b en utilisant la facorisation de Cholesky de A.
12/13
Imed MAHFOUDHI 2024-2025 ENIM
 Introduction

Méthode de Cholesky

Merci pour votre attention

13/13
Imed MAHFOUDHI 2024-2025 ENIM