ESP, Dakar

Master en Sécurité des Systèmes d’Information (MSSI)

Analyse numérique
chapitre1 : Méthodes directes (triangulation de
Gauss et LU)

Dr. Oumar Diop

[Link]@[Link]

2 décembre 2023
 PLAN
1

Définition et généralités

Les systèmes triangulaires

La méthode de Gauss

La factorisation LU

Oumar Diop Cal Num 2 L1/ANM |

 Définitions et généralités
2

Il est fréquent, dans toutes les disciplines scientifiques, de devoir résoudre

des systèmes linéaires de la forme

a11 x1 a12 x2 ... a1n xn = b1

a21 x1 a22 x2 ... a2n xn = b2
a31 x1 a32 x2 ... a3n xn = b3 (1)
.. .. .. .. ..
. . ... . . .
an1 x1 an2 x2 ... ann xn = bn

Le système d’équation (1) s’écrit aussi comme suit

Ax = b, (2)

où A est une matrice carrée de dimension n × n dont les éléments aij sont
réels ou complexes, et x et b sont des vecteurs colonnes de dimension n, où
x est l’inconnue et b un vecteur donné.

Oumar Diop Cal Num 2 L1/ANM |

 Définition et généralités
3

On appelle système linéaire d’ordre n (n entier positif), une expression de la

forme
AX = b (3)
où
A = (aij ), 1 ≤ i, j ≤ n
désigne une matrice de nombres réels ou complexes de taille n × n

b = (bi ), 1 ≤ i ≤ n

est un vecteur colonne réel ou complexe et

x = (xi ), 1 ≤ i ≤ n

est le vecteur des inconnues du système. La relation (3) équivaut aux

équations
Xn
aij xj = bi .
i=1

L’équation (3) admet une et une seule solution si la matrice A est régulière
(c’est à dire det(A) 6= 0).
Oumar Diop Cal Num 2 L1/ANM |
 Définitions et généralités
4

On rappelle que si la matrice A est régulière la solution (3) est donnée par la
formule de Cramer suivante :
det(Ai )
xi = , 1 ≤ i ≤ n,
det(A)
où Ai est la matrice obtenue en replaçant la i-ème colonne de A par le
vecteur b.
On calcul le déterminant de la matrice A par la formule suivante
n
X
det(A) = (−1)(σ) Πn
i=1 aiσi
i=1

Par cette formule, la résolution de l’équation (3) requiert (n + 1)!

floating-point opérations (flops).

Exercice 1
Déterminer la complexité algorithmique c’-à-d le temps nécessaire pour un
ordinateur effectuant 109 flops par seconde de résoudre un système linéaire
de 50 équation à 50 inconnues.
Oumar Diop Cal Num 2 L1/ANM |
 Définitions et généralités
5

Définition 2
On appelle méthode de résolution directe d’un système linéaire un
algorithme qui, si l’ordinateur faisait des calculs exacts, donnerait la solution
en un nombre fini d’opérations.

Il existe une autre famille de méthodes de résolution de systèmes linéaires.

Dans ce chapitre, nous nous limitons aux méthodes directes de résolution de

systèmes linéaires. On présentera les méthodes suivantes.
I L’algorithme de Gauss
I La méthode LU

Oumar Diop Cal Num 2 L1/ANM |

 Matrice diagonale
6

On rappelle qu’une matrice D est dite diagonale si elle peut s’exprimer sous
la forme :

0
 
d11
 .. 

 . 

D= dii
 

..
 
.
 
 
0 dnn

det(D) = Πn i=1 dii alors le système Dx = b admet une unique solution si et

seulement si dii 6= 0 ∀i = 1, ..., n.
La solution du système Dx = b est donnée par
bi
xi = ∀i = 1, ..., n.
dii

Oumar Diop Cal Num 2 L1/ANM |

 Systèmes triangulaire inférieur
7

Une matrice est dite triangulaire inférieure si elle s’écrit sous la forme
 
l11
 l21 l22

0 

l31 l32 l33
 
L= 
 .. ..
 

 . . 
ln1 ... lnn

det(L) = Πni=1 lii alors le système Lx = b admet une unique solution si et

seulement si lii 6= 0 ∀i = 1, ..., n.
L’algorithme qui permet de résoudre l’équation Lx = b est donné par :
b1
y1 = , (4)
l11
i−1
!
1 X
yi = bi − lij yj , ∀i = 2, ..., n. (5)
lii j=1

Oumar Diop Cal Num 2 L1/ANM |

 Systèmes triangulaire inférieur
8

L’implémentation de l’algorithme (4-5) nécessite des calculs élémentaire

(additions, multiplications et divisions) de l’ordre de n2 .
En effet,
1. Le calcul de (4) nécessite une division
2. Pour la formule (5), on :
n
X
((i − 1)additions + (i − 1)multiplications + 1division)
i=2

3. Le nombre d’opérations élémentaires CL est alors donné par :

n(n − 1) n(n − 1)
CL = additions + multiplications + n divsions.
2 2
CL est alors de l’ordre de n2 .

Exercice 3
Ecrire le code python permettant de résoudre le système Lx = b où L est
une matrice triangulaire inférieur.
Oumar Diop Cal Num 2 L1/ANM |
 Systèmes triangulaires supérieur
9

Exercice 4
1. Donner un exemple de matrice carrée triangulaire supérieure d’ordre 4
2. Calculer son déterminant.
3. Donner l’algorithme permettant de résoudre U x = b où U est une
matrice triangulaire supérieur
4. Ecrire le code python permettant de résoudre le système U x = b où U
est une matrice triangulaire supérieur.
5. Calculer le coût de cet algorithme en termes d’opérations élémentaires.

Oumar Diop Cal Num 2 L1/ANM |

 La méthode d’élimination de Gauss
10

La méthode d’élimination de Gauss consiste à transformer le système AX = b en un

système ayant la même solution de la forme U X = b0 où U est une matrice triangulaire
et b0 un vecteur. La résolution par élimination de Gauss se fait en deux étapes :
Triangularisation de la matrice A.
Résolution du système triangulaire en cascade.
Considérons l’exemple Ax = b avec :
   
1 0 6 2 6
 8 0 −2 −2   −2 
A=  2 9
, b = 
 −8 
 (6)
1 3 
2 1 −3 10 4
On met ce système sous la forme de tableau comme suit :
 
1 0 6 2 6 l1
 8 0 −2 −2 −2  l2
 
 2 9 1 3 −8  l3
2 1 −3 10 4 l4
Le premier pivot étant non nul, on effectue alors les opérations suivantes :
 
1 0 6 2 6
 0 0 −50 −18 −50  l2 ← l2 − 8l1

 0 9 −11
 (7)
−1 −20  l3 ← l3 − 2l1
0 1 −15 6 −8 l4 ← l4 − 2l1
Oumar Diop Cal Num 2 L1/ANM |
 La méthode d’élimination de Gauss
11

On voit ici que le second pivot est nul, on peut utiliser la méthode du pivot partiel. on
prend comme pivot le plus grand élément de la colonne
 
0
 9  (8)
1
Alors on intervertit la 2ième et la 3ième ligne
 
1 0 6 2 6
 0 9 −11 −1 −20  l2 ← l3
 
 0 0 −50 −18 −50  l3 ← l2
0 1 −15 6 −8
Le second pivot est 9, non nul donc on poursuit
 
1 0 6 2 6
 0 9
 −11 −1 −20  
 0 0 −50 −18 −50 
−124 −52
0 0 9
55
9 9
l4 ← l4 − 19 l2
On voit clairement qu’on peut simplifier ,la quatrième ligne par 9, ce qui donne
 
1 0 6 2 6
 0 9
 −11 −1 −20  
 0 0 −50 −18 −50 
0 0 −124 55 −52 l4 ← 9 ∗ l4
Oumar Diop Cal Num 2 L1/ANM |
 La méthode d’élimination de Gauss
12

Le 3ième pivot (-50) étant non nul, on poursuit alors

 
1 0 6 2 6
 0 9 −11 −1 −20 
 
 0 0 −50 −18 −50 
2491 62
0 0 0 25
72 l4 ← l4 − l
25 3

Ce dernier tableau est équivalent au système d’équations suivant :

    
1 0 6 −2 x1 6
 0 9 −11 −1   x2   −20 
A 0 0 −50 −18   x3  =  −50 
    (9)
2491
0 0 0 25
x4 72

On obtient alors un sytème triangulaire supérieur.

Exercice 5
1. Résoudre le sytème triangulaire (9).
2. Reprendre le même travail pour une triangulation supérieure.

Oumar Diop Cal Num 2 L1/ANM |

 La méthode d’élimination de Gauss
13

Remarque 6
Lorsqu’un pivot est nul dans ce processus d’élimination de GAUSS, on peut
utiliser une autre méthode appelée Pivot total
Par exemple pour le tableau (7), on utilise le plus grand élément en module
de la sous-matrice
 
0 −50 −18
 9 −11 −1 
1 −15 6

Oumar Diop Cal Num 2 L1/ANM |

 Stratégie de pivot
14

Le choix du pivot est déterminant dans le procédés de Gauss. En effet, un

mauvais choix du pivot peut conduire à des résultats désastreux en arithmé-
tique flottante, par exemple, si un pivot est voisin de zéro.
• Pivot partiel : on choisira, à l’étape k comme pivot l’élément (akik ) véri-
fiant :
|akik | = max |akpk |
k≤p≤n

• Pivot total : on choisira, à l’étape k comme pivot l’élément (akik ) vérifiant :

|akik | = max |akpk |

k≤p,q≤n

Remarque 7
Dans le cas du pivot total, il faut également effectuer des permutations des
colonnes.

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme d’élimination de Gauss
15

Algorithme 8

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme d’élimination de Gauss (suite)
16

Algorithme 9

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme d’élimination de Gauss (suite)
17

Algorithme 10

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme d’élimination de Gauss (suite)
18

Algorithme 11

Oumar Diop Cal Num 2 L1/ANM |

 La méthode d’élimination de Gauss
19

Exercice 12
1. Ecrire une fonction python [At, bt] = Gauss(A, b) qui renvoit une matrice
triangulaire inférieure At et un vecteur b tel que le système Ax = b soit
équivalent à Atx = bt. Tester sur le système suivant :
   
3 2 4 7
 3 5 7  x =  −3  .
0 −2 5 1

2. Ecrire une fonction [x] = ResolGauss(A, b) permettant de résoudre le

système Ax = b par la méthode de Gauss. Tester sur le système
   
−1 2 1 7
 3 0 1  x =  −3  .
2 5 4 1

Oumar Diop Cal Num 2 L1/ANM |

 La factorisation LU
20

La factorisation LU d’une matrice carrée A consiste en la décomposer sous

forme de produit de deux matrice A = LU :
• L est une matrice triangulaire inférieure, avec lii = 1.
• U est une matrice triangulaire supérieure.
La factorisation LU permet de résoudre plusieurs systèmes Ax = b, où b peut
varier

La résolution de Ax = b se fait alors en deux étapes :

LY = b

puis
U x = y.

Proposition 13
Soit A une matrice carrée d’ordre n, on suppose que les sous matrices
principales de dimension k sont inversibles pour k = 1, 2; . . . , n. Alors la
factorisation A = LU avec Li,i = 1, i = 1, . . . , n existe et est unique.
Oumar Diop Cal Num 2 L1/ANM |
 La factorisation LU (exemple)
21

Soit à résoudre le système d’équations suivant :


 3x −2y +z = 2
2x +y +z = 7 (10)
4x −3y +2z = 4


Ce système peut sécrire sous la forme AX = b avec

     
3 −2 1 2 x
A= 2 1 1  , b =  7  , et X =  y  (11)
4 −3 2 4 z
Les mineurs principaux de la matrice A sont :

2 −2 1
3 −2
|3| = 3 6= 0, = 7 6= 0, 2 1 1 = 5 6= 0. (12)
2 1
4 −3 2
Les matrice L et U sont de la forme suivante.
   
1 0 0 u11 u12 u13
L =  l21 1 0  , et U =  0 u22 u23  ,
l31 l32 1 0 0 u33
Oumar Diop Cal Num 2 L1/ANM |
 La factorisation LU (exemple)
22

Par identification A = LU , on obtient :

   
1 0 0 3 −2 1
2 7 1
L= 3 1 0  , et U =  0 3 3
,
2
3
− 71 1 0 0 5
7

La résolution du système initial revient à résoudre successivement les deux

systèmes triangulaires :
LX 0 = b


UX = Y

  0     
1 0 0 x 2 2
0 2 0 0 17
LX = b ⇐⇒  3
1 0   y  =  7  =⇒ X =  3 
2
3
− 17 1 z0 4 15
3

et
      
1 0 0 x 2 1
U X = X 0 ⇐⇒  2
3
1 0   y  =  17
3
 =⇒ X =  2 
2
3
− 17 1 z 15
3
3

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme de la méthode LU
23

Algorithme 14

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme de la méthode LU
24

Algorithme 15

Oumar Diop Cal Num 2 L1/ANM |

 Algorithme de la méthode avec stockage dans A
25

Algorithme 16

Oumar Diop Cal Num 2 L1/ANM |

 La factorisation LU (Exercice)
26

Exercice 17
Soit le système linéaire Ax = b, avec
     
2 3 −1 x1 2
A= 4 4 −3  x =  x2  b =  0 
−2 3 −1 x3 −1

1. La matrice A est-elle factorisable en LU ? Si oui pourquoi ?

2. Si A est factorisable, donner sa matrice L et U .
3. Résoudre le système Ax = b.
4. Trouver la matrice A−1 .

Oumar Diop Cal Num 2 L1/ANM |