Méthodes numériques (L2 - 2024/2025)

Feuille de TD no 3 — Méthodes de résolution directe de systèmes

linéaires.

Cette feuille est très largement extraite des feuilles de TD proposées par Guillaume Legendre (jusqu’en
2024), disponibles ici : https://www.ceremade.dauphine.fr/~legendre/enseignement/methnum/

1 Rappels sur la méthode d’élimination de Gauss

Exercice 1. Résoudre par la méthode d’élimination de Gauss, en donnant l’expression de toutes les
matrices et de tous les seconds membres intermédiaires, le système linéaire s’écrivant matriciellement Ax =
b, avec    
2 −1 4 0 8
 4 −1 5 1 16
A=  et b =   .
   
−2 2 −2 3 3
0 3 −9 4 3
Répondre à la même question avec
   
5 2 1 1
A =  5 −6 2 et b = 2 .
   
−4 2 1 3

Exercice 2. On considère le système linéaire s’écrivant matriciellement AX = B, avec

   
1 0 6 2 6
8 0 −2 −2 −2
A=  et b =   .
   
2 9 1 3 −8
2 1 −3 10 −4

1. Est-il possible d’utiliser la méthode d’élimination de Gauss sans échange pour la résolution de ce
système ?
2. Trouver des matrices de permutation P et Q telles que l’on puisse réaliser l’élimination sur la matrice
P AQ. Comment est transformé le système linéaire initial ?

Exercice 3. Soit la matrice  

2 1 0 0
0 4 1 0
U = .
 
0 0 3 1
0 0 0 1
Calculer son inverse en résolvant le système matriciel U X = I4 , dans lequel X désigne une matrice carrée
d’ordre 4, par la méthode d’élimination de Gauss–Jordan.

Exercice 4. Donner une formulation matricielle (c’est-à-dire en termes d’un produit de matrices de
transformations élémentaires) de la réduction à la forme échelonnée de la matrice rectangulaire
 
1 1 3 0 0 2
4 6 5 2 2 0
A=
 
4 2 4 1 3 4


2 2 0 3 3 8

par la méthode d’élimination de Gauss.

1
Exercice 5. On considère le système linéaire s’écrivant matriciellement Ax = b avec
 
2 4 2
0 4 4
A= .
 
2 0 2
0 1 8

1. En utilisant la méthode d’élimination de Gauss–Jordan, mettre le système sous une forme échelonnée
réduite équivalente.
2. Préciser le rang et la dimension du noyau de la matrice obtenue et en déduire ceux de A.
3. Déterminer des bases de l’image et du noyau de la matrice A.
4. Quelle(s) condition(s) doit vérifier le vecteur colonne b pour que le système possède une solution ?

2 Méthodes de factorisation pour la résolution de systèmes linéaires

Exercice 6. On considére le système linéaire s’écrivant matriciellement Ax = b avec

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

1. Calculer la factorisation LU de la matrice A.

2. Résoudre le système linéaire en utilisant la factorisation trouvée à la question précédente.
3. Calculer le déterminant de la matrice A.

Exercice 7. Calculer la factorisation LU de la matrice A dans les cas suivants

   
  1 0 1 0 a a a a
2 2 1
2 4 5 1 a b b b
   
 
1. A = −2 6 4 , 2. A =  , 3. A =  ,
0 4 0 4 a b c c
   
1 0 2
 
1 0 0 2 a b c d

en précisant à chaque étape de la factorisation les matrices intervenant dans le procédé.

Exercice 8. ⋄ (factorisation LU d’une matrice bande).

On dit qu’une matrice est une matrice bande si elle n’admet que des éléments non nuls sur un « certain
nombre » de diagonales autour de la diagonale principale. Plus précisément, une matrice A de Mm,n (R) de
largeur de bande valant 2p + 1 est telle qu’il existe un entier naturel p tel que aij = 0 pour |i − j| > p.
Montrer que la factorisation LU préserve la structure des matrices bandes au sens suivant : soit A une
matrice carrée d’ordre n admettant une factorisation LU, alors

aij = 0 pour |i − j| > p ⇒ lij = 0 pour i − j > p et uij = 0 pour j − i > p.

Exercice 9. (factorisation LU d’une matrice tridiagonale – algorithme de Thomas)

Soit n un entier naturel strictement plus grand que 2 et
 
a1 c1 0 ... 0
 .. .. 
d
 2 a2 c2  . . 

A= .. ..  ..
0 . . 0 
 .
.
..

.
. . dn−1 an−1 cn−1 


0 ... 0 dn an

une matrice tridiagonale d’ordre n.

2
 1. Vérifier que si A admet une factorisation LU alors les matrices L et U sont de la forme
   
1 0 ... ... 0 u1 c1 0 ... 0
 .. .. ..   .. .. .. .. 
l
2 . . .
0
 . . . . 

 .. .. ..   . . .. .. 
L=
0 . . . 0  et U =  .. .. . . 0 .
 
. .
.. .. .. .. ..
 
. .
. . . . 0 . . . cn−1 
 

0 . . . 0 ln 1 0 ... ... 0 un

2. Montrer que les coefficients ui , 1 ≤ i ≤ n, et lj , 2 ≤ j ≤ n, satisfont les relations

di
u1 = a1 , li = ui−1 , ui = ai − li ci−1 , 2 ≤ i ≤ n.

3. Obtenir les formules découlant de l’utilisation de cette factorisation pour la résolution du système
linéaire s’écrivant matriciellement Ax = b, la matrice colonne b de Mn,1 (R) étant donnée.
4. Déterminer le nombre d’opérations nécessaires pour la résolution de ce système.

Exercice 10. (factorisation LU d’une matrice à diagonale strictement dominante)

Soit n un entier naturel supérieur à 2 et A une matrice carrée d’ordre n à diagonale strictement
dominante par lignes, c’est-à-dire vérifiant les conditions
n
X
|aii | > |aij |, 1 ≤ i ≤ n.
j=1,j̸=i

Le but de cet exercice est de montrer qu’une telle matrice est inversible et admet une factorisation LU.
1. Montrer, en raisonnant par l’absurde, qu’une matrice carrée d’ordre n à diagonale strictement do-
minante par lignes est inversible.
2. Soit A une matrice carrée d’ordre n inversible. Montrer que A admet une factorisation LU si et
seulement si A⊤ admet une factorisation LU.
3. Soit A une matrice carrée d’ordre n, que l’on suppose pouvoir partitionner en blocs de la manière
suivante : !
a W⊤
A= ,
V A1
où a = a11 est un réel non nul, V et W sont des matrice colonnes de Mn−1,1 (R) et A1 est une
matrice d’ordre n − 1. En effectuant des produits par blocs, vérifier que
! ! !
1 0⊤ 1 0⊤ a W⊤ 1
A= 1 , avec B = A1 − V W ⊤,
aV In−1 0 B 0 In−1 a

où 0 désigne la matrice colonne nulle de Mn−1,1 (R).

4. Montrer alors que la matrice A admet une factorisation LU si c’est le cas pour le bloc B.
5. Dans cette question, on suppose que la matrice A est à diagonale strictement dominante par colonnes.
(a) En utilisant la décomposition et les notations précédentes, montrer successivement que
n−1
X
|vi | < |a| − |vj |, 1 ≤ j ≤ n − 1,
i=1,i̸=j

n−1
X
|(A1 )ij | < |(A1 )jj | − |wj |, 1 ≤ j ≤ n − 1,
i=1,i̸=j

n−1 n−1
X X |wj | n−1
X
|bij | ≤ |(A1 )ij | + |vi |, 1 ≤ j ≤ n − 1.
i=1,i̸=j i=1,i̸=j
|a| i=1,i̸=j

En déduire que la matrice B est à diagonale strictement dominante par colonnes.

(b) En raisonnant par récurrence, montrer que A admet alors une factorisation LU.
3
 6. En supposant à présent que la matrice A est à diagonale strictement dominante par lignes, déduire
des questions précédentes qu’elle admet une factorisation LU.
7. On considère la matrice A dans les trois cas suivants :
     
4 1 1 1 1 2 3 0 4 1 1 1
1 4 1 1 0 −1 0 4  1 4 1 1
     
(a) A =  , (b) A =  , (c) A =  .
1 1 4 1 0 0 2 3 −1 1 0 0
  
  
1 1 1 4 0 0 0 1 3 −3 0 0
Déterminer, en justifiant très simplement la réponse, dans quel(s) cas A admet une factorisation
LU et, le cas échéant, calculer sa factorisation en précisant à chaque étape les opérations effectuées
sur les lignes de la matrice.

Exercice 11. (existence et unicité de la factorisation de Cholesky)

Soit n un entier naturel non nul. On rappelle qu’une matrice réelle A symétrique d’ordre n est dite
définie positive si elle est telle que

∀X ∈ Mn,1 (R), X ⊤ AX ≥ 0, et X ⊤ AX = 0 ⇒ X = 0Mn,1 (R) .

Par ailleurs, on dit qu’une matrice A réelle symétrique d’ordre n admet une factorisation de Cholesky s’il
existe une matrice triangulaire inférieure inversible B à diagonale strictement positive telle que

A = BB ⊤ .

1. Montrer que si la matrice réelle A est symétrique définie positive alors A est inversible.
2. Montrer que si la matrice réelle A admet une factorisation de Cholesky alors A est une matrice
symétrique définie positive.
3. Montrer que si la matrice réelle A admet une factorisation de Cholesky alors A admet une factorisa-
tion LDL⊤ . En déduire que si A admet une factorisation de Cholesky, cette factorisation est unique
dès lors que les coefficients diagonaux de B sont strictement positifs.
Dans toute la suite, on suppose que A est une matrice symétrique d’ordre n définie positive.
4. Dans cette question, on veut prouver que A admet une factorisation de Cholesky par un raisonnement
par récurrence.
(a) Pour n strictement plus grand que 1, écrire la matrice A sous la forme
!
An−1 V
A= ,
V ⊤ ann

où V est une matrice colonne de Mn,1 (R), ann est un réel et An−1 est une matrice symétrique
d’ordre n − 1. Montrer que la matrice An−1 est définie positive.
(b) On suppose que An−1 admet une décomposition de Cholesky, c’est-à-dire qu’il existe une matrice
triangulaire inférieure à diagonale strictement positive Bn−1 telle que An−1 = Bn−1 Bn−1 ⊤ .
Montrer que l’on peut déterminer de manière unique M de Mn,1 (R) et b de R, b > 0, tels que
!
Bn−1 0
B=
M⊤ b

et A = BB ⊤ .
(c) En déduire que A admet une factorisation de Cholesky.
5. Écrire l’algorithme permettant de calculer les coefficients de la matrice B.
6. Comparer le nombre d’opérations nécessaires à la résolution d’un système linéaire à matrice sy-
métrique définie positive par la méthode de Cholesky avec celui de la méthode d’élimination de
Gauss.
7. Application : déterminer la factorisation de Cholesky des matrices suivantes :
−1
     
1 0 3 2 1 2 3 4 1 3 1
0 4 2 0 2 5 1 10 −1 5 −7 −4
     
(a) A =  , (b) A =  , (c) A = 
 .
3 2 11 7 3 1 35 5   3 −7 14 4
 
  
2 0 7 21 4 10 5 45 1 −4 4 8
4
Exercice 12. On considère la matrice  
ε 1 2
A = 1 3 1
 
2 1 3
d’un système linéaire, avec ε un réel.
1. Déterminer pour quelles valeurs du paramètre ε la matrice A est symétrique définie positive.
2. On suppose tout d’abord que ε = 0. On veut résoudre le système matriciel Ax = b par une méthode
directe. Quelle factorisation de la matrice A peut-on envisager dans ce cas ?
3. On suppose maintenant que ε = 2.
(a) Vérifier que la matrice A est définie positive et en calculer la factorisation de Cholesky.
 ⊤
(b) En supposant que b = 1 1 1 , résoudre le système linéaire en utilisant la factorisation
calculée à la question précédente.

Exercice 13. (factorisation QR)

Soit n un entier naturel non nul et A une matrice réelle d’ordre n inversible.
1. Montrer qu’il existe une matrice R triangulaire supérieure à diagonale strictement positive telle que

A⊤ A = R⊤ R.

2. En déduire qu’il existe une matrice orthogonale Q, c’est-à-dire vérifiant Q⊤ Q = QQ⊤ = In , telle
que
A = QR.

3. Montrer que cette décomposition est unique.

4. On note (Aj )1≤j≤n les colonnes de la matrice A, (Qj )1≤j≤n celles de Q et on pose R = (rij )1≤i,j≤n .
(a) Montrer que Aj = ji=1 rij Qi , j = 1, . . . , n.
P

(b) En déduire qu’obtenir la factorisation QR de A équivaut à construire une base orthonormale de

Mn,1 (R) à partir de la famille {Aj }1≤j≤n .