64
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
La relation (3.6) semble indiquer que le d´ eterminant est un candidat naturel pour mesurer le conditionnement d’une matrice, puisqu’avec (3.3) on
pourrait penser qu’une matrice ayant un petit d´ eterminant est “presque” singuli` ere. En fait, cette conclusion est fausse car il existe des exemples de matrices dont le conditionnement et le d´ eterminant sont tous les deux grands ou
tous les deux petits (voir Exercice 2).
3.1.2 Analyse a priori directe
Dans cette section nous introduisons une mesure de la sensibilit´ e du syst` eme
aux perturbations des donn´ ees. Ces perturbations seront interpr´ et´ ees ` a la
Section 3.9 comme ´ etant les effets des erreurs d’arrondi induites par la m´ ethode
num´ erique utilis´ ee pour r´ esoudre le syst` eme. Pour une analyse plus compl` ete
du sujet nous renvoyons `
a [Dat95], [GL89], [Ste73] et [Var62].
A cause des erreurs d’arrondi, une m´ ethode num´ erique pour r´ esoudre (3.2)
ne fournit pas la solution exacte mais seulement une solution approch´ ee qui
satisfait un syst` eme perturb´ e. En d’autres termes, une m´ ethode num´ erique
fournit une solution (exacte) x + δx du syst` eme perturb´ e
(A + δA)(x + δx) = b + δb.
(3.8)
Le r´ esultat suivant donne une estimation de δx en fonction de δA et δb.
Th´ eor` eme 3.1 Soit A ∈ R
n×n une matrice inversible et δA ∈ R
n×n telles
que l’in´ egalit´ e (3.7) soit satisfaite pour une norme matricielle subordonn´ ee
· ·. Si x∈ R
n est la solution de Ax=b avec b ∈ R
n (b = 0) et si δx ∈ R
n
satisfait (3.8) pour δb ∈ R
n , alors
x
≤
K(A)
1 − K(A)δA/A
b
+
A
.
(3.9)
D´ emonstration. D’apr` es (3.7), la matrice A
−1 δA a une norme inf´ erieure ` a 1.
Ainsi, d’apr` es le Th´ eor` eme 1.5, I + A
−1 δA est inversible et (1.28) implique
(I + A
−1 δA)
−1 ≤
1
1 − −A −1 δA
≤
1
1 − −A −1
.
(3.10)
D’autre part, en r´ esolvant (3.8) en δx et en rappelant que Ax = b, on obtient
δx = (I + A
−1 δA)
−1 A
−1 (δb − δAx).
En passant aux normes et en utilisant (3.10), on a donc
≤
−1
1 − −A −1
(δb + δA .
Enfin, en divisant les deux membres par x (qui est non nul puisque b = 0 et A
est inversible) et en remarquant que x ≥ ≥b/A, on obtient le r´ esultat voulu.
3
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
La relation (3.6) semble indiquer que le d´ eterminant est un candidat naturel pour mesurer le conditionnement d’une matrice, puisqu’avec (3.3) on
pourrait penser qu’une matrice ayant un petit d´ eterminant est “presque” singuli` ere. En fait, cette conclusion est fausse car il existe des exemples de matrices dont le conditionnement et le d´ eterminant sont tous les deux grands ou
tous les deux petits (voir Exercice 2).
3.1.2 Analyse a priori directe
Dans cette section nous introduisons une mesure de la sensibilit´ e du syst` eme
aux perturbations des donn´ ees. Ces perturbations seront interpr´ et´ ees ` a la
Section 3.9 comme ´ etant les effets des erreurs d’arrondi induites par la m´ ethode
num´ erique utilis´ ee pour r´ esoudre le syst` eme. Pour une analyse plus compl` ete
du sujet nous renvoyons `
a [Dat95], [GL89], [Ste73] et [Var62].
A cause des erreurs d’arrondi, une m´ ethode num´ erique pour r´ esoudre (3.2)
ne fournit pas la solution exacte mais seulement une solution approch´ ee qui
satisfait un syst` eme perturb´ e. En d’autres termes, une m´ ethode num´ erique
fournit une solution (exacte) x + δx du syst` eme perturb´ e
(A + δA)(x + δx) = b + δb.
(3.8)
Le r´ esultat suivant donne une estimation de δx en fonction de δA et δb.
Th´ eor` eme 3.1 Soit A ∈ R
n×n une matrice inversible et δA ∈ R
n×n telles
que l’in´ egalit´ e (3.7) soit satisfaite pour une norme matricielle subordonn´ ee
· ·. Si x∈ R
n est la solution de Ax=b avec b ∈ R
n (b = 0) et si δx ∈ R
n
satisfait (3.8) pour δb ∈ R
n , alors
x
≤
K(A)
1 − K(A)δA/A
b
+
A
.
(3.9)
D´ emonstration. D’apr` es (3.7), la matrice A
−1 δA a une norme inf´ erieure ` a 1.
Ainsi, d’apr` es le Th´ eor` eme 1.5, I + A
−1 δA est inversible et (1.28) implique
(I + A
−1 δA)
−1 ≤
1
1 − −A −1 δA
≤
1
1 − −A −1
.
(3.10)
D’autre part, en r´ esolvant (3.8) en δx et en rappelant que Ax = b, on obtient
δx = (I + A
−1 δA)
−1 A
−1 (δb − δAx).
En passant aux normes et en utilisant (3.10), on a donc
≤
−1
1 − −A −1
(δb + δA .
Enfin, en divisant les deux membres par x (qui est non nul puisque b = 0 et A
est inversible) et en remarquant que x ≥ ≥b/A, on obtient le r´ esultat voulu.
3