94
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
diagonaux de A. Ainsi, la pr´ esence de petits coefficients sur la diagonale de
A peut consid´ erablement r´ eduire les avantages du changement de pivot. Pour
traiter des matrices de ce type, on doit utiliser des algorithmes particuliers
(comme la m´ ethode de Parlett-Reid [PR70] ou la m´ ethode de Aasen [Aas71]).
Nous renvoyons le lecteur ` a [GL89] pour la description de ces techniques, et
` a [JM92] pour le cas des matrices creuses.
3.6 Calculer l’inverse d’une matrice
Le calcul explicite de l’inverse d’une matrice peut ˆ etre effectu´ e en utilisant la
factorisation LU comme suit. En notant X l’inverse d’une matrice r´ eguli` ere
A∈ R
n×n , les vecteurs colonnes de X sont les solutions des syst` emes lin´ eaires
Ax i = e i , pour i = 1, . . . , n.
En supposant que PA=LU, o` u P est la matrice de changement de pivot
partiel, on doit r´ esoudre 2n syst` emes triangulaires de la forme
Ly i = Pe i , Ux i = y i , i = 1, . . ., n,
c’est-` a-dire une suite de syst` emes lin´ eaires ayant la mˆ eme matrice mais des
seconds membres diff´ erents.
Le calcul de l’inverse d’une matrice est une op´ eration non seulement coˆ uteuse, mais qui peut aussi s’av´ erer parfois moins stable que la m´ ethode de
Gauss (voir [Hig88]).
Les formules de Faddev ou de Leverrier offrent une alternative pour le
calcul de l’inverse de A : posons B 0 =I, et calculons par r´ ecurrence
α k =
1
k
tr(AB k−1 ), B k = −AB k−1 + α k I, k = 1, 2, . . ., n.
Puisque B n = 0, si α n = 0 on obtient
A
−1 =
1
α n
B n−1 ,
et le coˆ ut de la m´ ethode pour une matrice pleine est de (n − 1)n
3 flops (pour
plus de d´ etails, voir [FF63], [Bar89]).
3.7 Syst` emes bandes
Les m´ ethodes de discr´ etisation des ´ equations aux d´ eriv´ ees partielles conduisent
souvent `
a la r´ esolution de syst` emes dont les matrices ont des structures bandes,
creuses ou par blocs. Exploiter la structure de la matrice permet une r´ eduction consid´ erable du coˆ ut des algorithmes de factorisation et de substitution.
Dans cette section et dans les suivantes, nous consid´ erons des variantes de la
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
diagonaux de A. Ainsi, la pr´ esence de petits coefficients sur la diagonale de
A peut consid´ erablement r´ eduire les avantages du changement de pivot. Pour
traiter des matrices de ce type, on doit utiliser des algorithmes particuliers
(comme la m´ ethode de Parlett-Reid [PR70] ou la m´ ethode de Aasen [Aas71]).
Nous renvoyons le lecteur ` a [GL89] pour la description de ces techniques, et
` a [JM92] pour le cas des matrices creuses.
3.6 Calculer l’inverse d’une matrice
Le calcul explicite de l’inverse d’une matrice peut ˆ etre effectu´ e en utilisant la
factorisation LU comme suit. En notant X l’inverse d’une matrice r´ eguli` ere
A∈ R
n×n , les vecteurs colonnes de X sont les solutions des syst` emes lin´ eaires
Ax i = e i , pour i = 1, . . . , n.
En supposant que PA=LU, o` u P est la matrice de changement de pivot
partiel, on doit r´ esoudre 2n syst` emes triangulaires de la forme
Ly i = Pe i , Ux i = y i , i = 1, . . ., n,
c’est-` a-dire une suite de syst` emes lin´ eaires ayant la mˆ eme matrice mais des
seconds membres diff´ erents.
Le calcul de l’inverse d’une matrice est une op´ eration non seulement coˆ uteuse, mais qui peut aussi s’av´ erer parfois moins stable que la m´ ethode de
Gauss (voir [Hig88]).
Les formules de Faddev ou de Leverrier offrent une alternative pour le
calcul de l’inverse de A : posons B 0 =I, et calculons par r´ ecurrence
α k =
1
k
tr(AB k−1 ), B k = −AB k−1 + α k I, k = 1, 2, . . ., n.
Puisque B n = 0, si α n = 0 on obtient
A
−1 =
1
α n
B n−1 ,
et le coˆ ut de la m´ ethode pour une matrice pleine est de (n − 1)n
3 flops (pour
plus de d´ etails, voir [FF63], [Bar89]).
3.7 Syst` emes bandes
Les m´ ethodes de discr´ etisation des ´ equations aux d´ eriv´ ees partielles conduisent
souvent `
a la r´ esolution de syst` emes dont les matrices ont des structures bandes,
creuses ou par blocs. Exploiter la structure de la matrice permet une r´ eduction consid´ erable du coˆ ut des algorithmes de factorisation et de substitution.
Dans cette section et dans les suivantes, nous consid´ erons des variantes de la