Enoncés et corrections : Ana Matos.

Exo7

Méthode de Gauss. Factorisation LU et de Cholesky

Exercice 1 Taille des éléments dans l’élimination de Gauss

Notons Ãk la matrice carrée d’ordre (n − k + 1) formée des éléments akij , k ≤ i, j ≤ n de la matrice Ak = (akij )
obtenue come résultat de la (k −1)–ème étape de l’élimination de Gauss. On suppose A = A1 symétrique définie
positive.
1. Notant (., .) le produit scalaire euclidien et v0 ∈ Rn−k le vecteur formé par les (n − k) dernières compo-
santes d’un vecteur v = (vi )ni=k ∈ Rn−k+1 quelconque, établir l’identité
 2
n
0 0 1  k k 

(Ãk v, v) = (Ãk+1 v , v ) + k akk vk + ∑ aik vi  .
akk  i=k+1


2. Montrer que chaque matrice A˜k est symétrique définie positive.

3. Etablir les inégalités suivantes :
0 < aiik+1 ≤ akii , k + 1 ≤ i ≤ n
 
max ak+1
 k+1   k k
= max a i j  ≤ max ai j = max aii
 
ii 
k+1≤i≤n k+1≤i, j≤n k≤i, j≤n k≤i≤n

Correction H [002222]

Exercice 2 Stratégie de pivotage

1. Montrer que pour une matrice quelconque A = (ai j ) de type (2 × 2) on a

∑2i, j=1 |ai j |2

cond2 (A) = σ + (σ 2 − 1)1/2 avec σ =
2| det(A)|

2. Calculer les conditionnements cond p (.) pour p = 1, 2, ∞ des matrices exactes obtenues à la première
étape de la procédure d’élimination de Gauss pour résoudre le système linéaire
 −4
10 u1 + u2 = 1
u1 + u2 = 2

selon que l’on commence, ou non, par échanger les deux équations. Conclusion ?
[002223]

Exercice 3 Factorisation LU d’une matrice bande

Montrer que la factorisation LU préserve la structure des matrices bande au sens suivant :

li j = 0 pour i − j ≥ p
ai j = 0 pour |i − j| ≥ p ⇒
ui j = 0 pour j − i ≥ p

Correction H [002224]

1
Exercice 4 Factorisation d’une matrice symétrique
Soit A une matrice symétrique inversible admettant une factorisation LU. Montrer que l’on peut écrire A sous
la forme
A = BB̃T où
– B est une matrice triangulaire inférieure ;
– B̃ est une matrice où chaque colonne est soit égale à la colonne correspondante de B, soit égale à la colonne
correspondante de B changée de signe.
Application numérique  
1 2 1 1
 2 3 4 3 
A=  1 4 −4 0  .


1 3 0 0

Correction H [002225]

Exercice 5 Quelques factorisations LU

1. Soit A = LU la décomposition LU d’une matrice A ∈ Rn×n avec |li j | ≤ 1. Soient aTi et uTi les lignes i de
A et U respectivement. Montrer que
i−1
uTi = aTi − ∑ li j uTj
j=1

et que
kUk∞ ≤ 2n−1 kAk∞

2. Soit A ∈ Rn×n définie par 

 1 si i = j ou j = n
ai j = −1 si i > j
0 sinon


Montrer que A a une décomposition LU avec |li j | ≤ 1 et unn = 2n−1 .

[002226]

Exercice 6
On suppose A ∈ Rn×n inversible. Montrer que si PAΠ = LU est obtenue par la méthode de Gauss avec pivotage
total, alors
∀i, j = 1, · · · , n |li j | ≤ 1
∀i = 1, · · · , n, ∀ j = i, · · · , n, |ui j | ≤ |uii |
[002227]

Exercice 7
Soit A ∈ Rn×n telle que AT soit à diagonale strictement dominante. Montrer que A admet une décomposition
LU avec LT à diagonale strictement dominante.
Correction H [002228]

Retrouver cette fiche et d’autres

exercices de maths sur
exo7.emath.fr
2
Correction de l’exercice 1 N

1. A la k-ème étape de l’élimination de Gauss, l’élément ak+1

i j est donné par

akk j akik
ak+1
ij = akij − k + 1 ≤ i, j ≤ n
akkk

et on remarque immédiatement par récurrence que toutes les matrices A˜k sont symétriques. On a
(k)
(Ãk+1 v0 , v0 ) = ∑ni=k+1 vi (∑nj=k+1 ai j v j ) − a1k (∑ni=k+1 akik vi )2
kk

(Ãk v, v) = ∑ni=k+1 vi (∑nj=k+1 akij v j ) + ∑ni=k+1 (akik + akki )vi vk + akkk v2k
Par symétrie akik = akki et donc
(Ãk v, v) = (Ãk+1 v0 , v0 ) + a1k [(∑ni=k+1 akik vi )2 + 2vk ∑ni=k+1 akik vi akkk + (akkk )2 v2k ] =
kk

n
1
(Ãk+1 v0 , v0 ) + k
[a k k k
v k + ∑ akik vi ]2
akk i=k+1

2. Faisons un raisonnement par récurrence

– Ã1 est symétrique définie positive ;
– Par hypothèse supposons que Ãk est définie positive ;
– Supposons par absurde que Ãk+1 ne soit pas définie positive : alors ∃v0 6= 0 : (Ãk+1 v0 , v0 ) ≤ 0. On
définit le vecteur v ∈ Rn−k+1 par :
– vi = v0i , k + 1 ≤ i ≤ n
– vk est solution de akkk + ∑ni=k+1 akik vi = 0
Alors (Ãk v, v) = 0 et v 6= 0 ; donc Ãk n’est pas définie positive, ce qui contredit l’hypothèse de récur-
rence.
2
|ak |
3. Première inégalité : en utilisant la relation d’élimination on obtient : aiik+1 = akii − aki2
kk
– une matrice définie positive a tous ses éléments diagonaux strictement positifs, donc aiik+1 > 0
 2  2
– akki  / akkk  ≥ 0, k + 1 ≤ i ≤ n
donc ak+1ii ≤ akii , k + 1 ≥ i
 
Deuxième inégalité : supposons qu’il existe un élément akij , i < J tel que akij  ≥ maxk≤l≤n akll . On consi-
 
dère le vecteur v 6= 0 défini par

vi = 1, v j = −sign(akij ), vl = 0 l 6= i, j

Alors
(Ãk v, v) = (akii − akij ) − (akij  − akj j ) ≤ 0
   

ce qui est impossible. Donc

max akij  = max akii 
   
1≤i, j≤n 1≤i≤n

Correction de l’exercice 3 N
Montrons par récurrence que An = U est une matrice bande.
A1 = A, Ak+1 = Lk Ak = Lk Lk−1 · · · L1 A, k = 1, · · · , n − 1.
Supposons que Ak est une matrice bande i.e., akij = 0 pour |i − j| ≥ p et montrons que Ak+1 est une matrice
bande.
akik akk j
aik+1
j = a k
ij −
akkk
Soit |i − j| ≥ p ⇔ |(i − k) − ( j − k)| ≥ p. On considère deux cas :
– k + 1 ≤ i ≤ n et k ≤ j ≤ n. Alors i − k ≥ p ou j − k ≥ p ⇒ akik akk j = 0 ⇒ ak+1 k
i j = ai j = 0
– i ≤ k ou j ≤ k − 1 alors ak+1 k
i j = ai j = 0

3
donc Ak+1 est une matrice bande et U est une matrice bande. On a A = LU et la matrice triangulaire inférieure
L a pour éléments li j = aijj /a jj j , j ≤ i ≤ n. Toutes les matrices A j étant des matrices bandes on a aijj = 0 pour
i − j ≥ p ⇒ li j = 0 pour i − j ≥ p.

Correction de l’exercice 4 N
p
Soit LU la factorisation LU de A. On va intercaler dans cette factorisation la matrice réelle Λ =diag( |uii |).
A = (LΛ)(Λ−1U) = BC. La symétrie de A entraine BC = CT BT . On a
C(BT )−1 matrice triangulaire supérieure, B−1CT matrice triangulaire inférieure et C(BT )−1 = B−1CT et donc
C(BT )−1 = B−1C= diag(sign(uii ) = S ⇒ C(BT )−1 S−1 = I = S−1 B−1CT ⇔ CT = BS = B̃. Donc A peut être mise
sous la forme
A = BB̃T avec B̃ = BS
i.e. la i-ème colonne de B̃ est égale à la i-ème colonne de B affectée du signe de uii
Application numérique :  
1 2 1 1
 −1 2 1 
B̃ =  .
 −1 −1 
1

Correction de l’exercice 7 N
α uT
 
A = A1 = , B1 = (bi j )n−1
i, j=1
v B1
AT étant à diagonale strictement dominante on a :
n−1
|α| > ∑ |vi |, |ui | + ∑ |b ji | < |bii |
i=1 j6=i

Il suffit de montrer que

– la première colonne de L vérifie |l11 | > ∑i6=1 |li1 |
– B2 est telle que
α uT
 
1 T
A2 = , C = B2 = B1 − vu
0 B2 α
vérifie |cii | > ∑ j6=i |c ji | avec Ci j = Bi j − α1 vi u j et itérer.
|vi |
– première colonne de L : li1 = vi /α ⇒ ∑ni=2 |li1 | = ∑n−1 i=1 α < 1
1 1
– ∑i6= j |ci j | = ∑i6= j bi j − α vi w j  ≤ ∑i6= j |bi j | + |α| |w j | ∑i6= j |vi |
 
1  1 
≤ |b j j | − |u j | + |u j |(|α| − |v j |) ≤ b j j − u j v j  = |c j j |

|α| α

donc BT2 est de diagonale strictement dominante. La démonstration se finit par récurrence.