3.5 Changement de pivot
91
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
0
0
k
k
k
k
r
r
q
Fig. 3.2. Changement de pivot partiel par ligne (` a gauche) et changement de pivot
total (` a droite). Les zones les plus sombres de la matrices sont celles o` u est effectu´ ee
la recherche du pivot
o` u b est choisi de fa¸ con `
a ce que x = [1, 1]
T soit la solution exacte. Supposons qu’on
travaille en base 2 avec 16 chiffres significatifs. La m´ ethode de Gauss sans changement de pivot donne xMEG = [0.99920072216264, 1]
T , alors qu’avec une strat´ egie
de pivot partiel, la solution obtenue est exacte jusqu’au 16
ime chiffre.
•
Analysons comment la strat´ egie de pivot partiel affecte la factorisation LU
induite par la m´ ethode de Gauss. Lors de la premi` ere ´ etape de l’´ elimination
de Gauss avec changement de pivot partiel, apr` es avoir trouv´ e l’´ el´ ement a r1
de module maximum dans la premi` ere colonne, on construit la matrice de
permutation ´ el´ ementaire P 1 qui ´ echange la premi` ere et la r-i` eme ligne (si
r = 1, P 1 est la matrice identit´ e). On cr´ ee ensuite la premi` ere matrice de
transformation de Gauss M 1 et on pose A
(2) = M 1 P 1 A
(1) . On proc` ede de
mˆ eme avec A
(2) , en cherchant les nouvelles matrices P 2 et M 2 telles que
A
(3) = M 2 P 2 A
(2) = M 2 P 2 M 1 P 1 A
(1) .
Apr` es avoir effectu´ e toutes les ´ etapes de l’´ elimination, la matrice triangulaire
sup´ erieure U obtenue est donn´ ee par
U = A
(n) = M n−1 P n−1 · · · M 1 P 1 A
(1) .
(3.48)
En posant M = M n−1 P n−1 · · · M 1 P 1 et P = P n−1 · · · P 1 , on a U=MA et donc
U = (MP
−1 )PA. On v´ erifie facilement que la matrice L = PM
−1 est triangulaire inf´ erieure (avec des 1 sur la diagonale), de sorte que la factorisation LU
s’´ ecrit
PA = LU.
(3.49)
On ne doit pas s’inqui´ eter de la pr´ esence de l’inverse de M, car M
−1 =
P
−1
1 M
−1
1 · · · P
−1
n−1 M
−1
n−1 , P
−1
i
= P
T
i et M
−1
i
= 2I n − M i .
91
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000 000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
111111111111111 111111111111111
111111111111111
111111111111111
111111111111111
111111111111111
0
0
k
k
k
k
r
r
q
Fig. 3.2. Changement de pivot partiel par ligne (` a gauche) et changement de pivot
total (` a droite). Les zones les plus sombres de la matrices sont celles o` u est effectu´ ee
la recherche du pivot
o` u b est choisi de fa¸ con `
a ce que x = [1, 1]
T soit la solution exacte. Supposons qu’on
travaille en base 2 avec 16 chiffres significatifs. La m´ ethode de Gauss sans changement de pivot donne xMEG = [0.99920072216264, 1]
T , alors qu’avec une strat´ egie
de pivot partiel, la solution obtenue est exacte jusqu’au 16
ime chiffre.
•
Analysons comment la strat´ egie de pivot partiel affecte la factorisation LU
induite par la m´ ethode de Gauss. Lors de la premi` ere ´ etape de l’´ elimination
de Gauss avec changement de pivot partiel, apr` es avoir trouv´ e l’´ el´ ement a r1
de module maximum dans la premi` ere colonne, on construit la matrice de
permutation ´ el´ ementaire P 1 qui ´ echange la premi` ere et la r-i` eme ligne (si
r = 1, P 1 est la matrice identit´ e). On cr´ ee ensuite la premi` ere matrice de
transformation de Gauss M 1 et on pose A
(2) = M 1 P 1 A
(1) . On proc` ede de
mˆ eme avec A
(2) , en cherchant les nouvelles matrices P 2 et M 2 telles que
A
(3) = M 2 P 2 A
(2) = M 2 P 2 M 1 P 1 A
(1) .
Apr` es avoir effectu´ e toutes les ´ etapes de l’´ elimination, la matrice triangulaire
sup´ erieure U obtenue est donn´ ee par
U = A
(n) = M n−1 P n−1 · · · M 1 P 1 A
(1) .
(3.48)
En posant M = M n−1 P n−1 · · · M 1 P 1 et P = P n−1 · · · P 1 , on a U=MA et donc
U = (MP
−1 )PA. On v´ erifie facilement que la matrice L = PM
−1 est triangulaire inf´ erieure (avec des 1 sur la diagonale), de sorte que la factorisation LU
s’´ ecrit
PA = LU.
(3.49)
On ne doit pas s’inqui´ eter de la pr´ esence de l’inverse de M, car M
−1 =
P
−1
1 M
−1
1 · · · P
−1
n−1 M
−1
n−1 , P
−1
i
= P
T
i et M
−1
i
= 2I n − M i .