74
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
´ equivalent
(A
(2) x = b
(2) )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
x1 +
1
2 x2 +
1
3 x3 =
11
6 ,
0 +
1
12 x2 +
1
12 x3 =
1
6 ,
0 +
1
12
x2 +
4
45
x3 =
31
180
.
Si on soustrait `
a pr´ esent de la troisi` eme ligne la seconde multipli´ ee par m32 = 1, on
obtient le syst` eme triangulaire sup´ erieur
(A
(3) x = b
(3) )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
x1 +
1
2
x2 +
1
3
x3 =
11
6
,
0 +
1
12 x2 +
1
12 x3 =
1
6 ,
0 +
0 +
1
180 x3 =
1
180 ,
` a partir duquel on calcule imm´ ediatement x3 = 1 et, par substitution r´ etrograde, les
autres inconnues x1 = x2 = 1.
•
Remarque 3.2 La matrice de l’Exemple 3.1 est appel´ ee matrice de Hilbert
d’ordre 3. Dans le cas g´ en´ eral n × n, ses ´ el´ ements sont
h ij = 1/(i + j − 1),
i,j = 1, . . ., n.
(3.29)
Comme nous le verrons plus tard, cette matrice est un exemple type de matrice
ayant un grand conditionnement.
Pour effectuer l’´ elimination de Gauss, 2(n − 1)n(n + 1)3 + n(n − 1) flops
sont n´ ecessaires, auxquels il faut ajouter n
2 flops pour la r´ esolution par “remont´ ee” du syst` eme triangulaire U x = b
(n) . Ainsi, environ (2n
3 /3+2n
2 ) flops
sont n´ ecessaires pour r´ esoudre le syst` eme lin´ eaire en utilisant la m´ ethode de
Gauss. En ne conservant que le terme dominant, on peut dire que le proc´ ed´ e
d’´ elimination de Gauss a un coˆ ut de 2n
3 /3 flops.
Comme indiqu´ e pr´ ec´ edemment, la m´ ethode de Gauss n’est correctement d´ efinie que si les pivots a
(k)
kk sont diff´ erents de z´ ero pour k = 1, . . . , n − 1. Malheureusement, le fait que les termes diagonaux de A soient non nuls ne suffit
pas ` a empˆ echer l’apparition de pivots nuls durant la phase d’´ elimination. Par
exemple, la matrice A dans (3.30) est inversible et ses termes diagonaux sont
non nuls
A =
⎡
⎣
1 2 3
2 4 5
7 8 9
⎤
⎦ , A
(2) =
⎡
⎣
1 2
3
0 0
−1
0 −6 −12
⎤
⎦ .
(3.30)
Pourtant, on doit interrompre la m´ ethode de Gauss ` a la seconde ´ etape car
a
(2)
22 = 0.
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
´ equivalent
(A
(2) x = b
(2) )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
x1 +
1
2 x2 +
1
3 x3 =
11
6 ,
0 +
1
12 x2 +
1
12 x3 =
1
6 ,
0 +
1
12
x2 +
4
45
x3 =
31
180
.
Si on soustrait `
a pr´ esent de la troisi` eme ligne la seconde multipli´ ee par m32 = 1, on
obtient le syst` eme triangulaire sup´ erieur
(A
(3) x = b
(3) )
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
x1 +
1
2
x2 +
1
3
x3 =
11
6
,
0 +
1
12 x2 +
1
12 x3 =
1
6 ,
0 +
0 +
1
180 x3 =
1
180 ,
` a partir duquel on calcule imm´ ediatement x3 = 1 et, par substitution r´ etrograde, les
autres inconnues x1 = x2 = 1.
•
Remarque 3.2 La matrice de l’Exemple 3.1 est appel´ ee matrice de Hilbert
d’ordre 3. Dans le cas g´ en´ eral n × n, ses ´ el´ ements sont
h ij = 1/(i + j − 1),
i,j = 1, . . ., n.
(3.29)
Comme nous le verrons plus tard, cette matrice est un exemple type de matrice
ayant un grand conditionnement.
Pour effectuer l’´ elimination de Gauss, 2(n − 1)n(n + 1)3 + n(n − 1) flops
sont n´ ecessaires, auxquels il faut ajouter n
2 flops pour la r´ esolution par “remont´ ee” du syst` eme triangulaire U x = b
(n) . Ainsi, environ (2n
3 /3+2n
2 ) flops
sont n´ ecessaires pour r´ esoudre le syst` eme lin´ eaire en utilisant la m´ ethode de
Gauss. En ne conservant que le terme dominant, on peut dire que le proc´ ed´ e
d’´ elimination de Gauss a un coˆ ut de 2n
3 /3 flops.
Comme indiqu´ e pr´ ec´ edemment, la m´ ethode de Gauss n’est correctement d´ efinie que si les pivots a
(k)
kk sont diff´ erents de z´ ero pour k = 1, . . . , n − 1. Malheureusement, le fait que les termes diagonaux de A soient non nuls ne suffit
pas ` a empˆ echer l’apparition de pivots nuls durant la phase d’´ elimination. Par
exemple, la matrice A dans (3.30) est inversible et ses termes diagonaux sont
non nuls
A =
⎡
⎣
1 2 3
2 4 5
7 8 9
⎤
⎦ , A
(2) =
⎡
⎣
1 2
3
0 0
−1
0 −6 −12
⎤
⎦ .
(3.30)
Pourtant, on doit interrompre la m´ ethode de Gauss ` a la seconde ´ etape car
a
(2)
22 = 0.