Université de Provence, Année 2011/2012

Licence Mathématiques-Informatique,
parcours Mécanique-3ème année
calcul scientifique
Corrigé des exercices de la feuille 3

Exercice 1 : Décomposition LU d’une matrice tridiagonale.

Soit une matrice tridiagonales n × n à coefficients réels
 
a1 c1
 b2 a2 c2
 (0) 

A=
 . .. . .. . .. 
 (1)
 
 (0) bn−1 an−1 cn−1 
bn an
et dont les coefficients sont tels que
ai 6= 0, i = 1, · · · , n; bi 6= 0, i = 1, · · ·, n − 1; ci 6= 0, i = 2, · · · , n (2)
et
|a1 | > |b2 |; |ai | ≥ |bi+1 | + |ci−1|, i = 2, · · · , n − 1; |an | ≥ |cn−1 | (3)
et on cherche une décomposition LU de Aavec L et U sous la forme
α1 γ1 (0)
   
1
 β2 1 (0)   .. .. 
L= = . .
U . (4)
   
.. ..
(0) αn−1 γn−1
 
 . .   
(0) βn 1 αn
1a) On suppose que les coefficients des matrices L et U sont obtenus en fonction des coefficients
de la matrice A par les relations
α1 = a1 , γ1 = c1 ; βi = bi /αi−1 , αi = ai − γi−1 βi , γi = ci , 2 ≤ i ≤ n − 1;
βn = bn /αn−1 , αn = an − γn−1 βn .
Montrer que sous les hypothèses sur les coefficients de la matrice A ci-dessus |βi | < 1, 2 ≤ i ≤ n,
ainsi que αi 6= 0, 1 ≤ i ≤ n − 1. Vérifier ensuite que l’on a bien A = LU .

Corrigé : D’abord on opère le produit LU ce qui donne

α1 γ1
 
 α 1 β 2 α 2 + γ1 β 2 γ2 (0) 
 
LU = 
 . .. . .. . .. .

αn−2 βn−1 αn−1 + γn−2 βn − 1 γn−1
 
 (0) 
αn−1 βn αn + γn−1 βn

1
On a bien A = LU pour les coefficients βi , αi et γi comme définis ci-dessus. Par hypothèse
α1 = a1 6= 0 et par (3) on a bien |β2| < 1 car β2 = b2 /α1 = b2 /a1 . Faisons alors une récurrence
pour montrer les autres inégalités, donc on suppose que αi 6= 0, et que |βi+1 | < 1. D’après les
relations entre les coefficients,
|αi+1 | = |ai+1 − ci βi+1 | ≥ |ai+1| − |ci ||βi+1|
> |ai+1 | − |ci | ≥ |bi+2| > 0
(5)
car par hypothèse de récurrence |βi+1| < 1 et en tenant compte de (3).On déduit des inégalités
ci-dessus que αi+1 6= 0 et que
|bi+2|
|βi+2 | = <1
|αi+1 |
ce qui achève la démonstration.
1b) Application : trouver la décomposition LU de la matrice
 
2 −1 0 0
 −1 2 −1 0 
A=  0 −1 2 −1 
 (6)
0 0 −1 2

Corrigé : Il suffit d’injecter les valeurs de cet exemple dans les relations pour trouver
   
1 0 0 0 2 −1 0 0
 −1 1 3
0 0   , U =  0 2 −1 0 

L= 2 .
2 4
 0 −
3 1 0   0 0
3 −1 
3 5
0 0 −4 1 0 0 0 4

Exercice 2 : décomposition de Cholesky.

Soit une matrice A, n × n, de coefficients réels que l’on note ai j , i = 1, · · · , n, j = 1, · · ·n. On
suppose que A est symétrique, c’est-à-dire ai j = a ji (ou encore AT = A, avec AT la matrice
transposée de A). En plus on suppose que A est définie positive, ce qui signifie que xT A x > 0,
pour tout vecteur x ∈ Rn , x 6= 0 (on note xT le vecteur transposé de x). On admet le résultat
suivant : sous ces hypothèses sur la matrice A, il existe une matrice triangulaire inférieure L
telle que A = L LT ; on note li j les éléments de L et on peut choisir L telle que les éléments sur
la diagonale lii > 0.
2a) L’égalité A = L LT s’écrit
    
a11 · · · a1n l11 l11 · · · ln1
 .. . . .   . .. . . 
. ..  =  .. . (0)   (0) . . ..  .

 .
an1 · · · ann ln1 · · · lnn lnn
En déduire que
n
ai j = ∑ lik l jk .
k=1

2
Corrigé : On note (LT )i j les coefficients de la matrice LT et si A = LLT , alors par la définition
du produit de matrices
n
ai j = ∑ lik (LT )k j = lik l jk
k=1

car bien entendu, (LT )k j = l jk par la définition de la matrice transposée.

2b) Etant donnée la symétrie de la matrice, il suffit de considérer les indices i avec i ≥ j.
√
Donc, par exemple l11 = a11 et li1 = ai1 /l11 , i = 2, · · ·, n etc. Préciser l’algorithme qui permet
de calculer, en parcourant les colonnes j = 1, 2, · · ·, n successives, les éléments de la matrice L,
en fonction de ceux de A.

Corrigé : Ayant calculé

√
l11 = a11 ,
on peut déterminer
li1 = ai1 /l11 , i = 2, · · ·n
ce qui donne la première colonne de la matrice L. Ensuite, on observe que
j
ajj = ∑ l 2jk
k=1

car l jk = 0, k > j, la matrice L étant triangulaire inférieure. Donc, ayant déterminé les j − 1
premières colonnes de L, on peut déterminer
v
j−1
u
l j j = ta j j − ∑ l 2jk .
u

k=1

Soit ensuite i > j et

j
ai j = ∑ lik l jk
k=1
et donc
j−1
ai j − ∑k=1 lik l jk
li j = .
ljj
Dans cette expression interviennent les coefficients de la matrice pour les colonnes k = 1, · · ·, j −
1 ainsi que l j j . Ces relations permettent bien de déterminer les coefficients non nuls de L pour
les colonnes successives de la matrice.
2c) On admet que la matrice A de (6) est définie positive. Déterminer pour cet exemple la ma-
trice L telle que A = L LT .
√ √
Corrigé : Par a11 = 2 on trouve l11 = 2 et ensuite l j1 = a j1 /l11 donne l21 = −1/ 2, l31 =

3
 q p p
2 =
l41 = 0. Puis l22 = a22 − l21 3/2 et l32 = −1/l22 = − 2/3, l42 = 0. Les coefficients res-
q p p q p
2 =
tant sont l33 = a33 − l32 2 =
4/3, l43 = −1/l33 = − 3/4 et enfin l44 = a44 − l43 5/4.
Ce qui donne
 √ 
√2 p0 0 0
 −1 2
L= p3/2 p0 0  
 0 − 2/3 p4/3 p 0 
0 0 − 3/4 5/4

Exercice 3 : décomposition LU simple.

Soit la matrice  
3 −2 6 −5
 24 −12 41 −39 
A=  −27 18 −62 54

 (7)
9 14 15 −47

3a) Déterminer la décomposition LU de la matrice ci-dessus, sans opérer aucune permutation

suivant les lignes, de façon à ce que
A = LU.
En déduire le déterminant de A

Corrigé : Pour faire apparaı̂tre un 0 dans la position (2, 1) de la matrice, on soustrait de la

deuxième ligne la première multipliée par 24/3 = 8 ; ensuite, pour faire apparaı̂tre 0 en position
(3, 1) on soustrait de la troisième ligne la première multipliée par (−27)/3 = −9 ; et enfin pour
avoir 0 en position (4, 1) on soustrait de la quatrième ligne la première multipliée par 9/3 = 3.
Or, d’après la méthode comme exposée dans le cours, ces coefficients 8, −9 et 3 sont respec-
tivement les coefficients l21 , l31 et l41 de la matrice L. Donc, à partir de A on forme le tableau,
avec les éléments de L entre parenthèses,
 
3 −2 6 −5
 (8) 4 −7 1 
 (−9) 0 −8 9  .
 

(3) 20 −3 −32
Ensuite, dans la matrice ci-dessus on considère la sous-matrice à partir de la deuxième ligne et
deuxième colonne. Il y a déjà 0 en position (3, 2), donc l32 = 0 ; ensuite, l42 = 20/4 = 5 et on
soustrait de la 4 ème ligne la deuxième multipliée par 5, en laissant la partie correspondant à L
inchangée. Par conséquent  
3 −2 6 −5
 (8) 4 −7 1 
 (−9) (0) −8 9  .
 

(3) (5) 32 −37

Enfin, on considère la sous-matrice à partir de la 3 ème ligne et la 3 ème colonne : pour faire
apparaı̂tre 0 en position (4, 3), on soustrait de la 4 ème ligne la troisième multipliée par l43 =

4
32/(−8) = −4 et finalement on obtient
 
3 −2 6 −5
 (8) 4 −7 1 
 .
 (−9) (0) −8 9 
(3) (5) (−4) −1
On en déduit les matrices L et U
   
1 0 0 0 3 −2 6 −5
 8 1 0 0 
  0 4 −7 1 
L=  −9 0 1 ,U =
 0 0 −8 9
.
0  
3 5 −4 1 0 0 0 −1
On peut donc affirmer que A = LU d’après le cours. On obtient aisément le déterminant de A
car
det(A) = det(L)det(U ).
Or, L et U sont des matrices triangulaires et le déterminant d’une matrice triangulaire est égal
au produit des éléments sur la diagonale, ce qui donne det(L) = 1 et det(U ) = det(A) = 96.

3b) Utiliser la décomposition L U pour résoudre le système

Ax = b
avec A la matrice donnée par (7) et b le vecteur
b = (1, 9, −15, 30)T .

Corrigé : Par A = LU , on aura LU x = b et par conséquent la résolution du système se ramène

à la résolution de deux systèmes avec des matrices triangulaires et
Ly = b, U x = y.
Le premier système se résout aisément par
y1 = 1
y2 = 9 − 8y1 = 1
y3 = −15 − (−9)y1 = −6
y4 = 30 − 3y1 − 5y2 − (−4)y3 = −2
Il reste à résoudre U x = y, en commençant par x4 et en “remontant”, car U est triangulaire
supérieure et
x4 = y4 /(−1) = 2
x3 = (y3 − 9x4 )/(−8) = 3
x2 = (y2 − (−7)x3 − x4 )/4 = 5
x1 = (y1 − (−2)x2 − 6x3 − (−5)x4 )/3 = 1

5
et d’où la solution x = (1, 5, 3, 2)T du système.

Exercice 4 : Décomposition LU avec permutation de lignes.

Soit la matrice  
2 −1 4 0
 4 −1 5 1 
A=  −2 2 −2 3 
 (8)
0 3 −9 4

4a) En recherchant le pivot maximal suivant les lignes de A, opérer une décomposition LU avec
permutation éventuelle des lignes de façon à ce que

P A = LU.

On ne demande pas d’expliciter la matrice de permutation P, il suffira de donner le résultat des

permutation sur le vecteur des indices (1, 2, 3, 4).

Corrigé : Il faut chercher dans la première ligne l’élément le plus grand en valeur absolue
(le pivot) pour le mettre en position (1, 1) : on permute donc les lignes 1 et 2, donc le vecteur
des indices devient (2, 1, 3, 4) et la matrice
 
4 −1 5 1
 2 −1 4 0 
 −2 2 −2 3  .
 

0 3 −9 4

Sur cette matrice, on fait des opérations algébriques comme pour l’exercice 2 afin de faire
apparaı̂tre des zéros en position (2, 1), (3, 1), (4, 1) et on remplace ces positions par les éléments
l21 , l31 , l41 de la matrice L, entre parenthèses, ce qui donne
 
4
−1 5 1
 1 1 3 1 
 2
−2 2 −2 .
 −1 3 1 7 
2 2 2 2
(0) 3 −9 4

Maintenant on considère la sous-matrice à partir de la colonne 2 et la ligne 2 et on voit qu’il

convient de permuter les lignes 2 et 4 afin de mettre le pivot maximal en position (2, 2). Il faut
aussi opérer cette permutation sur la partie correspondant à L dans le tableau ci-dessus, ce qui
donne  
4 −1 5 1
 (0)

33 −9 4 
7 .
 −1 1
 
2
2 2 2
1
2 − 12 32 − 21

6
On opère aussi cette permutation sur le vecteur des indices, qui devient (2, 4, 3, 1). Alors on
opère les opérations algébriques pour faire apparaı̂tre des zéros en position (3, 2) et (4, 2) en y
mettant l32 et l42 ce qui donne
 
4 −1 5 1
 (0) 3
−9 4 
 −1 1 3 .


2
2
5 2
1
2 − 61 0 16

Dans ce tableau il y a déjà 0 en position (4, 3), donc l43 = 0 et nous avons finalement
   
1 0 0 0 4 −1 5 1
 0 1 0 0   0 3 −9 4 
L=  −1 1 1 0 , U =  0 0
  3 .

2 2 5 2
1 1 1
2 − 6 0 1 0 0 0 6

4b) Utiliser le résultat de 4a) pour déterminer le déterminant de A.

Corrigé : Les matrices L et U ci-dessus sont telles que PA = LU , avec P les deux permuta-
tion ci-dessus. Or, le déterminant d’une matrice obtenue à partir d’une matrice de départ en
permutant deux lignes est égal au déterminant de la matrice de départ multiplié par -1. Donc,
det(PA) = (−1)q det(A) avec q le nombre de permutations opérées durant la décomposition
PA = LU . Ici q = 2 et donc det(A) = det(L)det(U ) = det(U ) = 10.