72
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
La m´ ethode d’´ elimination de Gauss a pour but de transformer le syst` eme
Ax=b en un syst` eme ´ equivalent (c’est-` a-dire ayant la mˆ eme solution) de la
forme Ux=
b, o` u U est une matrice triangulaire sup´ erieure et
b est un second
membre convenablement modifi´ e. Ce dernier syst` eme peut ˆ etre alors r´ esolu
par une m´ ethode de substitution r´ etrograde.
Au cours de la transformation, on utilise essentiellement la propri´ et´ e selon laquelle on ne change pas la solution du syst` eme quand on ajoute `
a une
´ equation donn´ ee une combinaison lin´ eaire des autres ´ equations.
Consid´ erons une matrice inversible A ∈ R
n×n dont le terme diagonal a 11
est suppos´ e non nul. On pose A
(1) = A et b
(1) = b. On introduit les multiplicateurs
m i1 =
a
(1)
i1
a
(1)
11
, i = 2, 3, . . ., n,
o` u les a
(1)
ij d´ esignent les ´ el´ ements de A
(1) . On peut ´ eliminer l’inconnue x 1 des
lignes i = 2, . . . , n en leur retranchant m i1 fois la premi` ere ligne et en faisant
de mˆ eme pour le membre de droite. On d´ efinit alors
a
(2)
ij = a
(1)
ij − m i1 a
(1)
1j , i,j = 2, . . ., n,
b
(2)
i
= b
(1)
i − m i1 b
(1)
1 , i = 2, . . . , n,
o` u les b
(1)
i
sont les composantes de b
(1) et on obtient un nouveau syst` eme de
la forme
⎡
⎢
⎢
⎢
⎢
⎣
a
(1)
11
a
(1)
12
. . . a
(1)
1n
0
a
(2)
22
. . . a
(2)
2n
. . .
. . .
. . .
0
a
(2)
n2
. . . a
(2)
nn
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
x 1
x 2
. . .
x n
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b
(1)
1
b
(2)
2
. . .
b
(2)
n
⎤
⎥
⎥
⎥
⎥
⎦
,
que l’on note A
(2) x = b
(2) et qui est ´ equivalent au syst` eme de d´ epart.
On peut `
a nouveau transformer ce syst` eme de fa¸ con `
a ´ eliminer l’inconnue x 2
des lignes 3, . . . , n. En poursuivant ainsi, on obtient une suite finie de syst` emes
A
(k) x = b
(k) , 1 ≤ k ≤ n,
(3.26)
o` u, pour k ≥ 2, la matrice A
(k) est de la forme suivante
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
3.3 M´ ethode d’´ elimination de Gauss et factorisation LU
La m´ ethode d’´ elimination de Gauss a pour but de transformer le syst` eme
Ax=b en un syst` eme ´ equivalent (c’est-` a-dire ayant la mˆ eme solution) de la
forme Ux=
b, o` u U est une matrice triangulaire sup´ erieure et
b est un second
membre convenablement modifi´ e. Ce dernier syst` eme peut ˆ etre alors r´ esolu
par une m´ ethode de substitution r´ etrograde.
Au cours de la transformation, on utilise essentiellement la propri´ et´ e selon laquelle on ne change pas la solution du syst` eme quand on ajoute `
a une
´ equation donn´ ee une combinaison lin´ eaire des autres ´ equations.
Consid´ erons une matrice inversible A ∈ R
n×n dont le terme diagonal a 11
est suppos´ e non nul. On pose A
(1) = A et b
(1) = b. On introduit les multiplicateurs
m i1 =
a
(1)
i1
a
(1)
11
, i = 2, 3, . . ., n,
o` u les a
(1)
ij d´ esignent les ´ el´ ements de A
(1) . On peut ´ eliminer l’inconnue x 1 des
lignes i = 2, . . . , n en leur retranchant m i1 fois la premi` ere ligne et en faisant
de mˆ eme pour le membre de droite. On d´ efinit alors
a
(2)
ij = a
(1)
ij − m i1 a
(1)
1j , i,j = 2, . . ., n,
b
(2)
i
= b
(1)
i − m i1 b
(1)
1 , i = 2, . . . , n,
o` u les b
(1)
i
sont les composantes de b
(1) et on obtient un nouveau syst` eme de
la forme
⎡
⎢
⎢
⎢
⎢
⎣
a
(1)
11
a
(1)
12
. . . a
(1)
1n
0
a
(2)
22
. . . a
(2)
2n
. . .
. . .
. . .
0
a
(2)
n2
. . . a
(2)
nn
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎣
x 1
x 2
. . .
x n
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b
(1)
1
b
(2)
2
. . .
b
(2)
n
⎤
⎥
⎥
⎥
⎥
⎦
,
que l’on note A
(2) x = b
(2) et qui est ´ equivalent au syst` eme de d´ epart.
On peut `
a nouveau transformer ce syst` eme de fa¸ con `
a ´ eliminer l’inconnue x 2
des lignes 3, . . . , n. En poursuivant ainsi, on obtient une suite finie de syst` emes
A
(k) x = b
(k) , 1 ≤ k ≤ n,
(3.26)
o` u, pour k ≥ 2, la matrice A
(k) est de la forme suivante