90
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Exemple 3.3 Revenons ` a la matrice (3.30) pour laquelle la m´ ethode de Gauss
donne un pivot nul `
a la seconde ´ etape. En ´ echangeant simplement la deuxi` eme et la
troisi` eme ligne, on trouve un pivot non nul et on peut ex´ ecuter une ´ etape de plus.
Le syst` eme obtenu est ´ equivalent au syst` eme de d´ epart, et on constate qu’il est d´ ej` a
triangulaire sup´ erieur. En effet,
A
(2) =
⎡
⎣
1
2
3
0 −6 −12
0
0
−1
⎤
⎦ = U,
et les matrices de transformation sont donn´ ees par
M1 =
⎡
⎣
1
0 0
−2 1 0
−7 0 1
⎤
⎦ , M2 =
⎡
⎣
1 0 0
0 1 0
0 0 1
⎤
⎦ .
D’un point de vue alg´ ebrique, ayant effectu´ e une permutation des lignes de A, l’´ egalit´ e
A=M
−1
1 M
−1
2 U doit ˆ etre remplac´ ee par A=M
−1
1
P M
−1
2 U o` u P est la matrice de
permutation
P =
⎡
⎣
1 0 0
0 0 1
0 1 0
⎤
⎦ .
(3.47)
•
La strat´ egie de pivot adopt´ ee dans l’Exemple 3.3 peut ˆ etre g´ en´ eralis´ ee en recherchant, `
a chaque ´ etape k de l’´ elimination, un pivot non nul parmi les termes
de la sous-colonne A
(k) (k : n, k). On dit alors qu’on effectue un changement
de pivot partiel (par ligne).
On peut voir `
a partir de (3.27) qu’une grande valeur de m ik (provenant par
exemple d’un petit pivot a
(k)
kk ) peut amplifier les erreurs d’arrondi affectant les
termes a
(k)
kj . Par cons´ equent, afin d’assurer une meilleure stabilit´ e, on choisit
comme pivot l’´ el´ ement de la colonne A
(k) (k : n, k) le plus grand en module
et le changement de pivot partiel est g´ en´ eralement effectu´ e ` a chaque ´ etape,
mˆ eme si ce n’est pas strictement n´ ecessaire (c’est-` a-dire mˆ eme s’il n’y a pas
de pivot nul).
Une m´ ethode alternative consiste `
a rechercher le pivot dans l’ensemble de
la sous-matrice A
(k) (k : n, k : n), effectuant alors un changement de pivot total
(voir Figure 3.2). Remarquer cependant que le changement de pivot partiel
ne requiert qu’un surcoˆ ut d’environ n
2 tests, alors que le changement de pivot
total en n´ ecessite environ 2n
3 /3, ce qui augmente consid´ erablement le coˆ ut de
la m´ ethode de Gauss.
Exemple 3.4 Consid´ erons le syst` eme lin´ eaire Ax = b avec
A =
10
−13
1
1
1
,
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Exemple 3.3 Revenons ` a la matrice (3.30) pour laquelle la m´ ethode de Gauss
donne un pivot nul `
a la seconde ´ etape. En ´ echangeant simplement la deuxi` eme et la
troisi` eme ligne, on trouve un pivot non nul et on peut ex´ ecuter une ´ etape de plus.
Le syst` eme obtenu est ´ equivalent au syst` eme de d´ epart, et on constate qu’il est d´ ej` a
triangulaire sup´ erieur. En effet,
A
(2) =
⎡
⎣
1
2
3
0 −6 −12
0
0
−1
⎤
⎦ = U,
et les matrices de transformation sont donn´ ees par
M1 =
⎡
⎣
1
0 0
−2 1 0
−7 0 1
⎤
⎦ , M2 =
⎡
⎣
1 0 0
0 1 0
0 0 1
⎤
⎦ .
D’un point de vue alg´ ebrique, ayant effectu´ e une permutation des lignes de A, l’´ egalit´ e
A=M
−1
1 M
−1
2 U doit ˆ etre remplac´ ee par A=M
−1
1
P M
−1
2 U o` u P est la matrice de
permutation
P =
⎡
⎣
1 0 0
0 0 1
0 1 0
⎤
⎦ .
(3.47)
•
La strat´ egie de pivot adopt´ ee dans l’Exemple 3.3 peut ˆ etre g´ en´ eralis´ ee en recherchant, `
a chaque ´ etape k de l’´ elimination, un pivot non nul parmi les termes
de la sous-colonne A
(k) (k : n, k). On dit alors qu’on effectue un changement
de pivot partiel (par ligne).
On peut voir `
a partir de (3.27) qu’une grande valeur de m ik (provenant par
exemple d’un petit pivot a
(k)
kk ) peut amplifier les erreurs d’arrondi affectant les
termes a
(k)
kj . Par cons´ equent, afin d’assurer une meilleure stabilit´ e, on choisit
comme pivot l’´ el´ ement de la colonne A
(k) (k : n, k) le plus grand en module
et le changement de pivot partiel est g´ en´ eralement effectu´ e ` a chaque ´ etape,
mˆ eme si ce n’est pas strictement n´ ecessaire (c’est-` a-dire mˆ eme s’il n’y a pas
de pivot nul).
Une m´ ethode alternative consiste `
a rechercher le pivot dans l’ensemble de
la sous-matrice A
(k) (k : n, k : n), effectuant alors un changement de pivot total
(voir Figure 3.2). Remarquer cependant que le changement de pivot partiel
ne requiert qu’un surcoˆ ut d’environ n
2 tests, alors que le changement de pivot
total en n´ ecessite environ 2n
3 /3, ce qui augmente consid´ erablement le coˆ ut de
la m´ ethode de Gauss.
Exemple 3.4 Consid´ erons le syst` eme lin´ eaire Ax = b avec
A =
10
−13
1
1
1
,