3.11 Am´ eliorer la pr´ ecision de la m´ ethode de Gauss
107
Le scaling de A par lignes consiste ` a trouver une matrice diagonale inversible D 1 telle que les ´ el´ ements diagonaux de D 1 A aient tous le mˆ eme ordre de
grandeur. Le syst` eme lin´ eaire Ax = b se transforme en
D 1 Ax = D 1 b.
Quand on consid` ere ` a la fois les lignes et les colonnes de A, le scaling de (3.2)
s’´ ecrit
(D 1 AD 2 )y = D 1 b avec y = D
−1
2 x,
o` u D 2 est suppos´ ee inversible. La matrice D 1 modifie les ´ equations tandis que
D 2 modifie les inconnues. Remarquer qu’afin d’´ eviter les erreurs d’arrondi, les
matrices de scaling sont choisies de la forme
D 1 = diag(β
r1 , . . . , β
rn ), D 2 = diag(β
c1 , . . . , β
cn ),
o` u β est la base de l’arithm´ etique `
a virgule flottante utilis´ ee et o` u les exposants
r 1 , . . ., r n , c 1 , . . . , c n sont `
a d´ eterminer. On peut montrer que
−1
2 ( x − x) ∞
D
−1
2 x ∞
uK ∞ (D 1 AD 2 ),
o` u u est l’unit´ e d’arrondi. Le scaling sera donc efficace si K ∞ (D 1 AD 2 ) est
beaucoup plus petit que K ∞ (A). Trouver des matrices D 1 et D 2 convenables
n’est en g´ en´ eral pas une tˆ ache facile.
Une strat´ egie consiste, par exemple, ` a prendre D 1 et D 2 de mani` ere ` a ce
que D 1 AD 2 ∞ et D 1 AD 2 1 appartiennent `
a l’intervalle [1/β, 1], o` u β est
la base de l’arithm´ etique `
a virgule flottante (voir [McK62] pour une analyse
d´ etaill´ ee dans le cas de la factorisation de Crout).
Remarque 3.6 (conditionnement de Skeel) Le conditionnement de Skeel,
d´ efini par cond(A) = |A
−1
| |A| | ∞ , est le supr´ emum pour x∈ R
n , x = 0,
des nombres
cond(A, x) =
|A
−1
| |A| |x| | ∞
x ∞
.
Contrairement `
a K(A), cond(A) est invariant par rapport au scaling par ligne
de A, c’est-` a-dire, par rapport aux transformations de A de la forme DA, o` u
D est une matrice diagonale inversible. Le conditionnement de Skeel cond(A)
est insensible au scaling de A par lignes.
3.11.2 Raffinement it´ eratif
Le raffinement it´ eratif est une technique pour am´ eliorer la solution obtenue
par une m´ ethode directe. Supposons que le syst` eme lin´ eaire (3.2) ait ´ et´ e r´ esolu par une factorisation LU (avec changement de pivot partiel ou total), et
107
Le scaling de A par lignes consiste ` a trouver une matrice diagonale inversible D 1 telle que les ´ el´ ements diagonaux de D 1 A aient tous le mˆ eme ordre de
grandeur. Le syst` eme lin´ eaire Ax = b se transforme en
D 1 Ax = D 1 b.
Quand on consid` ere ` a la fois les lignes et les colonnes de A, le scaling de (3.2)
s’´ ecrit
(D 1 AD 2 )y = D 1 b avec y = D
−1
2 x,
o` u D 2 est suppos´ ee inversible. La matrice D 1 modifie les ´ equations tandis que
D 2 modifie les inconnues. Remarquer qu’afin d’´ eviter les erreurs d’arrondi, les
matrices de scaling sont choisies de la forme
D 1 = diag(β
r1 , . . . , β
rn ), D 2 = diag(β
c1 , . . . , β
cn ),
o` u β est la base de l’arithm´ etique `
a virgule flottante utilis´ ee et o` u les exposants
r 1 , . . ., r n , c 1 , . . . , c n sont `
a d´ eterminer. On peut montrer que
−1
2 ( x − x) ∞
D
−1
2 x ∞
uK ∞ (D 1 AD 2 ),
o` u u est l’unit´ e d’arrondi. Le scaling sera donc efficace si K ∞ (D 1 AD 2 ) est
beaucoup plus petit que K ∞ (A). Trouver des matrices D 1 et D 2 convenables
n’est en g´ en´ eral pas une tˆ ache facile.
Une strat´ egie consiste, par exemple, ` a prendre D 1 et D 2 de mani` ere ` a ce
que D 1 AD 2 ∞ et D 1 AD 2 1 appartiennent `
a l’intervalle [1/β, 1], o` u β est
la base de l’arithm´ etique `
a virgule flottante (voir [McK62] pour une analyse
d´ etaill´ ee dans le cas de la factorisation de Crout).
Remarque 3.6 (conditionnement de Skeel) Le conditionnement de Skeel,
d´ efini par cond(A) = |A
−1
| |A| | ∞ , est le supr´ emum pour x∈ R
n , x = 0,
des nombres
cond(A, x) =
|A
−1
| |A| |x| | ∞
x ∞
.
Contrairement `
a K(A), cond(A) est invariant par rapport au scaling par ligne
de A, c’est-` a-dire, par rapport aux transformations de A de la forme DA, o` u
D est une matrice diagonale inversible. Le conditionnement de Skeel cond(A)
est insensible au scaling de A par lignes.
3.11.2 Raffinement it´ eratif
Le raffinement it´ eratif est une technique pour am´ eliorer la solution obtenue
par une m´ ethode directe. Supposons que le syst` eme lin´ eaire (3.2) ait ´ et´ e r´ esolu par une factorisation LU (avec changement de pivot partiel ou total), et