Résolution

des systèmes
linéaires
par des
méthodes
directes

Zouaouia
Résolution des systèmes linéaires par
BOULENOIR
des méthodes directes
Introduction

Les Méthodes
directes

Méthode de Zouaouia BOULENOIR

Gauss

Décomposition
A en L.U Ecole Supérieure en Informatique
Méthode de
Sidi Bel Abbes
Cholesky

22 & 28 Décembre 2020

1 / 63
 Table des matières

Résolution
des systèmes
linéaires
par des
méthodes
directes
1 Introduction
Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

2 / 63
 Table des matières

Résolution
des systèmes
linéaires
par des
méthodes
directes
1 Introduction
Zouaouia
BOULENOIR

Introduction 2 Méthode de Gauss

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

2 / 63
 Table des matières

Résolution
des systèmes
linéaires
par des
méthodes
directes
1 Introduction
Zouaouia
BOULENOIR

Introduction 2 Méthode de Gauss

Les Méthodes
directes

Méthode de
3 Méthode de décomposition de A en L.U
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

2 / 63
 Table des matières

Résolution
des systèmes
linéaires
par des
méthodes
directes
1 Introduction
Zouaouia
BOULENOIR

Introduction 2 Méthode de Gauss

Les Méthodes
directes

Méthode de
3 Méthode de décomposition de A en L.U
Gauss

Décomposition
A en L.U 4 Méthode de Cholesky
Méthode de
Cholesky

2 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes
Introduction
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

3 / 63
 Introduction

Résolution Dans ce chapitre, on se propose d’étudier quelques méthodes

des systèmes
linéaires permettant de résoudre le système de n équations à n
par des
méthodes inconnus de la forme
directes

Zouaouia
BOULENOIR

 a11 x1 + a12 x2 + · · · + a1n xn = b1
 a21 x1 + a22 x2 + · · · + a2n xn = b2

Introduction .. .. . .. .
Les Méthodes


 . + . + .. + . = ..
directes
an1 x1 + an2 x2 + · · · + ann xn = bn

Méthode de
Gauss
n
X
Décomposition
A en L.U ⇐⇒ aij xj = bi i = 1, 2, · · · n.
Méthode de j=1
Cholesky
Soit A = (aij ) ∈ Mn (R), b = (b1 , · · · , bn )t et X le vecteur
inconnu de composantes (x1 , · · · , xn )t .
• Résoudre le système revient à résoudre
4 / 63 l’équation matricielles: AX = b.
 Introduction

Résolution
des systèmes
linéaires
par des
méthodes
directes Pour résoudre ce système, la première idée est l’utilisation
Zouaouia
BOULENOIR de la méthode de ” Cramer” à condition que det(A) 6= 0:
Introduction
a11 a12 ··· a1i−1 b1 a1i+1 · · · a1n
Les Méthodes
directes 1 a21 a22 ··· a2i−1 b2 a2i+1 · · · a2n
xi = .. .. .. .. .. ..
Méthode de
Gauss
det(A) . ···
. . . . ··· .
Décomposition an1 an2 · · · ani−1 bn a1i+1 · · · ann
A en L.U

Méthode de
Cholesky
c’est-à-dire on remplace la colonne ”i” par le vecteur b.

5 / 63
 Exemple

Résolution
des systèmes
linéaires
par des Résoudre par la méthode de Cramer le système suivant:
méthodes
directes 
x1 + 2x2 = 1
Zouaouia AX = b
BOULENOIR x1 + x2 = 3
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

6 / 63
 Exemple

Résolution
des systèmes
linéaires
par des Résoudre par la méthode de Cramer le système suivant:
méthodes
directes 
x1 + 2x2 = 1
Zouaouia AX = b
BOULENOIR x1 + x2 = 3
Introduction      
Les Méthodes
1 2 x1 1
directes
A= ,X= ,b=
1 1 x2 3
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

6 / 63
 Exemple

Résolution
des systèmes
linéaires
par des Résoudre par la méthode de Cramer le système suivant:
méthodes
directes 
x1 + 2x2 = 1
Zouaouia AX = b
BOULENOIR x1 + x2 = 3
Introduction      
Les Méthodes
1 2 x1 1
directes
A= ,X= ,b=
1 1 x2 3
Méthode de
Gauss det(A) = −1 6= 0
Décomposition
A en L.U

Méthode de
Cholesky

6 / 63
 Exemple

Résolution
des systèmes
linéaires
par des Résoudre par la méthode de Cramer le système suivant:
méthodes
directes 
x1 + 2x2 = 1
Zouaouia AX = b
BOULENOIR x1 + x2 = 3
Introduction      
Les Méthodes
1 2 x1 1
directes
A= ,X= ,b=
1 1 x2 3
Méthode de
Gauss det(A) = −1 6= 0
Décomposition
A en L.U 1 1 2
x1 = −1 =5
Méthode de 3 1
Cholesky

6 / 63
 Exemple

Résolution
des systèmes
linéaires
par des Résoudre par la méthode de Cramer le système suivant:
méthodes
directes 
x1 + 2x2 = 1
Zouaouia AX = b
BOULENOIR x1 + x2 = 3
Introduction      
Les Méthodes
1 2 x1 1
directes
A= ,X= ,b=
1 1 x2 3
Méthode de
Gauss det(A) = −1 6= 0
Décomposition
A en L.U 1 1 2
x1 = −1 =5
Méthode de 3 1
Cholesky  
1 1 1 5
x2 = −1 = −2 =⇒X=
1 3 −2

6 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
Remarque 1.1.
directes
La formule de Cramer neccesite[n(n + 1)!] opérations
Zouaouia
BOULENOIR élémentaires.
Introduction Si on a un ordinature qui effectue 109 d’opérations par
Les Méthodes
directes
seconde, il faudrait un temps de calcul équivalent à
n(n+1)!
Méthode de 109
s.
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

7 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
Remarque 1.1.
directes
La formule de Cramer neccesite[n(n + 1)!] opérations
Zouaouia
BOULENOIR élémentaires.
Introduction Si on a un ordinature qui effectue 109 d’opérations par
Les Méthodes
directes
seconde, il faudrait un temps de calcul équivalent à
n(n+1)!
Méthode de 109
s.
Gauss
Par exemple un système d’ordre 50 demande un équivalent
Décomposition
A en L.U de temps 50(51)!
109
s.
Méthode de
Cholesky

7 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
Remarque 1.1.
directes
La formule de Cramer neccesite[n(n + 1)!] opérations
Zouaouia
BOULENOIR élémentaires.
Introduction Si on a un ordinature qui effectue 109 d’opérations par
Les Méthodes
directes
seconde, il faudrait un temps de calcul équivalent à
n(n+1)!
Méthode de 109
s.
Gauss
Par exemple un système d’ordre 50 demande un équivalent
Décomposition
A en L.U de temps 50(51)!
109
s.
Méthode de
Cholesky donc, il est impossible de résoudre des système d’ordre
élevés.

7 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
Méthodes directes
directes

Zouaouia
BOULENOIR
Une méthode est dite directe, si elle donne au bout d’un
Introduction nombre fini d’opérations une solution exacte du problème.
Les Méthodes
directes Remarque 2.1.
Méthode de
Gauss Utilisées généralement lorsque n ≤ 100, et si A est une
Décomposition matrice pleine (pas beaucoup de zéros parmi ses coefficients).
A en L.U

Méthode de
Cholesky
Les méhodes directes sont:
1 Méthode de Gauss.
2 Méthode de décomposition de A en L.U .
8 / 63
3 Méthode de cholesky.
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
Considérons le système suivant, ainsi que sa matrice
linéaires
par des
(tableau) associée.
méthodes
directes   . 
Zouaouia  x − y + z = 2

 1 −1 1 .. 2
BOULENOIR 
2x + y − z = 1 ←→  .. 
 2 1 −1 . 1

Introduction

 4x + 3y + z = 3 .


Les Méthodes 4 3 1 .. 3
directes

Méthode de
Gauss La première étape du pivot de Gauss consiste à utiliser
Décomposition
A en L.U
la première équation pour faire disparaitre les xdans les
Méthode de autres équations.
Cholesky

9 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
Considérons le système suivant, ainsi que sa matrice
linéaires
par des
(tableau) associée.
méthodes
directes   . 
Zouaouia  x − y + z = 2

 1 −1 1 .. 2
BOULENOIR 
2x + y − z = 1 ←→  .. 
 2 1 −1 . 1

Introduction

 4x + 3y + z = 3 .


Les Méthodes 4 3 1 .. 3
directes

Méthode de
Gauss La première étape du pivot de Gauss consiste à utiliser
Décomposition
A en L.U
la première équation pour faire disparaitre les xdans les
Méthode de autres équations.
Cholesky
Au niveau de la matrice, cela revient à utiliser la
première ligne pour faire apparaı̂tre des 0 sous le
premier coefficient de la première ligne. C’est ce
premier coefficient que l’on appelle le pivot.
9 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1 . 2
 2 1 −1 ... 1 
directes  
Zouaouia  
BOULENOIR
..
4 3 1 . 3
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

10 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires  . 
1 −1 1 ..
par des
méthodes 2
 2 1 −1 ...
directes  
Zouaouia  1 

BOULENOIR
.
4 3 1 .. 3
Introduction
 . 
Les Méthodes
directes
1 −1 1 .. 2
 0 3 −3 ...
 
Méthode de
Gauss   ← (L2 ← L2 − 2L1 )
−3 
.
Décomposition
A en L.U
4 3 1 .. 3
Méthode de
Cholesky

10 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1 . 2
directes 
 2 1 −1 .. 
Zouaouia  . 1  
BOULENOIR
..
4 3 1 . 3
Introduction
 .. 
Les Méthodes
directes
1 −1 1 . 2
 .. 
 ← (L2 ← L2 − 2L1 )
Méthode de  0 3 −3 . −3 
Gauss 
..
Décomposition
A en L.U
4 3 1 . 3
Méthode de On a ainsi fait apparaı̂tre un premier 0 sous notre pivot.
Cholesky

10 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1 . 2
directes 
 2 1 −1 .. 
Zouaouia  . 1  
BOULENOIR
..
4 3 1 . 3
Introduction
 .. 
Les Méthodes
directes
1 −1 1 . 2
 .. 
 ← (L2 ← L2 − 2L1 )
Méthode de  0 3 −3 . −3 
Gauss 
..
Décomposition
A en L.U
4 3 1 . 3
Méthode de On a ainsi fait apparaı̂tre un premier 0 sous notre pivot.
Cholesky
On fait alors apparaı̂tre un nouveau 0 en sous trayant 4
fois la première ligne à la troisième

10 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1 . 2
directes  . 
Zouaouia
 0
 3 −3 .. −3 

BOULENOIR
.
Introduction
4 3 1 .. 3
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

11 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1
. 2
directes  . 
Zouaouia

 0 3 −3 .. −3 

BOULENOIR
..
Introduction
4 3 1 . 3
 . 
Les Méthodes
directes 1 −1 1 .. 2
 . 
Méthode de
Gauss

 0 3 −3 .. −3 

.. ← (L3 ← L3 − 4L1 )
Décomposition
A en L.U
0 7 −3 . −5
Méthode de
Cholesky

11 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
 .. 
méthodes 1 −1 1 . 2
 0 3 −3 ... −3 
directes  
Zouaouia  
BOULENOIR
..
Introduction
4 3 1 . 3
 . 
Les Méthodes
directes 1 −1 1 .. 2
 0 3 −3 ... −3 
 
Méthode de
Gauss  
.. ← (L3 ← L3 − 4L1 )
Décomposition
A en L.U
0 7 −3 . −5
Méthode de On a maintenant terminé la première étape du pivot de
Cholesky
Gauss: on a mis des 0 sur toute la première colonne, à
l’exception de notre pivot.

11 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution Pour l’étape suivante, on oublie la première ligne et la

des systèmes
linéaires première colonne, qui resteront inchangées jusqu’à la fin
par des
méthodes du procédé:
directes  . 
Zouaouia 1 −1 1 .. 2
 0 3 −3 ... −3  .
BOULENOIR  
Introduction
 
..
Les Méthodes 0 7 −3 . −5
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

12 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution Pour l’étape suivante, on oublie la première ligne et la

des systèmes
linéaires première colonne, qui resteront inchangées jusqu’à la fin
par des
méthodes du procédé:
directes  . 
Zouaouia 1 −1 1 .. 2
 0 3 −3 ... −3  .
BOULENOIR  
Introduction
 
..
Les Méthodes 0 7 −3 . −5
directes

Méthode de
On recommence alors la première étape, sur la matrice
Gauss plus petite: dans notre exemple, notre nouveau pivot
Décomposition
A en L.U
est le 3, que l’on utilise pour faire apparaı̂tre des 0 en
Méthode de dessous. Ainsi,
Cholesky
 . 
1 −1 1 .. 2
 0 3 −3 ... −3 
 

← (L3 ← L3 − 73 L2 )
 
..
0 0 4 . 2
12 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes
On continue cette seconde étape jusqu’à ce qu’il n’y ait
Zouaouia
BOULENOIR plus que des 0 en dessous du second et l’on recommence
Introduction
sur la matrice plus petite.
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

13 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes
On continue cette seconde étape jusqu’à ce qu’il n’y ait
Zouaouia
BOULENOIR plus que des 0 en dessous du second et l’on recommence
Introduction
sur la matrice plus petite.
Les Méthodes Le processus s’arrête lorsque l’on a une matrice
directes
triangulaire (i.e. une matrice ne contenant que des 0
Méthode de
Gauss sous la diagonale), et donc un système triangulaire.
Décomposition
A en L.U

Méthode de
Cholesky

13 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes
On continue cette seconde étape jusqu’à ce qu’il n’y ait
Zouaouia
BOULENOIR plus que des 0 en dessous du second et l’on recommence
Introduction
sur la matrice plus petite.
Les Méthodes Le processus s’arrête lorsque l’on a une matrice
directes
triangulaire (i.e. une matrice ne contenant que des 0
Méthode de
Gauss sous la diagonale), et donc un système triangulaire.
Décomposition
A en L.U On revient alors à la notation système, et l’on peut faire
Méthode de ”remonter” les équations par substitution des variables.
Cholesky

13 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires  .. 
par des
méthodes
1 −1 1 . 2
 . 
−3 .. −3
directes
 0 3 
Zouaouia  
BOULENOIR .
0 0 4 .. 2
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

14 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires  .. 
par des
méthodes
1 −1 1 . 2
 0 3 −3 ... −3 
directes
 
Zouaouia  
BOULENOIR ..
0 0 4 . 2
Introduction
Dans notre exemple, la dernière ligne de notre matrice
Les Méthodes
directes nous donne l’équation
Méthode de
Gauss 4z = 2, soit z = 12 .
Décomposition
A en L.U

Méthode de
Cholesky

14 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires  .. 
par des
méthodes
1 −1 1 . 2
 0 3 −3 ... −3 
directes
 
Zouaouia  
BOULENOIR ..
0 0 4 . 2
Introduction
Dans notre exemple, la dernière ligne de notre matrice
Les Méthodes
directes nous donne l’équation
Méthode de
Gauss 4z = 2, soit z = 12 .
Décomposition La seconde ligne nous donne
A en L.U

Méthode de 3y − 3z = −3,
Cholesky
et en substituant à z la valeur trouvée, on obtient
3y = − 23 , d’où y = − 12 .

14 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Enfin, la première ligne nous donne

BOULENOIR
x − y + z = 2,
Introduction

Les Méthodes
et en substituant, on obtient
directes
x = 2 − 12 − 12 = 1.
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

15 / 63
 Méthode de Gauss
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Enfin, la première ligne nous donne

BOULENOIR
x − y + z = 2,
Introduction

Les Méthodes
et en substituant, on obtient
directes
x = 2 − 12 − 12 = 1.
Méthode de
Gauss La solution de notre système est donc le triplet
Décomposition
A en L.U (1, − 12 , 21 ).
Méthode de
Cholesky

15 / 63
 Méthode de Gauss

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR Soit AX = b où A est une matrice (n × n), régulière.
Introduction
Principe
Les Méthodes Transformation de la matrice A en une matrice
directes
triangulaire supérieure. Pour cela on construit [A : b] et:
Méthode de
Gauss [A : b]− transformation → [A0 : b0 ] où A0 est une matrice
Décomposition triangulaire supérieure.
A en L.U

Méthode de
Cholesky

16 / 63
 Méthode de Gauss

Résolution
des systèmes
linéaires
par des
méthodes
a’11 a012 · · · a01n b01
   
directes a11 a12 ··· a1n b1
Zouaouia
BOULENOIR
 a21 a22 ··· a2n b2   0 a022 · · · a02n b02 
→
   
 .. .. .. .. .. .. .. .. .. .. 
Introduction
 . . . . .   . . . . . 
Les Méthodes an1 an2 · · · ann bn 0 0 ··· a0nn b0n
directes

Méthode de
Gauss
[A : b] −→ [A0 : b0 ]
Décomposition
A en L.U
Puis, on résoud le système A0 X = b0 ( dont la solution
Méthode de
Cholesky est exactement la solution du système AX = b).

17 / 63
 Méthode de Gauss
Algorithme de Gauss

Résolution Pour k = 1, · · · , n − 1 et pour i = k + 1, · · · , n

des systèmes
linéaires  (i)
par des (k)
méthodes
 Lk ←− Lk


directes

Zouaouia (k)
aik
BOULENOIR
 L(k+1) (k)
←− Li −
(k)


i (k) .Lk .
akk
Introduction

Les Méthodes d’où: (Résolution par retour arrière).

directes

Méthode de
Gauss
Remarque 3.1.
Décomposition 1 La méthode de Gauss néccesite 23 n3 opérations pour un
A en L.U

Méthode de
système d’ordre n.
Cholesky
2 Elle permet de calculer det(A) puisque
n
(k)
Y
det(A) = (−1)j akk où j est le nombre de
k=1
permutations.
18 / 63
 Méthode de Gauss

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Exemple
BOULENOIR
Résoudre le système d’équations ci-contre par la méthode de
Introduction
Gauss:
Les Méthodes
directes 
Méthode de
 x1 + 2x2 − 3x3 = −7,
Gauss (S ) 2x1 − 3x2 + 5x3 = 18,
4x1 + x2 − 2x3 = 24
Décomposition

A en L.U

Méthode de
Cholesky

19 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes  . 
linéaires
par des
1 2 −3 .. −7
méthodes 
A(1)
 
: b(1) =  .. 
 2 −3 5 . 18
directes


Zouaouia .
BOULENOIR 4 1 −2 .. 24
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

20 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes  . 
linéaires
par des
1 2 −3 .. −7
méthodes 
A(1)
 
: b(1) =  .. 
 2 −3 5 . 18
directes


Zouaouia .
BOULENOIR 4 1 −2 .. 24
 (1)
Introduction

 a11 = 1 6= 0
Les Méthodes  (2)
 (1)
directes L1 ← L1
(2) (1) 2 (1) (1) (1) .
Méthode de
Gauss


 L2 ← L 2 − 1 L1 = L 2 − 2L1
 (2) (1) (1) (1) (1)
Décomposition L3 ← L3 − 14 L1 = L3 − 4L1
A en L.U

Méthode de
Cholesky

20 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes  . 
linéaires
par des
1 2 −3 .. −7
méthodes 
A(1)
 
: b(1) =  .. 
 2 −3 5 . 18
directes


Zouaouia .
BOULENOIR 4 1 −2 .. 24
 (1)
Introduction

 a11 = 1 6= 0
Les Méthodes  (2)
 (1)
directes L1 ← L1
(2) (1) (1) (1) (1) .
Méthode de
Gauss


 L2 ← L2 − 12 L1 = L2 − 2L1
 (2) (1) (1) (1) (1)
Décomposition L3 ← L3 − 14 L1 = L3 − 4L1
A en L.U
 . 
Méthode de
Cholesky
1 2 −3 .. −7
 (2) (2)   . 
,→ A : b =
 0 −7 11 .. 32 

.
0 −7 10 .. 52

20 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes
linéaires  (2)
par des 
 a22 = −7 6= 0
méthodes
 (3)
 (2)
directes L1 ← L1
Zouaouia (3) (2) .
BOULENOIR


 L2 ← L2
 (3) (2) −7 (2) (1) (2)
Introduction
L3 ← L3 − −7 L2 = L3 − 1L2
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

21 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes
linéaires  (2)
par des 
 a22 = −7 6= 0
méthodes
 (3)
 (2)
directes L1 ← L1
Zouaouia (3) (2) .
BOULENOIR


 L2 ← L2
 (3) (2) −7 (2) (1) (2)
Introduction
L3 ← L3 − −7 L2 = L3 − 1L2
Les Méthodes
 . 
directes 1 2 −3 .. −7
Méthode de
,→ A(3)
 
: b(3) = 
 .. 
 0 −7 11 . 32
Gauss


.
−1 .. 20
Décomposition
A en L.U 0 0
Méthode de
Cholesky

21 / 63
 Méthode de Gauss
Exemple

Résolution
des systèmes
linéaires  (2)
par des 
 a22 = −7 6= 0
méthodes
 (3)
 (2)
directes L1 ← L1
Zouaouia (3) (2) .
BOULENOIR


 L2 ← L2
 (3) (2) −7 (2) (1) (2)
Introduction
L3 ← L3 − = L3 − 1L2
−7 L2
Les Méthodes
 . 
directes 1 2 −3 .. −7
Méthode de

,→ A(3) : b(3) = 
  .. 
 0 −7 11 . 32
Gauss


.
−1 .. 20
Décomposition
A en L.U 0 0
Méthode de
 
Cholesky 5
X =  −36  .
−20

21 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Exemple
BOULENOIR
Soit  un petit nombre réel et considérons le système linéaire:
Introduction

Les Méthodes x1 + x2 = 1,
directes (S )
Méthode de
x1 + x2 = 2.
Gauss

Décomposition
A en L.U 1 Pour  = 0, on trouve x1 = x2 = 1.
Méthode de
Cholesky

22 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
Exemple(suite)
linéaires
par des Résolvons d’abord le système (S ) par la méthode de Gauss
méthodes
directes ordinaire (sanspermutations).
Zouaouia ..
BOULENOIR
 (1) (1)   1 . 1  h
(2) (2)
i
A :b = . ,→ a1 = A : b =
1 1 .. 2
11
Introduction
 
Les Méthodes .. (1)
  1 . 1  L1
directes

. (1) (1) .
Méthode de
Gauss 0 1 − 1 .. 2 − 1 L2 − 1 L1
 
Décomposition
A en L.U 2− 1 1
x2 = 1− 1
, x1 = 1− .
Méthode de
Cholesky

23 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
Exemple(suite)
linéaires
par des Résolvons d’abord le système (S ) par la méthode de Gauss
méthodes
directes ordinaire (sanspermutations).
Zouaouia ..
BOULENOIR
 (1) (1)   1 . 1  h
(2) (2)
i
A :b = . ,→ a1 = A : b =
1 1 .. 2
11
Introduction
 
Les Méthodes .. (1)
  1 . 1  L1
directes

. (1) (1) .
Méthode de
Gauss 0 1 − 1 .. 2 − 1 L2 − 1 L1
 
Décomposition
A en L.U 2− 1 1
x2 = 1− 1
, x1 = 1− .
Méthode de

Pour  = 10−9 , où 10−9 est la précision de la machine,

Cholesky

on trouve 1 − 101−9 = 1 − 109 = −109 et

2 − 101−9 = 2 − 109 = −109 sur la machine, d’où x2 = 1
et x1 = 0 qui n’est pas la solution du système donné!
23 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
linéaires
Exemple(suite)
par des
méthodes Si par contre, on permute les lignes 1 et 2,
directes
   
Zouaouia .. ..
 1 1 . 2  1 1 . 1
BOULENOIR

.. ,→  ..

Introduction
 1 . 1 0 1− . 1 − 2
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

24 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
linéaires
Exemple(suite)
par des
méthodes Si par contre, on permute les lignes 1 et 2,
directes
   
Zouaouia .. ..
 1 1 . 2  1 1 . 1
BOULENOIR

.. ,→  ..

Introduction
 1 . 1 0 1− . 1 − 2
Les Méthodes
directes

Méthode de
on obtient:
Gauss  
Décomposition
..
h i 1 1 . 2
A en L.U
A(2) : b(2)  ..
,
Méthode de
Cholesky
0 1 − 10−9 . 1 − 2.10−9

24 / 63
 Problème posé par la (quasi) annulation des
pivots
Résolution
des systèmes
linéaires
Exemple(suite)
par des
méthodes Si par contre, on permute les lignes 1 et 2,
directes
   
Zouaouia .. ..
 1 1 . 2  1 1 . 1
BOULENOIR

.. ,→  ..

Introduction
 1 . 1 0 1− . 1 − 2
Les Méthodes
directes

Méthode de
on obtient:
Gauss  
Décomposition
..
h i 1 1 . 2
A en L.U
A(2) : b(2)  ..
,
Méthode de
Cholesky
0 1 − 10−9 . 1 − 2.10−9

or 1 − 10−9 = 1 et 1 − 2.10−9 = 1 sur la machine, d’où

x2 = 1 et x1 = 1 qui est la solution du système donné.

24 / 63
 Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR
Conclusion 3.1.
Introduction
Il ne faut pas utiliser des pivots trop petits car les erreurs
Les Méthodes
directes d’arrondi peuvent donner des solutions fausses. Un moyen
Méthode de de contourner le problème d’un pivot nul ou presque est
Gauss
d’utiliser la technique de pivotage.
Décomposition
A en L.U

Méthode de
Cholesky

25 / 63
 Stratégie du choix du pivot
Stratégie du choix du pivot

Résolution Stratégie du choix du pivot:

des systèmes
linéaires (k)
par des Si on note note A(k) = (aik ) la matrice à l’étape k en
méthodes
directes appliquant l’élimination de Gauss à A.
Zouaouia
BOULENOIR Stratégie du pivot partiel: On prend à l’étape k comme
Introduction
pivot
(k) (k)
Les Méthodes aik = max |alk |.
directes kl≤n
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

26 / 63
 Stratégie du choix du pivot
Stratégie du choix du pivot

Résolution Stratégie du choix du pivot:

des systèmes
linéaires (k)
par des Si on note note A(k) = (aik ) la matrice à l’étape k en
méthodes
directes appliquant l’élimination de Gauss à A.
Zouaouia
BOULENOIR Stratégie du pivot partiel: On prend à l’étape k comme
Introduction
pivot
(k) (k)
Les Méthodes aik = max |alk |.
directes kl≤n
Méthode de
Gauss

Décomposition
Stratégie du pivot total: On prend à l’étape k comme
A en L.U pivot
Méthode de (k) (k)
Cholesky aik = max |alh |.
k≤l,h≤n

26 / 63
 Stratégie du choix du pivot
Stratégie du choix du pivot

Résolution Stratégie du choix du pivot:

des systèmes
linéaires (k)
par des Si on note note A(k) = (aik ) la matrice à l’étape k en
méthodes
directes appliquant l’élimination de Gauss à A.
Zouaouia
BOULENOIR Stratégie du pivot partiel: On prend à l’étape k comme
Introduction
pivot
(k) (k)
Les Méthodes aik = max |alk |.
directes kl≤n
Méthode de
Gauss

Décomposition
Stratégie du pivot total: On prend à l’étape k comme
A en L.U pivot
Méthode de (k) (k)
Cholesky aik = max |alh |.
k≤l,h≤n

Attention!: A chaque permutation de colonnes les

inconnues changent de places.
26 / 63
 Exemple
Méthode de Gauss avec pivot partiel

Résolution
des systèmes
linéaires
par des
méthodes Résoudre par la méthode de Gauss avec pivot partiel le
directes
système suivant:
Zouaouia
BOULENOIR 
 4x1 + 2x2 + 6x3 = 6,
Introduction
(S) 8x1 + 4x2 + 10x3 = 10,
Les Méthodes
6x1 + 14x2 + 6x3 = 4

directes

Méthode de
Gauss  .. 
Décomposition 4 2 6
. 6
A en L.U 
[A : b] =  .. 
 8 4 10 . 10 

Méthode de
Cholesky .
6 14 6 .. 4

27 / 63
 (1)
Résolution
des systèmes
1ère étape: Comme a11 = max(4, 8, 6) = 8 on permute
linéaires
par des
entre la ligne 2 et 1. On obtient le système suivant:
 . 
8 4 10 .. 10
méthodes
directes

Zouaouia
 (1) (1)  
A :b = .. 
 4 2 6 . 6 

BOULENOIR
.
Introduction 6 14 6 .. 4
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

28 / 63
 (1)
Résolution
des systèmes
1ère étape: Comme a11 = max(4, 8, 6) = 8 on permute
linéaires
par des
entre la ligne 2 et 1. On obtient le système suivant:
 . 
8 4 10 .. 10
méthodes
directes

Zouaouia
 (1) (1)  
A :b = .. 
 4 2 6 . 6 

BOULENOIR
.
Introduction 6 14 6 .. 4
Les Méthodes  (1)
directes 
 a11 = 8 6= 0
 (2)
 (1)
Méthode de
L1 ← L1
Gauss
(2) (1) 4 (1) (1) 1 (1)
.
Décomposition 
 L 2 ← L 2 − 8 L1 = L 2 − 2 L1
A en L.U 
 (2) (1) (1) (1) (1)
Méthode de
L3 ← L3 − 68 L1 = L3 − 34 L1
Cholesky

28 / 63
 (1)
Résolution
des systèmes
1ère étape: Comme a11 = max(4, 8, 6) = 8 on permute
linéaires
par des
entre la ligne 2 et 1. On obtient le système suivant:
 . 
8 4 10 .. 10
méthodes
directes

Zouaouia
 (1) (1)  
A :b = .. 
 4 2 6 . 6 

BOULENOIR
.
Introduction 6 14 6 .. 4
Les Méthodes  (1)
directes 
 a11 = 8 6= 0
 (2)
 (1)
Méthode de
L1 ← L1
Gauss
(2) (1) 4 (1) (1) 1 (1)
.
Décomposition 
 L 2 ← L 2 − 8 L1 = L 2 − 2 L 1
A en L.U 
 (2) (1) (1) (1) (1)
Méthode de
L3 ← L3 − 68 L1 = L3 − 34 L1
Cholesky  . 
8 4 10 .. 10
,→ [A0 : b0 ] = 
 .. 
 0 0 1 . 1  
3 .. 7
0 11 −
2 2 . −
28 / 63
 Résolution 2ème étape: Dans cette étape, la ligne 3 et 2 seront
des systèmes (2)
linéaires permutées du faite que le a22 = max(0, 11) = 11, ce qui
par des
méthodes implique :
directes  . 
Zouaouia 8 4 10 .. 10
3 ..
BOULENOIR  (2) (2)     (3) (3) 
A :b = 0 11 − 2 . − 2  = A : b
7 
Introduction
..
Les Méthodes 0 0 1 . 1
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

29 / 63
 Résolution 2ème étape: Dans cette étape, la ligne 3 et 2 seront
des systèmes (2)
linéaires permutées du faite que le a22 = max(0, 11) = 11, ce qui
par des
méthodes implique :
directes  . 
Zouaouia 8 4 10 .. 10
3 ..
BOULENOIR  (2) (2)     (3) (3) 
A :b =  0 11 − 2 . − 2  = A : b
7 
Introduction
..
Les Méthodes 0 0 1 . 1
directes
 (2)
Méthode de
Gauss
 a22 = 11 6= 0

 (3)
 (2)
L1 ← L1
Décomposition
A en L.U (3) (2) .

 L2 ← L 2
Méthode de 
 (3) (2) 0 (2) (1)
Cholesky L3 ← L3 − 11 L2 = L3

29 / 63
 Résolution 2ème étape: Dans cette étape, la ligne 3 et 2 seront
des systèmes (2)
linéaires permutées du faite que le a22 = max(0, 11) = 11, ce qui
par des
méthodes implique :
directes  . 
Zouaouia 8 4 10 .. 10
3 ..
BOULENOIR  (2) (2)     (3) (3) 
A :b =  0 11 − 2 . − 2  = A : b
7 
Introduction
..
Les Méthodes 0 0 1 . 1
directes
 (2)
Méthode de
Gauss
 a22 = 11 6= 0

 (3)
 (2)
L1 ← L1
Décomposition
A en L.U (3) (2) .

 L2 ← L 2
Méthode de 
 (3) (2) 0 (2) (1)
Cholesky L3 ← L3 − 11 L2 = L3
On en déduit les solutions par itérations inverse
1 2
X=( , − , 1).
29 / 63
11 11
 Exercice 1

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR Résoudre par la méthode de Gauss avec pivot total le
Introduction
système suivant:
Les Méthodes 
directes  2x + y − 4z = 8
Méthode de 3x + 3y − 5 z = 14 AX = b
Gauss
4x + 5y − 2 z = 16

Décomposition
A en L.U

Méthode de
Cholesky

30 / 63
 Exercice 2

Résolution
des systèmes
linéaires
par des
méthodes
directes
Soient
Zouaouia
BOULENOIR
   
2 1 3 3
Introduction A=  4 2 5  et b =  5 .
Les Méthodes
directes
3 7 3 2
Méthode de
Gauss 1 Résoudre par la méthode de Gauss le système Ax = b. En
Décomposition
A en L.U déduire le déterminant de A.
Méthode de 2 Inverser A et retrouver x = A−1 b.
Cholesky

31 / 63
 Exercice 3

Résolution
des systèmes
linéaires On cherche la solution du système linéaire Ax = b avec
par des
méthodes    
directes 1 0 6 2 6
Zouaouia  8 0 −2 −2   et b =  −2  .
 
BOULENOIR A=  2 9 1 3   −8 
Introduction
2 1 −3 10 −4
Les Méthodes
directes

Méthode de 1 Pourquoi la méthode de Gauss sans permutation ne

Gauss

Décomposition
fonctionne pas pour résoudre ce système linéaire?
A en L.U
2 Donner une permutation de lignes de A permettant
Méthode de
Cholesky d’utiliser ensuite la méthode de Gauss.
3 Donner la solution de ce système linéaire. (NB: La
solution prend ses valeurs dans Z)

32 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes Exemple
directes

Zouaouia
Résoudre le système linéaire suivant en utilisant la
BOULENOIR décomposition LU
Introduction 
Les Méthodes
 x1 + 4x2 + 7x3 = 18,
directes 2x1 + 5x2 + 8x3 = 24,
3x1 + 6x2 + 11x3 = 32
Méthode de

Gauss

Décomposition    
A en L.U u11 u12 u13 1 0 0
Méthode de
Cholesky
U = 0 u22 u23 , L =  l21 1 0 
0 0 u33 l31 l32 1

33 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
Exemple(suite)
linéaires  
par des
méthodes
1 4 7
directes A(1) = 2 5 8 
Zouaouia
BOULENOIR
3 6 11
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

34 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
Exemple(suite)
linéaires  
par des
méthodes
1 4 7
directes A(1) = 2 5 8 
Zouaouia
BOULENOIR
3 6 11
 (1)
Introduction 
 a11 = 1 6= 0
(2) (1)

L1 ← L1

Les Méthodes 

directes 

 (2) (1) 2 (1) (1) (1)
Méthode de L2 ← L2 − L1 = L2 − |{z}
2 L1 .
Gauss 1 l21
l21

 |{z}
Décomposition
3

(2) (1) (1) (1) (1)

A en L.U
L ← L3 − L1 = L3 − |{z}

 3 L1
 3

Méthode de
 1
|{z}l31 l31
Cholesky

34 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
Exemple(suite)
linéaires  
par des
méthodes
1 4 7
directes A(1) = 2 5 8 
Zouaouia
BOULENOIR
3 6 11
 (1)
Introduction 
 a11 = 1 6= 0
(2) (1)

L1 ← L1

Les Méthodes 

directes 

 (2) (1) 2 (1) (1) (1)
Méthode de L2 ← L2 − L1 = L2 − |{z}
2 L1 .
Gauss 1 l21
l21

 |{z}
Décomposition
3

(2) (1) (1) (1) (1)

A en L.U
L ← L3 − L1 = L3 − |{z}

 3 L1
 3

Méthode de
 1
|{z}l31 l31
Cholesky
   
1 4 7 1 0 0
,→ A(2) =  0 −3 −6  L =  2 1 0 
0 −6 −10 3 l32 1
34 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
Exemple
directes  (2)
Zouaouia

 a22 = −3 6= 0
BOULENOIR (3) (2)

L ← L1


 1(3)


Introduction (2)
L2 ← L2 .
Les Méthodes  (3) (2) −6 (2) (1) (2)
directes  L3 ← L 3 − L = L − 2 L
−3 2 3 |{z} 2


Méthode de


Gauss

 |{z} l32
l32
Décomposition
A en L.U

Méthode de
Cholesky

35 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
Exemple
directes  (2)
Zouaouia

 a22 = −3 6= 0
BOULENOIR (3) (2)

L ← L1


 1(3)


Introduction (2)
L2 ← L2 .
Les Méthodes  (3) (2) −6 (2) (1) (2)
directes 
 L3 ← L3 − L2 = L3 − |{z}
2 L2
−3


Méthode de 
Gauss

 |{z} l32
l32
Décomposition    
A en L.U
1 4 7 1 0 0
Méthode de
Cholesky ,→ A(3) =  0 −3 −6  = U , L =  2 1 0 
0 0 2 3 2 1

35 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR L.Y = b
A.X = b ⇐⇒ L. |{z}
U.X = b ⇐⇒
Introduction
U.X = Y.
Y
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

36 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR L.Y = b
A.X = b ⇐⇒ L. |{z}
U.X = b ⇐⇒
Introduction
U.X = Y.
Y
Les Méthodes
directes
On cherche lasolution Y 
dusystème
 LY= b: 
Méthode de
Gauss
1 0 0 y1 18
Décomposition LY = b ←→  2 1 0   y2  =  24 
A en L.U
3 2 1 y3 32
Méthode de
Cholesky

36 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR L.Y = b
A.X = b ⇐⇒ L. |{z}
U.X = b ⇐⇒
Introduction
U.X = Y.
Y
Les Méthodes
directes
On cherche lasolution Y 
dusystème
 LY= b: 
Méthode de
Gauss
1 0 0 y1 18
Décomposition LY = b ←→  2 1 0   y2  =  24 
A en L.U
3 2 1 y3 32
Méthode de  
Cholesky 18
y =  −12 
2

36 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes
Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X du système
  UX =Y
: 
Introduction
1 4 7 x1 18
Les Méthodes U X = Y ←→  0 −3 −6   x2  =  −12 
directes
0 0 2 x3 2
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

37 / 63
 Décomposition A en L.U
Un exemple concret avant le cas général

Résolution
des systèmes
linéaires
par des
méthodes
directes
Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X du système
  UX =Y
: 
Introduction
1 4 7 x1 18
Les Méthodes U X = Y ←→  0 −3 −6   x2  =  −12 
directes
0 0 2 x3 2
Méthode de  
Gauss 3
Décomposition
A en L.U
X= 2 
Méthode de 1
Cholesky

37 / 63
 Décomposition A en L.U :
Idée générale

Résolution
des systèmes
La décomposition LU consiste à factoriser A sous la forme
linéaires
par des P A = LU ;
méthodes
directes
avec
Zouaouia  
(k) (k)
···
 
BOULENOIR
1 0 ··· 0 a11 0 a1n
(k) (k)
l21 1 ··· 0 ···
 
Introduction    0 a22 a2n 
L = ,U =
 
Les Méthodes .. .. .. .. .. .. .. .. 
directes  . . . .  
 . . . .


Méthode de ln1 ln2 · · · 1 0 0 ···
(k)
ann
Gauss

Décomposition
A en L.U
et P , une matrice de permutation (en particulier P t = P −1 ).
Méthode de
Cholesky
Motivation:
La résolution du système Ax = b s’effectue en 2 étapes:

L.Y = P t .b

t
A.X = b ⇐⇒ L. |{z}
U.X = P .b ⇐⇒
U.X = Y.
38 / 63 Y
 Décomposition A en L.U sans pivot:

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR Proposition 4.1.
Introduction Une matrice A est décomposable en L.U avec P = Id
Les Méthodes
directes
(A = L.U ) ssi det(A)[k] 6= 0 (i.e: les sous matrices
Méthode de
principales de A sont inversibles).
Gauss
Cette décomposition si elle existe est unique.
Décomposition
A en L.U

Méthode de
Cholesky

39 / 63
 Décomposition de A en L.U sans pivot

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Par la méthode de Gauss on obtient U tel que U = A0 et

BOULENOIR
pour déterminer les coefficients de la matrice L:
Introduction
Algorithme L:
Les Méthodes  (k)
 akk 6= 0
directes 

Méthode de
Gauss
(k)
Décomposition aik
 lik ←−

A en L.U

(k) .
akk
Méthode de
Cholesky

40 / 63
 Décomposition de A en L.U sans pivot
Algorithme

Résolution
des systèmes
linéaires For k = 1, · · · , n − 1
par des
méthodes
directes
For i = k + 1, · · · , n
Zouaouia
(k−1)
BOULENOIR aik
lik = (k−1)
Introduction
akk
Les Méthodes
directes
For j = k + 1, · · · , n
Méthode de
Gauss
(k) (k−1) (k−1)
Décomposition aij = aij −lik akj
A en L.U

Méthode de
Cholesky End
End
End

41 / 63
 Décomposition de A en L.U sans pivot
Exemple

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia Exemple
BOULENOIR
Résoudre le système linéaire suivant en utilisant la
Introduction
décomposition LU sans pivot
Les Méthodes
directes    
Méthode de
2 1 2 1
Gauss A =  3 1 0  , et b =  0  .
Décomposition
A en L.U
4 1 0 0
Méthode de
Cholesky

42 / 63
 Décomposition de P.A en L.U avec pivot
Algorithme LU avec pivot

Résolution
des systèmes
linéaires
par des
méthodes Motivation:
directes
La décomposition LU est instable lorsque les
Zouaouia
(k)
BOULENOIR coefficients ak+1,k+1 deviennent trop petits et ne
Introduction s’applique plus si l’hypothèse des sous-matrices
Les Méthodes principales inversibles n’est pas vérifiée.
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

43 / 63
 Décomposition de P.A en L.U avec pivot
Algorithme LU avec pivot

Résolution
des systèmes
linéaires
par des
méthodes Motivation:
directes
La décomposition LU est instable lorsque les
Zouaouia
(k)
BOULENOIR coefficients ak+1,k+1 deviennent trop petits et ne
Introduction s’applique plus si l’hypothèse des sous-matrices
Les Méthodes principales inversibles n’est pas vérifiée.
directes

Méthode de
En pratique, il est plus efficace d’utiliser une
Gauss décomposition LU avec pivot
Décomposition
A en L.U

Méthode de
P.A = L.U.
Cholesky

43 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR Résoudre le système linéaire suivant en utilisant la
Introduction
décomposition LU avec pivot
Les Méthodes    
directes 0 2 2 4
Méthode de A =  4 2 4  , et b =  10  .
Gauss

Décomposition
2 4 4 10
A en L.U

Méthode de
Cholesky

44 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
des systèmes
linéaires
par des 1ère étape: Comme a11 = 0 on commence par choisir le
méthodes
directes pivot; le plus grand élément de la première colonne puis on
Zouaouia procède
 comme pour
 l’algorithme  L.U sanspivot
BOULENOIR
0 2 2 0 1 0
Introduction A =  4 2 4  −→ P1 =  1 0 0 −→
Les Méthodes
directes
2 4 4 0 1 1
 
Méthode de 4 2 4
Gauss
A(1) =  0 2 2 
Décomposition
A en L.U 2 4 4
Méthode de
Cholesky

45 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
des systèmes
linéaires
par des 1ère étape: Comme a11 = 0 on commence par choisir le
méthodes
directes pivot; le plus grand élément de la première colonne puis on
Zouaouia procède
 comme pour
 l’algorithme  L.U sanspivot
BOULENOIR
0 2 2 0 1 0
Introduction A =  4 2 4  −→ P1 =  1 0 0 −→
Les Méthodes
directes
2 4 4 0 1 1
 
Méthode de 4 2 4
Gauss
A(1) =  0 2 2 
Décomposition
A en L.U 2 4 4
Méthode de
Cholesky
Les mineurs principaux de la matrice proposée sont :
4 2
∆1 = 4 6= 0, ∆2 = = 8 6= 0, ∆3 = −8 6= 0
0 2

45 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
par des
méthodes
directes

Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes

Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes (2) (1) (1) (1) (1)
Zouaouia
L2 ← L2 − 04 L1 = L2 − |{z}
0 L1
BOULENOIR
l21
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes (2) (1) (1) (1) (1)
Zouaouia
L2 ← L2 − 04 L1 = L2 − |{z}
0 L1
BOULENOIR
l21
Introduction (2) (1) (1) (1) 1 (1)
L3 ← L3 − 24 L1 = L3 − L
Les Méthodes 2 1
directes |{z}
Méthode de
l31
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes (2) (1) (1) (1) (1)
Zouaouia
L2 ← L2 − 04 L1 = L2 − |{z}
0 L1
BOULENOIR
l21
Introduction (2) (1) (1) (1) 1 (1)
L3 ← L3 − 24 L1 = L3 − L
Les Méthodes 2 1
directes |{z}
Méthode de
l31
Gauss (1)
a21 0
Décomposition l21 = (1) = 4 =0
A en L.U
a11
Méthode de
Cholesky

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes (2) (1) (1) (1) (1)
Zouaouia
L2 ← L2 − 04 L1 = L2 − |{z}
0 L1
BOULENOIR
l21
Introduction (2) (1) (1) (1) 1 (1)
L3 ← L3 − 24 L1 = L3 − L
Les Méthodes 2 1
directes |{z}
Méthode de
l31
Gauss (1)
a21 0
Décomposition l21 = (1) = 4 =0
A en L.U
a11
(1)
a31
= 12 .
Méthode de
Cholesky l31 = (1)
a11

46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

(1)
Résolution
des systèmes a11 = 4 6= 0
linéaires
(2) (1)
par des
méthodes
L1 ← L1
directes (2) (1) (1) (1) (1)
Zouaouia
L2 ← L2 − 04 L1 = L2 − |{z}
0 L1
BOULENOIR
l21
Introduction (2) (1) (1) (1) 1 (1)
L3 ← L3 − 24 L1 = L3 − L
Les Méthodes 2 1
directes |{z}
Méthode de
l31
Gauss (1)
a21 0
Décomposition l21 = (1) = 4 =0
A en L.U
a11
(1)
a31
= 12 .
Méthode de
Cholesky l31 = (1)
a11
   
4 2 4 1 0 0
A(2) =  0 2 2 , L =  0 1 0 
1
0 3 2 2 l32 1
46 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes

Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR (3) (2)
L1 ← L1
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR (3) (2)
L1 ← L1
Introduction (3) (2)
L2 ← L2
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR (3) (2)
L1 ← L1
Introduction (3) (2)
L2 ← L2
Les Méthodes
directes (3) (2) (2) (2) 3 (1)
L3 ← L3 − 32 L2 = L3 − L1
Méthode de
Gauss
2
|{z}
Décomposition l32
A en L.U

Méthode de
Cholesky

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR (3) (2)
L1 ← L1
Introduction (3) (2)
L2 ← L2
Les Méthodes
directes (3) (2) (2) (2) 3 (1)
L3 ← L3 − 32 L2 = L3 − L1
Méthode de
Gauss
2
|{z}
Décomposition l32
A en L.U (2)
a32 2
Méthode de l32 = (2) = 3
Cholesky a22

47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
(2)
des systèmes
linéaires
2ème étape: Comme a22 = 2 on procède l’algorithme L.U
par des
méthodes
sans pivot
directes (2)
a22 = 2 6= 0
Zouaouia
BOULENOIR (3) (2)
L1 ← L1
Introduction (3) (2)
L2 ← L2
Les Méthodes
directes (3) (2) (2) (2) 3 (1)
L3 ← L3 − 32 L2 = L3 − L1
Méthode de
Gauss
2
|{z}
Décomposition l32
A en L.U (2)
a32 2
Méthode de l32 = (2) = 3
Cholesky a22
   
4 2 4 1 0 0
A(3) =  0 2 2  = U, L =  0 1 0 
1 3
0 0 −1 2 2 1
47 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
des systèmes
linéaires
par des
méthodes
directes  
Zouaouia
0 1 0
BOULENOIR P = P1 =  1 0 0 
Introduction 0 0 1
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

48 / 63
 Décomposition de P.A en L.U avec pivot
Exemple

Résolution
des systèmes
linéaires
par des
méthodes
directes  
Zouaouia
0 1 0
BOULENOIR P = P1 =  1 0 0 
Introduction 0 0 1
Les Méthodes Résolution du Système :
directes

Méthode de

Gauss L.Y = P.b
U.X = P.b ⇐⇒
P.A.X = P.b ⇐⇒ L. |{z}
Décomposition U.X = Y.
A en L.U Y
Méthode de
Cholesky

48 / 63
 Décomposition P.A en L.U

Résolution
des systèmes
linéaires
par des
méthodes Exemple(suite)
directes      
Zouaouia 0 1 0 0 2 2 4 2 4
BOULENOIR
P.A =  1 0 0  .  4 2 4  =  0 2 2 
Introduction 0 0 1 2 4 4 2 4 4
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

49 / 63
 Décomposition P.A en L.U

Résolution
des systèmes
linéaires
par des
méthodes Exemple(suite)
directes      
Zouaouia 0 1 0 0 2 2 4 2 4
BOULENOIR
P.A =  1 0 0  .  4 2 4 = 0 2 2 
Introduction 0 0 1 2 4 4 2 4 4
Les Méthodes    
directes 1 0 0 4 2 4
Méthode de L.U =  0 1 0 . 0
  2 2 =
Gauss 1 3
2 2 1 0 0 −1
Décomposition 
A en L.U 4 2 4
Méthode de  0 2 2  = P.A
Cholesky
2 4 4

49 / 63
 Décomposition P.A en L.U

Résolution
des systèmes Exemple(suite)
linéaires
par des On cherche la solution Y dusystème LY
 = P.b:
méthodes  
directes 1 0 0 y1
Zouaouia LY = P.b ←→  0 1 0  .  y2 
BOULENOIR 1 3
   2 2 1 y3
Introduction
0 1 0 4
Les Méthodes
directes =  1 0 0  .  10 
Méthode de 0 0 1 10
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

50 / 63
 Décomposition P.A en L.U

Résolution
des systèmes Exemple(suite)
linéaires
par des On cherche la solution Y du système LY
 = P.b:
méthodes  
directes 1 0 0 y1
Zouaouia LY = P.b ←→  0 1 0  .  y2 
BOULENOIR 1 3
   2 2 1 y3
Introduction
0 1 0 4
Les Méthodes
directes =  1 0 0  .  10 
Méthode de 0 0 1 10
Gauss      
Décomposition
1 0 0 y1 10
A en L.U
←→  0 1 0  .  y2  =  4 
Méthode de 1 3
Cholesky 2 2 1 y3 10

50 / 63
 Décomposition P.A en L.U

Résolution
des systèmes Exemple(suite)
linéaires
par des On cherche la solution Y du système LY
 = P.b:
méthodes  
directes 1 0 0 y1
Zouaouia LY = P.b ←→  0 1 0  .  y2 
BOULENOIR 1 3
   2 2 1 y3
Introduction
0 1 0 4
Les Méthodes
directes =  1 0 0  .  10 
Méthode de 0 0 1 10
Gauss      
Décomposition
1 0 0 y1 10
A en L.U
←→  0 1 0  .  y2  =  4 
Méthode de 1 3
Cholesky 2 2 1 y3 10
 
10
y= 4 
−1
50 / 63
 Décomposition P.A en L.U

Résolution
des systèmes
linéaires
par des
méthodes
directes
Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X du 
système
 U
X =Y : 
Introduction
4 2 4 x1 10
Les Méthodes U X = Y ←→  0 2 2   x2  =  4 
directes
0 0 −1 x3 −1
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

51 / 63
 Décomposition P.A en L.U

Résolution
des systèmes
linéaires
par des
méthodes
directes
Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X du 
système
 U
X =Y : 
Introduction
4 2 4 x1 10
Les Méthodes U X = Y ←→  0 2 2   x2  =  4 
directes
0 0 −1 x3 −1
Méthode de  
Gauss 1
Décomposition
A en L.U
X= 1 
Méthode de 1
Cholesky

51 / 63
 Méthode de Cholesky

Résolution
des systèmes
linéaires
par des
méthodes
directes La décomposition de Cholesky consiste à factoriser A
Zouaouia
BOULENOIR
sous la forme R.RT = A où: R une matrice triangulaire
inférieure (M.T.I)
Introduction
 
Les Méthodes
directes
r11 0 · · · 0
 r21 r22 · · · 0 
Méthode de
R = . ..  .
 
Gauss .. ..
Décomposition
 .. . . . 
A en L.U
rn1 rn2 · · · rnn
Méthode de
Cholesky

52 / 63
 Méthode de Cholesky

Résolution
des systèmes
linéaires Motivation
par des
méthodes
directes
Comme pour la décomposition LU , la résolution du
Zouaouia
système Ax = b s’effectue en 2 étapes:
BOULENOIR

T R.Y = b
Introduction A.X = b ⇐⇒ R. R | {z.X} = b ⇐⇒ RT .X = Y.
Les Méthodes
directes Y
Méthode de
Gauss

Décomposition
A en L.U Avantage
Méthode de L’avantage par rapport à la factorisation LU est
Cholesky
• de n’avoir qu’une seule matrice à stocker
• de présenter un algorithme 2 fois plus rapide!

53 / 63
 Méthode de Cholesky

Résolution
des systèmes
linéaires
par des Proposition 5.1.
méthodes
directes A est dite symétrique si AT = A.
Zouaouia
BOULENOIR A est dite défine positive si
Introduction
∀X ∈ Rn , X 6= 0, < AX, X >= X T AX > 0.
Les Méthodes
directes
Théorème 5.1.
Méthode de
Gauss A est définie positive ssi tous ses mineurs:
Décomposition
A en L.U
a11 a12
Méthode de 41 = a11 , 42 = , · · · , 4n = det(A)
Cholesky a21 a22

sont strictement positifs.

54 / 63
 Méthode de Cholesky

Résolution
des systèmes
linéaires
par des
méthodes
directes

Zouaouia
Théorème 5.2.
BOULENOIR
Si A est une matrice symétrique définie positive, alors il
Introduction existe une unique matrice R triangulaire inférieure avec
Les Méthodes
directes
coefficients diagonaux positifs telle que
Méthode de
Gauss A = R.Rt .
Décomposition
A en L.U

Méthode de
Cholesky

55 / 63
 Méthode de Cholesky
Algorithme (Décomposition de Cholesky)

Résolution
des systèmes
linéaires
par des
For k = 1, · · · , n
méthodes
directes
v
u k−1
Zouaouia
u X
2
BOULENOIR rkk = takk − rkj
j=1
Introduction

Les Méthodes
directes For i = k + 1, · · · , n
Méthode de  
Gauss k−1
1  X
Décomposition rik = aik − rij rkj 
A en L.U
rkk
Méthode de
j=1
Cholesky

End
End.

56 / 63
 Méthode de Cholesky

Résolution
des systèmes
linéaires
par des Remarque 5.1.
méthodes
3
directes
La méthode de Cholesky nécessite n3 opérations
Zouaouia
BOULENOIR élémentaires (meilleur que celle de Gauss).
Introduction La méthode de Cholesky permet le calcul du
Les Méthodes déterminant de A. En effet:
directes

Méthode de n
Y
Gauss
A = R.RT =⇒ det(A) = det(R.RT ) = ( rii )2 .
Décomposition
A en L.U i=1
Méthode de
Cholesky
La décomposition A = RRT n’est pas unique si on
n’impose pas que rii > 0, i = 1, ..., n.

57 / 63
 Exemple

Résolution
des systèmes
linéaires
par des
méthodes
directes
Résoudre par la méthode de Cholesky le système suivant:
Zouaouia 
BOULENOIR  4x + 2 z = 30
Introduction 9y + 3 z = 15
2x + 3y + 18 z = 40

Les Méthodes
directes

Méthode de
Gauss
   
Décomposition
A en L.U
4 0 2 30
Méthode de
A =  0 9 3  , b =  15 
Cholesky 2 3 18 40

58 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes Exemple
linéaires
par des
méthodes
Avant d’avancer la factorisation de Cholesky, on doit
directes vérifier si A = AT et ∆k > 0, k = 1, 2, 3. En effet,
Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

59 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes Exemple
linéaires
par des
méthodes
Avant d’avancer la factorisation de Cholesky, on doit
directes vérifier si A = AT et ∆k > 0, k = 1, 2, 3. En effet,
Zouaouia
BOULENOIR A est symétrique car A = AT
Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

59 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes Exemple
linéaires
par des
méthodes
Avant d’avancer la factorisation de Cholesky, on doit
directes vérifier si A = AT et ∆k > 0, k = 1, 2, 3. En effet,
Zouaouia
BOULENOIR A est symétrique car A = AT
Introduction A est une matrice définie positive car:
Les Méthodes 4 0
directes ∆1 = 4 > 0, ∆2 = = 36 > 0, ∆3 = det(A) =
0 9
Méthode de
Gauss 576 > 0.
Décomposition
A en L.U

Méthode de
Cholesky

59 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes Exemple
linéaires
par des
méthodes
Avant d’avancer la factorisation de Cholesky, on doit
directes vérifier si A = AT et ∆k > 0, k = 1, 2, 3. En effet,
Zouaouia
BOULENOIR A est symétrique car A = AT
Introduction A est une matrice définie positive car:
Les Méthodes 4 0
directes ∆1 = 4 > 0, ∆2 = = 36 > 0, ∆3 = det(A) =
0 9
Méthode de
Gauss 576 > 0.
Décomposition Alors, A est décomposable en R.RT .
A en L.U

Méthode de
   
Cholesky r11 0 0 r11 r21 r31
R =  r21 r22 0  , RT =  0 r22 r32 
r31 r32 r33 0 0 r33

59 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia
BOULENOIR

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31 = a31
= 2
=1
Introduction a11 r11 2
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31
= a31
= =1 2
Introduction a11 r11 2
p p √
Les Méthodes
directes r22 = a22 − (r21 )2 = 9 − (0)2 = 9 = 3
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31
= a31
= =1 2
Introduction a11 r11 2
p p √
Les Méthodes
directes r22 = a22 − (r21 )2 = 9 − (0)2 = 9 = 3
1
Méthode de r32 = r11 (a32 − r31 r21 ) = 13 (3 − 0.1) = 1
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31
= a31
= =1 2
Introduction a11 r11 2
p p √
Les Méthodes
directes r22 = a22 − (r21 )2 = 9 − (0)2 = 9 = 3
1 1
r32 = r11 (a32 − r31 r21 ) = 3 (3 − 0.1) = 1
Méthode de
Gauss
p p
Décomposition r√33 = a33 − (r32 )2 − (r31 )2 = 18 − (1)2 − (1)2 =
A en L.U

Méthode de
16 = 4
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31
= a31
= =1 2
Introduction a11 r11 2
p p √
Les Méthodes
directes r22 = a22 − (r21 )2 = 9 − (0)2 = 9 = 3
1 1
r32 = r11 (a32 − r31 r21 ) = 3 (3 − 0.1) = 1
Méthode de
Gauss
p p
Décomposition r√33 = a33 − (r32 )2 − (r31 )2 = 18 − (1)2 − (1)2 =
A en L.U

Méthode de
16 = 4
Cholesky

60 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
√ √
méthodes
directes
r11 = a11 = 4=2
Zouaouia r21 = √a21 = a21
= 0
=0
BOULENOIR a11 r11 2
r31 = √a31
= a31
= =1 2
Introduction a11 r11 2
p p √
Les Méthodes
directes r22 = a22 − (r21 )2 = 9 − (0)2 = 9 = 3
1 1
r32 = r11 (a32 − r31 r21 ) = 3 (3 − 0.1) = 1
Méthode de
Gauss
p p
Décomposition r√33 = a33 − (r32 )2 − (r31 )2 = 18 − (1)2 − (1)2 =
A en L.U

Méthode de
16 = 4
   
Cholesky 2 0 0 2 0 1
R =  0 3 0 , R T =  0 3 1 
1 1 4 0 0 4

60 / 63
 Méthode de Cholesky R.RT

Résolution Exemple(suite)
des systèmes
linéaires
 √  
4=2 0 0

par des 2 0 0
méthodes  0
R =  √4 = 0 r22 0  =  0 r22 0 

directes

Zouaouia √2 = 1 r32 r33 1 r32 r33

BOULENOIR 4

Introduction

Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

61 / 63
 Méthode de Cholesky R.RT

Résolution Exemple(suite)
des systèmes
linéaires
 √  
4=2 0 0

par des 2 0 0
méthodes  0
R =  √4 = 0 r22 0  =  0 r22 0 

directes

Zouaouia √2 = 1 r32 r33 1 r32 r33

BOULENOIR 4
 
Introduction
2 p 0 0
Les Méthodes
 ←0 ← 9 − (0)2 = 3 0 
directes R=  l


Méthode de
Gauss ←1 ← 13 [3 − (1.0)] = 1 r33
Décomposition
A en L.U

Méthode de
Cholesky

61 / 63
 Méthode de Cholesky R.RT

Résolution Exemple(suite)
des systèmes
linéaires
 √  
4=2 0 0

par des 2 0 0
méthodes  0
R =  √4 = 0 r22 0  =  0 r22 0 

directes

Zouaouia √2 = 1 r32 r33 1 r32 r33

BOULENOIR 4
 
Introduction
2 p 0 0
Les Méthodes
 ←0 ← 9 − (0)2 = 3 0 
directes R=  l


Méthode de 1
Gauss ←1 ← 3 [3 − (1.0)] = 1 r33
Décomposition
 
A en L.U
2 0 0
Méthode de R= 0 3 p 0 
Cholesky
1 ←1 ← 18 − (1)2 − (1)2 = 4

61 / 63
 Méthode de Cholesky R.RT

Résolution Exemple(suite)
des systèmes
linéaires
 √  
4=2 0 0

par des 2 0 0
méthodes  0
R =  √4 = 0 r22 0  =  0 r22 0 

directes

Zouaouia √2 = 1 r32 r33 1 r32 r33

BOULENOIR 4
 
Introduction
2 p 0 0
Les Méthodes
 ←0 ← 9 − (0)2 = 3 0 
directes R=  l


Méthode de 1
Gauss ←1 ← 3 [3 − (1.0)] = 1 r33
Décomposition
 
A en L.U
2 0 0
Méthode de R= 0 3 p 0 
Cholesky
1 ←1 ← 18 − (1)2 − (1)2 = 4
 
2 0 0
R= 0 3 0 
1 1 4
61 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR T R.Y = b
A.X = b ⇐⇒ R. R
| {z.X} = b ⇐⇒
Introduction
RT .X = Y.
Y
Les Méthodes
directes

Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

62 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR T R.Y = b
A.X = b ⇐⇒ R. R
| {z.X} = b ⇐⇒
Introduction
RT .X = Y.
Y
Les Méthodes
directes
On cherche lasolution Y 
du
système
 RY= b: 
Méthode de
Gauss
2 0 0 y1 30
Décomposition RY = b ←→  0 3 0   y2  =  15 
A en L.U
1 1 4 y3 40
Méthode de
Cholesky

62 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires Exemple(suite)
par des
méthodes Résolution du Système :
directes

Zouaouia 
BOULENOIR T R.Y = b
A.X = b ⇐⇒ R. R
| {z.X} = b ⇐⇒
Introduction
RT .X = Y.
Y
Les Méthodes
directes
On cherche lasolution Y 
du
système
 RY= b: 
Méthode de
Gauss
2 0 0 y1 30
Décomposition RY = b ←→  0 3 0   y2  =  15 
A en L.U
1 1 4 y3 40
Méthode de  
Cholesky 15
Y = 5 
5

62 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires
par des
méthodes
directes Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X dusystème
 RT X= Y : 

Introduction 2 0 1 x1 15
Les Méthodes RT X = Y ←→  0 3 1   x2  =  5 
directes
0 0 4 x3 5
Méthode de
Gauss

Décomposition
A en L.U

Méthode de
Cholesky

63 / 63
 Méthode de Cholesky R.RT

Résolution
des systèmes
linéaires
par des
méthodes
directes Exemple(suite)
Zouaouia
BOULENOIR On cherche la solution
 X dusystème
 RT X= Y : 

Introduction 2 0 1 x1 15
Les Méthodes RT X = Y ←→  0 3 1   x2  =  5 
directes
0 0 4 x3 5
Méthode de  
Gauss
55/8
Décomposition
A en L.U X=  5/4 
Méthode de 5/4
Cholesky

63 / 63