Livre_silo 30 août 2013 16:32 Page 196
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
196
Informatique pour tous
Exercice 7.20 * Si A est une matrice réelle symétrique définie positive, alors il existe U triangulaire
supérieure telle que A = t U.U : c’est la décomposition de Choleski, qui est un cas particulier de la décomposition LU . Elle est unique si on impose aux coefficients diagonaux de U d’être strictement positifs,
ce qu’on va faire dans la suite.
Une façon de construire U consiste à calculer les coefficients u i,j à i croissant, puis (à i fixé) à j croissant.
1 En observant le coefficient (1, 1) du produit
t U.U , donner la valeur nécessaire de u 1,1 . De même,
donner les valeurs nécessaires de u 1,j pour j ⩾ 2.
2 En continuant le procédé, donner des conditions nécessaires sur tous les u i,j pour avoir
t U.U = A.
Vérifier qu’elles sont suffisantes.
3 Déduire de ce qui précède un algorithme calculant la décomposition de Choleski d’une matrice carrée.
4 Évaluer la complexité de cet algorithme en termes d’opérations arithmétiques élémentaires.
5 Programmer en Python la décomposition de Choleski.
6 Tester, comparer avec la fonction linalg.cholesky de numpy.
En changeant peu de choses, cet algorithme de Choleski permet de tester le caractère positif d’une matrice
symétrique... en espérant que la matrice n’ait pas de valeurs propres trop proches de 0.
POUR ALLER PLUS LOIN Décomposition QR
Toute matrice carrée ¹⁶réelle peut se décomposer sous la forme QR, avec Q orthogonale
et R triangulaire supérieure. Cette décomposition a beaucoup d’applications théoriques...
mais aussi pratiques ! Par exemple, une fois la décomposition A = QR connue, résoudre
AX = Y se décompose en deux opérations plus simples : d’abord une résolution (quadratique) de système triangulaire, puis une multiplication (elle aussi quadratique) par
Q −1 = t Q.
Trois points de vue conduisent à cette décomposition :
• On peut voir la matrice initiale comme représentant n vecteurs dans la base canonique
de R n muni de son produit scalaire euclidien canonique. Le procédé de Gram-Schmidt
appliqué à cette famille de vecteurs fournit une base orthonormée. Si on s’intéresse aux
matrices de passage entre les trois bases en présence, on obtient la décomposition souhaitée. Cette méthode a le bon goût d’être d’interprétation géométrique claire... mais
est numériquement assez instable.
• La méthode de Householder, présentée dans l’exercice suivant, consiste à composer l’application de départ avec une réflexion (symétrie orthogonale par rapport à un hyperplan)
pour que le premier vecteur soit envoyé sur un vecteur colinéaire à lui-même. On continue ensuite le travail récursivement.
• La méthode de Givens consiste, elle, à composer avec des « rotations ». Cette dernière
méthode est un peu plus coûteuse, mais est plus stable que la méthode de Householder.
Exercice 7.21 * On présente ici la méthode de Householder pour trouver une décomposition QR
de A ∈ Mn(R). Notons e 1 le premier vecteur de la base canonique de R n .
Si Ae 1 est colinéaire à e 1 , alors on peut écrire par blocs A =
(
α
L
(0) A 1
)
, avec A 1 ∈ M n−1 (R). Un
appel récursif fournit Q 1 ∈ O n−1 (R) et R 1 ∈ M n−1 (R) triangulaire supérieure, telles que A 1 = Q 1 R 1 .
Il suffit alors de prendre Q =
(
1
(0)
(0) Q 1
)
et R =
(
α
L
(0) Q 1
)
pour répondre au problème.
Si Ae 1 n’est pas colinéaire à e 1 , on va considérer v = Ae 1 − ε ∥Ae 1 ∥ e 1 (avec ε ∈ {−1, 1} du signe de la
première composante de Ae 1 ; condition imposée pour la stabilité). La réflexion par rapport à l’orthogonal
16. En fait, une adaptation de cette décomposition existe aussi (et est utile) pour les matrices rectangulaires
quelconques.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
196
Informatique pour tous
Exercice 7.20 * Si A est une matrice réelle symétrique définie positive, alors il existe U triangulaire
supérieure telle que A = t U.U : c’est la décomposition de Choleski, qui est un cas particulier de la décomposition LU . Elle est unique si on impose aux coefficients diagonaux de U d’être strictement positifs,
ce qu’on va faire dans la suite.
Une façon de construire U consiste à calculer les coefficients u i,j à i croissant, puis (à i fixé) à j croissant.
1 En observant le coefficient (1, 1) du produit
t U.U , donner la valeur nécessaire de u 1,1 . De même,
donner les valeurs nécessaires de u 1,j pour j ⩾ 2.
2 En continuant le procédé, donner des conditions nécessaires sur tous les u i,j pour avoir
t U.U = A.
Vérifier qu’elles sont suffisantes.
3 Déduire de ce qui précède un algorithme calculant la décomposition de Choleski d’une matrice carrée.
4 Évaluer la complexité de cet algorithme en termes d’opérations arithmétiques élémentaires.
5 Programmer en Python la décomposition de Choleski.
6 Tester, comparer avec la fonction linalg.cholesky de numpy.
En changeant peu de choses, cet algorithme de Choleski permet de tester le caractère positif d’une matrice
symétrique... en espérant que la matrice n’ait pas de valeurs propres trop proches de 0.
POUR ALLER PLUS LOIN Décomposition QR
Toute matrice carrée ¹⁶réelle peut se décomposer sous la forme QR, avec Q orthogonale
et R triangulaire supérieure. Cette décomposition a beaucoup d’applications théoriques...
mais aussi pratiques ! Par exemple, une fois la décomposition A = QR connue, résoudre
AX = Y se décompose en deux opérations plus simples : d’abord une résolution (quadratique) de système triangulaire, puis une multiplication (elle aussi quadratique) par
Q −1 = t Q.
Trois points de vue conduisent à cette décomposition :
• On peut voir la matrice initiale comme représentant n vecteurs dans la base canonique
de R n muni de son produit scalaire euclidien canonique. Le procédé de Gram-Schmidt
appliqué à cette famille de vecteurs fournit une base orthonormée. Si on s’intéresse aux
matrices de passage entre les trois bases en présence, on obtient la décomposition souhaitée. Cette méthode a le bon goût d’être d’interprétation géométrique claire... mais
est numériquement assez instable.
• La méthode de Householder, présentée dans l’exercice suivant, consiste à composer l’application de départ avec une réflexion (symétrie orthogonale par rapport à un hyperplan)
pour que le premier vecteur soit envoyé sur un vecteur colinéaire à lui-même. On continue ensuite le travail récursivement.
• La méthode de Givens consiste, elle, à composer avec des « rotations ». Cette dernière
méthode est un peu plus coûteuse, mais est plus stable que la méthode de Householder.
Exercice 7.21 * On présente ici la méthode de Householder pour trouver une décomposition QR
de A ∈ Mn(R). Notons e 1 le premier vecteur de la base canonique de R n .
Si Ae 1 est colinéaire à e 1 , alors on peut écrire par blocs A =
(
α
L
(0) A 1
)
, avec A 1 ∈ M n−1 (R). Un
appel récursif fournit Q 1 ∈ O n−1 (R) et R 1 ∈ M n−1 (R) triangulaire supérieure, telles que A 1 = Q 1 R 1 .
Il suffit alors de prendre Q =
(
1
(0)
(0) Q 1
)
et R =
(
α
L
(0) Q 1
)
pour répondre au problème.
Si Ae 1 n’est pas colinéaire à e 1 , on va considérer v = Ae 1 − ε ∥Ae 1 ∥ e 1 (avec ε ∈ {−1, 1} du signe de la
première composante de Ae 1 ; condition imposée pour la stabilité). La réflexion par rapport à l’orthogonal
16. En fait, une adaptation de cette décomposition existe aussi (et est utile) pour les matrices rectangulaires
quelconques.