328
9 Solutions des exercices
q
s=1
s =
q(q + 1)
2
,
q
s=1
s
2 =
q(q + 1)(2q + 1)
6
, q ≥ 1,
on en déduit que la factorisation de Gauss complète nécessite le nombre d’opérations suivant
n−1
k=1
n
i=k+1
⎛
⎝ 1 +
n
j=k+1
2
⎞
⎠ =
n−1
k=1
(n − k)(1 + 2(n − k))
=
n−1
j=1
j + 2
n−1
j=1
j
2 =
(n − 1)n
2
+ 2
(n − 1)n(2n − 1)
6
=
2
3
n
3 −
n
2
2
−
n
6
.
Solution 5.5 Par définition, l’inverse X d’une matrice A ∈ R
n×n vérifie
XA = AX = I. Donc, pour j = 1, . . . , n le vecteur colonne xj de X est solution du système linéaire Axj = ej , où ej est le j-ème vecteur de la base
canonique de R
n (celui dont toutes les composantes sont nulles sauf la j-ème
qui vaut 1). Après avoir effectué la factorisation LU de A, le calcul de l’inverse
de A nécessite la résolution de n systèmes linéaires associés à la même matrice
mais avec des seconds membres différents.
Solution 5.6 En utilisant le Programme 5.1 on calcule les facteurs L et U
L =
⎡
⎣
1
0
0
2
1
0
3 −3.38 · 10
15 1
⎤
⎦ , U =
⎡
⎣
1
1
3
0 −8.88 · 10
−16
14
0
0
4 .73 · 10
−16
⎤
⎦ .
Si on calcule leur produit, on obtient la matrice :
L*U
ans =
1.0000
1.0000
3.0000
2.0000
2.0000
20.0000
3.0000
6.0000
0.0000
qui est différente de A, puisque le coefficient (3,3) vaut 0 alors que celui de
A vaut 4. Dans Octave, le coefficient (3,3) est 0 ou 2. Ce résultat dépend de
l’implémentation de l’arithmétique flottante, c’est-à-dire à la fois du matériel
et de la version d’Octave (ou de MATLAB).
Un calcul précis de L et U est obtenu en effectuant un pivot partiel par
lignes. L’instruction [L,U,P]=lu(A) conduit effectivement à des résultats corrects.
Solution 5.7 Usuellement, on ne stocke que la partie triangulaire (inférieure
ou supérieure) d’une matrice symétrique. Par conséquent, toute opération qui
ne respecte pas la symétrie de la matrice est sous-optimale du point de vue du
stockage en mémoire. C’est le cas de la stratégie de pivot par ligne. Une possibilité est d’échanger simultanément les lignes et les colonnes ayant même indice,
limitant par conséquent le choix du pivot aux seuls coefficients diagonaux. De
manière générale, une stratégie de pivot impliquant un changement de lignes et
de colonnes est appelée stratégie de pivot complet (voir p.ex. [QSS07, Chap. 3]).
9 Solutions des exercices
q
s=1
s =
q(q + 1)
2
,
q
s=1
s
2 =
q(q + 1)(2q + 1)
6
, q ≥ 1,
on en déduit que la factorisation de Gauss complète nécessite le nombre d’opérations suivant
n−1
k=1
n
i=k+1
⎛
⎝ 1 +
n
j=k+1
2
⎞
⎠ =
n−1
k=1
(n − k)(1 + 2(n − k))
=
n−1
j=1
j + 2
n−1
j=1
j
2 =
(n − 1)n
2
+ 2
(n − 1)n(2n − 1)
6
=
2
3
n
3 −
n
2
2
−
n
6
.
Solution 5.5 Par définition, l’inverse X d’une matrice A ∈ R
n×n vérifie
XA = AX = I. Donc, pour j = 1, . . . , n le vecteur colonne xj de X est solution du système linéaire Axj = ej , où ej est le j-ème vecteur de la base
canonique de R
n (celui dont toutes les composantes sont nulles sauf la j-ème
qui vaut 1). Après avoir effectué la factorisation LU de A, le calcul de l’inverse
de A nécessite la résolution de n systèmes linéaires associés à la même matrice
mais avec des seconds membres différents.
Solution 5.6 En utilisant le Programme 5.1 on calcule les facteurs L et U
L =
⎡
⎣
1
0
0
2
1
0
3 −3.38 · 10
15 1
⎤
⎦ , U =
⎡
⎣
1
1
3
0 −8.88 · 10
−16
14
0
0
4 .73 · 10
−16
⎤
⎦ .
Si on calcule leur produit, on obtient la matrice :
L*U
ans =
1.0000
1.0000
3.0000
2.0000
2.0000
20.0000
3.0000
6.0000
0.0000
qui est différente de A, puisque le coefficient (3,3) vaut 0 alors que celui de
A vaut 4. Dans Octave, le coefficient (3,3) est 0 ou 2. Ce résultat dépend de
l’implémentation de l’arithmétique flottante, c’est-à-dire à la fois du matériel
et de la version d’Octave (ou de MATLAB).
Un calcul précis de L et U est obtenu en effectuant un pivot partiel par
lignes. L’instruction [L,U,P]=lu(A) conduit effectivement à des résultats corrects.
Solution 5.7 Usuellement, on ne stocke que la partie triangulaire (inférieure
ou supérieure) d’une matrice symétrique. Par conséquent, toute opération qui
ne respecte pas la symétrie de la matrice est sous-optimale du point de vue du
stockage en mémoire. C’est le cas de la stratégie de pivot par ligne. Une possibilité est d’échanger simultanément les lignes et les colonnes ayant même indice,
limitant par conséquent le choix du pivot aux seuls coefficients diagonaux. De
manière générale, une stratégie de pivot impliquant un changement de lignes et
de colonnes est appelée stratégie de pivot complet (voir p.ex. [QSS07, Chap. 3]).