3.9 Pr´ ecision de la m´ ethode de Gauss
103
flottante. La solution
x fournie par la m´ ethode de Gauss peut ˆ etre vue comme
la solution (en arithm´ etique exacte) du syst` eme perturb´ e (A + δA) x = b, o` u
δA est une matrice de perturbation telle que
|δA| ≤ nu
3|A| + 5|
L||
U|
+ O(u
2 ),
(3.56)
o` u u d´ esigne l’unit´ e d’arrondi et o` u on a utilis´ e la notation valeur absolue.
Par cons´ equent, les ´ el´ ements de δA sont petits `
a condition que ceux de
L et
U le soient. En effectuant un changement de pivot partiel, on peut majorer
le module des ´ el´ ements de
L par 1. Ainsi, en prenant la norme infinie, et en
remarquant que
L ∞ ≤ n, l’estimation (3.56) devient
∞ ≤ nu
3A ∞ + 5n
U ∞
+ O(u
2 ).
(3.57)
La majoration de δA ∞ dans (3.57) n’a d’int´ erˆ et pratique que s’il est possible
d’avoir une estimation de
U ∞ . Dans ce but, on peut effectuer une analyse
r´ etrograde en introduisant le facteur d’accroissement
ρ n =
max
i,j,k
| a
(k)
ij |
max
i,j
|a ij |
.
(3.58)
En utilisant le fait que | u ij | ≤ ρ n max
i,j
|a ij |, le r´ esultat suivant, dˆ u `
a Wilkinson,
peut ˆ etre d´ eduit de (3.57),
∞ ≤ 8un
3 ρ n A ∞ + O(u
2 ).
(3.59)
Le facteur d’accroissement peut ˆ etre born´ e par 2
n−1 , et, bien que dans la
plupart des cas il soit de l’ordre de 10, il existe des matrices pour lesquelles
l’in´ egalit´ e (3.59) devient une ´ egalit´ e (voir, par exemple, l’Exercice 5). Pour
des classes de matrices particuli` eres, on peut trouver des majorations pr´ ecises
de ρ n :
1. pour les matrices bandes dont les largeurs de bande sup´ erieure et inf´ erieure sont ´ egales ` a p, ρ n ≤ 2
2p−1
− (p − 1)2
p−2 ( par cons´ equent, dans le
cas tridiagonal on a ρ n ≤ 2) ;
2. pour les matrices de Hessenberg, ρ n ≤ n ;
3. pour les matrices sym´ etriques d´ efinies positives, ρ n = 1 ;
4. pour les matrices ` a diagonale dominante par colonnes, ρ n ≤ 2.
Pour obtenir une meilleure stabilit´ e en utilisant la m´ ethode de Gauss avec
des matrices quelconques, le recours ` a la m´ ethode du pivot total semble indispensable. On est alors assur´ e que ρ n ≤ n
1/2
2 · 3
1/2
· . . . · n
1/(n−1)
1/2 ,
dont la croissance est plus lente que 2
n−1 quand n augmente.
N´ eanmoins, en dehors de ce cas tr` es particulier, la m´ ethode de Gauss avec
changement de pivot partiel pr´ esente des facteurs d’accroissement acceptables.
Ceci fait d’elle la m´ ethode la plus couramment utilis´ ee dans les calculs pratiques.
103
flottante. La solution
x fournie par la m´ ethode de Gauss peut ˆ etre vue comme
la solution (en arithm´ etique exacte) du syst` eme perturb´ e (A + δA) x = b, o` u
δA est une matrice de perturbation telle que
|δA| ≤ nu
3|A| + 5|
L||
U|
+ O(u
2 ),
(3.56)
o` u u d´ esigne l’unit´ e d’arrondi et o` u on a utilis´ e la notation valeur absolue.
Par cons´ equent, les ´ el´ ements de δA sont petits `
a condition que ceux de
L et
U le soient. En effectuant un changement de pivot partiel, on peut majorer
le module des ´ el´ ements de
L par 1. Ainsi, en prenant la norme infinie, et en
remarquant que
L ∞ ≤ n, l’estimation (3.56) devient
∞ ≤ nu
3A ∞ + 5n
U ∞
+ O(u
2 ).
(3.57)
La majoration de δA ∞ dans (3.57) n’a d’int´ erˆ et pratique que s’il est possible
d’avoir une estimation de
U ∞ . Dans ce but, on peut effectuer une analyse
r´ etrograde en introduisant le facteur d’accroissement
ρ n =
max
i,j,k
| a
(k)
ij |
max
i,j
|a ij |
.
(3.58)
En utilisant le fait que | u ij | ≤ ρ n max
i,j
|a ij |, le r´ esultat suivant, dˆ u `
a Wilkinson,
peut ˆ etre d´ eduit de (3.57),
∞ ≤ 8un
3 ρ n A ∞ + O(u
2 ).
(3.59)
Le facteur d’accroissement peut ˆ etre born´ e par 2
n−1 , et, bien que dans la
plupart des cas il soit de l’ordre de 10, il existe des matrices pour lesquelles
l’in´ egalit´ e (3.59) devient une ´ egalit´ e (voir, par exemple, l’Exercice 5). Pour
des classes de matrices particuli` eres, on peut trouver des majorations pr´ ecises
de ρ n :
1. pour les matrices bandes dont les largeurs de bande sup´ erieure et inf´ erieure sont ´ egales ` a p, ρ n ≤ 2
2p−1
− (p − 1)2
p−2 ( par cons´ equent, dans le
cas tridiagonal on a ρ n ≤ 2) ;
2. pour les matrices de Hessenberg, ρ n ≤ n ;
3. pour les matrices sym´ etriques d´ efinies positives, ρ n = 1 ;
4. pour les matrices ` a diagonale dominante par colonnes, ρ n ≤ 2.
Pour obtenir une meilleure stabilit´ e en utilisant la m´ ethode de Gauss avec
des matrices quelconques, le recours ` a la m´ ethode du pivot total semble indispensable. On est alors assur´ e que ρ n ≤ n
1/2
2 · 3
1/2
· . . . · n
1/(n−1)
1/2 ,
dont la croissance est plus lente que 2
n−1 quand n augmente.
N´ eanmoins, en dehors de ce cas tr` es particulier, la m´ ethode de Gauss avec
changement de pivot partiel pr´ esente des facteurs d’accroissement acceptables.
Ceci fait d’elle la m´ ethode la plus couramment utilis´ ee dans les calculs pratiques.