3.1 Analyse de stabilit´ e des syst` emes lin´ eaires
65
Le fait qu’un syst` eme lin´ eaire soit bien conditionn´ e n’implique pas n´ ecessairement que sa solution soit calcul´ ee avec pr´ ecision. Il faut en plus, comme on l’a
soulign´ e au Chapitre 2, utiliser des algorithmes stables. Inversement, le fait
d’avoir une matrice avec un grand conditionnement n’empˆ eche pas n´ ecessairement le syst` eme global d’ˆ etre bien conditionn´ e pour des choix particuliers
du second membre b (voir Exercice 4).
Voici un cas particulier du Th´ eor` eme 3.1.
Th´ eor` eme 3.2 Supposons que les conditions du Th´ eor` eme 3.1 soient remplies et posons δA = 0. Alors
1
K(A)
b
≤
x
≤ K(A)
b
.
(3.11)
D´ emonstration. Nous prouvons seulement la premi` ere in´ egalit´ e puisque la seconde d´ ecoule directement de (3.9). La relation δx = A
−1 δb implique δb ≤
En multipliant les deux membres par x et en rappelant que x ≤
−1 il vient x ≤ K(A)b qui est l’in´ egalit´ e voulue.
3
En vue d’utiliser les in´ egalit´ es (3.9) et (3.11) pour l’analyse de la propagation des erreurs d’arrondi dans le cas des m´ ethodes directes, δA et δb
doivent ˆ etre major´ es en fonction de la dimension du syst` eme et des caract´ eristiques de l’arithm´ etique `
a virgule flottante.
Il est en effet raisonnable de s’attendre `
a ce que les perturbations induites
par une m´ ethode de r´ esolution soient telles que δA ≤ γA et δb ≤ γb,
γ ´ etant un nombre positif qui d´ epend de l’unit´ e d’arrondi u (d´ efini en (2.34)).
Par exemple, nous supposerons dor´ enavant que γ = β
1−t , o` u β est la base et
t le nombre de chiffres significatifs de la mantisse du syst` eme F des nombres `
a
virgule flottante. Dans ce cas, on peut compl´ eter (3.9) par le th´ eor` eme suivant.
Th´ eor` eme 3.3 Supposons que δA ≤ γA, δb ≤ γb avec γ ∈ R
+ et
δA ∈ R
n×n , δb ∈ R
n . Alors, si γK(A) < 1, on a les in´ egalit´ es suivantes :
+ δx
x
≤
1 + γK(A)
1 − γK(A)
,
(3.12)
x
≤
2γ
1 − γK(A)
K(A).
(3.13)
D´ emonstration. D’apr` es (3.8), (I + A
−1 δA)(x + δx) = x + A
−1 δb. De plus,
puisque γK(A) < 1 et δA ≤ γA, I + A
−1 δA est inversible. En prenant
l’inverse de cette matrice et en passant aux normes, on obtient x + δx ≤
(I + A
−1 δA)
−1
+ γA
−1
. Le Th´ eor` eme 1.5 entraˆ ıne alors que
+ δx ≤
1
1 − −A −1 δA
+ γA
−1
,
65
Le fait qu’un syst` eme lin´ eaire soit bien conditionn´ e n’implique pas n´ ecessairement que sa solution soit calcul´ ee avec pr´ ecision. Il faut en plus, comme on l’a
soulign´ e au Chapitre 2, utiliser des algorithmes stables. Inversement, le fait
d’avoir une matrice avec un grand conditionnement n’empˆ eche pas n´ ecessairement le syst` eme global d’ˆ etre bien conditionn´ e pour des choix particuliers
du second membre b (voir Exercice 4).
Voici un cas particulier du Th´ eor` eme 3.1.
Th´ eor` eme 3.2 Supposons que les conditions du Th´ eor` eme 3.1 soient remplies et posons δA = 0. Alors
1
K(A)
b
≤
x
≤ K(A)
b
.
(3.11)
D´ emonstration. Nous prouvons seulement la premi` ere in´ egalit´ e puisque la seconde d´ ecoule directement de (3.9). La relation δx = A
−1 δb implique δb ≤
En multipliant les deux membres par x et en rappelant que x ≤
−1 il vient x ≤ K(A)b qui est l’in´ egalit´ e voulue.
3
En vue d’utiliser les in´ egalit´ es (3.9) et (3.11) pour l’analyse de la propagation des erreurs d’arrondi dans le cas des m´ ethodes directes, δA et δb
doivent ˆ etre major´ es en fonction de la dimension du syst` eme et des caract´ eristiques de l’arithm´ etique `
a virgule flottante.
Il est en effet raisonnable de s’attendre `
a ce que les perturbations induites
par une m´ ethode de r´ esolution soient telles que δA ≤ γA et δb ≤ γb,
γ ´ etant un nombre positif qui d´ epend de l’unit´ e d’arrondi u (d´ efini en (2.34)).
Par exemple, nous supposerons dor´ enavant que γ = β
1−t , o` u β est la base et
t le nombre de chiffres significatifs de la mantisse du syst` eme F des nombres `
a
virgule flottante. Dans ce cas, on peut compl´ eter (3.9) par le th´ eor` eme suivant.
Th´ eor` eme 3.3 Supposons que δA ≤ γA, δb ≤ γb avec γ ∈ R
+ et
δA ∈ R
n×n , δb ∈ R
n . Alors, si γK(A) < 1, on a les in´ egalit´ es suivantes :
+ δx
x
≤
1 + γK(A)
1 − γK(A)
,
(3.12)
x
≤
2γ
1 − γK(A)
K(A).
(3.13)
D´ emonstration. D’apr` es (3.8), (I + A
−1 δA)(x + δx) = x + A
−1 δb. De plus,
puisque γK(A) < 1 et δA ≤ γA, I + A
−1 δA est inversible. En prenant
l’inverse de cette matrice et en passant aux normes, on obtient x + δx ≤
(I + A
−1 δA)
−1
+ γA
−1
. Le Th´ eor` eme 1.5 entraˆ ıne alors que
+ δx ≤
1
1 − −A −1 δA
+ γA
−1
,