102
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
En posant H 21 = H
−T
11 A
T
21 et c 1 = H
−T
11 b 1 , on a A 21 = H
T
21 H 11 et les deux
premi` eres lignes du syst` eme sont donc
H 11 x 1 + H 21 x 2 = c 1 ,
H
T
21 H 11 x 1 + A 22 x 2 + A
T
32 x 3 = b 2 .
Par cons´ equent, en multipliant la premi` ere ligne par H
T
21 et en la soustrayant
` a la seconde, on ´ elimine l’inconnue x 1 et on obtient l’´ equation ´ equivalente
suivante
A
(1)
22 x 2 + A
T
32 x 3 = b 2 − H 21 c 1 ,
avec A
(1)
22 = A 22 − H
T
21 H 21 . On effectue alors la factorisation de A
(1)
22 puis on
´ elimine l’inconnue x 3 de la troisi` eme ligne et on r´ ep` ete ces op´ erations pour les
autres lignes du syst` eme. A la fin de cette proc´ edure, au cours de laquelle on
a r´ esolu (n − 1)
n−1
j=1 n j syst` emes lin´ eaires pour calculer les matrices H i+1,i ,
i = 1, . . ., n − 1, on aboutit au syst` eme bidiagonal par blocs suivant
⎡
⎢
⎢
⎢
⎢
⎢
⎣
H 11 H 21
0
H 22
. . .
. . . H n,n−1
0
H nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
c 1
. . .
. . .
c n
⎤
⎥
⎥
⎥
⎥
⎦
qui peut ˆ etre r´ esolu par une m´ ethode de substitution r´ etrograde (“remont´ ee”)
par blocs. Si tous les blocs sont de mˆ eme taille p, le nombre de multiplications
effectu´ ees par cet algorithme est d’environ (7/6)(n − 1)p
3 (en supposant p et
n tr` es grands).
Remarque 3.5 (matrices creuses) Quand le nombre de coefficients non
nuls de la matrice A ∈ R
n×n est de l’ordre de n et que la matrice n’a pas
de structure particuli` ere, on dit que la matrice est creuse. Dans ce cas, la
factorisation entraˆ ıne l’apparition d’un grand nombre de termes non nuls `
a
des endroits o` u les ´ el´ ements ´ etaient initialement nuls. Ce ph´ enom` ene, appel´ e
remplissage (fill-in en anglais), est tr` es coˆ uteux car il empˆ eche de stocker la
matrice factoris´ ee dans le mˆ eme emplacement m´ emoire que la matrice creuse
elle-mˆ eme. Pour cette raison, des algorithmes dont le but est de diminuer le
remplissage ont ´ et´ e d´ evelopp´ es (voir p. ex. [QSS07], Section 3.9).
3.9 Pr´ ecision de la m´ ethode de Gauss
Analysons les effets des erreurs d’arrondi sur la pr´ ecision de la solution obtenue par la m´ ethode de Gauss. Supposons que A et b soient une matrice et un
vecteur de nombres ` a virgule flottante. Notons
L et
U les matrices de la factorisation LU induite par la m´ ethode de Gauss effectu´ ee en arithm´ etique `
a virgule
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
En posant H 21 = H
−T
11 A
T
21 et c 1 = H
−T
11 b 1 , on a A 21 = H
T
21 H 11 et les deux
premi` eres lignes du syst` eme sont donc
H 11 x 1 + H 21 x 2 = c 1 ,
H
T
21 H 11 x 1 + A 22 x 2 + A
T
32 x 3 = b 2 .
Par cons´ equent, en multipliant la premi` ere ligne par H
T
21 et en la soustrayant
` a la seconde, on ´ elimine l’inconnue x 1 et on obtient l’´ equation ´ equivalente
suivante
A
(1)
22 x 2 + A
T
32 x 3 = b 2 − H 21 c 1 ,
avec A
(1)
22 = A 22 − H
T
21 H 21 . On effectue alors la factorisation de A
(1)
22 puis on
´ elimine l’inconnue x 3 de la troisi` eme ligne et on r´ ep` ete ces op´ erations pour les
autres lignes du syst` eme. A la fin de cette proc´ edure, au cours de laquelle on
a r´ esolu (n − 1)
n−1
j=1 n j syst` emes lin´ eaires pour calculer les matrices H i+1,i ,
i = 1, . . ., n − 1, on aboutit au syst` eme bidiagonal par blocs suivant
⎡
⎢
⎢
⎢
⎢
⎢
⎣
H 11 H 21
0
H 22
. . .
. . . H n,n−1
0
H nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
c 1
. . .
. . .
c n
⎤
⎥
⎥
⎥
⎥
⎦
qui peut ˆ etre r´ esolu par une m´ ethode de substitution r´ etrograde (“remont´ ee”)
par blocs. Si tous les blocs sont de mˆ eme taille p, le nombre de multiplications
effectu´ ees par cet algorithme est d’environ (7/6)(n − 1)p
3 (en supposant p et
n tr` es grands).
Remarque 3.5 (matrices creuses) Quand le nombre de coefficients non
nuls de la matrice A ∈ R
n×n est de l’ordre de n et que la matrice n’a pas
de structure particuli` ere, on dit que la matrice est creuse. Dans ce cas, la
factorisation entraˆ ıne l’apparition d’un grand nombre de termes non nuls `
a
des endroits o` u les ´ el´ ements ´ etaient initialement nuls. Ce ph´ enom` ene, appel´ e
remplissage (fill-in en anglais), est tr` es coˆ uteux car il empˆ eche de stocker la
matrice factoris´ ee dans le mˆ eme emplacement m´ emoire que la matrice creuse
elle-mˆ eme. Pour cette raison, des algorithmes dont le but est de diminuer le
remplissage ont ´ et´ e d´ evelopp´ es (voir p. ex. [QSS07], Section 3.9).
3.9 Pr´ ecision de la m´ ethode de Gauss
Analysons les effets des erreurs d’arrondi sur la pr´ ecision de la solution obtenue par la m´ ethode de Gauss. Supposons que A et b soient une matrice et un
vecteur de nombres ` a virgule flottante. Notons
L et
U les matrices de la factorisation LU induite par la m´ ethode de Gauss effectu´ ee en arithm´ etique `
a virgule