62
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
r´ ecurrence (1.5), le coˆ ut du calcul des formules de Cramer est de l’ordre de
(n + 1)! flops ce qui est inacceptable mˆ eme pour des matrices A de petites
dimensions (par exemple, un ordinateur capable d’effectuer 10
9 flops par seconde mettrait 9.6·10
47 ann´ ees pour r´ esoudre un syst` eme lin´ eaire de seulement
50 ´ equations).
Pour cette raison, des m´ ethodes num´ eriques alternatives aux formules de Cramer ont ´ et´ e d´ evelopp´ ees. Elles sont dites directes si elles fournissent la solution
du syst` eme en un nombre fini d’´ etapes, et it´ eratives si elles n´ ecessitent (th´ eoriquement) un nombre infini d’´ etapes. Les m´ ethodes it´ eratives seront ´ etudi´ ees
dans le prochain chapitre.
Notons d` es ` a pr´ esent que le choix entre une m´ ethode directe et une m´ ethode it´ erative pour la r´ esolution d’un syst` eme d´ epend non seulement de l’efficacit´ e th´ eorique des algorithmes, mais aussi du type de matrice, des capacit´ es
de stockage en m´ emoire, et enfin, de l’architecture de l’ordinateur.
3.1 Analyse de stabilit´ e des syst` emes lin´ eaires
La r´ esolution d’un syst` eme lin´ eaire par une m´ ethode num´ erique conduit invariablement `
a l’introduction d’erreurs d’arrondi. Seule l’utilisation de m´ ethodes
stables peut ´ eviter de d´ et´ eriorer la pr´ ecision de la solution par la propagation
de telles erreurs. Dans cette section, nous aborderons deux aspects de l’analyse
de stabilit´ e.
Tout d’abord, nous analyserons la sensibilit´ e de la solution de (3.2) aux
perturbations des donn´ ees A et b (analyse a priori directe). Ensuite, en supposant donn´ ee une solution approch´ ee
x de (3.2), nous quantifierons les perturbations des donn´ ees A et b afin que
x soit la solution exacte d’un syst` eme
perturb´ e (analyse a priori r´ etrograde). La taille de ces perturbations nous permettra alors de mesurer la pr´ ecision de la solution calcul´ ee
x par une analyse
a posteriori.
3.1.1 Conditionnement d’une matrice
Le conditionnement d’une matrice A ∈ C
n×n est d´ efini par
K(A) = A A
−1
,
(3.4)
o` u · · est une norme matricielle subordonn´ ee. En g´ en´ eral, K(A) d´ epend du
choix de la norme ; ceci est signal´ e en introduisant un indice dans la notation,
par exemple K ∞ (A) = A ∞ A
−1
∞ . Plus g´ en´ eralement, K p (A) d´ esigne
le conditionnement de A dans la p-norme. Les cas remarquables sont p = 1,
p = 2 et p = ∞ (nous renvoyons `
a l’Exercice 1 pour des relations entre K 1 (A),
K 2 (A) et K ∞ (A)).
Comme cela a d´ ej` a ´ et´ e not´ e dans l’Exemple 2.3, plus le conditionnement
de la matrice est grand, plus la solution du syst` eme lin´ eaire est sensible aux
perturbations des donn´ ees.
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
r´ ecurrence (1.5), le coˆ ut du calcul des formules de Cramer est de l’ordre de
(n + 1)! flops ce qui est inacceptable mˆ eme pour des matrices A de petites
dimensions (par exemple, un ordinateur capable d’effectuer 10
9 flops par seconde mettrait 9.6·10
47 ann´ ees pour r´ esoudre un syst` eme lin´ eaire de seulement
50 ´ equations).
Pour cette raison, des m´ ethodes num´ eriques alternatives aux formules de Cramer ont ´ et´ e d´ evelopp´ ees. Elles sont dites directes si elles fournissent la solution
du syst` eme en un nombre fini d’´ etapes, et it´ eratives si elles n´ ecessitent (th´ eoriquement) un nombre infini d’´ etapes. Les m´ ethodes it´ eratives seront ´ etudi´ ees
dans le prochain chapitre.
Notons d` es ` a pr´ esent que le choix entre une m´ ethode directe et une m´ ethode it´ erative pour la r´ esolution d’un syst` eme d´ epend non seulement de l’efficacit´ e th´ eorique des algorithmes, mais aussi du type de matrice, des capacit´ es
de stockage en m´ emoire, et enfin, de l’architecture de l’ordinateur.
3.1 Analyse de stabilit´ e des syst` emes lin´ eaires
La r´ esolution d’un syst` eme lin´ eaire par une m´ ethode num´ erique conduit invariablement `
a l’introduction d’erreurs d’arrondi. Seule l’utilisation de m´ ethodes
stables peut ´ eviter de d´ et´ eriorer la pr´ ecision de la solution par la propagation
de telles erreurs. Dans cette section, nous aborderons deux aspects de l’analyse
de stabilit´ e.
Tout d’abord, nous analyserons la sensibilit´ e de la solution de (3.2) aux
perturbations des donn´ ees A et b (analyse a priori directe). Ensuite, en supposant donn´ ee une solution approch´ ee
x de (3.2), nous quantifierons les perturbations des donn´ ees A et b afin que
x soit la solution exacte d’un syst` eme
perturb´ e (analyse a priori r´ etrograde). La taille de ces perturbations nous permettra alors de mesurer la pr´ ecision de la solution calcul´ ee
x par une analyse
a posteriori.
3.1.1 Conditionnement d’une matrice
Le conditionnement d’une matrice A ∈ C
n×n est d´ efini par
K(A) = A A
−1
,
(3.4)
o` u · · est une norme matricielle subordonn´ ee. En g´ en´ eral, K(A) d´ epend du
choix de la norme ; ceci est signal´ e en introduisant un indice dans la notation,
par exemple K ∞ (A) = A ∞ A
−1
∞ . Plus g´ en´ eralement, K p (A) d´ esigne
le conditionnement de A dans la p-norme. Les cas remarquables sont p = 1,
p = 2 et p = ∞ (nous renvoyons `
a l’Exercice 1 pour des relations entre K 1 (A),
K 2 (A) et K ∞ (A)).
Comme cela a d´ ej` a ´ et´ e not´ e dans l’Exemple 2.3, plus le conditionnement
de la matrice est grand, plus la solution du syst` eme lin´ eaire est sensible aux
perturbations des donn´ ees.