Université Paris Sud Prépa agrèg : option B

Résolution des systèmes linéaires

Méthodes directes pour résoudre Ax = b

Cadre. On cherche les vecteurs x ∈ Kn solutions de Ax = b, avec A ∈ Mn (K) et b ∈ Kn (avec K = R

ou C).
— Si A est inversible, alors, il existe une unique solution x = A−1 b
— Si A est non inversible et si b ∈ Im(A) alors, il existe une infinité de solutions (qui diffèrent d’un
élément de ker(A))
— Si A est non inversible et si b ∈/ Im(A) alors, il n’y a pas de solution.
Nous nous restreindrons par la suite au cas où A est inversible.

Proposition 1. Formules de Cramer. (p.80 [Cia], Prop.5.1.1 [AK]) Soit A ∈ Mn (K) inversible et
a1 , ..., an ∈ Kn les colonnes de A :
A = (a1 |a2 |...|an ).
Soit b ∈ Kn . Alors l’unique solution x ∈ Kn du système Ax = b est donnée par x = (x1 , ..., xn ) avec

det ((a1 |...|ai−1 |b|ai+1 |...|an ))

xi = , ∀i ∈ {1, ..., n}.
det(A)

Remarque 1. Les formules de Cramer sont très peu adaptées au calcul sur ordinateur puisque calculer un
déterminant est très coûteux (le coût d’un déterminant n × n est cn = n(1 + cn−1 ) ≥ ncn−1 donc cn ≥ n!
et nous devons évaluer n + 1 déterminants donc le coût des formules de Cramer est de l’ordre de (n + 1)!).
(Ch.5 [AK]).

Remarque 2. Les méthodes directes reposent sur une décomposition de la matrice A en A = M N où M

est facile à inverser (triangulaire ou orthonormale) et N est triangulaire. On aura donc
(
M y = b,
Ax = b ⇔ M N x = b ⇔
N x = y.

Il faut donc savoir résoudre le système Ax = b lorsque A est triangulaire inférieure (ou supérieure) :
c’est l’algorithme de descente (ou de remontée).

Proposition 2. Algorithme de descente. (p. 89 [Ser]) Soit A triangulaire inférieure et inversible (i.e
ai,i 6= 0, ∀i ∈ {1, ..., n})  
a1,1 0 0
 a2,1 a2,2 0 
A= . .
 
 .. ..
. 0 
an,1 an,2 . . . an,n
La solution x de Ax = b est alors donnée par

b
 x1 = 1 ,

a1,1


Pi−1
 bi − j=1 ai,j xj
 xi = , pour i ∈ {2, ..., n}.


ai,i

Remarque 3. Si A est triangulaire supérieure, on trouve xn en premier puis on en déduit xn−1 , xn−2 , ..., x1 ,
il s’agit de l’algorithme de remontée. (§4.1 [Cia]).

Année 2017-2018 1 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

1 Méthode de Gauss
1.1 Opérations élémentaires sur les lignes
Remarque 4. Matrices de dilatation. Pour λ ∈ K∗ et p ∈ {1, ..., n}, la matrice de dilatation Dp (λ) est
définie par  
1 p 0
 .. 
 . ↓ 
 

 1 

Dp (λ) = 
 λ ← p .

 1 

 .. 
 0 . 
1
Pour toute matrice M ∈ Mn (K), la multiplication à gauche par la matrice Dp (λ) multiplie la ligne p de M
par λ.
Matrices de transposition. Pour (p, q) ∈ {1, ..., n}2 , la matrice de transposition Pp,q (cas particulier
d’une matrice de permutation) est définie par
 
1 p q
 .. 
 . ↓ ↓ 
 

 1 


 0 1 ← p 
 1 
Pp,q =  .
 
. .

 . 


 1 


 1 0 ← q 
 .. 
 . 
1

Pour toute matrice M ∈ Mn (K), la multiplication à gauche par la matrice de transposition Pp,q inverse les
lignes p et q de la matrice.
Matrices de transvection. Pour (p, q) ∈ {1, ..., n}2 et λ ∈ K∗ on appelle la matrice de transvection,
la matrice suivante  
1 q
 .. 

 . ↓ 

Tp,q (λ) = 
 .. .

 . λ ← p 
 .. 
 . 
1
Pour toute matrice M ∈ Mn (K), la multiplication à gauche par la matrice Tp,q (λ) change Lp , la p-ième
ligne de M , en Lp + λLq .

Proposition 3. La matrice de transvection Tp,q (λ) est inversible, d’inverse Tp,q (λ)−1 = Tp,q (−λ).

Définition 1. On appelle opération élémentaire sur les lignes une application de la forme Mn (K) 3 M 7→
U M où U est une matrice de transvection, transposition ou dilatation.

1.2 La méthode de Gauss

Théorème 1 (Thm 4.2-1 [Cia], Thm 6.1.1 [AK]). Soit A ∈ Mn (K) (inversible ou non) alors il existe (au
moins) une matrice M ∈ Gln (K), produit de matrices de transposition et de transvection, telle que M A soit
triangulaire supérieure.

Année 2017-2018 2 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Remarque 5. Pour obtenir que M A soit une matrice triangulaire inférieure, il faudrait raisonner sur des
opérations élémentaires sur les colonnes.

Démonstration du Théorème 1. L’idée est de construire en n − 1 étapes une suite de matrices Ai ayant
toutes des zéros en dessous de la diagonale dans les i premières colonnes.
Initialisation : On pose A0 = A.
Étape i, i ≥ 1 : On suppose qu’à la fin de l’étape i − 1, on a construit une matrice Ai−1 telle que

Ai−1
k,j = 0, si k > j, pour tout j ∈ {1, ..., i − 1}.

Les coefficients de Ai−1 sont bien nuls au dessous de la diagonale dans les i − 1 premières colonnes.

∗
 
..
. ∗
 
 
∗
 
 
i−1 Ai−1
 
A = i,i

i−1
 

 0 Ai+1,i ∗ 

 .. 
 . 
Ai−1
in,i

• Si A est inversible.
i−1
1. Si Ai,i = 0, on choisit j > i tel que Ai−1
j,i 6= 0 (un tel j existe puisque sinon, la i-ème ligne serait
combinaison linéaire des i − 1 premières lignes et la matrice A ne serait pas inversible). On choisit
ce Ai−1
j,i comme pivôt et on échange les lignes i et j de A
i−1 : L ↔ L .
i j
Du point de vue matriciel, cela revient à multiplier la matrice Ai−1 par la matrice de transposition
Pi,j . On notera P i cette matrice : P i = Pi,j .
(par la suite Lj , Li , Ai−1 i−1
i,i , Aj,i seront les lignes et les coefficients de la matrice A
i−1 après cette

étape de permutation).
Ai−1
2. On fait la somme de chaque ligne Lj de Ai−1 avec − j,i
i−1 Li pour j > i
Ai,i

Ai−1
j,i
Lj → Lj − Li , ∀j > i.
Ai−1
i,i

Du point de vue matriciel, cela revient à multiplier Ai−1 à gauche par une somme de matrices de
Ai−1
transvection nj=i+1 Tj,i (− j,i i
P
i−1 ). Notons E cette matrice
Ai,i

 
1
 ..
.


 0 

n i−1
 1 
i
X Aj,i 
Ai−1

E = Tj,i (− i−1 ) =  − i+1,i .
 
i−1 1
j=i+1
A i,i
 Ai,i 
 .. .. 
0

. . 

 Ai−1 
− n,i
i−1 1
Ai,i

À la fin de l’étape i, nous obtenons une matrice

Ai = E i P i Ai−1 = E i P i ...E 1 P 1 A.
i−1
• Si A est non inversible, alors les éléments Aj,i , j > i, sont tous égaux à 0 pour au moins un i. Dans ce
cas, la matrice A i−1 est déjà sous la forme souhaitée et on pose P i = E i = In , la matrice identité.

Année 2017-2018 3 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

A la fin des n − 1 étapes : on aura obtenu une matrice

An−1 = E n−1 P n−1 ...E 1 P 1 A

triangulaire supérieure.
On pose M = E n−1 P n−1 ...E 1 P 1 et on a
• M A triangulaire supérieure par construction
• M inversible et det(M ) = ±1 selon le nombre de permutations de deux lignes effectuées (det(M ) = 1 si
le nombre de permutations est pair et det(M ) = −1 si ce nombre est impair).

Remarque 6. Attention, en pratique, on ne calcule pas les E i et P i (et on ne les stocke pas même si ce
sont des matrices creuses !), on implémente directement la transformation sur les lignes Li .
Pour résoudre Ax = b, il suffit de résoudre An−1 x = M b par l’algorithme de remontée (pour calculer M b,
i−1
Aj,i
on effectue les mêmes opérations d’échanges de lignes et de multiplications par − sur le vecteur b). Si A
Ai−1
i,i
n’est pas inversible, on pourra toujours écrire la décomposition An−1 x = M b, mais il n’y aura pas forcément
de solution.

2 Décomposition LU
Objectif. Décomposer la matrice A en produit de deux matrices triangulaires, et ainsi ramener le
système Ax = b à la résolution de deux systèmes triangulaires.
Nous verrons que cela revient à appliquer la méthode de Gauss sans l’étape de permutation des lignes
(puisqu’on suppose des hypothèses supplémentaires sur la matrice A).
Définition 2. Soit A ∈ Mn (K). On appelle sous-matrice d’ordre k de A la matrice ∆k ∈ Mk (K) construite
à partir de A par
∆ki,j = Ai,j , ∀(i, j) ∈ {1, ..., k}2 .
On appelle «mineur principal» d’ordre k de A le déterminant det(∆k ).
Théorème 2 (Thm 4.3-1 du [Cia], Thm 8.1.1 [Ser], Thm 6.2.1 [AK]). Soit A ∈ Mn (K). Si toutes les
sous-matrices ∆k d’ordre k de A sont inversibles alors il existe un unique couple (L, U ) de matrices avec
L ∈ Mn (K) triangulaire inférieure à diagonale unitaire (i.e Li,i = 1) et U ∈ Mn (K) triangulaire supérieure
tels que A = LU .
Remarque 7. L’appellation «décomposition LU » vient de la forme des matrices
L = "lower triangular matrix" et U = "upper triangular matrix".
Remarque 8. En particulier, si A est une matrice symétrique définie positive (i.e xT Ax > 0 pour x 6= 0)
alors A vérifie bien les hypothèses du théorème de décomposition LU : det(∆k ) 6= 0 pour tout k ∈ {1, ..., n}
(on a même det(∆k ) > 0 dans ce cas particulier, la preuve se trouve à l’exercice 4 p.247 [Gou]).
Démonstration du Théorème 2. Unicité : Supposons (L1 , U1 ) et (L2 , U2 ) comme dans le théorème 2. On a
donc
A = L1 U1 = L2 U2 . (1)
Pour j ∈ {1, 2}, (Lj )i,i = 1 et Lj est triangulaire (inférieure) donc Lj est bien inversible. De même, A = ∆n
qui est bien supposé inversible donc Uj = L−1 j A est bien inversible pour j ∈ {1, 2}. L’équation (1) implique
donc
L−1
2 L1 = U2 U1 .
−1

Comme L−1 −1 −1 −1
2 L1 est triangulaire inférieure et U2 U1 est triangulaire supérieure, on a que L2 L1 et U2 U1
sont diagonales.
Mais L1 et L2 sont à diagonale unitaire donc L−1 2 L1 est, elle aussi, à diagonale unitaire. Donc

U2 U1−1 = L−1
2 L1 = In .

Année 2017-2018 4 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Ainsi L1 = L2 et U1 = U2 , d’où l’unicité de la décomposition.

Existence : Supposons que, au cours de l’algorithme de Gauss, il n’y ait pas besoin de changer de pivôt
i−1
(i.e Ai,i 6= 0, tous les pivots naturels sont non nuls). On montre alors avec la méthode de Gauss que
la matrice An−1 = E n−1 ...E 1 A (pas besoin des matrices de permutation P i ) est une matrice triangulaire
supérieure, avec la matrice E i définie précédemment à l’algorithme de Gauss.
Soit
−1
U = An−1 et L = E n−1 ...E 1 .
Alors, U est triangulaire supérieure et A = LU . Il nous reste à vérifier que L est une matrice triangulaire
inférieure à diagonale unitaire.
Ai−1
Par définition de E i , on a E i = nj=i+1 Tj,i (− j,i
P
i−1 ). D’après la proposition 3, on montre facilement que
Ai,i
E i est inversible, d’inverse
n i−1
!
X Aj,i
(E i )−1 = Tj,i i−1
j=i+1
Ai,i
 
1
 ..
.


 0 

 1 
Ai−1
 
= i+1,i
.
 
1
 Ai−1
i,i 
 .. .. 
0

. . 

 Ai−1
n,i

1
Ai−1
i,i

Ainsi, en notant Cki la k-ième colonne de la matrice (E i )−1 , nous avons

 
1
∗ 1 0 
 
n−1 1 −1 1 −1 2 −1 n−1 −1 .


E ...E = (E ) (E ) ...(E ) = C C 2 . . .
 1 
 1 2 
∗ ∗ ∗ 1 
n−1
∗ ∗ ∗ Cn−1 1
La matrice L est donc triangulaire inférieure et Li,i = 1, ∀i ∈ {1, ..., n}.
Montrons que tous les pivôts «naturels» sont effectivement non nuls : Il faut montrer (par récurrence
sur k) que l’hypothèse det(∆k ) 6= 0 pour tout k ∈ {1, ..., n} implique que les pivôts de chaque étape sont
non nuls.
• Initialisation : Pour k = 1, det(∆1 ) 6= 0 signifie que A01,1 = A1,1 6= 0. Donc le pivôt de la première
étape A01,1 est non nul.
• Soit i ∈ J1, nK. Supposons l’hypothèse de récurrence : «det(∆k ) 6= 0, ∀k = 1, ..., i − 1 implique que
tous les pivôts jusqu’à l’étape i − 1 sont non nuls.» Alors montrons que «si det(∆k ) 6= 0, ∀k = 1, ...i alors le
pivôt de l’étape i est non nul.»
Puisque det(∆k ) 6= 0 pour tout k ∈ {1, ..., i − 1} (entre autre), on a pu construire par hypothèse de
récurrence une matrice Ai−1 telle que
Ai−1 = E i−1 ...E 1 A.
C’est-à-dire
∗
   
1
 .. | ∗
 
. ∗
  ..
 ∗ .

 0  ∆i |
∗
   
  C 1 ∗ 1
 
  1  − − Ai,i

 i−1 
 Ai,i =∗ ∗ ∗ 1  .
i−1
   
0 Ai+1,i ∗  i−1

∗ ∗ Ci−1 1
 
    
 .
.
 
∗ ∗ ∗ 0 1

. ∗ ∗
   
i−1
Ain,i ∗ ∗ ∗ 1

Année 2017-2018 5 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

En posant M i−1 = E i−1 ...E 1 , on a donc en considérant les matrices précédentes par blocs
 i−1   i−1  i 
(A )1,..,i ∗ (M )1,...,i 0 ∆ ∗
= .
∗ ∗ ∗ In−i ∗ ∗

On a donc : det ∆i det(M i−1 )1,...,i = det(Ai−1 )1,...,i . Puisque det ∆i 6= 0 par hypothèse et det(M i−1 )1,...,i =

1, alors det(Ai−1 )1,...,i est lui aussi non nul.

j−1
Or det(Ai−1 )1,...,i = ij=1 Ai−1
Q Qi i−1
j,j = j=1 Aj,j 6= 0 Donc Ai,i 6= 0 et ainsi, le pivôt de l’étape i est bien
non nul.

Remarque 9. Lorsque la matrice A est tridiagonale (et qu’elle vérifie les hypothèses du théorème 2) alors
les matrices L et U sont des matrices bandes. (p.85 [Cia]).

3 Décomposition de Cholesky
Dans cette section, K = R et on se restreindra à des matrices A symétriques définies positives. Pour
de telles matrices, on a vu précédemment qu’une décomposition LU existait, mais il existe une décomposi-
tion «plus simple» dans le sens où elle ne fait intervenir qu’une seule matrice : la décomposition de Cholesky.

Rappel. Une matrice A est dite symétrique définie positive si et seulement si xT Ax > 0 pour tout x 6= 0
(la forme quadratique définie par A est strictement positive).

Théorème 3 (Thm 4.4-1 [Cia], Thm 8.2.1 [Ser], Thm 6.3.1 [AK]). Soit A ∈ Mn (R) symétrique définie
positive, alors il existe une unique matrice B ∈ Mn (R) triangulaire inférieure avec des éléments diagonaux
strictement positifs telle que A = BB T .

Remarque 10. Attention, ne marche que si A est symétrique définie positive !

Démonstration du Théorème 3. Existence : La matrice A étant symétrique définie positive, ses mineurs
principaux sont tous strictement positifs (voir remarque 8), elle admet donc une décomposition LU .
On a donc
 
1
| ∗
   
U1,1
∆i   1 0
 
 |  U2,2 ∗ 

− − Ai,i
  . ..  
   . . 
 =  . .
   ..   
   .  . . 
    0 . 
 ∗ 1 
∗ ∗ Un,n
1

En regardant les blocs en haut à gauche de chaque matrice (argument déjà utilisé dans la preuve de la
décomposition LU ) nous avons l’égalité des déterminants
i
Y
Uj,j = det(∆i ) > 0.
j=1

Donc par récurrence, chaque Ui,i est strictement positif, on peut donc définir la matrice (inversible) D
suivante : p p p
D = diag( U1,1 , U2,2 , ..., Un,n ).
−1
On a A = |{z}
LD D | {z U}.
=B =C
Montrons que C = B T : Par hypothèse sur A, on a A = AT et en même temps A = BC. Donc

BC = C T B T =⇒ (C T )−1 B = B T C −1 .

Année 2017-2018 6 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Or (C T )−1 B est une matrice triangulaire inférieure et B T C −1 est une matrice triangulaire supérieure. Ainsi
(C T )−1 B et B T C −1 sont toutes deux des matrices diagonales.
Or nous avons, pour tout i ∈ J1, nK,
p
Bi,i = Ui,i (puisque Li,i = 1)

et
−1 Ui,i p
Ci,i = Di,i Ui,i = p = Ui,i .
Ui,i
Donc (C T )i,i = Ui,i et (C T )−1 √1 , pour tout i ∈ {1, ..., n}.
p
i,i = Ui,i
Ainsi nous obtenons
n
X
T −1
((C ) B)i,i = (C T )−1
i,k Bk,i
k=1
n
X
= (C T )−1
i,k Bk,i (car B est triangulaire inférieure)
k=i
= (C T )−1
i,i Bi,i (car (C T )−1 est triangulaire supérieure)
= 1.

Donc C T = B et ainsi la matrice A se décompose en A = BB T .

Unicité : Supposons qu’il existe deux décompositions de Cholesky de la matrice : A = B1 B1T = B2 B2T .
On obtient ainsi B2−1 B1 = B2T (B1T )−1 avec B2−1 B1 une matrice triangulaire inférieure et B2T (B1T )−1
une matrice triangulaire supérieure. Donc ces deux matrices sont en réalité diagonales et on note D cette
matrice diagonale : B2−1 B1 = D =⇒ B1 = B2 D.
La décomposition de Cholesky donne B2 B2T = A = B1 B1T = (B2 D)(B2 D)T = B2 (DDT )B2T . Ainsi
DDT = In (donc Di,i = ±1) et l’hypothèse que les coefficients diagonaux de B1 et de B2 sont strictement
positifs implique que D = In .
Nous avons donc prouvé que B1 = B2 D = B2 , d’où l’unicité de la décomposition de Cholesky.

Remarque 11. En pratique, on ne calcule pas la factorisation de Cholesky à partir de la décomposition LU

comme fait dans la preuve précédente, mais on la calcule directement à partir de la matrice A (voir p.88
[Cia] ou §6.3.1 [AK]).

Remarque 12. Il existe une décomposition de Cholesky lorsque A est une matrice hermitienne définie
positive (K = C). Les coefficients de la matrice B sont alors complexes sauf les coefficients diagonaux (qui
restent réels positifs). (p. 96 [Ser]).

4 Factorisation QR
Principe. C’est la décomposition de A en une matrice unitaire Q et une matrice triangulaire supérieure
R. L’avantage de la décomposition QR c’est qu’elle s’applique à toutes matrices (pas de contrainte sur les
mineurs principaux comme pour LU ni sur le caractère symétrique défini positif comme pour Cholesky).
Cette méthode peut même s’appliquer sur des matrices non carrées. L’inconvénient de cette méthode est
qu’elle est «moins efficace» que les décompositions LU ou de Cholesky (car Q est une matrice unitaire et
non triangulaire).

Définition 3. Une matrice Q ∈ Mn (R) est dite orthogonale (ou unitaire) si et seulement si Q−1 = QT .
Une matrice Q ∈ Mn (C) est dite unitaire si et seulement si Q−1 = Q∗ = Q̄T .

Théorème 4 (Thm 4.5-2 [Cia], Prop 8.3.1 [Ser], Thm 6.4.1 [AK]). Soit A ∈ Mn (K) inversible. Alors
il existe un unique couple (Q, R) avec Q unitaire, R triangulaire supérieure à diagonale positive, tel que
A = QR.

Année 2017-2018 7 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Remarque 13. Résoudre le système Ax = b revient alors à résoudre Rx = QT b au moyen d’un algorithme
de remontée.
Démonstration du Théorème 4. Il existe une preuve de la décomposition QR se basant sur le procédé d’or-
thonormalisation de Gramm-Schmidt dans Cn (p. 97 [Ser], p.117 [AK]). Mais nous lui préfèrerons la mé-
thode de Householder développée ci-après (puisque c’est elle qu’on codera en pratique). Cette méthode de
Householder consiste à multiplier la matrice A par une succession de matrices unitaires (les matrices de
Householder) pour rendre A progressivement triangulaire supérieure.

Remarque 14. Lorsque la matrice A n’est pas inversible, il existe une décomposition QR mais elle n’est
pas unique (p.98 [Ser]).

4.1 Algorithme de Householder

Pour simplifier, on prend K = R dans ce paragraphe mais l’algorithme marche aussi dans C.
Définition 4. Soit v ∈ Rn \{0} (vecteur colonne), la matrice de Householder associée à v est définie par

2vv T
Hv = In − ∈ Mn (R).
||v||2
Remarque 15. Le vecteur v étant un vecteur colonne, v T est un vecteur ligne. Le produit vv T est donc une
matrice n × n dont le coefficient d’indice (i, j) s’écrit vi vj .
Remarque 16. Si v = 0 ∈ Rn , alors H0 = In (la matrice identité est donc considérée comme une matrice
de Householder).
Proposition 4 (Lem 7.3.1 [AK], Thm 4.5-1 [Cia]). Soit v ∈ Rn ,
• la matrice de Householder Hv est symétrique et orthogonale.
• Soit ei le ième vecteur de la base canonique de Rn , on a Hv±||v||ei v = ∓||v||ei (attention, au changement
de signe).
Démonstration de la proposition 4. • Le coefficient d’indice (i, j) de la matrice Hv vaut
2vi vj
(Hv )i,j = δi,j − = (Hv )j,i .
||v||2
Ainsi la matrice Hv est bien symétrique.
• Puisque Hv est symétrique, nous avons
2vv T 2vv T
  
HH T = HH = In − I n −
||v||2 ||v||2
4vv T 4(vv )(vv T )
T
= In − +
||v||2 ||v||4
4vv T 4v(v T v)v T
= In − + .
||v||2 ||v||4

Puisque v T v = ||v||2 , nous obtenons

4vv T 4v||v||2 v T
HH T = In − + .
||v||2 ||v||4

Ainsi, HH T = In et H est bien une matrice orthogonale.

• Soit ei le ième vecteur de la base canonique de Rn , nous posons w = v ± ||v||ei . Alors soit w est le vecteur
nul et dans ce cas Hw v = v (d’après la remarque 16). On a alors Hw v = v = w ∓ ||v||ei = ∓||v||ei .
Soit w est un vecteur non nul, dans ce cas,
2wwT 2(v ± ||v||ei )(v T v ± ||v||v) 2(v ± ||v||ei )(||v||2 ± ||v||vi )
Hw v = v − 2
v=v− 2
=v− .
||w|| ||v ± ||v||ei || ||v ± ||v||ei ||2

Année 2017-2018 8 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Or ||v ± ||v||ei ||2 = 2||v||2 ± 2||v||vi , donc

Hw v = v − (v ± ||v||ei ) = ∓||v||ei .

Algorithme de Householder. (p.138 [AK], p.91-92 [Cia])

Étape 1 : On pose A1 = A. Soit a1 ∈ Rn la première colonne de A1 .
 
α
0
— Si a1 =  . , on pose H 1 = In .
 
 .. 
0
— Sinon, on pose H 1 = Ha1 +||a1 ||e1 (où e1 est le premier vecteur de la base canonique de Rn ).
 
−||a1 || ∗
 0 ∗ 
On définit A2 = H 1 A1 qui est donc de la forme  .  d’après la proposition 4.
 
 . . ∗ ∗
0 ∗
Étape k : On suppose qu’à la fin de l’étape k − 1, on a obtenu Ak où les k − 1 premières colonnes sont
nulles sous la diagonale  
∗
 ..
.

 ∗ 
Akk,k
 
 
k
 
A = 
.

 .
. 

 0 . ∗ 
 
∗
 k 
Ak,k
 .. 
On considère ak =  .  ∈ Rn−(k−1) .
Ak
  n,k
α
0
— Si ak =  . , on pose H k = In .
 
 .. 
0
 
Ik−1 0
— Sinon, on pose H k =  , où e1 est le premier vecteur de la base canonique de
0 Hak +||ak ||e1
R n−(k−1) .
On définit Ak+1 = H k Ak , qui est bien de la forme souhaitée : la colonne k est nulle sous la diagonale.
 k 
A1,k
k
  A2,k 

Ak1,k
 
 .. 
 Ak2,k   . 


  k
Ak−1,k 

En effet, la k ième-colonne de A k+1 vaut 
 .
.. =
   , (et les k − 1 premières colonnes
  −||ak ||
 Ak   
k−1,k  0 

Hak +||ak ||e1 ak
 ... 
 

0
sont inchangées).
À la fin de n − 1 étapes, on a une matrice

An = H n ...H 1 A

Année 2017-2018 9 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

triangulaire supérieure, donc

−1
A = H n ...H 1 An ,
| {z } |{z}
=Q =R

avec Q orthogonale car chaque H k l’est (voir proposition 4) et R triangulaire supérieure.

Pour imposer aux coefficients diagonaux de R d’être tous positifs ou nuls on pose D la matrice diagonale
telle que Di,i = ±1 pour que R̃ = D−1 R avec R̃ une matrice triangulaire supérieure à diagonale positive.
Alors Q̃ = QD est encore une matrice orthogonale et A = Q̃R̃.

Remarque 17. Nous n’avons pas encore utilisé le caractère inversible de la matrice A (il sera primordial
pour l’uncité des matrices Q et R). La décomposition QR existe donc pour une matrice A non inversible (et
non carrée).

Démonstration de l’unicité de R et Q dans le cas où A est inversible. Si la matrice A est inversible, on

peut imposer à la matrice R d’être à diagonale strictement positive et dans ce cas, R sera inversible. Soit
deux telles décompositions Q1 R1 et Q2 R2 (avec R1 et R2 inversibles à diagonale sctrictement positive) :

A = Q1 R1 = Q2 R2 .

On a QT2 Q1 = R2 R1−1 . Notons T cette matrice, on a

T T T = QT1 Q2 QT2 Q1 = In puisque Qi est orthogonale.

Or Ri est triangulaire supérieure, donc T l’est aussi. De plus on a (R1 )i,i > 0 et (R2 )i,i > 0 donc Ti,i =
(R2 )i,i
(R1 )i,i > 0. L’égalité précédente n’est donc rien d’autre qu’une décomposition de Cholesky de la matrice
identité. Par unicité d’une telle décomposition, on a T = In et donc R1 = R2 . On en déduit alors facilement
que Q1 = Q2 .

Année 2017-2018 10 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Résolution des systèmes linéaires

Méthodes itératives pour résoudre Ax = b

Cadre. Les méthodes directes donnent des solutions exactes de Ax = b mais le calcul est souvent assez
coûteux (par exemple si la matrice est pleine ou si elle est de grande taille). L’idée des méthodes itératives
est de construire une suite de vecteurs (xk )k ∈ Kn qui converge vers la solution x de Ax = b.
Remarque 18. Les méthodes itératives que nous étudierons ici sont toutes basées sur une décomposition
de la matrice A en A = M − N avec M une matrice inversible (et facilement inversible, par exemple M
diagonalisable ou M triangulaire). On a alors
Ax = b ⇔ (M − N )x = b
⇔ Mx = Nx + b
⇔ x = M −1 N x + M −1 b.
Cette forme suggère d’étudier les points fixes de la fonction
y ∈ Kn 7→ M −1 N y + M −1 b.

5 Principe des méthodes itératives

Définition 5 (Def 8.1.1 [AK]). Soit A ∈ Mn (K) une matrice inversible (pour que la matrice M soit elle-
aussi inversible).
• Une paire de matrices (M, N ) avec M facilement inversible satisfaisant
A=M −N
est appellée une décomposition régulière de A.
• La méthode itérative basée sur la décomposition régulière A = M − N , M, N ∈ Mn (K) est donnée par la
suite (
x0 ∈ Kn quelconque,
(2)
xk+1 = M −1 N xk + M −1 b.
• La matrice B = M −1 N est appellée matrice de la méthode itérative.
Remarque 19. Si la suite (xk )k admet une limite x alors cette limite sera forcément solution de Ax = b
(par l’unicité de la solution puisque A est inversible).
Définition 6. • La méthode itérative est dite convergente si ∀x0 ∈ Kn , la suite (xk )k définie par (2)
converge.
• On appelle l’erreur à l’itération k la différence ek = ||xk − x||.
• On appelle le résidu à l’itération k la valeur rk = ||Axk − b||.
Une question à se poser en pratique est de savoir quand arrêter la méthode itérative (on parle de critère
d’arrêt). En toute généralité, il faudrait arrêter la méthode lorsque l’erreur ek est petite, mais on ne connait
pas x ce qui rend ce critère d’arrêt inutilisable. La convergence en pratique est déterminée grâce au critère
d’arrêt sur le résidu rk .
Théorème 5. Critères de convergence. (Thm 8.1.1 [AK], Thm 5.1-1 [Cia], Prop 9.1.1 [Ser]). Soit la
méthode itérative donnée par la suite (2), de matrice B = M −1 N . Alors, les trois propositions suivantes
sont équivalentes :
• la méthode itérative converge,
• le rayon spectral de la matrice B vérifie
ρ(B) < 1,
• on a |||B||| < 1 pour au moins une norme matricielle ||| · |||.

Année 2017-2018 11 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Rappel. Le rayon spectral ρ(A) d’une matrice A est défini par ρ(A) = max |λi | où les λi sont les
i∈J1,nK
valeurs propres complexes (comptées avec multiplicité) de la matrice A.
De plus le rayon spectral vérifie les deux inégalités suivantes : (Thm 1.4-3 [Cia], Prop 3.1.4 [AK], Cor
4.4.1 [Ser])
1. Pour toute matrice A ∈ Mn (K) et pour toute norme matricielle |||·||| sur Mn (K), on a ρ(A) ≤ |||A|||.
2. Pour tout  > 0 et pour toute matrice A ∈ Mn (K), il existe une norme matricielle ||| · ||| (qui dépend
de A) telle que |||A||| ≤ ρ(A) + .
Démonstration du rappel. • Soit A ∈ Mn (K) et ||| · ||| une norme matricielle. Si la norme est subordonnée
à une norme vectorielle, alors |||A||| = sup ||Ax|| n
||x|| . Soit λ ∈ K tel que |λ| = ρ(A) et soit u un vecteur
x∈Kn \{0}
propre associé. Alors on a ρ(A)||u|| = ||λu|| = ||Au|| ≤ |||A|||.||u||.
Si la norme est non subordonnée à une norme vectorielle. On prend λ ∈ Kn et u comme précédemment.
On choisit aussi un vecteur v ∈ Kn tel que uv ∗ 6= 0 ∈ Mn (K). Alors |λ||||uv ∗ ||| = |||λuv ∗ ||| = |||Auv ∗ ||| ≤
|||A|||.|||uv ∗ ||| (car ||| · ||| est une norme matricielle).

• Soit A ∈ Mn (K). Il existe U inversible tel que U −1 AU = T où T est une matrice triangulaire avec Ti,i
les valeurs propres de A, pour i ∈ {1, ..., n}.
Soit δ > 0, on définie la matrice Dδ diagonale suivante Dδ = diag(1, δ, δ 2 , ..., δ n−1 ) et on montre que
. . . δ n−1 T1,n
 
T1,1 δT1,2

 T2,2 δT2,3 . . . δ n−2 T2,n  
.. ..
(U Dδ )−1 A(U Dδ ) = 
 
 . . .

 . . .
. 
 0 . . 
Tn,n
Définissions la norme suivante :
n
X
−1
|||A|||δ = ||(U Dδ ) A(U Dδ )||∞ = max |(U Dδ )−1 A(U Dδ )|i,j .
i∈J1,nK
j=1
Pn j−1 T |
Soit  > 0 fixé, il ne nous reste plus qu’à choisir δ > 0 tel que j=1 |δ i,j ≤  et on aura dans ce cas
|||A|||δ ≤ ρ(A) + .

Démonstration du Théorème 5. Par définition, la méthode itérative converge si et seulement si, pour tout
x0 ∈ Kn , nous avons xk −→ x, avec nécessairement Ax = b (soit x = M −1 N x + M −1 b). C’est-à-dire, si
k→+∞
et seulement si, pour tout e0 ∈ Kn donné, ek = xk − x −→ 0.
k→+∞
Or xk+1 = M −1 N xk + M −1 b ce qui implique que
xk+1 − x = M −1 N xk + M −1 b − x = M −1 N xk + M −1 b − M −1 N x − M −1 b = M −1 N (xk − x).
Ainsi, ek −→ 0 si et seulement si (M −1 N )k+1 −→ 0 (pour une certaine norme matricielle) ce qui
k→+∞ k→+∞
est équivalent aux deux propositions suivantes :
• ρ(M −1 N ) < 1,
• |||M −1 N ||| < 1 pour au moins une norme matricielle ||| · |||, d’après le rappel précédent.

Remarque 20. Les méthode itératives reposent sur la recherche des points fixes de
F : y ∈ Kn 7→ M −1 N y + M −1 b
par la méthode des approximations successives (ou méthode de Picard). Nous savons que cette méthode de
Picard converge si F est contractante ce qui revient à supposer |||M −1 N ||| < 1 comme dans le théorème 5.
Il n’est donc pas étonnant que la méthode itérative converge si et seulement si cette condition est respectée
(voir p.96 [Cia]).

Année 2017-2018 12 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

5.1 Condition suffisante de convergence pour les matrices hermitiennes définies posi-
tives
Dans certains cas, il n’est pas nécessaire de calculer le rayon spectral de la matrice B pour savoir s’il y
a convergence ou pas. C’est le cas notamment des matrices hermitiennes définies positives, comme expliqué
dans le théorème suivant.

Théorème 6 (Thm 8.1.2 [AK], Thm 5.3-1 [Cia], Lem 9.3.1 [Ser]). Soit A une matrice hermitienne définie
positive et M, N telles que A = M − N avec M inversible. Alors, si la matrice M ∗ + N , qui est hermitienne,
est aussi définie positive, la méthode itérative de matrice M −1 N converge.

Démonstration du théorème 6. Matrice hermitienne : La matrice M ∗ + N est bien hermitienne car A est
hermitienne, donc A = A∗ soit encore (M − N )∗ = M − N . Donc M ∗ − N ∗ = M − N donc M ∗ + N =
M + N ∗ = (M ∗ + N )∗ .
Condition du théorème 5 vérifiée : On montre que si M ∗ + N est définie positive alors, il existe une
norme matricielle ||| · ||| telle que |||M −1 N ||| < 1. p
Puisque A est hermitienne définie positive, on peut définir une norme sur Kn par ||x||A = hAx, xi.
Soit ||| · |||A la norme matricielle subordonnée à || · ||A . Par définition, on a donc |||M −1 N |||A =
sup ||M −1 N x||A . Soit x ∈ Kn tel que ||x||A = 1 alors hAx, xi = 1 et on a
||x||A =1

||M −1 N x||2A = A(M −1 N x), M −1 N x

= A(M −1 (M − A)x), M −1 (M − A)x (définition de N )
−1 −1
= Ax − AM Ax, x − M Ax
−1
= hAx, xi − AM Ax, x − Ax, M −1 Ax + AM −1 Ax, M −1 Ax .

En notant v = M −1 Ax on a M v = Ax et donc les égalités précédentes deviennent

||M −1 N x||2A = 1 − hAv, xi − hM v, vi + hAv, vi (car x est choisi tel que hAx, xi = 1)
= 1 − hv, M vi − hM v, vi + hAv, vi (car A est hermitienne donc hAv, xi = hv, Axi = hv, M vi)
∗
= 1 − h(M + M − A)v, vi
= 1 − h(M ∗ + N )v, vi

Or M ∗ + N est supposé définie positive donc pour v 6= 0 on a h(M ∗ + N )v, vi > 0 donc

||M −1 N x||2A = 1 − h(M ∗ + N )v, vi < 1.

Soit |||M −1 N |||A < 1. Le théorème 5 sur les critères de convergence permet de conclure quant à la conver-
gence de la méthode itérative.

6 Méthodes itératives de Jacobi, Gauss-Seidel et relaxation

Remarque 21. Ces trois méthodes se basent sur la décomposition de A en les trois matrices suivantes :
Soit A ∈ Mn (K). On considère
• D la diagonale de A,
• −E sa partie strictement triangulaire inférieure et
• −F sa partie triangulaire strictement supérieure
 
..
 . −F 
A=  D 

..
−E .

telles que A = D − E − F = D − (E + F )

Année 2017-2018 13 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

Définition 7 (Def 8.2.1, 8.2.2, 8.2.3 [AK], §9.2 [Ser], §5.2 [Cia]). Soit A ∈ Mn (K) avec une décomposition
en les matrices D, −E, −F comme précédemment. Supposons de plus D inversible (par exemple, A inversible
suffit).
— La méhode de Jacobi se base sur la décomposition
A = D − (D − A) = |{z}
D − (E + F )
| {z }
M N

(i.e on ne distingue pas séparément les matrices −E et −F ici). La matrice de la méthode est
J = D−1 (D − A) = In − D−1 A.
— La méthode de Gauss-Seidel est basée sur la décomposition
A = (D − E) − |{z}
F .
| {z }
M N

La matrice de la méthode est G = (D − E)−1 F .

— La méthode de relaxation de paramètre ω 6= 0 se base sur la décomposition
   
D 1−ω
A= −E − D+F .
ω ω
| {z } | {z }
M N

D

−1 1−ω


La matrice de la méthode est donnée par Gω = ω −E ω D +F .
Calcul pratique. Une itération pour calculer xk+1 à partide xk dans ces méthodes est donnée par
Dxk+1 = (D − A)xk + b (méthode de Jacobi),
(D − E)xk+1 = F xk + b (méthode de Gauss-Seidel),
D 1−ω
( − E)xk+1 = ( D + F )xk + b (méthode de relaxation).
ω ω
Remarque 22. Si ω = 1 dans la méthode de relaxation, on retrouve la méthode de Gauss-Seidel. Le choix
de ω dans la méthode de relaxation est important puisque qu’il permet de minimiser ρ(Gω ) et ainsi d’avoir
une méthode qui converge plus rapidement.
Remarque 23. Ces trois méthodes sont bien définies si la matrice diagonale D est inversible.
Remarque 24. La méthode de relaxation est aussi appelée méthode SOR pour "Successive OverRelaxation
method".

6.1 Cas d’une matrice A à diagonale strictement dominante

Proposition 5 (Prop 9.3.1 [Ser]). Si A est à diagonale strictement dominante alors la méthode de Jacobi
converge, de même que la méthode de relaxation pour ω ∈]0, 1] (ce qui inclut la méthode de Gauss-Seidel).
P
Rappel. Une matrice A est dite à diagonale strictement dominante si et seulement si |Ai,i | > j6=i |Ai,j |.

Démonstration de la proposition 5. Méthode de Jacobi : D’après le théorème 5 des critères de convergence,

il suffit de montrer que
Xn
|||In − D−1 A|||∞ = max |(In − D−1 A)i,j | < 1.
i∈J1,nK
j=1

Or, pour tout (i, j) ∈ {1, ..., n}2 , on a

 n
X
−1 −1 Ai,i
1 − Di,k Ak,i = 1 − Di,i Ai,i = 1 − = 0, si i = j,




 Ai,i
k=1
(In − D−1 A)i,j = n
 X
−1 Ai,j
− Di,k Ak,j = − , si i 6= j.



A i,i
k=1

Année 2017-2018 14 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

On a donc
n n n
X X Ai,j 1 X
|(In − D−1 A)i,j | = = |Ai,j | < 1.
Ai,i |Ai,i |
j=1 j=1,j6=i j=1,j6=i

La dernière inégalité vient du fait que A soit à diagonale strictement dominante.

Méthode de Gauss-Seidel : Nous rappelons au préalable le théorème de Gerschgörin (Prop 4.5.1 [Ser])
Théorème 7. Le spectre d’une matricePB est inclus dans la réunion des disques de Gerschgörin, qui sont
les disques Di de centre bi,i et de rayon j6=i |bi,j |. C’est-à-dire, que pour tout λ valeur propre de B, il existe
i0 ∈ {1, ..., n} tel que X
|λ − bi0 ,i0 | ≤ |bi0 ,j |.
j6=i0

Pour démontrer la proposition 5 dans le cas de la décomposition de Gauss-Seidel, il suffit de montrer,

d’après le théorème 5 des critères de convergence, que

ρ((D − E)−1 F ) < 1.

Soit λ une valeur propre de (D − E)−1 F , alors par définition det(λ(D − E) − F ) = 0, soit encore
det(λD − (λE + F )) = 0. Ainsi, λ apparaît comme une valeur propre de la matrice D−1 (λE + F ). Le
coefficient d’indice (i, j) de cette matrice D−1 (λE + F ) vaut
n
X
−1
D−1 (λE + F ) i,j =


Di,k (λEk,j + Fk,j )
k=1
−1
= Di,i (λEi,j + Fi,j ) (puisque D est une matrice diagonale)

1

 (−λAi,j ) , si i > j,
 Ai,i



= 1 d’après les définitions des matrices D, E, F.
(−Ai,j ) , si i < j,



 A i,i

0, si i = j.


D’après le théorème de Gerschgörin, rappelé précédemment, il existe donc i0 ∈ {1, ..., n} tel que
X Ai0 ,j X Ai ,j
|λ − 0| ≤ −λ + − 0 .
Ai0 ,i0 Ai0 ,i0
j<i0 j>i0

Soit encore, en considérant tous les indices i des lignes

 
X Ai,j X Ai,j 
|λ| ≤ max |λ| + .
i∈{1,...,n}  Ai,i Ai,i 
j<i j>i

n o
1 P
L’inégalité précédente fournit |λ| ≤ max(|λ|, 1) max |Ai,i | j6=i |A i,j | .
i∈{1,...,n}
Puisque A est supposée à diagonale strictement dominante, nous obtenons |λ| < max(|λ|, 1) ce qui n’est
vrai que si |λ| < 1. Nous avons donc montré que toutes les valeurs propres de (D − E)−1 F étaient de module
strictement inférieur à 1, on a donc bien ρ((D − E)−1 F ) < 1.

Remarque 25. La preuve de la proposition 5 dans le cas de la méthode de relaxation se démontre de la

même manière que pour la méthode de Gauss-Seidel en introduisant le paramètre ω en plus (une preuve se
trouve p.103 [Ser]).

Année 2017-2018 15 [Link]@[Link]

Université Paris Sud Prépa agrèg : option B

6.2 Cas d’une matrice A hermitienne définie positive

Proposition 6. Si A est hermitienne, la méthode de Jacobi converge si A et 2D − A sont définies positives.

Démonstration de la proposition 6. Si A est définie positive alors Dii > 0 donc D est bien inversible (donc
la méthode de Jacobi est bien définie). De plus, M ∗ + N = D∗ + D − A = 2D − A. Le théorème 6 permet
de conclure quant à la convergence de cette méthode.

Proposition 7. Si A est hermitienne définie positive, la méthode de Gauss-Seidel converge.

Démonstration de la proposition 7. Nous allons utiliser le théorème 6.

Montrons tout d’abord que D − E (qui est la matrice M de la méthode de Gauss-Seidel) est bien
inversible. On a (D − E)i,i = Di,i = Ai,i > 0 car A est définie positive, donc D − E est inversible (car
triangulaire à diagonale sans 0).
Ensuite, montrons que M ∗ + N = (D − E)∗ + F est hermitienne définie positive. La matrice A est
hermitienne donc A∗ = ĀT = A donc (−E)∗ = −F donc E ∗ = F . Ainsi

M ∗ + N = (D − E)∗ + F = D∗ − E ∗ + F = D

qui est définie positive car Dii = Aii > 0 et D est diagonale.
Les hypothèses du théorème 6 sont donc vérifiées et la méthode de Gauss-Seidel converge donc.

Remarque 26. Il existe aussi un critère de convergence pour la méthode de relaxation sur les matrices
hermitiennes définies positives : (Thm 8.2.1 [AK], Thm 5.3-2 [Cia], Thm 9.3.1 [Ser])
Si A est hermitienne définie positive et si ω ∈]0, 2[ alors la méthode de relaxation converge.

Remarque 27. Notons également le cas particulier des matrices tridiagonales (§9.4 [Ser], §8.3 [AK], Thm
5.3-4, Thm 5.3-5 [Cia])...

Références
[AK] G. Allaire and S. M. Kaber. Numerical Linear Algebra, volume 55 of Texts in Applied Mathematics.
Springer, 2008.
[Cia] P. G. Ciarlet. Introduction à l’analyse numérique matricielle et à l’optimsation. Dunod, 2006.
[Gou] X. Gourdon. Algèbre. Les maths en tête. Ellipses, 2009.
[Ser] D. Serre. Les Matrices. Dunod, 2001.

Année 2017-2018 16 [Link]@[Link]