3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
79
D’apr` es le th´ eor` eme pr´ ec´ edent, si une sous-matrice A i , i = 1, . . ., n − 1, est
singuli` ere, alors la factorisation peut ne pas exister ou ne pas ˆ etre unique (voir
Exercice 8).
Dans le cas o` u la factorisation LU est unique, notons que, puisque d´ et(A) =
d´ et(LU) = d´ et(L)d´ et(U) = d´ et(U), le d´ eterminant de A est donn´ e par
d´ et(A) = u 11 · · · u nn .
Indiquons la propri´ et´ e suivante (dont la preuve se trouve par exemple dans
[GL89] ou [Hig96]) :
Propri´ et´ e 3.2 Si A est une matrice `
a diagonale dominante par ligne ou par
colonne, alors la factorisation LU de A existe et est unique. En particulier, si
A est ` a diagonale dominante par colonne alors |l ij | ≤ 1 ∀i, j.
Dans la preuve du Th´ eor` eme 3.4, nous avons exploit´ e le fait que les termes
diagonaux de L ´ etaient ´ egaux `
a 1. Nous aurions pu, de mani` ere analogue, fixer
` a 1 les termes diagonaux de la matrice triangulaire sup´ erieure U, obtenant
alors une variante de la m´ ethode de Gauss. Nous consid´ ererons cette variante
` a la Section 3.3.4.
La libert´ e d’imposer les valeurs des termes diagonaux de L ou de U implique que plusieurs factorisations LU existent, chacune pouvant ˆ etre d´ eduite
de l’autre par multiplication par une matrice diagonale convenable (voir Section 3.4.1).
3.3.2 Effets des erreurs d’arrondi
Si les erreurs d’arrondi sont prises en compte, la factorisation induite par la
m´ ethode de Gauss conduit `
a deux matrices,
L et
U, telles que
L
U = A + δA,
o` u δA est une matrice de perturbation. Une estimation de cette perturbation
est donn´ ee par
|δA| ≤
nu
1 − nu
|
L| |
U|,
(3.37)
o` u u est l’unit´ e d’arrondi (voir [Hig89] pour la preuve de ce r´ esultat). On
voit que la pr´ esence de petits pivots peut rendre tr` es grand le second membre
de l’in´ egalit´ e (3.37), conduisant alors `
a un mauvais contrˆ ole de la matrice de
perturbation δA. Il serait donc int´ eressant de trouver des estimations du type
|δA| ≤ g(u)|A|,
o` u g(u) est une fonction de u ` a d´ eterminer. Par exemple, supposons que
L et
U aient des termes positifs. On obtient alors, puisque |
L| |
U| = |
L
U|,
|
L| |
U| = |
L
U| = |A + δA| ≤ |A| + |δA| ≤ |A| +
nu
1 − nu
|
L| |
U|,
(3.38)
79
D’apr` es le th´ eor` eme pr´ ec´ edent, si une sous-matrice A i , i = 1, . . ., n − 1, est
singuli` ere, alors la factorisation peut ne pas exister ou ne pas ˆ etre unique (voir
Exercice 8).
Dans le cas o` u la factorisation LU est unique, notons que, puisque d´ et(A) =
d´ et(LU) = d´ et(L)d´ et(U) = d´ et(U), le d´ eterminant de A est donn´ e par
d´ et(A) = u 11 · · · u nn .
Indiquons la propri´ et´ e suivante (dont la preuve se trouve par exemple dans
[GL89] ou [Hig96]) :
Propri´ et´ e 3.2 Si A est une matrice `
a diagonale dominante par ligne ou par
colonne, alors la factorisation LU de A existe et est unique. En particulier, si
A est ` a diagonale dominante par colonne alors |l ij | ≤ 1 ∀i, j.
Dans la preuve du Th´ eor` eme 3.4, nous avons exploit´ e le fait que les termes
diagonaux de L ´ etaient ´ egaux `
a 1. Nous aurions pu, de mani` ere analogue, fixer
` a 1 les termes diagonaux de la matrice triangulaire sup´ erieure U, obtenant
alors une variante de la m´ ethode de Gauss. Nous consid´ ererons cette variante
` a la Section 3.3.4.
La libert´ e d’imposer les valeurs des termes diagonaux de L ou de U implique que plusieurs factorisations LU existent, chacune pouvant ˆ etre d´ eduite
de l’autre par multiplication par une matrice diagonale convenable (voir Section 3.4.1).
3.3.2 Effets des erreurs d’arrondi
Si les erreurs d’arrondi sont prises en compte, la factorisation induite par la
m´ ethode de Gauss conduit `
a deux matrices,
L et
U, telles que
L
U = A + δA,
o` u δA est une matrice de perturbation. Une estimation de cette perturbation
est donn´ ee par
|δA| ≤
nu
1 − nu
|
L| |
U|,
(3.37)
o` u u est l’unit´ e d’arrondi (voir [Hig89] pour la preuve de ce r´ esultat). On
voit que la pr´ esence de petits pivots peut rendre tr` es grand le second membre
de l’in´ egalit´ e (3.37), conduisant alors `
a un mauvais contrˆ ole de la matrice de
perturbation δA. Il serait donc int´ eressant de trouver des estimations du type
|δA| ≤ g(u)|A|,
o` u g(u) est une fonction de u ` a d´ eterminer. Par exemple, supposons que
L et
U aient des termes positifs. On obtient alors, puisque |
L| |
U| = |
L
U|,
|
L| |
U| = |
L
U| = |A + δA| ≤ |A| + |δA| ≤ |A| +
nu
1 − nu
|
L| |
U|,
(3.38)