Chapitre 8

Résolution de systèmes linéaires,

décompositions LU et décomposition
de Cholesky

8.1 Introduction
Soit K “ R ou C et soit n un entier naturel non nul.
Soient une matrice A P Mn pKq et un vecteur colonne B P Mn,1 pKq, et considérons le système
linéaire
pSq AX “ B
de vecteur inconnu X P Mn,1 pRq. L’objectif de ce chapitre est de présenter des méthodes de
résolution d’un tel système qui soient “peu” coûteuses en calculs pour n “grand”.

Supposons tout d’abord que A est une matrice inversible. Dans ce cas, le système pSq possède
une unique solution X “ A´1 B. En particulier, le calcul de l’inverse A´1 de A permet de
résoudre le système pSq. Une méthode
` de ˘calcul de cet inverse consiste à déterminer les vecteurs
´1
colonnes de la matrice A “ Y1 | ¨ ¨ ¨ |Yn à l’aide de la résolution des n systèmes linéaires
$
’
&AY1 “ X1
’
..
’ .
’
%AY
n “X n

de vecteurs inconnus Y1 , . . . , Yn P Mn,1 pRq, où, pour i P t1, . . . , u, Xi désigne le vecteur colonne
de Mn,1 pRq dont toutes les coordonnées sont nulles sauf la ième coordonnée qui est 1 : on a
` ˘ ` ˘
AA´1 “ In ssi A Y1 | ¨ ¨ ¨ |Yn “ X1 | ¨ ¨ ¨ |Xn ssi @i P t1, . . . , nu, AYi “ Xi .

Dans la visée de la résolution du seul système pSq, cette méthode est bien trop coûteuse en
calculs. Il faut donc recourir à d’autres méthodes plus “efficaces”.

143
144 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

Par exemple, lorsque A, en plus d’être inversible, est une matrice triangulaire supérieure,
il existe une méthode permettant de résoudre le système pSq avec un minimum de calculs :
la méthode dite de remontée. Cette méthode consiste à partir de la dernière équation du
système pSq et puis “remonter” les équations une à une pour déterminer successivement les
coordonnées
¨ du vecteur
˛ solution.
¨ ˛ Précisément,
¨ ˛on procède de la manière suivante. Notons
a1 1 ¨ ¨ ¨ a1 n b1 x1
˚ . .. .
.. ‚, B “ ˝ .. ‚ et X “ ˝ ... ‹
‹ ˚ . ‹ ˚
A“˝ ‚, alors
0 an n bn xn
¨ ˛¨ ˛ ¨ ˛
a1 1 ¨ ¨ ¨ a1 n x1 b1
pSq AX “ B ô
˚ . .. .
.. ‚˝ .. ‚ “ ˝ ... ‹
‹ ˚ . ‹ ˚
˝ ‚
0 an n xn bn
$
’
’a1 1 x1 ` . . . ` a1 n xn “ b1
&
.. ..
ô . .
’
’
% a n n x n “ bn
$
’
&a1 1 x1 ` . . . ` a1 n xn “ b1
’
.. ..
ô . .
’
’
% xn “ abnnn
$
’
’ a1 1 x1 ` ... ` a1 n xn “ b1
’
’ ..
& ..
. .
ô
’
’ an´1 n´1 xn´1 ` an´1 n xn “ bn´1
’
’
%
xn “ abnnn
$
’
’ a 1 1 x1 ` . . . ` a 1 n xn “ b1
’
’ ..
& ..
. .
ô
’
’ xn´1 “ an´11 n´1 pbn´1 ´ pan´1 n xn qq
’
’
%
xn “ an1 n bn
$
’
’
’ x1 “ a11 1 pb1 ´ pa1 2 x2 ` . . . ` a1 n xn qq
’
’
’x2
’
& “ a21 2 pb2 ´ pa2 3 x3 ` . . . ` a2 n xn qq
..
ô .
’
’
’
’xn´1 “ a 1 pbn´1 ´ an´1 n xn q
’
’
’
%x
n´1 n´1
bn
n “ an n

(il est ici à noter que, pour¨tout˛ i P t1, . . . , nu, ai i ‰ 0, car A est inversible). On dit que l’on
x1
˚ .. ‹
a obtenu la solution X “ ˝ . ‚ du système pSq par “remontées successives” : on obtient une
xn
8.1. INTRODUCTION 145

coordonnée xi , i P t1, . . . , nu, à partir des coordonnées xj , j ° i déterminées “plus bas”. Les
calculs mis en œuvre dans cette méthode sont en particulier simples et “peu” nombreux.
Exemple 8.1.1. On considère le système

¨ ˛¨ ˛ ¨ ˛ $
1 ´2 5 x 2 &x ´ 2y ` 5z
’ “2
˝
pSq 0 ´4 3 ‚˝ ‚ ˝ ‚
y “ 0 ô ´4y ` 3z “0
’
%
0 0 ´1 z 3 ´z “3
¨ ˛
x
de vecteur inconnu ˝y ‚ P M3,1 pRq. Alors
z
$ $
&x ´ 2y ` 5z
’ “2 &x ´ 2y ` 5z “ 2
’
pSq ´4y ` 3z “0 ô ´4y ` 3z “ 0
’
% ’
%
´z “3 z “ ´3
$
&x ´ 2y ` 5z “ 2
’
ô y “ ´3ˆp´3q
´4 “ ´ 94
’
%
z “ ´3
$ ` 9˘ 25
&x “ 2 ` 2 ˆ ´ 4 ´ 5 ˆ p´3q “
’ 2
ô y “ ´ 94
’
%
z “ ´3

Remarque 8.1.2. On peut adapter la méthode de remontée décrite ci-dessus dans le cas où A
est une matrice triangulaire supérieure non inversible (i.e. au moins un coefficient diagonal de
A est nul). Considérons par exemple les deux systèmes suivants.
¨ ˛
x
Soit ˝y ‚ P M3,1 pRq. Alors le système
z

¨ ˛¨ ˛ ¨ ˛ $
3 7 0 x 1 &3x ` 7y
’ “1
˝0 0 2 ‚˝y ‚ “ ˝ 7 ‚ ô 2z “ 7
’
%
0 0 ´5 z ´2 ´5z “ ´2
$
&3x ` 7y
’ “1
ô 2z “ 7
’
%
z “ 52
$
&3x ` 7y
’ “1
ô 0 “ 7 ´ 45
’
%
z “ 25
146 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

n’a pas de solution, et le système

¨ ˛¨ ˛ ¨ ˛ $
1 ´2 3 x 5 &x ´ 2y ` 3z “ 5
’
˝0 4 5 ‚ ˝ ‚ ˝
y “ 1 ‚ ô 4y ` 5z “ 1
’
%
0 0 0 z 0 0 “0
$
&x ´ 2y ` 3z “ 5
’
ô y “ 1´5z
4
’
%
0 “0
# ` ˘
x “ 5 ` 2 1´5z ´ 3z “ 11´11z
ô 1´5z
4 2
y “ 4
a pour ensemble de solutions
$ ¨ 11´11z ˛ ¨ 11 ˛ ¨ ´11 ˛ ˇ ,
& ˇ .
2 2 2 ˇ
˝ 1´5z ‚ “ ˝ 1 ‚` z ˝ ´ 5 ‚ ˇ zPR .
% 4 4 4 ˇ -
z 0 1 ˇ

Si la matrice A est triangulaire inférieure, il existe une méthode dite de descente, analogue
de la méthode de remontée pour les systèmes triangulaires supérieurs.
¨ ˛ On illustre la méthode
x
de descente avec le système triangulaire inférieur suivant : si ˝y ‚ P M3,1 pRq, alors
z
¨ ˛¨ ˛ ¨ ˛ $
2 0 0 x 3 ’
& 2x “3
˝´1 7 0‚˝y ‚ “ ˝ 2 ‚ ô ´x ` 7y “2
’
%
1 3 4 z ´1 x ` 3y ` 4z “ ´1
$
’
&x “ 32
ô ´x ` 7y “2
’
%
x ` 3y ` 4z “ ´1
$
’
&x “ 32
` ˘
ô y “ 17 2 ` 32 “ 12
’
%
x ` 3y ` 4z “ ´1
$
3
&x “ 2
’
ô y “ 12
’
% ` ˘
z “ 14 ´1 ´ 32 ´ 3 ˆ 12 “ ´1
Les méthodes de résolution des systèmes linéaires que nous allons présenter dans ce chapitre
vont consister en des “factorisations matricielles” permettant de se ramener à des systèmes
triangulaires, systèmes triangulaires que l’on résout ensuite à l’aide des méthodes de remontée
et/ou de descente décrites plus haut.
Nous allons étudier une méthode qui permet de ramener la résolution du système pSq à la
résolution d’un système triangulaire supérieur.
8.2. MÉTHODE DU PIVOT DE GAUSS 147

8.2 Méthode du pivot de Gauss pour la résolution de systèmes

linéaires
Considérons le système pSq AX “ B comme dans l’introduction, avec A P Mn pRq quel-
conque. Une première méthode de résolution de ce système consiste à lui appliquer l’algorithme
du pivot de Gauss : en utilisant des “pivots”, on effectue des opérations sur les lignes de A et
sur les coordonnées du vecteur colonne B (les mêmes), de façon à se ramener à un système
triangulaire supérieur, pour lequel on peut alors employer la méthode de remontée.

¨ On introduit
˛ cette méthode avec l’exemple suivant. On
¨ suppose
˛ que A est la matrice
5 2 1 12
˝ 5 ´6 2‚ de M3 pRq et que B est le vecteur colonne ˝´1‚ de M3,1 pRq. Alors, si X “
´4 2 1 3
¨ ˛
x
˝y ‚ P M3,1 pRq,
z
$ ¨ ˛¨ ˛ ¨ ˛
& 5x ` 2y ` z
’ “ 12 5 2 1 x 12
pSq AX “ B ô 5x ´ 6y ` 2z “ ´1 ô ˝ 5 ´6 2‚˝y ‚ “ ˝´1‚
’
%
´4x ` 2y ` z “3 ´4 2 1 z 3

$ ¨ ˛¨ ˛ ¨ ˛
& 5x ` 2y ` z
’ “ 12 5 2 1 x 12
ô ´8y ` z “ ´13 ô ˝0 ´8 1 ‚˝y ‚ “ ˝´13‚
L2 –L2 ´L1 , L3 –L3 ` 54 L1 ’
% 18 9
“ 63 0 18 9
z 63
5 y ` 5z 5 5 5 5

$ ¨ ˛¨ ˛ ¨ ˛
& 5x ` 2y ` z
’ “ 12 5 2 1 x 12
ô ´8y ` z “ ´13 ô ˝0 ´8 1 ‚˝y ‚ “ ˝´13‚
L3 –L3 ` 18 1
L ’
%
5 8 2 9
“ 27 0 0 94 z 27
4z 4 4

Ce dernier système étant triangulaire supérieure, on peut le résoudre par remontée et on a

finalement $
1 1
&x “ 5 p12 ´ p2y ` zqq “ 5 p12 ´ p2 ˆ 2 ` 3qq “ 1
’
pSq ô y “ ´ 18 p´13 ´ zq “ ´ 18 p´13 ´ 3q “ 2
’
%
z “ 49 ˆ 27 4 “3
¨ ˛ ¨ ˛
x 1
et le système pSq possède donc une unique solution ˝y ‚ “ ˝2‚.
z 3
Les opérations sur les lignes du système effectuées ci-dessus à chaque étape de l’algorithme
du pivot de Gauss reviennent à multiplier à gauche la matrice A et le vecteur B par certaines
matrices particulières, appelées matrices d’élimination :
148 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

Définition 8.2.1. On appelle matrice d’élimination toute matrice de la forme

k
¨ Ó ˛
1
˚ .. ‹
˚ . ‹
˚ ‹
˚ 1 ‹ –k
˚ ‹
˚ ↵ ‹
˚ k`1 ‹
˚ .. .. ‹
˝ . . ‚
↵n 1

(où tous les coefficients non indiqués sont nuls) avec k P t1, . . . , nu et ↵k`1 , . . . , ↵n P K. La
matrice ci-dessus est notée Ek p↵k`1 , . . . , ↵n q.

Reprenons notre matrice A quelconque de Mn pKq et notons L1 , . . . , Ln ses lignes (dans

l’ordre). Alors :

Lemme 8.2.2. Soient k P t1, . . . , nu et ↵k`1 , . . . , ↵n P K. La matrice Ek p↵k`1 , . . . , ↵n qA est

la matrice obtenue à partir de la matrice A en ajoutant, pour tout k P tl ` 1, . . . , nu, ↵l Lk à la
ligne Ll .

Démonstration. Soit l P tk ` 1, . . . , nu alors, pour tout j P t1, . . . , nu, le coefficient situé à la

ligne l et la colonne j de la matrice Ek p↵k`1 , . . . , ↵n qA est ↵l ak j ` al j .

Dans l’exemple ci-dessus, la première étape de l’algorithme

¨ consistait
˛ à multiplier à gauche
` ˘ 1 0 0
A et B par la matrice d’élimination E1 ´1, 45 “ ˝´1 1 0‚, la deuxième à multiplier à
4
0 1
` ˘ ` ˘ 5 `9˘
gauche la matrice E1 ´1, 5 A et le vecteur E1 ´1, 5 B par la matrice d’élimination E2 20
4 4
“
¨ ˛
1 0 0
˝0 1 0‚. Autrement dit, pour passer du système initial pSq au système triangulaire de la
9
0 20 1
fin de l’algorithme, nous avons multiplier à gauche la matrice A et le vecteur B par la matrice
¨ ˛ ¨ ˛
ˆ ˙ ˆ ˙ ˆ ˙ 1 0 0 1 0 0
9 4 9 ˝
M :“ E2 E1 ´1, “ E2 ´1 1 0‚ “ ˝´1 1 0‚
20 5 20 4 7 9
5 0 1 20 20 1

Remarque 8.2.3. • Pour k P t1, . . . , nu et ↵k`1 , . . . , ↵n P K, la matrice d’élimination Ek p↵k`1 , . . . , ↵n q

est inversible d’inverse Ek p´↵k`1 , . . . , ´↵n q.

• Pour k P t1, . . . , nu et ↵k`1 , . . . , ↵n P K, det pEk p↵k`1 , . . . , ↵n qAq “ 1.

• La matrice identité In est une matrice d’élimination : In “ E1 p0, . . . , 0q.

8.2. MÉTHODE DU PIVOT DE GAUSS 149

Lorsque l’on applique l’algorithme du pivot de Gauss pour résoudre un système linéaire, on
peut également être amené à effectuer un échange de lignes pour “déplacer” un pivot à la “bonne
place”. Par exemple, dans le système
¨ ˛¨ ˛ ¨ ˛
0 1 1 x ´1
˝1 0 1‚˝y ‚ “ ˝ 0 ‚
1 1 1 z 5
le coefficient situé à la ligne 1 et la colonne 1 de la matrice est nulle et on échange alors, par
exemple, les deux premières lignes de la matrice, afin de se ramener au système équivalent
¨ ˛¨ ˛ ¨ ˛
1 0 1 x 0
˝0 1 1‚˝y ‚ “ ˝´1‚
1 1 1 z 5
où le coefficient non nul situé à la ligne 1 et la colonne 1 peut être utilisé comme premier pivot.
Les échanges de deux lignes ainsi appliqués au cours de l’algorithme du pivot de Gauss
correspondent à des multiplications à gauche par des matrices dites de transposition :
Définition 8.2.4. On appelle matrice de transposition toute matrice obtenue à partir de la
matrice identité In en échangeant deux lignes. Pour i, j P t1, . . . , nu, la matrice de transposition
obtenue en échangeant les lignes i et j de In est notée Ti,j .
Lemme 8.2.5. Soient i, j P t1, . . . , nu. La matrice Ti,j A est la matrice obtenue à partir de la
matrice A en échangeant les lignes i et j de A.
Démonstration. Soit k, l P t1, . . . , nu. Si k R ti, ju, le coefficient situé à la ligne k et la colonne
n
ÿ
l de la matrice Ti,j A est k,m am l “ ak l . Le coefficient situé à la ligne i et la colonne l de
m“1
la matrice Ti,j A, quant à lui, est aj l . Enfin, le coefficient situé à la ligne j et la colonne l de la
matrice Ti,j A est lui ai l .

Dans l’exemple considéré plus haut, on a¨multiplié˛à gauche la matrice et le vecteur consi-
0 1 0
dérés par la matrice de transposition T1,2 “ ˝1 0 0‚.
0 0 1
Remarque 8.2.6. Soient i, j P t1, . . . , nu. On a
• Ti,j “ Tj,i ,
• la matrice Ti,j est inversible et l’inverse de Ti,j est Ti,j elle-même,
• det pTi,j q “ ´1.
Nous allons à présent montrer que la méthode du pivot de Gauss pour la résolution de
systèmes linéaires fonctionne toujours, autrement dit qu’il est toujours possible, à partir d’un
système pSq AX “ B quelconque, de se ramener à un système triangulaire supérieur à l’aide
d’opérations élémentaires sur les lignes, i.e. à l’aide de produits à gauche par des matrices
d’éliminations et de transpositions :
150 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

Théorème 8.2.7 (Méthode du pivot de Gauss). Il existe une matrice M P GLn pKq, produit
de matrices d’éliminations et de transpositions, telle que M A soit une matrice triangulaire
supérieure.

Remarque 8.2.8. Si M est une telle matrice alors, en particulier, le système pSq AX “ B est
équivalent au système M AX “ M B, qui est triangulaire supérieur.

Démonstration du théorème 8.2.7. On montre le résultat par récurrence sur n. Précisément, on

montre que pour tout n P Nzt0u, pour tout A P Mn pKq, il existe une matrice M P GLn pKq, pro-
duit de matrices d’éliminations et de transpositions, telle que M A est une matrice triangulaire
supérieure.

Le résultat est vrai pour n “ 1 car toute matrice carrée de taille 1 est en particulier trian-
gulaire supérieure.

Supposons à présent la propriété vérifiée au rang n ´ 1 pour n P Nzt0, 1u fixé et reprenons

notre matrice quelconque A de Mn pKq.
Si la première colonne de A est nulle, A est de la forme
¨ ˛
0 ‹ ¨¨¨ ‹
˚0 ‹
˚ ‹
˚ .. ‹
˝. B ‚
0

où B P Mn´1 pKq : d’après l’hypothèse de récurrence, il existe alors une matrice N P GLn´1 pKq,
produit de matrices N1 , . . . , Nm où m P N et, pour tout s P t1, . . . , mu, Ns est une matrice
d’élimination ou une matrice de transposition de Mn´1 pKq, telle que N B soit une matrice
triangulaire supérieure de Mn´1 pKq. Si l’on note alors
¨ ˛
1 0 ¨¨¨ 0
˚0 ‹
˚ ‹
M :“ ˚ . ‹ P GLn pKq.
˝ .. N ‚
0

et, pour tout s P t1, . . . , mu,

¨ ˛
1 0 ¨¨¨ 0
˚0 ‹
˚ ‹
Ms :“ ˚ . ‹ P GLn pKq
˝ .. Ns ‚
0
m
π
on a M “ Ms . De plus, pour tout s P t1, . . . , mu, si Ns est une matrice d’élimination, resp.
s“1
de transition, de Mn´1 pKq, alors Ms est une matrice d’élimination, resp. de transposition, de
8.3. LA DÉCOMPOSITION LU 151

Mn pKq. Enfin, la matrice

¨ ˛¨ ˛ ¨ ˛
1 0 ¨¨¨ 0 0 ‹ ¨¨¨ ‹ 0 ‹ ¨¨¨ ‹
˚0 ‹ ˚0 ‹ ˚0 ‹
˚ ‹˚ ‹ ˚ ‹
MA “ ˚. ‹ ˚ .. ‹ “ ˚ .. ‹
˝ .. N ‚˝ . B ‚ ˝. NB ‚
0 0 0
est triangulaire supérieure.
Supposons maintenant que la première colonne de A soit non nulle, et notons i0 le plus petit
indice i P t1, . . . , nu tel que ai 1 ‰ 0. Si i0 ‰ 1, on multiplie tout d’abord à gauche la matrice
A par la matrice de transposition Ti0 ,1 (afin d’échanger les lignes i0 et 1 de A) et´on considère
¯
alors la matrice A1 :“ Ti0 ,1 A. Si i0 “ 1, on pose A1 :“ A. Ainsi, si on note A1 “ a1i j ,
1§i,j§n
on a dans tous les cas 1
a´ ‰ 0 et on peut¯alors multiplier, à gauche, la matrice A1 par la matrice
11
a1 a1
d’élimination E :“ E1 ´ a21 1 , . . . , ´ an1 1 afin d’éliminer les autres coefficients de la première
11 11
colonne de A1 : on a ¨ 1 ˛
a1 1 ‹ ¨ ¨ ¨ ‹
˚ 0 ‹
˚ ‹
EA1 “ ˚ . ‹
˝ .. B ‚
0
où B P Mn´1 pKq. On applique ensuite l’hypothèse de récurrence à B comme dans le cas précé-
dent : reprenant les mêmes notations, le produit
¨ ˛¨ 1 ˛ ¨ 1 ˛
1 0 ¨¨¨ 0 a1 1 ‹ ¨ ¨ ¨ ‹ a1 1 ‹ ¨ ¨ ¨ ‹
˚0 ‹˚ 0 ‹ ˚ 0 ‹
˚ ‹˚ ‹ ˚ ‹
M EA1 “ ˚ . ‹ ˚ .. ‹ “ ˚ .. ‹
˝ .. N ‚ ˝ . B ‚ ˝ . NB ‚
0 0 0
est une matrice triangulaire supérieure, et la matrice M E Ti0 ,1 , resp. M E, est bien une matrice
inversible produit de matrices d’éliminations et de transpositions.

8.3 La décomposition LU
La décomposition dite LU consiste en la “factorisation” de matrices vérifiant une certaine
condition de “régularité” en le produit d’une matrice triangulaire inférieure (L pour “Lower”)
par une matrice triangulaire supérieure (U pour “Upper”). Cela permet de ramener la résolution
de systèmes linéaires mettant en jeu ces matrices particulières à la résolution de deux systèmes
triangulaires.
Précisément, la décomposition LU existe pour les matrices dont toutes les sous-matrices
principales sont inversibles :
Définition 8.3.1. Soit A P Mn pKq et soit i P t1, . . . , nu. La sous-matrice principale de taille i
de A est la sous-matrice de A obtenue en en supprimant les n ´ i dernières lignes et n ´ i
dernières colonnes. On appelle également mineur principal d’ordre i de A le déterminant de la
sous-matrice principale de taille i de A.
152 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES
¨ ˛
5 2 1 ˆ ˙
` ˘ 5 2
Exemple 8.3.2. Les sous-matrices principales de la matrice ˝ ‚
5 ´6 2 sont 5 ,
5 ´6
´4 2 1
¨ ˛
5 2 1
et ˝ 5 ´6 2‚, et les mineurs principaux de A sont donc 5, ´40 et ´90.
´4 2 1
Soit A P Mn pKq.

Théorème 8.3.3 (Décomposition LU ). On suppose que tous les mineurs principaux de A sont
non nuls (i.e. toutes les sous-matrices principales de A sont inversibles). Alors il existe des
matrices L et U de GLn pKq uniques telles que

• L est une matrice triangulaire inférieure dont tous les coefficients diagonaux sont égaux
à 1,

• U est une matrice triangulaire supérieure,

• A “ LU .

Remarque 8.3.4. Si tous les mineurs principaux de la matrice A sont non nuls, alors A est en par-
ticulier inversible (car la sous-matrice principale d’ordre n de A est A elle-même).
ˆ La ˙réciproque
0 1
est fausse : par exemple, le mineur principal d’ordre 1 de la matrice inversible P M2 pRq
1 0
est égal à 0.
La démonstration de l’existence de la décomposition LU va consister à appliquer l’algorithme
du pivot de Gauss. Dans la preuve du théorème 8.3.3, nous aurons également besoin du lemme
suivant :

Lemme 8.3.5. Supposons que tous les mineurs principaux de A sont non nuls, et soit E P
Mn pKq une matrice d’élimination. Alors tous les mineurs principaux de la matrice produit EA
sont non nuls.

Démonstration. Soit i P t1, . . . , nu. Notons Ai la sous-matrice principale de taille i de A. Alors

ˆ ˙
Ai B
A“
C D

avec B P Mi,n´i pKq, C P Mn´i,i pKq et D P Mn´i pKq. Quant à la matrice d’élimination E, elle
est de la forme ˆ 1 ˙
E 0i,n´i
C1 D1
où E 1 P Mi pKq et D1 P Mn´i pKq sont également des matrices d’éliminations, et C 1 P Mn´i,i pKq.
On a alors
ˆ 1 ˙ˆ ˙ ˆ 1 ˙ ˆ ˙
E 0i,n´i Ai B E Ai ` 0i,n´i C E 1 B ` 0i,n´i D E 1 Ai E1B
EA “ “ “
C1 D1 C D C 1 Ai ` D 1 C C 1 B ` D1 D C 1 Ai ` D 1 C C 1 B ` D 1 D
8.3. LA DÉCOMPOSITION LU 153

et la matrice principale de taille i de EA est donc la matrice E 1 Ai . Or

detpE 1 Ai q “ detpE 1 qdetpAi q “ detpAi q ‰ 0.

Démonstration du théorème 8.3.3. On montre tout d’abord l’existence de la décomposition LU

de A, par récurrence sur n : on montre que pour tout n P Nzt0u, toute matrice A P Mn pKq
dont les mineurs principaux sont tous non nuls admet une décomposition A “ LU telle que
L P GLn pKq est une matrice triangulaire inférieure dont tous les coefficients diagonaux sont
égaux à 1, U P GLn pKq est une matrice triangulaire supérieure et A “ LU .
` ˘ ` ˘ ` ˘` ˘
Pour n “ 1, `si ˘ a P M1 pKq est inversible (i.e. a ‰ 0), alors a “ 1 a est une décompo-
sition LU pour a .

Maintenant, supposons la propriété vérifiée au rang n´1 pour n P Nzt0, 1u fixé, et reprenons
notre matrice A P Mn pKq dont tous les mineurs principaux sont supposés non nuls.
Notons A “ pai j q1§i,j§n . On applique la première étape de l’algorithme du pivot de Gauss
à A en choisissant le coefficient a1 1 comme
´ pivot : a1 1 est¯le mineur principal d’ordre 1 de A et
est donc non nul. Si l’on note E1 :“ E1 ´ aa21 11 , . . . , ´ aan1 11 , on a alors
¨ ˛
a1 1 a1 2 ¨ ¨ ¨ a1 n
˚ 0 ‹
˚ ‹
E1 A “ ˚ . ‹
˝ .. A1 ‚
0

où A1 P Mn´1 pKq. Soit i P t1, . . . , n ´ 1u et notons A1i la matrice principale d’ordre i de A1 et

pE1 Aqi`1 la matrice principale d’ordre i ` 1 de E1 A. On a
¨ ˛
a1 1 a1 2 ¨ ¨ ¨ a1 i`1
˚ 0 ‹
˚ ‹
pE1 Aqi`1 “ ˚ . ‹
˝ .. A 1
i
‚
0

et, d’après le lemme 8.3.5, det ppE1 Aqi`1 q ‰ 0. Or det ppE1 Aqi`1 q “ a1 1 det pA1i q donc det pA1i q ‰ 0.
On a ainsi montré que tous les mineurs principaux de la matrice A1 de Mn´1 pKq étaient non
nuls. On peut appliquer l’hypothèse de récurrence l’hypothèse de récurrence à A1 : il existe une
matrice triangulaire inférieure L1 P GLn´1 pKq de coefficients diagonaux tous égaux à 1 et une
matrice triangulaire supérieure U 1 P GLn´1 pKq telles que A1 “ L1 U 1 . On a alors
¨ ˛ ¨ ˛¨ ˛
a1 1 a1 2 ¨ ¨ ¨ a1 n 1 0 ¨¨¨ 0 a1 1 a1 2 ¨ ¨ ¨ a1 n
˚ 0 ‹ ˚0 ‹˚ 0 ‹
˚ ‹ ˚ ‹˚ ‹
E1 A “ ˚ . ‹ “ ˚. ‹ ˚ . ‹.
˝ .. LU1 1 ‚ ˝. . L 1 ‚˝ . . U 1 ‚
0 0 0
154 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

et on pose
¨ ˛ ¨ ˛ ¨ ˛
1 0 ¨¨¨ 0 1 0 ¨¨¨ 0 a1 1 a1 2 ¨ ¨ ¨ a1 n
˚0 ‹ ˆ ˙˚ ‹ ˚ 0 ‹
˚ ‹ a2 1 an 1 ˚0 ‹ ˚ ‹
L :“ pE1 q´1 ˚ . ‹ “ E1 ,..., ˚. ‹ et U :“ ˚ .. ‹
˝ .. L1 ‚ a1 1 a1 1 ˝ .. L1 ‚ ˝ . U1 ‚
0 0 0

La matrice L est une matrice triangulaire inférieure de GLn pKq dont tous les coefficients dia-
gonaux sont égaux à 1 (car L1 P Mn´1 pKq et pE1 q´1 P Mn pKq sont des matrices triangulaires
inférieures de coefficients diagonaux tous égaux à 1) et U est une matrice triangulaire supérieure
inversible de Mn pKq (car U 1 est une matrice triangulaire supérieure inversible de Mn´1 pKq et
a1 1 ‰ 0).

On montre enfin l’unicité de la décomposition LU de A : soit L r P GLn pKq une matrice

triangulaire inférieure dont tous les coefficients diagonaux sont égaux à 1 et soit U r P GLn pKq
une matrice triangulaire supérieure telles que A “ L rU
r . On montre que L r “ L et Ur “ U.
r r r ´1 r ´1 r ´1
On a LU “ LU et donc L L “ U U . Or le produit L L est une matrice triangulaire
inférieure dont tous les coefficients diagonaux sont égaux à 1 (car L, L r ´1 sont toutes
r et donc L
r U ´1 est une matrice triangulaire supérieure (car U
de telles matrices) et le produit U r , U et U ´1
r ´1 r ´1
sont toutes de telles matrices). Ainsi, nécessairement, L L “ U U “ In , et donc L “ L r et
U “U r.
¨ ˛
5 2 1
Exemple 8.3.6. On calcule la décomposition LU de la matrice A :“ ˝ 5 ´6 2‚ P M3 pRq
´4 2 1
dont tous les mineurs principaux sont¨ non nuls
˛ (exemple 8.3.2). ¨ ˛
1 0 0 d e f
Nous savons qu’il existe L :“ ˝a 1 0‚ P GL3 pRq et U :“ ˝0 g h‚ P GL3 pRq telles
b c 1 0 0 k
que ¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 d e f
A “ ˝ 5 ´6 2‚ “ ˝a 1 0‚˝0 g h‚.
´4 2 1 b c 1 0 0 k
On a alors
1. d “ 5, e “ 2, f “ 1, ainsi
¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 5 2 1
˝ 5 ´6 2‚ “ ˝a 1 0‚˝0 g h‚
´4 2 1 b c 1 0 0 k

2. 5 “ a ˆ 5 donc a “ 1, et ´4 “ b ˆ 5 donc b “ ´ 45 , ainsi

¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 5 2 1
˝ 5 ´6 2‚ “ ˝ 1 1 0‚˝0 g h‚
´4 2 1 ´ 45 c 1 0 0 k
8.3. LA DÉCOMPOSITION LU 155

3. ´6 “ 1 ˆ 2 ` 1 ˆ g donc g “ ´8, et 2 “ 1 ˆ 1 ` 1 ˆ h donc h “ 1, ainsi

¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 5 2 1
˝ 5 ´6 2‚ “ ˝ 1 1 0‚˝0 ´8 1‚
´4 2 1 ´ 45 c 1 0 0 k
` ˘
4. 2 “ ´ 45 ˆ 2 ` c ˆ p´8q donc c “ ´ 20
9
, ainsi
¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 5 2 1
˝ 5 ´6 2‚ “ ˝ 1 1 0‚˝0 ´8 1‚
4 9
´4 2 1 ´ 5 ´ 20 1 0 0 k
` ˘ ` 9˘
5. 1 “ ´ 45 ˆ 1 ` ´ 20 ˆ 1 ` 1 ˆ k donc k “ 94 , ainsi
¨ ˛ ¨ ˛¨ ˛
5 2 1 1 0 0 5 2 1
A “ ˝ 5 ´6 2‚ “ ˝ 1 1 0‚˝0 ´8 1 ‚
4 9
´4 2 1 ´ 5 ´ 20 1 0 0 94

et cette dernière expression est la décomposition LU de A.

Supposons que tous les mineurs principaux de la matrice A soient non nuls. Comme illustré
par l’exemple ci-dessus, le calcul de la décomposition LU de A est peu coûteux en calculs. De
plus, si B est un vecteur colonne de Mn,1 pRq, cette factorisation nous permet de résoudre le
système pSq AX “ B, de vecteur inconnu X P Mn,1 pRq, de manière particulièrement efficace.
En effet,
AX “ B ssi LpU Xq “ B.
Ainsi, X P Mn,1 pRq est l’unique solution du système pSq (unique car A est inversible) si et
seulement si le vecteur U X est l’unique solution Y P Mn,1 pRq du système LY “ B (L est
inversible). Résoudre le système pSq revient donc à résoudre successivement le système LY “
B puis le système U X “ Y (U est également inversible), qui sont tous deux des systèmes
triangulaires que l’on peut donc résoudre à l’aide des méthodes de remontée et de descente.
¨ ˛
5 2 1
Exemple 8.3.7. On reprend la matrice A :“ ˝ 5 ´6 2‚ P M3 pRq de l’exemple 8.3.6 précédent
´4 2 1
et on résout le système ¨ ˛
1
AX “ 2‚ ˝
3
¨ ˛
x
de vecteur inconnu X “ ˝y ‚ P M3,1 pRq.
z
La décomposition LU de A est
¨ ˛¨ ˛
1 0 0 5 2 1
A“˝ 1 1 0‚˝0 ´8 1 ‚ :
4 9
´ 5 ´ 20 1 0 0 94
156 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES
¨ ˛ ¨ ˛
1 0 0 5 2 1
notons L :“ ˝ 1 1 0‚ et U :“ ˝0 ´8 1 ‚. Pour résoudre le système AX “ B, on
´ 45 9
´ 20 1 0 0 94
¨ ˛ ¨ ˛
1 a
commence par résoudre le système LY “ ˝2‚ de vecteur inconnu Y “ ˝ b ‚ P M3,1 pRq : on a
3 c
¨ ˛ ¨ ˛¨ ˛ ¨ ˛
1 1 0 0 a 1
LY “ ˝2‚ ô ˝ 1 1 0‚˝ b ‚ “ ˝2‚
3 ´ 45 ´ 20
9
1 c 3
$
’
&a “1
ô a`b “2
’
% 4 9
´ 5 a ´ 20 b ` c “ 3
$
’
&a “1
ô b “2´1“1
’
% 4 9
´ 5 a ´ 20 b ` c “ 3
$
&a “ 1
’
ô b “1
’
%
c “ 3 ` 45 ˆ 1 ` 20 9
ˆ 1 “ 17
4
¨ ˛
1
Puis on résout le système U X “ ˝ 1 ‚ : on a
17
4
¨ ˛ ¨ ˛¨ ˛ ¨ ˛
1 5 2 1 x 1
˝
UX “ 1 ‚ ô ˝0 ´8 1 ‚ ˝ y “ 1‚
‚ ˝
17 9 17
4 0 0 4 z 4
$
&5x ` 2y ` z “ 1
’
ô ´8y ` z “ 1
’
% 9 17
4z “ 4
$
&5x ` 2y ` z “ 1
’
ô ´8y ` z “ 1
’
%
z “ 17 9
$
&5x ` 2y ` z “ 1 `
’
˘ 1
ô y “ ´ 18 1 ´ 17 9 “9
’
% 17
z “ 9
$ ` ˘
1 1 17 10 2
&x “ 5 1 ´ 2 ˆ 9 ´ 9 “ ´ 45 “ ´ 9
’
ô y “ 19
’
%
z “ 179
8.4. LA DÉCOMPOSITION P LU 157
¨ ˛ ¨ ˛
´2 1
1˝
et le vecteur X “ 9 1 est l’unique solution du système AX “ 2‚.
‚ ˝
17 3

8.4 La décomposition P LU
Une généralisation de la décomposition LU existe pour toute matrice de Mn pKq. Cette
décomposition fait apparaître, en plus d’une matrice triangulaire inférieure de coefficients dia-
gonaux tous égaux à 1 et d’une matrice triangulaire supérieure, une matrice dite de permutation,
due aux éventuels échanges de lignes dans l’application de l’algorithme du pivot de Gauss.

Définition 8.4.1. Une matrice de permutation de Mn pKq est une matrice dans laquelle chaque
ligne et chaque colonne ne contient qu’un seul coefficient non nul, égal à 1.

Remarque 8.4.2. • Une matrice de permutation est obtenue par permutation (au sens du
groupe symétrique) des lignes de la matrice identité In i.e. en appliquant une permutation
du groupe symétrique Sn à l’ensemble des lignes de la matrice In . Il est à noter que, une
permutation de Sn étant une composition de transpositions et une matrice de transposi-
tion (définition 8.2.4) étant obtenue en appliquant une transposition (au sens du groupe
symétrique) à l’ensemble des lignes de la matrice In , une matrice de permutation est un
produit de matrices de transpositions.

• Si P P Mn pKq est une matrice de permutation obtenue en appliquant une permutation

P Sn aux lignes de la matrice identité In , detpP q “ ✏p q où ✏p q désigne la signature
de la permutation . En particulier, P est inversible.

• P P Mn pKq est une matrice de permutation obtenue en appliquant une permutation

P Sn aux lignes de In , et si M P Mn pKq, la matrice produit P M est la matrice obtenue
à partir de M en appliquant la même permutation aux lignes de M .
Considérons donc maintenant une matrice A quelconque de Mn pKq. On a le résultat de
décomposition/factorisation suivant :

Théorème 8.4.3 (Décomposition P LU ). Il existe des matrices P , L et U de Mn pKq telles que

• P est une matrice de permutation,

• L est une matrice triangulaire inférieure dont tous les coefficients diagonaux sont égaux
à 1,

• U est une matrice triangulaire supérieure,

• A “ P LU .

Dans la preuve de ce théorème, on utilisera, comme dans la preuve du théorème 8.3.3 de

décomposition LU , l’algorithme du pivot de Gauss mais en faisant, ici, également intervenir des
échanges de lignes. On emploiera également le lemme suivant :
158 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

Lemme 8.4.4. Soient i, j, k P t1, . . . , nu tels que k † i † j. Soient ↵k`1 , . . . , ↵n P K et

considérons les matrices de transposition Ti,j et d’élimination Ek p↵k`1 , . . . , ↵n q de Mn pKq.
Alors
Ek p↵k`1 , . . . , ↵n q Ti,j “ Ti,j Ek p↵k`1 , . . . , ↵j , . . . , ↵i , . . . , ↵n q
Démonstration. Commençons par remarquer que multiplier à droite une matrice M P Mn pKq
par une matrice de transposition Tr,s , r, s P t1, . . . , nu, r ‰ s, échange les colonnes r et s de la
matrice M .
Considérons ensuite la matrice Ek p↵k`1 , . . . , ↵n q. Il s’agit de la matrice

k
¨ Ó ˛
1
˚ .. ‹
˚ . ‹
˚ ‹
˚ 1 ‹ –k
˚ ‹
˚ ↵k`1 ‹
˚ ‹
˚ .. .. ‹
˝ . . ‚
↵n 1

La matrice Ek p↵k`1 , . . . , ↵n q Ti,j , obtenue en échangeant les colonnes i et j de Ek p↵k`1 , . . . , ↵n q,

est la matrice obtenue en échangeant les lignes i et j de la matrice Ek p↵k`1 , . . . , ↵j , . . . , ↵i , . . . , ↵n q,
i.e. la matrice Ti,j Ek p↵k`1 , . . . , ↵j , . . . , ↵i , . . . , ↵n q (k † i † j).

Démonstration du théorème 8.4.3. Nous allons montrer le résultat suivant, par récurrence sur
n P N : pour tout n P Nzt0u, pour toute matrice A dans Mn pKq, il existe une matrice triangulaire
supérieure U P Mn pKq, il existe r, s P N et des matrices de transposition T1 , . . . , Tr P Mn pKq
ainsi que des matrices d’élimination E1 , . . . , Es P Mn pKq telles que
˜ ¸˜ ¸
π r πs
A“ Ti Ej U :
i“1 j“1
˜ ¸ ˜ ¸
r
π s
π
un tel produit Ti forme une matrice de permutation et le produit Ej forme une
i“1 j“1
matrice triangulaire inférieure de coefficients diagonaux tous égaux à 1.

Le résultat est vrai pour n “ 1 pour la même raison que celle évoquée dans la preuve du
théorème 8.3.3. Supposons donc maintenant le résultat vrai au rang n ´ 1 pour n P Nzt0, 1u
fixé, et considérons notre matrice quelconque A de Mn pKq.
Si la première colonne de A est nulle, A est de la forme
¨ ˛
0 a1 2 ¨ ¨ ¨ a1 n
˚0 ‹
˚ ‹
˚ .. ‹
˝. B ‚
0
8.4. LA DÉCOMPOSITION P LU 159

où B P Mn´1 pKq : d’après l’hypothèse de récurrence, il existe alors une matrice triangulaire
supérieure U 1 P Mn´1 pKq, il existe des entiers naturels r et s, il existe des matrices de trans-
position 1 1 1 1
˜ T1 , .¸. .˜, Tr P M ¸n´1 pKq et des matrices d’élimination E1 , . . . , Es P Mn´1 pKq telles que
πr πs
B“ Ti1 Ej1 U 1 .
i“1 j“1
On pose alors
¨ ˛
0 a1 2 ¨ ¨ ¨ a1 n
˚0 ‹
˚ ‹
U :“ ˚ . ‹ P Mn pKq
˝ .. U1 ‚
0

et, pour tout i P t1, . . . , ru et tout j P t1, . . . , su,

¨ ˛ ¨ ˛
1 0 ¨¨¨ 0 1 0 ¨¨¨ 0
˚0 ‹ ˚0 ‹
˚ ‹ ˚ ‹
Ti :“ ˚ . ‹ et Ej :“ ˚ .. ‹.
˝ .. Ti1 ‚ ˝. Ej1 ‚
0 0

Pour i P t1, . . . , r1 u, la matrice Ti est une matrice de transposition de Mn pKq et, pour j P
t1, . . . , s1 u, la matrice Ej est une matrice d’élimination de Mn pKq. Enfin,
˜ ¸˜ ¸
r
π s
π
A“ Ti Ej U.
i“1 j“1

Si la première colonne de A est non nulle, notons i0 le plus petit indice i P t1, . . . , nu tel
que ai 1 ‰ 0 : si i0 ‰ 1, on commence par multiplier à gauche la matrice A par la matrice de
transposition T :“ Ti0´ 1 1
,1 et¯on considère la matrice A :“ T A, et, si i0 “ 1, on pose A :“ A.
Ainsi, si on note A1 “ a1i j , a11 1 ‰ 0, on peut ensuite multiplier à gauche la matrice A1
1§i,j§n
´ 1 ¯
a a1
par la matrice d’élimination E :“ E1 ´ a21 1 , . . . , ´ an1 1 afin d’éliminer les autres coefficients
11 11
de la première colonne de A1 : on a
¨ 1 ˛
a1 1 a11 2 ¨ ¨ ¨ a11 n
˚ 0 ‹
˚ ‹
EA1 “ ˚ . ‹
˝ .. B ‚
0

où B P Mn´1 pKq. En procédant de la même manière que dans le cas précédent (i.e. en appliquant
l’hypothèse de récurrence à B) et en conservant les mêmes notations, on obtient alors l’égalité
˜ ¸˜ ¸
r
π s
π
EA1 “ Ti Ej U
i“1 j“1
160 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

i.e. ˜ ¸˜ ¸
r
π s
π
A1 “ E ´1 Ti Ej U.
i“1 j“1
´ ´ 1 ¯¯´1 ´ 1 ¯
a a1 a a1
Maintenant, E ´1 “ E1 ´ a21 1 , . . . , ´ an1 1 “ E1 a21 1 , . . . , an1 1 . Comme les matrices de
11 11 11 11
transposition Ti , i P t1, . . . , ru, échangent des lignes d’indices strictement plus grands
˜ que
¸ 1,˜il ¸
πr πr
existe, d’après le lemme 8.4.4, une matrice d’élimination E r P Mn pKq telle que E ´1 Ti “ r
Ti E,
i“1 i“1
et alors ˜ ¸ ˜ ¸
r
π s
π
1 r
A “ Ti E Ej U.
i“1 j“1

Enfin, dans le cas où i0 ‰ 1, T ´1 “ T et donc

˜ ¸ ˜ ¸
πr s
π
A“T Ti Er Ej U.
i“1 j“1

Remarque 8.4.5. Il n’y a pas unicité de la décomposition P LU . Par exemple :

ˆ ˙ ˆ ˙ˆ ˙ ˆ ˙ˆ ˙ˆ ˙
1 1 1 0 1 1 0 1 1 0 2 3
“ I2 “ 1 .
2 3 2 1 0 1 1 0 2 1 0 ´ 12
¨ ˛
0 1 1
Exemple 8.4.6. Considérons la matrice A :“ ˝1 0 1‚ P M3 pRq. On applique l’algorithme du
1 1 1
pivot de Gauss pour déterminer une décomposition P LU de A.
On commence par échanger les deux premières lignes :
¨ ˛
1 0 1
T2,1 A “ ˝0 1 1‚.
1 1 1

Puis on élimine le coefficient non nul de la première colonne de cette dernière matrice :
¨ ˛
1 0 1
E1 p0, ´1q T2,1 A “ ˝0 1 1‚.
0 1 0

Enfin, on utilise le coefficient situé sur la ligne 2 et la colonne 2 de cette dernière matrice comme
pivot et on a : ¨ ˛
1 0 1
E2 p´1q E1 p0, ´1q T2,1 A “ ˝0 1 1 ‚.
0 0 ´1
8.4. LA DÉCOMPOSITION P LU 161
¨ ˛
1 0 1
On pose alors U :“ ˝0 1 1 ‚ (la matrice U P M3 pRq est triangulaire supérieure) et on a :
0 0 ´1

A “ pT2,1 q´1 pE1 p0, ´1qq´1 pE2 p´1qq´1 U

“ T2,1 E1 p0, 1q E2 p1q U.
¨ ˛ ¨ ˛
0 1 0 1 0 0
Si on pose P :“ T2,1 “ ˝1 0 0‚ et L :“ E1 p0, 1q E2 p1q “ ˝0 1 0‚, P est une matrice
0 0 1 1 1 1
de permutation de M3 pRq, L est une matrice triangulaire inférieure de M3 pRq de coefficients
diagonaux tous égaux à 1, et on a :
A “ P L U.

Une décomposition P LU d’une matrice A de Mn pKq permet notamment de résoudre effica-

cement tout système AX “ B de vecteur inconnu X P Mn,1 pKq, où B est un vecteur colonne
de Mn,1 pKq. La résolution d’un tel système revient à la résolution successive des trois systèmes

1. P Z “ B, de vecteur inconnu Z P Mn,1 pKq, système possédant une unique solution Z

rapide à calculer car P est une matrice de permutation (les coordonnées de Z “ P ´1 B
sont obtenues par permutation des coordonnées de B),

2. LY “ Z, de vecteur inconnu Y P Mn,1 pKq, système possédant une unique solution Y (L

est inversible) et résoluble par la méthode de descente (L est triangulaire inférieure),

3. U X “ Y , de vecteur inconnu X P Mn,1 pKq, qui est un système triangulaire supérieur et

donc résoluble par la méthode de remontée.

En effet, si X P Mn,1 pKq,

AX “ B ssi P L U X “ B ssi L U X “ P ´1 B “ Z ssi U X “ L´1 Z “ Y.

Exemple 8.4.7. Reprenons la matrice A de l’exemple précédent 8.4.6. Nous allons ¨

utiliser
˛ la
0
décomposition P LU calculée alors pour déterminer la solution du système AX “ ˝´1‚ de
5
¨ ˛
x
vecteur inconnu X “ ˝y ‚ P M3,1 pRq.
z
¨ ˛ ¨ ˛
0 ↵
On commence par résoudre le système P Z “ ˝´1‚ de vecteur inconnu Z “ ˝ ‚ P
5
162 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES

M3,1 pRq : on a

¨ ˛ ¨ ˛¨ ˛ ¨ ˛
0 0 1 0 ↵ 0
P Z “ ˝´1‚ ô ˝1 0 0‚˝ ‚ “ ˝´1‚
5 0 0 1 5
$
’
& “0
ô ↵ “ ´1
’
%
“5
$
&↵ “ ´1
’
ô “0
’
%
“5

¨ ˛ ¨ ˛
´1 a
Puis on résout le système LY “ ˝ 0 de vecteur inconnu Y “ b ‚ P M3,1 pRq : on a
‚ ˝
5 c

¨ ˛ ¨ ˛¨ ˛ ¨ ˛
´1 1 0 0 a ´1
LY “ ˝ 0 ‚ ô ˝0 1 0‚˝ b ‚ “ ˝ 0 ‚
5 1 1 1 c 5
$
’
&a “ ´1
ô b “0
’
%
a`b`c “5
$
&a “ ´1
’
ô b “0
’
%
c “ 5 ´ p´1q ´ 0 “ 6
8.5. LA DÉCOMPOSITION DE CHOLESKY 163
¨ ˛
´1
Enfin, on résout le système U X “ ˝ 0 ‚ : on a
6

¨ ˛ ¨ ˛¨ ˛ ¨ ˛
´1 1 0 1 x ´1
U X “ ˝ 0 ‚ ô ˝0 1 1 ‚˝y ‚ “ ˝ 0 ‚
6 0 0 ´1 z 6
$
’
&x ` z “ ´1
ô y`z “0
’
%
´z “ 6
$
’
&x ` z “ ´1
ô y`z “0
’
%
z “ ´6
$
’
&x ` z “ ´1
ô y “ ´p´6q “ 6
’
%
z “ ´6
$
&x “ ´1 ´ p´6q “ 5
’
ô y “6
’
%
z “ ´6

¨ ˛ ¨ ˛
5 0
et le vecteur X “ ˝ 6 est l’unique solution du système AX “ ´1‚.
‚ ˝
´6 5

8.5 La décomposition de Cholesky

La décomposition de Cholesky est une factorisation des matrices symétriques définies positives
(définition 5.3.1). Elle est construite à partir de la décomposition LU de ces matrices : les ma-
trices symétriques définies positives vérifient en effet l’hypothèse de “régularité” du théorème
8.3.3.

Proposition 8.5.1. Soit S P Sn pRq une matrice symétrique définie positive. Alors tous les
mineurs principaux de S sont strictement positifs.

Démonstration. Soit i P t1, . . . , nu et notons Si la sous-matrice principale

¨ ˛ de taille$i¨de˛S.,
x1 & 0 /
’ .
r ˚ .. ‹ ˚ .. ‹
Remarquons tout d’abord que Si P Si pRq. Soit maintenant X “ ˝ . ‚ P Mi,1 pRqz ˝ . ‚
’
% /
-
xi 0
164 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES
¨ ˛
x1
˚ .. ‹ $¨ ˛,
˚.‹
˚ ‹
˚ xi ‹ & 0 /
’ .
et notons X :“ ˚ ‹ P Mn,1 pRqz ˝ ... ‚ . On a alors t XA
˚ ‹ ˚ ‹ r iX
r “ t XAX ° 0 et la matrice
0
˚ ‹ ’
% /
-
˚ .. ‹ 0
˝.‚
0
symétrique Si est donc définie positive. En particulier, la matrice Si P Si pRq est diagonalisable
(théorème 5.2.5) et ses valeurs propres sont strictement positives (proposition 5.3.4) : le déter-
minant de Si est alors égal au produit de ses valeurs propres (avec multiplicités) et est donc
strictement positif.

Corollaire 8.5.2. Soit S P Sn pRq une matrice symétrique définie positive. Alors S admet une
décomposition LU . De plus, les coefficients diagonaux de U sont strictement positifs.

Démonstration. D’après la proposition précédente, tous les mineurs principaux de S sont stric-
tement positifs, en particulier non nuls : on peut donc appliquer le¨théorème ˛8.3.3 à la ma-
1 0
˚ .. ‹
trice S qui possède alors une décomposition S “ LU avec L “ ˝ . ‚ P Mn pRq et
‹ 1
¨ ˛
u1 1 ‹
U “˝
˚ . . ‹
‚ P Mn pRq.
.
0 un n
Soit i P t1, . . . , nu et notons
¨ Si , L˛i et Ui les
¨ sous-matrices˛ principales de taille i respectives
1 0 u1 1 ‹
˚ .. ‹ ˚ . .. ‹
de S, L et U : on a Li “ ˝ . ‚, Ui “ ˝ ‚ P Mi pRq et
‹ 1 0 ui i
ˆ ˙ ˆ ˙ ˆ ˙
Si A Li 0i,n´i Ui F
S“ ,L “ ,U “
B C D E 0n´i,i G

avec A, F P Mi,n´i pRq, B, D P Mn´i,i pRq et C, E, G P Mn´i pRq. Alors

ˆ ˙
Li U i Li F
S “ LU “
DUi DF ` EG

i
π
et, en particulier, Si “ Li Ui et donc det pSi q “ det pLi q det pUi q “ uj j . Or det pSi q ° 0 (par
j“1
i
π
la preuve de la proposition précédente) donc uj j ° 0.
j“1
i
π
On a ainsi montré que, pour tout i P t1, . . . , nu, uj j ° 0. En particulier u1 1 ° 0 et, si
j“1
8.5. LA DÉCOMPOSITION DE CHOLESKY 165

i
π
uj j
i
π i´1
π j“1
i P t2, . . . , nu, uj j ° 0 et uj j ° 0 donc, nécessairement, ui i “ i´1
° 0.
π
j“1 j“1
uj j
j“1

Soit S P Sn pRq une matrice symétrique définie positive. Considérons donc la décomposition
LU de S suivant les notations de la preuve précédente. Nous allons utiliser cette factorisation
pour écrire S comme le produit d’une matrice triangulaire inférieure de coefficients diagonaux
strictement positifs et de de sa transposée :

Théorème 8.5.3 (Décomposition de Cholesky). Il existe une unique matrice T P Mn pRq trian-
gulaire inférieure à coefficients diagonaux strictement positifs (en particulier T est inversible)
telle que
S “ T t T.

Démonstration. On considère la décomposition S “ LU de S. D’après le corollaire 8.5.2 ci-

dessus, les coefficients diagonaux u1 1 , . . . , un n de U sont tous strictement positifs et on pose
alors ¨? ˛
u1 1 0
˚ .. ‹
‚ P GLn pRq.
D :“ ˝ .
?
0 un n
Remarquons que l’on a
S “ LU “ LDD´1 U.
¨? ˛ ¨? ˛
u1 1 0 u1 1 ‹
On pose ensuite T :“ LD “ ˝
˚ .. ‹ ˚
‚ et Tr “ D´1 U “ ˝ .. ‹
. . ‚
? ?
‹ un n 0 un n
¨?1 ˛
u1 1 0
´1
(D “ ˝
˚ .. ‹
‚), et on a donc S “ T Tr. Notons que T est une matrice triangulaire
.
0 ?1
un n
inférieure et que ses coefficients diagonaux sont tous strictement positifs.

Nous allons maintenant montrer que Tr “ t T . Comme S est une matrice symétrique, on a

T Tr “ S “ t S “ t Tr t T

et donc, comme la matrice Tr est inversible,

t r´1
T T “ t T Tr´1 .
¨?1 ˛ ¨ ˛
u1 1 ‹ 1 0
˚
A présent, comme Tr´1 “ ˝ .. ‚, on a t Tr´1 T “ ˝ . . . ‚ et t T Tr´1 “
‹ ˚ ‹
.
0 ?1 ‹ 1
un n
166 CHAPITRE 8. RÉSOLUTION DE SYSTÈMES LINÉAIRES
¨ ˛
1 ‹
˚ .. ‹
˝ . ‚, d’où
0 1
t r´1
T T “ t T Tr´1 “ In

et donc Tr “ t T .

Montrons enfin que la décomposition S “ T t T , avec T P Mn pRq triangulaire

¨ inférieure
˛
t1 1 0
à coefficients diagonaux strictement positifs, est unique. Soit donc T 1 “ ˝
˚ .. ‹
‚P
.
‹ tn n
Mn pKq une matrice triangulaire inférieure à coefficients diagonaux strictement positifs tels que
1t 1 que T 1 “ T . Commençons par noter D1 la matrice diagonale inversible
¨ “ T T et montrons
S ˛
t1 1 0
˚
˝ . .. ‹
‚ P Mn pRq. On a
0 tn n

´1
S “ T 1 t T 1 “ T 1 D1 D1 t T 1 :

comme T 1 D1 ´1 P M¨n pKq est une matrice

˛ triangulaire inférieure de coefficients diagonaux tous
1
t1 1 0
1 ´1 ˚ . .. ‹
égaux à 1 (D “˝ ‚) et D1 t T 1 P Mn pKq est une matrice triangulaire supérieure,
1
0
´ ¯` t
˘n n
l’égalité S “ T 1 D1 ´1 1 1
D T est la décomposition LU de S.
t

On obtient ainsi les égalités L “ T 1 D¨ 1 ´1 et U “ D 1 t T 1 i.e. T D ´1 “ T 1 D 1 ´1 (T “ LD) et

˛ ¨2 ˛
u1 1 ‹ t1 1 ‹
D t T “ D1 t T 1 (t T “ D´1 U ). Or D t T “ ˝
˚ .. ‹ ˚
‚ et D1 t T 1 “ ˝ .. ‹
‚ donc,
. .
0 un n 0 2
tn n
? 1
pour tout i P t1, . . . , nu, ti i “ ui i i.e. ti i “ ui i (car ti i ° 0), et donc D “ D. D’où, comme
2

T D´1 “ T 1 D1 ´1 , l’égalité T “ T 1 .

Exemple 8.5.4. Considérons la matrice symétrique

¨ ˛
6 2 ´2
S :“ ˝ 2 6 ´2‚ P S3 pRq.
´2 ´2 10

Son polynôme caractéristique est ˛ ´ Xqp12 ´ Xq donc la matrice symétrique S

“
p6 ´ Xqp4
S¨
a 0 0
est définie positive. On cherche T “ ˝ b c 0 ‚ P M3 pRq triangulaire inférieure de coefficients
d e f
8.5. LA DÉCOMPOSITION DE CHOLESKY 167

diagonaux strictement positifs telle que

¨ ˛¨ ˛
a 0 0 a b d
S “ T t T “ ˝ b c 0 ‚˝0 c e ‚.
d e f 0 0 f

On a alors
?
1. a2 “ 6 donc a “ 6 (car a ° 0),

2. ba “ 2 donc b “ ?2 ,
6

3. da “ ´2 donc d “ ´ ?26 ,
? b
4. b2 ` c2 “ 6 donc c “ 6 ´ b2 “ 16
3 (c ° 0),
b ` ˘ b
5. db ` ec “ ´2 donc e “ 1
c p´2 ´ dbq “ 3
16 ´2 ` 2
3 “ ´ 43 16 ,
3

b
6. d2 ` e2 ` f 2 “ 10 donc f “ 10 ´ 2
3 ´ 1
3 “ 3 (f ° 0).

Ainsi ¨? ˛ ?
6 b0 0 ¨ 6 ?2 ´ ?26
˛
˚ ?2 ‹ b6 b ‹
S“˚
16
0‹ ˚˝ 0 16
´ 43 163 ‚
˝ 6 b3 ‚ 3
´ ?26 ´ 43 3
16 3 0 0 3
est la décomposition de Cholesky de la matrice symétrique définie positive S.
Remarque 8.5.5. • Comme illustré dans l’exemple ci-dessus, le calcul de la décomposition
de Cholesky de S est plus avantageux que le calcul de la décomposition LU de S (il y a
moins de coefficients à déterminer).

• Si B est un vecteur colonne de Mn,1 pRq, la décomposition de Cholesky de la matrice S

permet de résoudre efficacement le système SX “ B de vecteur inconnu X P Mn,1 pRq :
résoudre ce système revient à résoudre successivement les deux systèmes triangulaires
inversibles T Y “ B, de vecteur inconnu Y P Mn,1 pRq, et t T X “ Y .