100
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
o` u
L 21 = A 21 R
−1
11 D
−1
1 , R 12 = D
−1
1 L
−1
11 A 12 ,
∆ 2 = A 22 − L 21 D 1 R 12 .
Si n´ ecessaire, la proc´ edure de r´ eduction peut ˆ etre r´ ep´ et´ ee sur la matrice ∆ 2 ,
obtenant ainsi une version par blocs de la factorisation LU.
Si A 11 est un scalaire, l’approche ci-dessus permet de r´ eduire de 1 la dimension de la matrice ` a factoriser. En appliquant it´ erativement cette m´ ethode, on
obtient une mani` ere alternative d’effectuer la m´ ethode de Gauss.
Notons que la preuve du Th´ eor` eme 3.4 peut ˆ etre ´ etendue au cas des matrices par blocs. On a donc le r´ esultat suivant :
Propri´ et´ e 3.5 Une matrice A ∈ R
n×n d´ ecompos´ ee en m × m blocs A ij ,
i, j = 1, . . . , m, admet une unique d´ ecomposition LU par blocs (o` u L n’a que
des 1 sur la diagonale) si et seulement si les m − 1 mineurs principaux par
blocs de A sont non nuls.
L’analyse de stabilit´ e effectu´ ee pour la factorisation LU classique est encore
valable pour la factorisation par blocs, les deux d´ ecompositions ayant une
formulation analogue.
On trouvera dans [Hig88] des r´ esultats plus fins concernant l’utilisation
efficace de produits matrice-matrice rapides dans les algorithmes par blocs.
Dans la section suivante, nous nous concentrons seulement sur le cas des matrices tridiagonales par blocs.
3.8.2 Inverse d’une matrice par blocs
L’inverse d’une matrice par blocs peut ˆ etre construit en utilisant la factorisation introduite dans la section pr´ ec´ edente. Consid´ erons le cas particulier o` u A
est une matrice par blocs de la forme
A = C + UBV,
o` u C est la matrice des blocs diagonaux de A, et o` u le produit UBV repr´ esente
les blocs extradiagonaux. Dans ce cas, la matrice A peut ˆ etre invers´ ee en
utilisant la formule dite de Sherman-Morrison ou de Woodbury
A
−1 = (C + UBV)
−1 = C
−1
− C
−1 U
I + BVC
−1 U
−1 BVC
−1 ,
(3.54)
o` u l’on a suppos´ e inversibles les matrices C et I + BVC
−1 U. Cette formule a
de nombreuses applications th´ eoriques et pratiques (voir [JM92]).
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
o` u
L 21 = A 21 R
−1
11 D
−1
1 , R 12 = D
−1
1 L
−1
11 A 12 ,
∆ 2 = A 22 − L 21 D 1 R 12 .
Si n´ ecessaire, la proc´ edure de r´ eduction peut ˆ etre r´ ep´ et´ ee sur la matrice ∆ 2 ,
obtenant ainsi une version par blocs de la factorisation LU.
Si A 11 est un scalaire, l’approche ci-dessus permet de r´ eduire de 1 la dimension de la matrice ` a factoriser. En appliquant it´ erativement cette m´ ethode, on
obtient une mani` ere alternative d’effectuer la m´ ethode de Gauss.
Notons que la preuve du Th´ eor` eme 3.4 peut ˆ etre ´ etendue au cas des matrices par blocs. On a donc le r´ esultat suivant :
Propri´ et´ e 3.5 Une matrice A ∈ R
n×n d´ ecompos´ ee en m × m blocs A ij ,
i, j = 1, . . . , m, admet une unique d´ ecomposition LU par blocs (o` u L n’a que
des 1 sur la diagonale) si et seulement si les m − 1 mineurs principaux par
blocs de A sont non nuls.
L’analyse de stabilit´ e effectu´ ee pour la factorisation LU classique est encore
valable pour la factorisation par blocs, les deux d´ ecompositions ayant une
formulation analogue.
On trouvera dans [Hig88] des r´ esultats plus fins concernant l’utilisation
efficace de produits matrice-matrice rapides dans les algorithmes par blocs.
Dans la section suivante, nous nous concentrons seulement sur le cas des matrices tridiagonales par blocs.
3.8.2 Inverse d’une matrice par blocs
L’inverse d’une matrice par blocs peut ˆ etre construit en utilisant la factorisation introduite dans la section pr´ ec´ edente. Consid´ erons le cas particulier o` u A
est une matrice par blocs de la forme
A = C + UBV,
o` u C est la matrice des blocs diagonaux de A, et o` u le produit UBV repr´ esente
les blocs extradiagonaux. Dans ce cas, la matrice A peut ˆ etre invers´ ee en
utilisant la formule dite de Sherman-Morrison ou de Woodbury
A
−1 = (C + UBV)
−1 = C
−1
− C
−1 U
I + BVC
−1 U
−1 BVC
−1 ,
(3.54)
o` u l’on a suppos´ e inversibles les matrices C et I + BVC
−1 U. Cette formule a
de nombreuses applications th´ eoriques et pratiques (voir [JM92]).