Chapitre 1

Méthodes directes pour la résolution

des systèmes linéaires

1.1 Introduction
La résolution des systèmes linéaires de grandes tailles est l’un des plus importants
problèmes en analyse numérique. Le but de ce chapitre est d’étudier des méthodes de
résolution numérique d’un linéaire Ax = b, où A est une matrice carrée inversible.
Pour motivation, commençons par citer le problème mécanique classique suivant qui
conduit à la résolution d’un système linéaire.
La déformation y d’une corde élastique, fixée aux bords et soumise à un champ de
force f , peut se traduire par l’équation différentielle suivante

−x′′ (t) = f (t), t ∈ [0, 1]
(1.1)
x(0) = x(1) = 0,
pour f une fonction continue sur [0, 1]. En général, il n’est pas possible d’expliciter la
solution exacte de ce problème. L’idée donc est de chercher une solution approchée xh de
x en prenant une subdivision 0 = t0 ≤ t1 ≤ · · · ≤ tn+1 = 1, avec ti = ih, i = 0, . . . , n + 1
1
et h = . On se limitera à calculer xh (ti ) = xi ≃ x(ti ), pour i = 0, . . . , n + 1 et par
n+1
interpolation par exemple, on peut avoir xh sur tout l’intervalle [0, 1].
Si on suppose que notre solution x est de classe C 2 , alors on a les deux développement
de Taylor suivants :
h2
x(ti+1 ) = x(ti + h) = x(ti ) + x′ (ti )h + x′′ (ti ) + O(h3 ),
2
et
h2
x(ti−1 ) = x(ti − h) = x(ti ) − x′ (ti )h + x′′ (ti ) + O(h3 ).
2
Si on fait la somme de deux égalités on obtient
x(ti + h) − 2x(ti ) + x(ti − h)
x′′ (ti ) = + O(h).
h2
1
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

Si on néglige les termes d’ordre O(h) dans l’expression de la dérivée seconde, le problème
discrétisé pour résoudre notre équation devient
( x − 2x + x
i+1 i i−1
− = f (xi ), i = 1, . . . , n
h2 (1.2)
x0 = xn+1 = 0

qui est équivalent au système linéaire Ah x = bh , où

 
2 −1 0 ··· 0
..     
−1 2 −1 .  x1 f (t1 )

1  .. .. ..  .  . 
Ah = 2 
h  0 . . . 0  x =  ..  et bh =  ..  .
 . xn f (tn )
 ..

−1 2 −1
0 ··· 0 −1 2

La solution approchée est d’autant plus proche de la solution exacte y lorsque n est grand.
On rappele que la solution unique x = (x1 , . . . , xn ) d’un système Ax = b, pour
A = (aij )1≤i,j≤n une matrice inversible et b = (b1 , . . . , bn )T est donnée par les formules de
Cramer suivantes :
det Ai
xi = , i = 1, . . . , n,
det A
où det désigne le déterminant et Ai est la matrice d’ordre n obtenue à partir de A en
remplaçant sa colonne i par le vecteur de second membre b. Donc la résolution d’un
système linéaire d’ordre n, par les formules de Cramer fait intervenir le calcul de n +
1 déterminants dont chaque déterminant nécessite de l’ordre de n! multiplications. La
méthode de Cramer devient trop coûteuse même pour des matrices de tailles assez petites.
D’où l’idée de concevoir des méthodes qui en général donnent la solution à une valeur près,
mais avec un nombre d’opérations raisonnable.
On distinguera deux méthodes numériques pour résoudre un système linéaire. Les
méthodes directes, dont certaines font l’objet de ce chapitre et les méthodes itératives qui
seront développées dans les chapitres suivants.

1.2 Principe des méthodes directes

On appelle méthode directe pour résoudre un système de type Ax = b, une méthode
qui donne x après un nombre fini d’opérations élémentaires. Le principe de ces méthodes
est de se ramener à un système linéaire linéaire équivalent, mais qui est plus simple à
résoudre. C’est le cas par exemple où la matrice du système est diagonale, triangulaire ou
orthogonale.

1.2.1 Rappels et notations sur les vecteurs et les matrices

Tout au long de ce cours on utilisera les notations suivantes :

2
1.2 Principe des méthodes directes

n
Pour n un entier naturel non  nul fixé,
 on note par R l’espace vectoriel des vecteurs
x1
 .. 
colonnes à coefficients réels x =  . . Le vecteur ligne xT = (x1 , . . . , xn ) désigne la
xn
transposée du vecteur x ∈ Rn .
Le produit scalaire dans Rn sera noté (·, ·) et est défini par
n
X
(x, y) = xi yi ,
i=1

et la norme associée est la norme euclidienne donnée par

n
!1
X 2 1
2
kxk2 = |xi | = (x, x) 2 .
i=1

On notera l’espace vectoriel des matrices à n lignes et p colonnes et à coefficients dans

R par Mn,p (R) et par Mn (R) l’ensemble des matrices carrées d’ordre n à coefficients dans
R. La transposée d’une matrice A = (aij )1≤i≤n,1≤j≤p ∈ Mn,p (R) par

AT = (aji )1≤i≤p,1≤j≤n ∈ Mp,n (R).

La matrice transposée vérifie

(Ax, y) = (Ax)T y = xT AT y = (x, AT y) pour tout x ∈ Rp et y ∈ Rn .

Définition 1.2.1 Soit A = (aij )1≤i,j≤n ∈ Mn (R). A est dite :

• diagonale si aij = 0 pour tout i 6= j.
• triangulaire supérieure (respectivement inférieure) si

aij = 0 pour tout i > j (respectivement i < j).

• inversible si son déterminant est non nul ou s’il existe une matrice B ∈ Mn (R) notée
A−1 telle que
AB = BA = In
où In est la matrice unité d’ordre n suivante
 
1
In =  .. .
.
 
1

• semblable à une matrice D ∈ Mn (R) s’il existe une matrice inversible P telle que
D = P −1 AP .
• diagonalisable si elle est semblable à une matrice diagonale.

3
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

On peut vérifier facilement que

Proposition 1.2.1
1. Le produit de deux matrices triangulaires supérieures (repectivement inférieures) est
une matrice triangulaire supérieure (respectivement inférieure).
2. Une matrice A = (aij )1≤,i,j≤n ∈ Mn (R) triangulaire est inversible si et seulement si
1
aii 6= 0, pour tout i = 1, . . . , n. De plus A−1 est de même type que A et (A−1 )ii = ,
aii
pour tout i = 1, . . . , n.

1.2.2 Résolution d’un système triangulaire

Soit le système trianglaire supérieur


 u11 x1 + u12 x2 + · · · u1n xn = b1
u22 x2 + · · · u2n xn = b2


.. .. . (1.3)

 . .

 unn xn = bn

Si U est la matrice triangulaire supérieure suivante :

 
u11 u12 · · · u1n
 u22 · · · u2n 
U = ..  ,
 
. .
 . . 
unn

alors, le système (1.3) est équivalent à U x = b où b = (bi )1≤i≤n . On utilise la méthode de
remontée pour résoudre ce système dont l’algorithme est le suivant :


xn = bn /unn
 Pour k = (n − 1), . . . , 1
 n
!
 X
 xk = bk − uki xi /ukk

 i=k+1
Fin de la boucle sur k

A chaque étape k on a une division, (n − k) multiplication pour 1 ≤ k ≤ n et (n − k)

additions pour k ≤ n − 1. Au total le nombre d’opérations est
n n−1
X X n(n + 1) n(n − 1)
(n − k + 1) + (n − k) = + = n2 .
k=1 k=1
2 2

4
1.3 Factorisation LU

Pour la résolution d’un système triangulaire inférieur Lx = b, on utilise la méthode de

descente dont l’algorithme est le suivant :


b1
 x1 = l11

 Pour k = 2, . . . , n
 k−1
!

 x = b − X 1
k k lki xi
lkk

i=1

Fin de la boucle sur k

Cette méthode nécessite aussi n2 opérations.

1.3 Factorisation LU
1.3.1 Rappel sur la méthode de Gauss
Parmi les méthodes directes classiques pour résoudre un système linéaire Ax = b, pour
A une matrice carrée inversible d’ordre n, on cite la méthode d’élimination de Gauss dont
le principe est d’effectuer uu nombre fini d’opérations algébriques linéaires sur les lignes
de la matrice A et sur b, pour se ramener à un système triangulaire supérieur équivalent.

Exemple 1.3.1 Soit à résoudre le système linéaire d’ordre 4, suivant :



 x1 − 3x2 − x3 = 2
−x1 + x2 + 2x4 = 3


 x2 − x3 = 1
2x1 + x2 − x4 = 0


Sous forme matricielle ce système s’écrit sous la forme Ax = b, pour

   
1 −3 −1 0 2
−1 1 0 2  3
A= et b =  .
0 1 −1 0   1
2 1 0 −1 0

Dans la première étape on élimine la première inconnue x1 des équations 2,3 et 4 en

combinant chacune avec la première équation. Afin d’éliminer il faut d’abord vérifier que
x1 apparait dans la première équation. Si ce n’est pas le cas, il faut permuter l’équation
avec une autre dont le coefficient de x1 est non nul. On choisit comme premier pivot α1
le coefficient de x1 dans la nouvelle première équation qui est appelée ligne de pivot. Dans
notre exemple α1 = 1. Eliminer x1 des autre équations revient à annuler les coefficients
de la première colonne de A en dessous de la diagonale. Ceci revient dans la méthode de

5
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

Gauss à remplacer chaque ligne Li de A et de b par Li − aαi11 L1 , pour i = 2, 3 et 4. Dans

notre cas
L2 ←− L2 + L1 , L3 ←− L3 , L4 ←− L4 − 2L1 .
Après cette première étape, le système équivalent a comme nouvelle matrice et comme
second membre    
1 −3 −1 0 2
A(1) = 
0 −2 −1 2   5 .
   
0 et b = 1
1 −1 0 
0 7 2 −1 −4
Dans la deuxième étape c’est la deuxième ligne qui joue le role de ligne de pivot si x2 est
présent (Sinon, on permute la deuxième équation avec une autre sans toucher la première).
Le coefficient de x2 devient le nouveau pivot α2 qui vaut −2 dans cet exemple. Pour annuler
les coefficients de la deuxième colonne en dessous de la diagonale, on fait les opérations
7
L3 ←− L3 + 21 L2 , L4 ←− L4 + L2 .
2
Le système équivalent a pour matrice et second membre
1 −3 −1 0
   
2
0 −2 −1 2
A(2) =   et b(2) =  5  .
 
0 0 −3/2 1  7/2 
0 0 −3/2 6 27/2
Enfin, pour éliminer x3 de la quatrième équation, on utilise le pivot α3 = −3
2
et on
fait L4 ←− L4 + L3 . La matrice et le second membre de système équivalent sont
   
1 −3 −1 0 2
0 −2 −1 2  5 
A(3) =  (3)
   
0 0 −3/2 1 et b = 7/2 .


0 0 0 5 10
Le dernier système est triangulaire supérieur. On
 résout
 par la méthode de remontée ce
1
0
système triangulaire supérieur pour obtenir x = 
−1 qui est aussi la solution de (S).


2
Remarque 1.3.1 Si on note U = A(3) , alors on peut vérifier qu’on a
 
1 0 0 0
−1 1 0 0
A = LU, avec L =   0 −1/2 1 0


2 −7/2 1 1
est la matrice triangulaire inférieure dont les termes diagonaux valent 1 et dont le coeffi-
(k)
aik (k)
cient lik de la matrice L sous la diagonale est exactement le terme , où aik désigne
αk
les coefficients de A(k) , matrice d’élimination de Gauss à l’étape k.

6
1.3 Factorisation LU

Algorithme de Gauss et nombre d’opérations

Si pour i = 1, . . . , n et p = 1, . . . , n, on désigne par A[i, p : n] les termes de la ligne
i d’une matrice A situés dans l’ordre entre les colonnes p et n, alors l’algorithme de la
méthode d’élimination de Gauss pour résoudre un système Ax = b, s’écrit :


Pour k = 1, . . . , n − 1,
Recherche de pivot et permutation des lignes


 Pour i = k + 1, . . . , n
 ℓik = aik


  akk
  A[i, k : n] = A[i, k : n] − ℓik A[k, k : n]
 
  bi = bi − ℓik bk

 Fin de la boucle sur i
Fin de la boucle sur k.

Puis, on résout le système triangulaire obtenu.

A chaque étape k de l’élimination de xk il faut effectuer :
– (n − k) divisions,
– (n − k)2 multiplications,
– (n − k)2 additions.
Le nombre total d’opérations est donc
n−1
X n−1
X n−1
X n−1
X
(n − k) + 2 (n − k)2 = p+2 p2 .
k=1 k=1 p=1 p=1

n n
X n(n + 1) X n(n + 1)(2n + 1)
Si on utilise le fait que p= et que p2 = on tire que le
p=1
2 p=1
6
n(n − 1) n(n − 1)(2n − 1)
nombre d’opérations dans la méthode d’élimination de Gauss est +2
2 6
qui est de l’ordre de 23 n3 lorsque n est très grand.

Remarque 1.3.2 Le choix du pivot peut avoir une grande importance dans le calcul
comme le montrera l’exemple suivant.
Soit à résoudre le système
 −p     
10 1 x1 1
= ,
1 1 x2 0

1
 
−
dont la solution exacte est  1 −1 10 .
−p 

1 − 10−p

7
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

Après la première étape d’élimination de Gauss, on obtient

 −p    
10 1 x1 1
= .
0 1 − 10p x2 −10−p
   
p p x1 0
Pour p tel que sur une machine 1 − 10 ≃ −10 on obtient = qui n’est pas
x2 1
proche de la solution exacte.
Cet exemple montre l’effet des erreurs d’arrondi qui proviennent de la division par des
pivots trop petits. La stratégie de pivot partiel consiste à choisir comme pivot αk vérifiant
(k)
|αk | = max |ãik | le coefficient de module maximum de la partie de la colonne k en dessous
k≤i≤n
de la diagonale.
Dans l’exemple(2.3), l’élimination de Gauss était faite sans stratégie de pivot. Avec
la stratégie de pivot partiel, et dans la première étape, on doit choisir le premier pivot
a31 = 2 au lieu de a11 = 1.

1.3.2 Factorisation LU
Dans cette partie on développe la technique de la factorisation LU qui permet aussi
de résoudre un système Ax = b en se ramenant à la résolution d’un système triangulaire
inférieur puis un système triangulaire supérieur.

Proposition 1.3.1 Soit A = (aij )1≤i,j≤n ∈ Mn (R) une matrice carrée d’ordre n telle
que les n sous matrices A(k) = (aij )1≤i,j≤k , pour k = 1, . . . , n, sont inversibles.
Alors, il existe une matrice triangulaire inférieure L dont les coefficients diagonaux
sont égaux à 1, et une matrice triangulaire supérieure U telle que A = LU . De plus cette
décomposition, dite décomposition ou factorisation LU de A, est unique.

Preuve. Unicité : On suppose que A = L1 U1 = L2 U2 avec Li , i = 1, 2 triangulaire

inférieure vérifiant (Li )kk = 1 pour tout k = 1, . . . , n, Ui , i = 1, 2 triangulaire supérieure.
Alors les matrices U1 et U2 sont inversibles, puisque det A = det U1 = det U2 . On a alors
L−1 −1
2 L1 = U2 U1 qui est une matrice triangulaire inférieure et triangulaire supérieure, donc
L2 L1 est une matrice diagonale. Comme (L1 )kk = (L−1
−1 −1
2 )kk = 1, donc L2 L1 = In et par
suite L2 = L1 et U2 = U1 .

Existence : Notons d’abord que si une telle factorisation existe pour U = (uij )1≤i,j≤n
triangulaire inférieure U = (uij )1≤i,j≤n est triangulaire supérieure, alors

min(i,j)
X
aij = lik ukj , pour tout 1 ≤ i, j ≤ n (1.4)
k=1

On montre l’existence par récurrence sur n, l’ordre de la matrice A à factoriser.

8
1.3 Factorisation LU

 
a b
Si n = 2, A = vérifiant a 6= 0 et det(A) = ad − bc 6= 0, alors A admet la
c d
factorisation
a b
! !
1 0
A= c ad − bc .
1 0
a a
Supposons que le résultat est vrai jusqu’à l’ordre n − 1. Soit A = (aij ) une matrice
d’ordre n telle que les matrices A(k) , pour k = 1, . . . , n sont inversibles. D’après l’hypothèse
de récurrence la matrice A(n−1) qui est d’ordre n − 1 admet une factorisation L̃Ũ , où
L̃ = (lij )1≤i,j≤n−1 est une matrice triangulaire inférieure d’ordre n − 1 à diagonale unité
et Ũ = (uij )1≤i,j≤n−1 est une matrice triangulaire supérieure d’ordre n − 1 dont les termes
diagonaux sont tous non nuls (uii 6= 0 ∀ i = 1, . . . , n − 1). On pose



 u1n = a1n ,

u2n = a2n − l21 u2n ,



..
.
p−1



 X
upn = apn − lpk ukn ,



k=1

et  an1
ln1 = ,
u11




 an2 − ln1 u12
ln2 = ,


u22



..
 .


 p−1
X
lnk ukp

anp −




k=1

l =
np upp
.
Clairement lnn = 1 et si L et U les matrices d’ordre n définies par
   
0 u1n
L=
 ..  et U =  .. 
L̃ .  Ũ . 
ln1 · · · ln,n−1 1 0 · · · 0 unn

Alors L est triangulaire inférieure à diagonale unité, U est triangulaire supérieure avec
coefficients diagonaux non nuls et on peut vérifier facilement que A = LU .

Algorithme de la factorisation LU
De (1.4) et pour p = 1, . . . , n, en lisant dans l’ordre les termes de la p-ième ligne
eu dessus de la diagonale de la matrice à factoriser A, on obtient la p-ième ligne de U ,
puis au fur et on mesure qu’on écrit les termes de la p-ième colonnes de A en dessus de

9
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

la diagonale, on déduit la p-ième colonne de L. Ceci peut se traduire par l’algorithme

suivant :

Pour
 p = 1, . . . , n


 Pour j = p, . . . , n
  p−1
X
 upj := apj − lpk ukj
 

 
 k=1

 Fin de la boucle sur j

 

 Pour i = p + 1, . . . , n !
  p−1
X
lip := aip − lik ukp /upp
 
 
 
 k=1
 Fin de la boucle sur i
Fin de la boucle sur p

Remarque 1.3.3 De la preuve ou de l’algorithme de la factorisation LU de la matrice A

on tire que toutes les sous matrices A(k) de A admettent aussi une factorisation L(k) U (k)
pour L(k) = (lij )1≤i,j≤k et U (k) = (uij )1≤i,j≤k , pour k = 1, . . . , n. Ainsi la matrice A admet
une factorisation LU si et seulement si toutes les matrices A(k) sont inversibles.

Nombre d’opérations
A chaque étape p, pour calculer upj , j = p, . . . , n il faut effectuer
• p − 1 multiplications,
• p − 1 additions,
donc 2(p − 1) opérations.
Le nombre total d’opérations pour déterminer la p-ième ligne de U est
n
X
2(p − 1) = 2(n − p + 1)(p − 1).
j=p

Ensuite pour calculer le terme lip , i = p + 1, . . . , n il faut

• 1 division,
• p − 1 multiplications,
• p − 1 additions.
Donc le calcul de la p-ième colonne de L nécessite
n
X
(2(p − 1) + 1) = (n − p)(2p − 1).
i=p+1

10
1.3 Factorisation LU

Le nombre total d’opérations pour effectuer la factorisation LU de A est

n
X n
X
[2(n − p + 1)(p − 1) + (n − p)(2p − 1)] = 2 (n − p)p + 2.
p=1 p=1

n n
X
2 n(n + 1)(2n + 1) X n(n + 1)
Si on utilise le fait que p = et que p= on tire que
p=1
6 p=1
2
le nombre d’opérations pour effectuer la factorisation LU d’une matrice d’ordre n est de
l’ordre de 32 n3 .

Résolution de Ax = b pour A = LU
Le système Ax = b donne LU x = b. Si on pose y = U x, il suffit de résoudre le système
triangulaire inférieur Ly = b puis le système triangulaire supérieur U x = y.
Puisque la résolution d’un système triangulaire, nécessite n2 opérations, le nombre
d’opérations pour résoudre un système linéaire Ax = b, par la factorisation A = LU est
de l’ordre 23 n3 .

Remarques 1.3.1
1. On utilise la factorisation LU surtout d’une matrice A pour résoudre plusieurs
systèmes linéaires avec la même matrice A mais avec des seconds membres différents.
Si on a par exemple à résoudre p systèmes linéaires avec la même matrice A, le coût
est de l’ordre de 23 n3 + 2pn2 au lieu de p 32 n3 .
2. La factorisation LU permet aussi de calculer det A en 32 n3 au lieu de n! opérations
puisque
Yn
det A = det L det U = uii .
i=1

Matrices bandes
Définition 1.3.1 Une matrice A = (aij )1≤i,j≤n ∈ Mn (C) est dite matrice bande s’il
existe nb ∈ N, tel que aij = 0 pour |i − j| > nb . Autrement dit les coefficients non nuls
de la matrice A sont situés dans une bande de longueur 2nb + 1, centrée sur la diagonale
principale.
Pour nb = 1, la matrice est dite tridiagonale.

Proposition 1.3.2 La factorisation A = LU conserve la structure bande.

Preuve. On montre cette proprièté par récurrence sur les étapes de la factorisation de la
matrice A.

11
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

La matrice A étant bande, la proprièté est vraie à l’étape 0. Supposons la propriété

est vraie jusqu’à l’étape p − 1 où on a donc lij = uij = 0 pour 1 ≤ i, j ≤ p − 1, |i − j| > nb .
A l’étape p on a
p−1
X
upj := apj − lpk ukj , pour j = p, . . . , n
k=1

et
p−1
X
aip − lik ukp
k=1
lip := , pour i = p + 1, . . . , n.
upp
Soit p tel que |p − j| > nb . Alors apj = 0 puisque A est une matrice bande.
Si p − j > nb > 0 alors upj = 0, puisque U est triangulaire supérieure.
Si p − j < −nb < 0, donc pour 1 ≤ k ≤ p − 1, on a k − j ≤ p − 1 − j < p − j < −nb .
D’après l’hypothèse de récurrence ukj = 0. Ainsi upj = 0 et la propriété est vérifiée pour
la matrice U à l’étape k. De même, si p est tel que |i − p| > nb , alors apj = 0.
Si i − p < −nb < 0 alors lip = 0, puisque L est triangulaire inférieure.
Si i − p > nb < 0, donc pour 1 ≤ k ≤ p − 1 < p, on a i − k ≤ i − p < −nb . D’après
l’hypothèse de récurrence lik = 0. Ainsi lip = 0 et la propriété est vérifiée aussi pour la
matrice L à l’étape k.

1.4 Factorisation de Cholesky des matrices symétriques

définies positives
1.4.1 Rappels sur les matrices symétriques
Définition 1.4.1 Soit A = (aij )1≤i,j≤n ∈ Mn (R). La matrice transposée de A, notée AT
est définie par
AT = (aji )1≤i,j≤n .

L’opérateur transposé vérifie, pour toutes marices A et B de Mn (R),

1. (A + B)T = AT + B T
2. (AB)T = B T AT
3. Si A est inversible, alors AT est inversible et (AT )−1 = (A−1 )T .
4. (Ax, y) = (x, AT y) pout tout x, y ∈ Rn .

Définition 1.4.2 Soit A ∈ Mn (R). La matrice A est dite :

1. symétrique si AT = A.
2. orthogonale si AAT = AT A = In .

12
1.4 Factorisation de Cholesky des matrices symétriques définies positives

Remarque 1.4.1 Si A ∈ Mn (R) est une matrice orthogonale, alors A est inversible et
A−1 = AT puisqu’on a AAT = AT A = In . De plus les vecteurs lignes ainsi que les vecteurs
colonnes forment une base orthonormée de Rn .

Définition 1.4.3 Vecteurs et valeurs propres

Soit A ∈ Mn (R). On rappelle que λ ∈ C est une valeur propre de A si det(A−λIn ) =
0. Un vecteur x ∈ Cn non nul est dit vecteur propre de A associé à la valeur propre λ si
Ax = λx.

Un résultat connu concernant la réduction de matrices symétriques est le suivant :

Proposition 1.4.1 Soit A ∈ Mn (R) une matrice symétrique. Alors, il existe une ma-
trice orthogonale O ∈ Mn (R) telle que la matrice D = OT AO soit diagonale réelle.

Remarques 1.4.1 Si A ∈ Mn (R) symétrique et O une matrice orthogonale telle que

 
λ1
OT AO = D = 
 ... ,

λn

alors λ1 , λ2 , . . . , λn sont les valeurs propres de A. De plus si f1 , f2 , . . . , fn sont les vecteurs

colonnes de O, alors fi est un vecteur propre de A associé à la valeur λi pour i = 1, . . . , n
et la famille (f1 , . . . , fn ) forme une base orthonormée des vecteurs propres de A.

Conséquences 1.4.1
1. Toute matrice symétrique est diagonalisable.
2. Les valeurs propres d’une matrice symétrique sont toutes réelles.

Définition 1.4.4 Soit A ∈ Mn (R) une matrice symétrique. La matrice A est dite semi-
définie positive si
(Ax, x) ≥ 0 pour tout x ∈ Rn .
Si de plus A vérifie, (Ax, x) = 0 si et seulement si x = 0, alors A est dite définie positive.

Proposition 1.4.2 Soit A ∈ Mn (R) une matrice symétrique.

1. La matrice A est semi-définie positive si et seulement si toutes ses valeurs propres
sont positives.
2. La matrice A est définie positive si et seulement toutes ses valeurs propres sont
strictement positives.

Preuve. Soit A ∈ Mn (R). On suppose que A est semi-définie positive (resp. définie
positive). Soit λ une valeur propre de A et x ∈ Rn (non nul) un vecteur propre associé à
la valeur propre λ. On a Ax = λx, donc

(Ax, x) = λ(x, x) = λkxk22 .

13
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

Comme A est semi-définie positive (resp. définie positive), donc (Ax, x) ≥ 0 (resp. > 0)
et par conséquent
λkxk22 ≥ 0 (resp. > 0)
ou λ ≥ 0 (resp. > 0).
Supposons que toutes les valeurs propres de A sont positives (resp. strictement po-
sitives) et montrons que A est semi-définie positive (resp. strictement positives). On sait
qu’il existe une base orthonormée (f1 , . . . , fn ) de vecteurs propres de A. Soit x ∈ Rn ,
(resp. x ∈ Rn \ {0},
X n
x= xi fi .
i=1

Donc
n
X
Ax = xi λi fi ,
i=1

et
n
X
(Ax, x) = λi x2i ≥ 0 (resp. > 0). (1.5)
i=1

Remarque 1.4.2 De (1.5) on tire facilement que si A est une matrice symétrique d’ordre
n et λ1 , λn respectivement la plus petite et la plus grande valeur propre de A, alors pour
tout x ∈ Rn , on a
λ1 kxk22 ≤ (Ax, x) ≤ λn kxk22 . (1.6)

L’inégalité (1.6) sera fort utile pour la suite.

1.4.2 Factorisation des matrices symétriques

Proposition 1.4.3 Soit A = (aij )1≤i,j≤n ∈ Mn (R) une matrice symétrique définie posi-
tive. Alors la matrice A admet une factorisation LU avec les éléments diagonaux de U
sont strictement positifs.

Preuve. Soit pour k = 1, . . . , n, A(k) = (aij )1≤i,j≤k ∈ A(k) (R). Montrons que la matrice
symétrique A(k) est inversible. En effet, pour tout x = (x1 , . . . , xk )T ∈ Rk \ {0}, on pose
x̃ = (x1 , . . . , xk , 0, . . . , 0) ∈ Rn . Alors x̃ 6= 0 et on a (A(k) x, x) = (Ax̃, x̃) > 0. La matrice
A(k) est par conséquent définie positive, donc inversible. La matrice A admet donc une
factorisation LU . Montrons que uii > 0. Posons la matrice diagonale
 
u11
D= .. .
.
 
unn

14
1.4 Factorisation de Cholesky des matrices symétriques définies positives

Puisque
n
Y
det A = det L det U = uii 6= 0,
i=1

donc la matrice diagonale D est inversible. Soit

uij
S = D−1 U = ( )1≤i,j≤n ,
uii
alors U = DS et
A = LDS = S T DLT .
La matrice S T est triangulaire inférieure à diagonale unité ((S T )ii = 1, i = 1, . . . , n) et
la matrice DLT est une matrice triangulaire supérieure. D’après l’unicité de factorisation
LU , on a L = S T et U = DLT . Ainsi A = LDLT . Soit x ∈ Rn \ {0} et y tel que x = LT y,
alors y est aussi non nul et on a

(Dx, x) = (DLT y, LT y) = (LDLT y, y) = (Ay, y) > 0,

donc la matrice diagonale symétrique D est définie positive, ses valeurs propres uii , i =
1, . . . , n sont donc strictement positives.

Remarque 1.4.3 (Factorisation de Crout)

De la preuve de la proposition précédente on déduit que si A est une matrice symétrique in-
versible et admettant une factorisation LU , alors A admet la factorisation A = LDLT où
D est une matrice diagonale. La factorisation LDLT est appelée factorisation de Crout.

1.4.3 Factorisation de Cholesky

Proposition 1.4.4 Soit A une matrice symétrique définie positive. Alors il existe une
matrice triangulaire inférieure B à éléments diagonaux strictement positifs telle
que A = BB T . De plus cette factroisation est unique. Une telle factorisation est dite
factorisation de Cholesky de A.

Preuve. On sait que A admet une factoriasion LDLT = LU avec (L)ii = 1 et (D)ii =
uii > 0 pour i = 1, . . . , n. Si on pose
√ 
u11
D′ = 
 ... ,

√
unn

alors
A = (LD′ )(D′ LT ) = BB T .
L’unicité découle de celle de la factorisation LU .

15
 Chapitre 1. Méthodes directes pour la résolution des systèmes linéaires

Remarque 1.4.4 La matrice B de la factorisation de Cholesky de la matrice symétrique

√
A = LU vérifie B = L diag( uii ) où
√ 
u11
√ ...
diag( uii ) =  .
 
√
unn

Algorithme de la factorisation de Cholesky

Il suffit d’identifier le produit A et BB T pour B = (bij ) une matrice triangulaire
inférieure. On en déduit
min(i,j)
X
aij = bik bjk ∀ 1 ≤ i, j ≤ n.
k=1

On commence par calculer terme à terme la première colonne de la matrice triangulaire B,

puis on passe à la deuxième colonne et ensuite connaissant les (i−1) premières colonnes de
B, on peut déduire les termes de la i-ème colonne se trouvant au dessous de la diagonale
jusqu’on on obtient toute la matrice triangulaire inférieure B. Ceci se traduit aussi par
l’algorithme suivant :


Pour i =v1, . . . , n
 u
Xi−1
 u

 bii := aij −
t b2ik
 k=1
 

 Pour j = i + 1, . . . , p − 1!
  Xi−1
bij := aij − bik bkj /bii
 
 
 
 k=1
 Fin de la boucle sur j
Fin de la boucle sur i

3
Remarque 1.4.5 Clairement, le coût de la méthode de Cholesky est de l’ordre de n3
qui est la moitié de la factorisation LU , puisque ici le calcul de la matrice B donne
immédiatement sa matrice transposée B T .

16