Méthodes

directes de
Résolution
d’un Système
Linéaire

Méthode de
Méthodes directes de Résolution d’un Système
Gauss

Factorisation
Linéaire
LU d’une
matrice

Factorisation
et méthode de BENAZZA HAFIDA
Cholesky

Factorisation
QR et
FSR–Université Mohammed V Rabat
méthode de PHYSIQUE–S4
Householder

Décomposition
LU Printemps 2025
 Méthodes
directes de
Résolution
d’un Système Plan :
Linéaire

Méthode de
1 Méthode de Gauss
Gauss

Factorisation
LU d’une
matrice 2 Factorisation LU d’une matrice
Factorisation
et méthode de
Cholesky
3 Factorisation et méthode de Cholesky
Factorisation
QR et
méthode de
Householder

Décomposition
4 Factorisation QR et méthode de Householder
LU
 Méthodes Méthode de Gauss :
directes de
Résolution La méthode de Gauss est une méthode de résolution d’un
d’un Système
Linéaire système linéaire
Ax = b.
Méthode de
Gauss où :
Factorisation A ∈ Mn (R) : matrice carrée inversible de dimension n × n
LU d’une
matrice x , b ∈ Rn : vecteurs de dimension n. Elle comporte trois
Factorisation étapes :
et méthode de
Cholesky Procédure d’élimination qui permet de déterminer une
Factorisation matrice une matrice inversible M telle que MA soit
QR et
méthode de triangulaire supérieure ;
Householder
On calcul simultanément le vecteur Mb ;
Décomposition
LU On résoud le système linéaire triangulaire supérieur
MAx = Mb,
par la méthode de remontée.
 Méthodes
directes de
Résolution
d’un Système
Linéaire
Théorème
Méthode de
Le système Ax = b admet une solution unique si et
Gauss
seulement si det(A) 6= 0.
Factorisation
LU d’une Remarque :
matrice
Si det(A) = 0 deux cas se présentent :
Factorisation
et méthode de Si b ∈ Im(A) alors le système Ax = b admet une infinité
Cholesky

Factorisation
de solution
QR et
méthode de Si b ∈ Rn − Im(A) alors le système Ax = b n’admet
Householder
aucune solution.
Décomposition
LU
 Méthodes Exemple 1 : Le système admet une solution unique
directes de
Résolution
( ! ! !
d’un Système 2x1 + 3x2 = 5 2 3 x1 5
Linéaire ⇔ =
4x1 − 3x2 = 1 4 −3 x2 1
Méthode de
( !)
Gauss 1
det(A) = −18 ⇒ S = .
Factorisation 1
LU d’une
matrice
Exemple 2 : Le système admet une infinité de solutions
Factorisation
et méthode de
( ! ! !
Cholesky 2x1 + 3x2 = 5 2 3 x1 5
⇔ =
Factorisation 4x1 + 6x2 = 10 4 6 x2 10
QR et
méthode de ( ! )
Householder
x1
Décomposition det(A) = 0 ⇒ S = ∈ R2 | 2x1 + 3x2 = 5
LU x2
! ( !)
0 3
S= 5 + vect .
3 −2
 Méthodes
directes de
Résolution
d’un Système
Linéaire

Exemple 3 : L’ensemble de solutions est vide

Méthode de
Gauss
( ! ! !
2x1 + 3x2 = 5 2 3 x1 5
Factorisation ⇔ =
LU d’une 4x1 + 6x2 = 9 4 6 x2 9
matrice

Factorisation ( ! ( )
et méthode de
x1 2x1 + 3x2 = 5
Cholesky
det(A) = 0 ⇒ S = ∈ R2 |
Factorisation x2 2x1 + 3x2 = 92
QR et
méthode de
Householder Don S = ∅.
Décomposition
LU
 Méthodes
directes de
Résolution
d’un Système
Linéaire

Opérations permises sur les lignes d’une matrice

Méthode de On ne change pas la solution d’un système linéaire si :
Gauss

Factorisation Li ↔ Lj
LU d’une
matrice
On permute deux lignes Li et Lj .
Factorisation Li → λLi
et méthode de
Cholesky on multiplie une ligne par un réel non nul.
Factorisation
QR et Li ↔ αLi + βLj
méthode de
Householder
on remplace une ligne par une combinaison linéaire.
Décomposition
LU
 Méthodes
directes de
Résolution Résolution d’un système diagonal
d’un Système
Linéaire Si A = diag(aii )1≤i≤n
    
Méthode de
a11 0 0 ··· 0 x1 b1
Gauss  0 a
 22 0 ··· 0  x  b 
  2  2
Factorisation
 0 0 a33 ··· 0  x3  = b3 
    
LU d’une
 .. .. .. .. ..   ..   .. 
matrice
    
Factorisation
 . . . . .  .   . 
et méthode de
Cholesky
0 0 0 ··· ann xn bn
Factorisation
QR et
Puisque det(A) 6= 0 alors aii 6= 0 ∀i ∈ {1, · · · , n}. Les
méthode de
Householder
coordonnéees de la solution sont données par la formule :
Décomposition
LU bi
xi = , ∀i ∈ {1, · · · , n}.
aii
 Méthodes
directes de
Résolution
d’un Système
Linéaire
Résolution d’un système triangulaire supérieur
Méthode de
Si A = diag(aij )1≤i,j≤n avec aij = 0 si i > j
Gauss
    
Factorisation a11 a12 · · · ··· a1n x1 b1
LU d’une
22 · · · ···
 0 a a2n 
 x2  b2 
matrice
   

 0 0 a33 ··· a3n  x3  = b3 
Factorisation
    
et méthode de
 .. .. .. ..  .   . 
.. 
    
.   ..   .. 
Cholesky
 . . . .
Factorisation
QR et 0 0 0 ··· ann xn bn
méthode de
Householder
Puisque det(A) 6= 0 alors aii 6= 0 ∀i ∈ {1, · · · , n}.
Décomposition
LU
 Méthodes
directes de
Résolution En appliquant la méthode de remontée, on obtient :
d’un Système
Linéaire i =n

Méthode de bn
Gauss xn = .
ann
Factorisation
LU d’une
matrice
i =n−1
Factorisation
et méthode de 1
Cholesky xn−1 = (bn−1 − an−1n xn ).
ann
Factorisation
QR et
méthode de
1≤i ≤n−1
Householder
n
Décomposition 1 X
LU xi = (bi − aik xk ).
aii k=i+1
 Méthodes
directes de
Résolution
d’un Système
Linéaire

Résolution d’un système triangulaire inférieur

Méthode de Si A = diag(aij )1≤i,j≤n avec aij = 0 si i < j
Gauss

Factorisation
    
LU d’une a11 0 0 ··· 0 x1 b1
matrice
a21 a22

0 ··· 0  x2  b2 
   
Factorisation  . .. .. ..  .  =  . 
et méthode de  . ..  .   . 
Cholesky  . . . . .  .   . 
Factorisation an1 an2 · · · ··· ann xn bn
QR et
méthode de
Householder Puisque det(A) 6= 0 alors aii 6= 0 ∀i ∈ {1, · · · , n}.
Décomposition
LU
 Méthodes
directes de
Résolution
d’un Système
Linéaire
En appliquant la méthode de remontée, on obtient :
Méthode de
Gauss
i =1
Factorisation
LU d’une b1
matrice x1 = .
a11
Factorisation
et méthode de
Cholesky
n≥i ≥2
i−1
Factorisation
1 X
QR et xi = (bi − aik xk ).
méthode de aii k=1
Householder

Décomposition
LU
 Méthodes Algorithme de résolution d’un système triangulaire
directes de
Résolution supérieur
d’un Système
Linéaire Données :
A = (A[i, j])1≤i,j≤n , b = (b[i])1≤i≤n
Méthode de
Gauss
début
Factorisation b[n]
LU d’une
matrice
x [n] ←
A[n, n]
Factorisation
et méthode de pour i = n − 1 à 1 faire
Cholesky

Factorisation sum ← 0
QR et
méthode de
Householder pour k = i + 1 à n faire
Décomposition
LU
sum ← sum + A[i, k] · x [k]
b[i] − sum
x [i] ←
A[i, i]
fin
 Méthode d’élimination de Gauss :

Méthodes
directes de
Exemple :
Résolution
d’un Système
On
 résoutlesystème
 linéaire
 :
Linéaire 1 2 3 x1 4
1 1 2 x2  = 5
    
Méthode de
Gauss 1 1 1 x3 6
Factorisation On va triangulariser la matrice A augmentée du vecteur b
LU d’une
matrice soit
 : 
Factorisation
1 2 3 4
et méthode de
1 1 2 5
 
Cholesky

Factorisation 1 1 1 6
QR et
méthode de Puisque det(A) 6= 0 alors le système admet une solution
Householder
unique dans R3 ;
Décomposition
LU étape 1 : annuler les termes de la première colonne au
dessous de la diagonale. C’est à dire, on annule les
coefficients de la première colonne à partir de la deuxième
ligne.
 Méthode d’élimination de Gauss :

Méthodes
directes de
Résolution
d’un Système Les opérations effectuées sont :
Linéaire
2 ← L2 − L1 et 
L L3 ← L3 − L1 , on obtient alors la matrice :
1 2 3 4
Méthode de
0 −1 −1 1
 
Gauss

Factorisation 0 −1 −2 2
LU d’une
matrice étape 2 : annuler les termes de la deuxième colonne au
Factorisation dessous de la diagonale. C’est à dire, on annule les coefficients
et méthode de
Cholesky de la deuxième colonne à partir de la troisième ligne.
Factorisation L’opération effectuée est :
QR et
méthode de
Householder
3 ← L3 − L2 , onobtient alors la matrice :
L
1 2 3 4
Décomposition
0 −1 −1 1
 
LU

0 0 −1 1
 Méthode d’élimination de Gauss :

Méthodes
directes de
Résolution
d’un Système
Linéaire

Le système à résoudre se ramène au système triangulaire

Méthode de
Gauss supérieur
 suivant
 :   
Factorisation 1 2 3 x1 4
LU d’une
0 −1 −1 x2  = 1
    
matrice

Factorisation 0 0 −1 x3 1
et méthode de
Cholesky La méthode de la remontée permet de caculer
Factorisation
QR et
successivement x3 puis x2 et enfin x1 par : x3 = −1 puis
méthode de −x2 − x3 = 1 ⇒ x2 = 0 et enfin x1 + 2x2 + x3 = 4 ⇒ x1 = 7
Householder

Décomposition
LU
 Méthode d’élimination de Gauss :

Méthodes
directes de
Résolution
d’un Système
Linéaire
Cas général :
Méthode de
Pour résoudre le système Ax = b, il faut appliquer les
Gauss
modifications à la fois à la matrice A et au vecteur b. Pour
Factorisation
LU d’une résoudre le système Ax = b. On travaille sur la matrice
matrice
augmentée [A|b] qui a n lignes et n + 1 colonnes. C’est
Factorisation
et méthode de l’élimination de Gauss
Cholesky
Pour résoudre le système, il faut :
Factorisation
QR et
méthode de
Une triangularisation,
Householder

Décomposition
Une remontée (solution d’un système triangulaire).
LU
 Triangularisation :

Méthodes
directes de
Résolution
d’un Système
Linéaire
On considère la matrice A augmentée du vecteur b, soit :
 
Méthode de
Gauss
a11 a12 · · · a1n b1
Factorisation

 a21 a22 · · · a2n b2 
LU d’une  .. .. .. .. .. 
matrice

 . . . . . 

Factorisation
et méthode de
an1 an2 · · · ann bn
Cholesky

Factorisation
Pour l’instant, on fait l’hypothèse que les termes diagonaux aii
QR et
méthode de
pour 1 ≤ i ≤ n sont non nuls à chaque étape de la
Householder transformation. Ces éléments sont encore appelés les pivots de
Décomposition
LU
la matrice correspondante.
 Triangularisation :

Méthodes
directes de
étape 1 : annuler les termes de la première colonne au dessous
Résolution
d’un Système
de la diagonale. C’est à dire, on annule les coefficients de la
Linéaire première colonne à partir de la deuxième ligne. Les opérations à
effectués sont alors :
Méthode de
Gauss ai1
Factorisation Li ← Li − L1 , ∀i ∈ J2, nK
LU d’une a11
matrice
donc chaque coefficient reçoit la transformation suivante :
Factorisation
et méthode de
Cholesky ai1
aij ← aij − a1j , ∀i ∈ J2, nK, ∀j ∈ J1, n + 1K
Factorisation a11
QR et
méthode de On note alors la matrice obtenue :
Householder (1)
A(1) = (aij )
Décomposition
LU (1)
où la première ligne ne change pas : a1j = a1j et
(1) ai1
aij = aij − a1j , ∀i ∈ J2, nK, ∀j ∈ J1, n + 1K
a11
 Méthodes
directes de
Résolution
d’un Système
Linéaire

Méthode de
soit :
Gauss

a11 a12 · · · a1n b1

 
Factorisation
LU d’une
(1) (1) (1)
matrice
 0 a22 · · · a2n b2
 
(1)

Factorisation A =
 .. .. .. .. 
et méthode de  0 . . . .


Cholesky
(1) (1) (1)
Factorisation 0 an2 ··· ann bn
QR et
méthode de
Householder

Décomposition
LU
 Triangularisation :

Méthodes
directes de étape 2 : annuler les termes de la deuxième colonne au
Résolution
d’un Système dessous de la diagonale. C’est à dire, on annule les coefficients
Linéaire
de la deuxième colonne à partir de la trpoisième ligne. Les
opérations à effectués sont alors :
Méthode de
Gauss
ai2
Factorisation Li ← Li − L2 , ∀i ∈ J3, nK
LU d’une
matrice
a22
Factorisation donc chaque coefficient reçoit la transformation suivante :
et méthode de
Cholesky
ai2
Factorisation aij ← aij − a2j , ∀i ∈ J3, nK, ∀j ∈ J2, n + 1K
QR et a22
méthode de
Householder
On note alors la matrice obtenue :
(2)
Décomposition
LU A(2) = (aij )
(2) (1)
où la première ligne ne change pas : a1j = a1j = a1j et la
(2) (1)
deuxième ligne a2j = a2j
 Triangularisation :

Méthodes
directes de
Résolution
d’un Système
Linéaire
(1)
(2) (1) ai2 (1)
aij = aij − a
(1) 1j
, ∀i ∈ J3, nK, ∀j ∈ J2, n + 1K
Méthode de
Gauss
a22
Factorisation soit :
LU d’une
matrice
 
Factorisation a11 a12 a13 · · · a1n b1
et méthode de (1) (1) (1) (1)
0 a22 a23 · · · a2n b2
 
Cholesky  
(2) (2) (1)
 
Factorisation (2) 0 0 a33 · · · a3n b3
A =
 
QR et 
méthode de  .. .. .. .. 
Householder

 0 0 . . . . 

Décomposition (2) (2) (2)
LU 0 0 an3 · · · ann bn
 Triangularisation :

Méthodes
directes de
étape k : annuler les termes de la colonne k au dessous de la
Résolution
d’un Système
diagonale. C’est à dire, on annule les coefficients de la colonne
Linéaire k à partir de la k + 1 ligne. Les opérations à effectués sont
alors :
Méthode de
Gauss aik
Factorisation Li ← Li − Lk , ∀i ∈ Jk + 1, nK
LU d’une akk
matrice
donc chaque coefficient reçoit la transformation suivante :
Factorisation
et méthode de
Cholesky aik
Factorisation aij ← aij − akj , ∀i ∈ Jk + 1, nK, ∀j ∈ Jk, n + 1K
QR et akk
méthode de
Householder On note alors la matrice obtenue :
(k)
Décomposition A(k) = (aij )
LU
où la première ligne ne change pas :
(k) (k−1) (1)
a1j = a1j = · · · = a1j = a1j et les lignes jusqu’à k ne
changent pas c’est à dire garde les valeurs de la l’étape k − 1
(k) (k−1)
 Triangularisation :

Méthodes
directes de
Résolution
d’un Système (k−1)
Linéaire
(k) (k−1) aik (k−1)
aij = aij − a
(k−1) kj
, ∀i ∈ Jk +1, nK, ∀j ∈ Jk, n+1K
akk
Méthode de
Gauss

Factorisation
soit :
LU d’une
matrice

Factorisation
a11 a12 · · · ···
 
et méthode de a1k+1 a1n b1
Cholesky (1) (1) (1) (1)
 0 a22 · · · a2k+1 ··· a2n b2
 

Factorisation
QR et

.. .. .. .. 
 0 0 . . ··· . .
 
méthode de
A(k) = 

Householder (k) (k) (k) 

Décomposition
 0
 0 ··· ak+1k+1 ··· ak+1n bk+1 
LU
 .. .. .. .. 
 0 0 . . . ··· . 
 
(k) (k) (k)
0 0 ··· ank+1 ··· ann bn
 Triangularisation :

Méthodes
directes de
Résolution
d’un Système
étape n-1 : annuler les termes de la colonne n-1 au dessous de
Linéaire la diagonale. C’est à dire, on annule les coefficients de la
colonne n-1 à partir de la n ligne. Les opérations à effectués
Méthode de
Gauss
sont alors :
Factorisation
ann−1
LU d’une
matrice
Ln ← Ln − Ln−1
an−1n−1
Factorisation
et méthode de
Cholesky
donc chaque coefficient reçoit la transformation suivante :
Factorisation ann−1
QR et anj ← anj − an−1j ∀j ∈ Jn − 1, n + 1K
méthode de
Householder
an−1n−1
Décomposition On note alors la matrice obtenue :
LU (n−1)
A(n−1) = (aij )
où seule la ligne n change :
 Triangularisation :

Méthodes
directes de
Résolution
d’un Système (n−2)
Linéaire
(n−1) (n−2) ann−1 (n−2)
anj = anj − (n−2)
an−1j ∀j ∈ Jn − 1, n + 1K
an−1n−1
Méthode de
Gauss

Factorisation soit :
LU d’une
matrice

Factorisation
a11 a12 · · · ···
 
et méthode de a1k+1 a1n b1
Cholesky (1) (1) (1) (1)
 0 a22 · · · a2k+1 ··· a2n b2
 
Factorisation

QR et

.. .. .. ..
 0 0 . . ··· . .
 
méthode de
A(n−1) = 

Householder
(k) (k) (k)

Décomposition
 0
 0 ··· ak+1k+1 ··· ak+1n bk+1 

LU
 .. .. .. 
 0

0 ··· 0 . . .


(n−1) (n−1)
0 0 ··· 0 ··· ann bn
 Triangularisation :

Méthodes
directes de
La matrice est augmentée du second membre soit : A ← [A, b]
Résolution
d’un Système
Algorithme de la triangularisation :
Linéaire Données : A = (A[i, j]),
n : nombre de lignes,
Méthode de
Gauss n + 1 : nombre de colonnes.
Factorisation 1: Début
LU d’une
matrice 2: for k = 1 to n − 1 do
Factorisation
et méthode de
3: p ← A[k, k]
Cholesky
4: for i = k + 1 to n do
Factorisation
QR et 5: q ← A[i, k]
méthode de
Householder 6: A[i, k] ← 0
Décomposition 7: for j = k + 1 to n + 1 do
LU q
8: A[i, j] ← A[i, j] − A[k, j] · p
9: end for
10: end for
 Factorisation LU : Forme matricielle de la
triangularisation
Méthodes
directes de
• Si on a à résoudre plusieurs systèmes avec la même matrice :
Résolution
d’un Système
Linéaire Ax = b1 , · · · , Ax = bk .

Méthode de • On décompose A en produit de deux matrices triangulaires

Gauss
(U est supérieure et L inférieure) :
Factorisation
LU d’une
matrice A=L·U
Factorisation
et méthode de
Cholesky • Une résolution se fait grâce à deux systèmes triangulaires :
Factorisation
QR et
(
méthode de Lyk = bk
Householder Axk = bk ⇔
Décomposition
Uxk = yk
LU

. C’est la décomposition LU
• Il faut une triangulation pour « préparer » la matrice et deux
remontées par vecteur bk .
 Méthodes La méthode LU consiste à factoriser la matrice A sous forme :
directes de
Résolution
d’un Système
Linéaire   
l11 0 0 ··· 0 u11 u12 · · · ··· u1n
Méthode de
l21 l22

0 ··· 0   0 u22 · · ·

··· u2n 

A = LU = 
 .. .. .. .. .. 
 .
 .. .. .. .. 
.   ..
Gauss
 . . . . . . . . 

Factorisation
LU d’une ln1 ln2 · · · ··· lnn 0 0 0 ··· unn
matrice

Factorisation
et méthode de Le système initial Ax = b est un système de n équations à n
Cholesky
inconnues et le nombre des coefficients de A est n2 . Pourtant,
Factorisation
QR et si on compte le nomre de coefficients de L et U on trouve pour
méthode de
Householder chacune 1 + 2 + ....n = n(n+1)
2 donc la somme de nombres de
2
coefficients est : n + n pour que le problème soit bien posé il
Décomposition
LU
faut imposer n coefficients. On pose alors

lii = 1, ∀i ∈ {1, · · · , n}
 Méthodes
directes de
Résolution
d’un Système
Linéaire

Méthode de
Gauss
Or l’élimination de Gauss après l’étape n-1, la matrice A est
Factorisation transformée sous forme A(n−1) qui est triangulaire supérieure.
LU d’une
matrice
On pose alors U = A(n−1) .
Factorisation Une étape k de l’élimination de Gauss revient à multiplier la
et méthode de
Cholesky nouvelle matrice provenant de A par une matrice M (k) que l’on
Factorisation doit déterminer.
QR et
méthode de
Householder

Décomposition
LU
 Méthodes Exemple : triangularisation sous forme matricielle
directes de
Résolution Soit la matrice :
d’un Système
Linéaire  
1 2 3
A = 1 1 2
 
Méthode de
Gauss
1 1 1
Factorisation
LU d’une
matrice
Pour annuler les termes de la 1ère colonne en dessous de la
Factorisation
diagonale, on utilise la matrice élémentaire :
et méthode de
Cholesky    
1 0 0 1 0 0
Factorisation − a21
QR et E1 =  a11 1 0 = −1 1 0
 
méthode de
Householder − aa11
31
0 1 −1 0 1
Décomposition
LU Ainsi, en multipliant E1 A, on obtient :
 
1 2 3
E1 A = 0 −1 −1
 
0 −1 −2
 Méthodes Ensuite, on applique une seconde matrice élémentaire pour
directes de
Résolution annuler l’élément de la seconde colonne au dessous de la
d’un Système
Linéaire diagonale :
   
Méthode de
1 0 0 1 0 0
Gauss
E2 = 0 1 0 = 0 1 0 
  
Factorisation
LU d’une
0 − aa32
22
1 0 −1 1
matrice

Factorisation En multipliant E2 par E1 A, on obtient :

et méthode de
Cholesky  
Factorisation 1 2 3
QR et
E2 E1 A = 0 −1 −1 = U
 
méthode de
Householder
0 0 −1
Décomposition
LU
Les deux matrices L et U de la factorisation LU de A est
donnée par :
U = E2 E1 A, L = E1−1 E2−1 .
 Méthodes
directes de Il faut calculer E1−1 et E2−1
Résolution
d’un Système    
Linéaire 1 0 0 1 0 0
−1
E1 = −1 1 0 ⇒ E1 = 1 1 0
   
Méthode de
Gauss
−1 0 1 1 0 1
Factorisation
   
LU d’une ]1 0 0 ]1 0 0
matrice
E2 =  0 1 0 ⇒ E2−1 =  0 1 0
   
Factorisation
et méthode de 0 −1 1 0 1 1
Cholesky

Factorisation La factorisation LU est donnée par :

QR et
méthode de
Householder
   
Décomposition ]1 0 0 ]1 2 3
LU
L = E1−1 E2−1 =  1 1 0 , et U = E2 E1 A =  0 −1 −1
   
1 1 1 0 0 −1
 Méthodes
directes de
Résolution
d’un Système
Linéaire

triangularisation sous forme matricille

Méthode de
Gauss On considère la matrice A à factoriser sous forme LU :
Factorisation  
LU d’une a11 a12 · · · a1n
matrice 
 a21 a22 · · · a2n 

Factorisation
et méthode de
A= .. .. .. .. 
Cholesky

 . . . .


Factorisation an1 an2 · · · ann
QR et
méthode de
Householder

Décomposition
LU
 Méthodes
directes de étape 1 : On annule les coefficients de la première colonne à
Résolution
d’un Système partir de la deuxième ligne. On mutiplie alors la matrice A à
Linéaire
gauche par la matrice E1 = (eij1 )1≤i,j≤n .

1 0 0 ··· 0
Méthode de
 
Gauss

Factorisation

 − aa21
11
1 0 ··· 0 

LU d’une
− aa31 0 1 ··· 0
 
matrice E1 =  11


.. .. .. .. .. 
Factorisation
.
 
et méthode de
 . . . . 
Cholesky
− aan1
11
0 ··· ··· 1
Factorisation
QR et
méthode de ou encore sous forme :
Householder 
Décomposition 
 0 si i=6 j et j ∈ {2, · · · n}
LU
eij1 = 1 si i =j
 − ai1

si j = 1 et i ∈ {2, · · · n}
a11
 Méthodes étape 2 : La matrice A devient alors :
directes de
Résolution
d’un Système A ← E1 A
Linéaire
On annule les coefficients de la colonne 2 à partir de la ligne 3.
Méthode de On mutiplie alors la matrice A à gauche par la matrice
Gauss
E2 = (eij2 )1≤i,j≤n
Factorisation 
LU d’une
matrice 
 0 si i 6= j et j ∈ {3, · · · n}

 1 si i =j
Factorisation
et méthode de eij2 =
Cholesky 
 0 si j = 1 et i ∈ {2, · · · n}
 − ai2

si j = 2 et i ∈ {3, · · · n}
Factorisation a22
QR et
méthode de
0 ···
 
Householder 1 0 0
Décomposition

 0 1 0 ··· 0 

LU 
E2 =  0 − aa32
22
1 ··· 0 


.. .. .. . . .. 
. . . . .
 
 
0 − aan2
22
0 ··· 1
 Méthodes
directes de
Résolution
d’un Système étape k : La matrice A devient alors :
Linéaire

A ← Ek−1 A
Méthode de
Gauss

Factorisation
On annule les coefficients de la colonne k à partir de la ligne
LU d’une
matrice
k+1. On mutiplie alors la matrice A à gauche par la matrice
Factorisation
Ek = (eijk )1≤i,j≤n
et méthode de
Cholesky 
Factorisation

 0 si i 6= j et j ∈ {3, · · · n}

QR et  1 si i =j
méthode de
eijk =
Householder 
 0 si j ∈ {1, · · · , k − 1} et i ∈ {j + 1, · · · n}
− aakkik et i ∈ {k + 1, · · · n}

Décomposition
LU
 si j =k
 Méthodes
directes de
Résolution
d’un Système
Linéaire  
1 0 0 ··· ··· ··· ··· 0
Méthode de

 0 1 0 ··· ··· ··· ··· 0 

Gauss
0 0 1 0 ··· ··· ··· 0
 
 
.. .. .
Factorisation
 
. . 0 .. ··· ··· ···
 
LU d’une
matrice
 0 
.. .. ..
 
Ek = 
 
Factorisation
et méthode de  . . . 0 1 0 ··· 0 

.. .. .. ..
− ak+1k
Cholesky
 
 . . . . akk 1 ··· 0 
Factorisation
 
QR et
 .. .. .. .. .. .. 
méthode de

 . . . . . 0 . 0


Householder  .. 
Décomposition 0 0 0 . − aank
kk
0 ··· 1
LU
 Méthodes
directes de
Résolution
d’un Système
Linéaire étape n-1 : La matrice A devient alors :

Méthode de
A ← En−2 A
Gauss

Factorisation On annule les coefficients de la colonne n-1 à partir de la ligne

LU d’une
matrice n. On mutiplie alors la matrice A à gauche par la matrice
Factorisation
et méthode de
En−1 = (eijn−1 )1≤i,j≤n
Cholesky

Factorisation  0 si i 6= j
QR et 
méthode de
Householder
eijn−1 = 1 si i =j
 − ann−1

si i = n et j = n − 1
Décomposition an−1n−1
LU
 Méthodes
directes de  
Résolution 1 0 0 ··· 0
d’un Système
Linéaire
 .. 

 0 1 0 ··· . 

 .. .. 
Méthode de
En−1 = 
 . 0 . 0 

Gauss  .. .. .. 
. . . 1 0 
 
Factorisation 
LU d’une ann−1
matrice 0 0 0 − an−1n−1 1
Factorisation
et méthode de Factorisation LU
Cholesky
Après le produit matriciel, on obtient la matrice triangulaire
Factorisation
QR et supérieure :
méthode de
Householder En−1 En−2 · · · E2 E1 A = U
Décomposition
LU donc :

A = (En−1 En−2 · · · E2 E1 )−1 U = E1−1 E2−1 · · · En−1

−1
U
 Méthodes On sait que le produit et l’inverse d’une matrice inversible et
directes de
Résolution triangulaire inférieure est une matrice triangulaire inférieure.
d’un Système
Linéaire On pose alors :

Méthode de L = E1−1 E2−1 · · · En−1

−1
Gauss

Factorisation sachant que :

LU d’une
1 0 0 ··· 0
 
matrice
 a21 1 0 ··· 0 
Factorisation  a11 
et méthode de  a31
−1 0 1 ··· 0

Cholesky E1 =   a11

 .. .. .. .. .. 
Factorisation
.

QR et  . . . . 
méthode de an1
Householder 0 ··· ··· 1
 a11
0 0 ··· 0

Décomposition 1
LU

 0 1 0 ··· 0 

a32
0 a22 1 · · · 0
−1
 
E2 =  

.. .. .. . . . 
. . . . ..
 
 
 Méthodes
directes de
Résolution
d’un Système
Linéaire  
1 0 0 ··· ··· ··· ··· 0
Méthode de

 0 1 0 ··· ··· ··· ··· 0 

Gauss
0 0 1 0 ··· ··· ··· 0
 
 
.. .. .
Factorisation
 
. . 0 .. ··· ··· ···
 
LU d’une
matrice
 0 
.. .. ..
 
Ek−1 = 
 
Factorisation
et méthode de  . . . 0 1 0 ··· 0 

Cholesky
 .. .. .. .. ak+1k

 . . . . akk 1 ··· 0 
Factorisation
 
QR et
 .. .. .. .. .. .. 
méthode de

 . . . . . 0 . 0


Householder  . 
Décomposition 0 0 0 .. ank
akk 0 ··· 1
LU
 Méthodes
directes de
Résolution
d’un Système
Linéaire

 
Méthode de
Gauss
1 0 0 ··· 0
 .. 
Factorisation
LU d’une

 0 1 0 ··· . 

matrice −1 .. .
. 0 ..
 
En−1 = 0 
Factorisation
 
et méthode de
 .. .. .. 
. . . 1 0 
 
Cholesky 
ann−1
Factorisation 0 0 0 an−1n−1 1
QR et
méthode de
Householder

Décomposition
LU