3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
75
Des conditions plus restrictives sur A sont donc n´ ecessaires pour assurer
que la m´ ethode s’applique bien. Nous verrons `
a la Section 3.3.1 que si les
mineurs principaux d i de A sont non nuls pour i = 1, . . . , n − 1 alors les pivots
correspondants a
(i)
ii sont ´ egalement non nuls (rappelons que d i est le d´ eterminant de la i-i` eme sous-matrice principale A i , i.e. la sous-matrice constitu´ ee
des i premi` eres lignes et colonnes de A). La matrice de l’exemple pr´ ec´ edent
ne satisfait pas cette condition puisque d 1 = 1 et d 2 = 0.
Il existe des cat´ egories de matrices pour lesquelles la m´ ethode de Gauss peut
ˆ etre utilis´ ee sans risque dans sa forme de base (3.28). Parmi ces matrices,
citons les suivantes :
1. les matrices ` a diagonale dominante par ligne ;
2. les matrices ` a diagonale dominante par colonne. Dans ce cas, on peut
mˆ eme montrer que les multiplicateurs ont un module inf´ erieur ou ´ egal ` a
1 (voir Propri´ et´ e 3.2) ;
3. les matrices sym´ etriques d´ efinies positives (voir Th´ eor` eme 3.6).
Ces r´ esultats seront ´ etablis rigoureusement dans les prochaines sections.
3.3.1 La m´ ethode de Gauss comme m´ ethode de factorisation
Dans cette section, nous montrons que la m´ ethode de Gauss est ´ equivalente `
a
la factorisation de la matrice A sous la forme d’un produit de deux matrices,
A=LU, avec U=A
(n) . Les matrices L et U ne d´ ependant que de A (et non
du second membre), la mˆ eme factorisation peut ˆ etre r´ eutilis´ ee quand on r´ esout plusieurs syst` emes lin´ eaires ayant la mˆ eme matrice A mais des seconds
membres b diff´ erents. Le nombre d’op´ erations est alors consid´ erablement r´ eduit, puisque l’effort de calcul le plus important, environ 2n
3 /3flops, est d´ edi´ e
` a la proc´ edure d’´ elimination.
Revenons ` a l’Exemple 3.1 concernant la matrice de Hilbert H 3 . En pratique, pour passer de A
(1) =H 3 ` a A
(2) , on a multipli´ e ` a la premi` ere ´ etape le
syst` eme par la matrice
M 1 =
⎡
⎢
⎢
⎢
⎣
1 0 0
−
1
2
1 0
−
1
3
0 1
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
1 0 0
−m 21 1 0
−m 31 0 1
⎤
⎥
⎥
⎥
⎦
.
En effet,
M 1 A = M 1 A
(1) =
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
0
1
12
1
12
0
1
12
4
45
⎤
⎥
⎥
⎥
⎦
= A
(2) .
75
Des conditions plus restrictives sur A sont donc n´ ecessaires pour assurer
que la m´ ethode s’applique bien. Nous verrons `
a la Section 3.3.1 que si les
mineurs principaux d i de A sont non nuls pour i = 1, . . . , n − 1 alors les pivots
correspondants a
(i)
ii sont ´ egalement non nuls (rappelons que d i est le d´ eterminant de la i-i` eme sous-matrice principale A i , i.e. la sous-matrice constitu´ ee
des i premi` eres lignes et colonnes de A). La matrice de l’exemple pr´ ec´ edent
ne satisfait pas cette condition puisque d 1 = 1 et d 2 = 0.
Il existe des cat´ egories de matrices pour lesquelles la m´ ethode de Gauss peut
ˆ etre utilis´ ee sans risque dans sa forme de base (3.28). Parmi ces matrices,
citons les suivantes :
1. les matrices ` a diagonale dominante par ligne ;
2. les matrices ` a diagonale dominante par colonne. Dans ce cas, on peut
mˆ eme montrer que les multiplicateurs ont un module inf´ erieur ou ´ egal ` a
1 (voir Propri´ et´ e 3.2) ;
3. les matrices sym´ etriques d´ efinies positives (voir Th´ eor` eme 3.6).
Ces r´ esultats seront ´ etablis rigoureusement dans les prochaines sections.
3.3.1 La m´ ethode de Gauss comme m´ ethode de factorisation
Dans cette section, nous montrons que la m´ ethode de Gauss est ´ equivalente `
a
la factorisation de la matrice A sous la forme d’un produit de deux matrices,
A=LU, avec U=A
(n) . Les matrices L et U ne d´ ependant que de A (et non
du second membre), la mˆ eme factorisation peut ˆ etre r´ eutilis´ ee quand on r´ esout plusieurs syst` emes lin´ eaires ayant la mˆ eme matrice A mais des seconds
membres b diff´ erents. Le nombre d’op´ erations est alors consid´ erablement r´ eduit, puisque l’effort de calcul le plus important, environ 2n
3 /3flops, est d´ edi´ e
` a la proc´ edure d’´ elimination.
Revenons ` a l’Exemple 3.1 concernant la matrice de Hilbert H 3 . En pratique, pour passer de A
(1) =H 3 ` a A
(2) , on a multipli´ e ` a la premi` ere ´ etape le
syst` eme par la matrice
M 1 =
⎡
⎢
⎢
⎢
⎣
1 0 0
−
1
2
1 0
−
1
3
0 1
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
1 0 0
−m 21 1 0
−m 31 0 1
⎤
⎥
⎥
⎥
⎦
.
En effet,
M 1 A = M 1 A
(1) =
⎡
⎢
⎢
⎢
⎣
1
1
2
1
3
0
1
12
1
12
0
1
12
4
45
⎤
⎥
⎥
⎥
⎦
= A
(2) .