Livre_silo 30 août 2013 16:32 Page 195
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
195
7 – Pivot de Gauss et résolution de systèmes
mat50.png
mat50inv.png
mat50invbis.png
Figure 7.1
La matrice initiale, son inverse « maison » et celle calculée avec linalg.inv
Le lecteur intrigué par les régularités de la matrice inverse pourra aller consulter [Appel].
Exercice 7.19 * On a vu en section 7.1.5 que l’algorithme du pivot de Gauss conduit à une décomposition
« lower-upper » de certaines matrices. Cet exercice précise ce point.
1 Montrer que si les n mineurs principaux d’une matrice sont non nuls, alors dans l’algorithme du pivot
de Gauss (sans choix du module maximal), on trouve à chaque étape (qu’on appellera k) un élément
non nul en position (k, k) dans la matrice.
2 On suppose qu’à chaque opération sur les lignes de A (la matrice qu’on veut mettre sous la forme LU ),
on réalise l’opération équivalente sur une matrice B initialisée à In.
Montrer qu’on obtient ainsi une matrice B triangulaire inférieure telle que BA soit triangulaire supérieure.
3 On suppose que dans la question précédente B = M N ...M 2 M 1 , les M k étant associées à des opérations sur les lignes. Que vaut alors B −1 ? Et comment faire en sorte de calculer cette matrice B −1 à la
volée (pendant la mise sous forme triangulaire de A) plutôt qu’a posteriori ?
4 Écrire un programme Python prenant en entrée une matrice vérifiant les hypothèses faites plus
haut et renvoyant deux matrices L et U , respectivement triangulaires inférieure et supérieure, telles
que A = LU .
On pourra comparer le résultat avec celui proposé par la fonction lu du sous-module numpy.linalg.
5 Sans l’hypothèse faite sur les mineurs de A, montrer que si A est inversible, alors on peut trouver L
et U , triangulaires inférieure et supérieure, et P une matrice de permutation ¹⁵, telles que A = LP U
(décomposition de Bruhat).
Lorsque la décomposition LU est connue, la résolution cubique de AX = Y se ramène à deux résolutions
quadratiques de systèmes triangulaires, ce qui est très intéressant.
ATTENTION Encore les flottants et l’égalité
Le calcul effectif de la décomposition de Bruhat est peu pertinent en arithmétique flottante, puisqu’il est associé à l’annulation d’un coefficient de la matrice et on sait ce qu’il
en est de la nullité d’un coefficient représenté par un flottant...
Il peut être intéressant tout de même d’écrire un programme réalisant la décomposition
de Bruhat pour une matrice à coefficients dans Q : en pseudo-code dans un premier temps,
puis en Python en utilisant le module fractions dans un deuxième temps.
15. Elle ne contient que des zéros, sauf un « 1 » par ligne et par colonne ; bref, on a permuté les lignes (ou
colonnes) de la matrice identité.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
195
7 – Pivot de Gauss et résolution de systèmes
mat50.png
mat50inv.png
mat50invbis.png
Figure 7.1
La matrice initiale, son inverse « maison » et celle calculée avec linalg.inv
Le lecteur intrigué par les régularités de la matrice inverse pourra aller consulter [Appel].
Exercice 7.19 * On a vu en section 7.1.5 que l’algorithme du pivot de Gauss conduit à une décomposition
« lower-upper » de certaines matrices. Cet exercice précise ce point.
1 Montrer que si les n mineurs principaux d’une matrice sont non nuls, alors dans l’algorithme du pivot
de Gauss (sans choix du module maximal), on trouve à chaque étape (qu’on appellera k) un élément
non nul en position (k, k) dans la matrice.
2 On suppose qu’à chaque opération sur les lignes de A (la matrice qu’on veut mettre sous la forme LU ),
on réalise l’opération équivalente sur une matrice B initialisée à In.
Montrer qu’on obtient ainsi une matrice B triangulaire inférieure telle que BA soit triangulaire supérieure.
3 On suppose que dans la question précédente B = M N ...M 2 M 1 , les M k étant associées à des opérations sur les lignes. Que vaut alors B −1 ? Et comment faire en sorte de calculer cette matrice B −1 à la
volée (pendant la mise sous forme triangulaire de A) plutôt qu’a posteriori ?
4 Écrire un programme Python prenant en entrée une matrice vérifiant les hypothèses faites plus
haut et renvoyant deux matrices L et U , respectivement triangulaires inférieure et supérieure, telles
que A = LU .
On pourra comparer le résultat avec celui proposé par la fonction lu du sous-module numpy.linalg.
5 Sans l’hypothèse faite sur les mineurs de A, montrer que si A est inversible, alors on peut trouver L
et U , triangulaires inférieure et supérieure, et P une matrice de permutation ¹⁵, telles que A = LP U
(décomposition de Bruhat).
Lorsque la décomposition LU est connue, la résolution cubique de AX = Y se ramène à deux résolutions
quadratiques de systèmes triangulaires, ce qui est très intéressant.
ATTENTION Encore les flottants et l’égalité
Le calcul effectif de la décomposition de Bruhat est peu pertinent en arithmétique flottante, puisqu’il est associé à l’annulation d’un coefficient de la matrice et on sait ce qu’il
en est de la nullité d’un coefficient représenté par un flottant...
Il peut être intéressant tout de même d’écrire un programme réalisant la décomposition
de Bruhat pour une matrice à coefficients dans Q : en pseudo-code dans un premier temps,
puis en Python en utilisant le module fractions dans un deuxième temps.
15. Elle ne contient que des zéros, sauf un « 1 » par ligne et par colonne ; bref, on a permuté les lignes (ou
colonnes) de la matrice identité.