5.4 Méthode du pivot
147
0
20
40
60
80
100
120
0
20
40
60
80
100
120
nz = 379
0
20
40
60
80
100
120
0
20
40
60
80
100
120
nz = 253
Figure 5.7. Structure des matrices A et R de l’Exemple 5.7 après renumérotation
5.4 Méthode du pivot
Nous allons expliquer une technique qui permet d’effectuer la factorisation LU pour toute matrice régulière, même quand les hypothèses de la
Proposition 5.1 ne sont pas vérifiées.
Revenons au cas décrit dans l’Exemple 5.6 et prenons ε = 0. En
posant A
(1) = A après avoir effectué la première itération (k = 1) de
l’algorithme, les nouveaux coefficients de A sont
⎡
⎣
1 1 3
2 0 -4
3 3 -5
⎤
⎦ .
(5.18)
Comme le pivot a 22 est égal à zéro, on ne peut aller plus loin dans
cette voie. Cependant, en intervertissant préalablement la deuxième et
la troisième ligne, on aurait obtenu la matrice
⎡
⎣
1
1
3
3
3
-5
2
0
-4
⎤
⎦
sur laquelle on aurait pu faire les calculs sans entraîner une division
par 0.
Ainsi, en effectuant une permutation convenable des lignes de la matrice originale A, on rend la factorisation possible même quand les hypothèses de la Proposition 5.1 ne sont pas vérifiées, à condition bien sûr
d’avoir det(A) = 0. On ne peut malheureusement pas savoir a priori
quelles lignes devront être permutées. Néanmoins, on peut effectuer une
permutation à chaque étape k où un terme diagonal a
(k)
kk s’annule.
Revenons à la matrice (5.18), dans laquelle le coefficient (2, 2) est nul.
En remarquant que le terme (3,2) est non nul, échangeons la troisième