148
5 Systèmes linéaires
et la deuxième ligne et vérifions si le nouveau coefficient (2, 2) est encore
nul. En effectuant la deuxième étape de l’algorithme de factorisation, on
trouve la matrice qu’on aurait obtenue en permutant a priori les lignes
correspondantes de A.
On peut donc effectuer une permutation de ligne seulement quand
c’est nécessaire, et éviter ainsi de procéder à des transformations a priori
de A. Comme une permutation de ligne revient à changer le pivot,
cette technique s’appelle méthode du pivot par ligne. La factorisation
construite de cette manière redonne la matrice originale à une permutation de lignes près. Plus précisément, on a
PA = LU
(5.19)
où P est une matrice de permutation, initialement égale à l’identité.
Quand, au cours de l’algorithme, les lignes r et s de A sont permutées,
la même permutation est appliquée sur les lignes correspondantes de P.
On doit donc résoudre les systèmes triangulaires suivants
Ly = Pb,
Ux = y.
(5.20)
Dans (5.13), on voit non seulement que les pivots a
(k)
kk ne doivent
pas être nuls, mais aussi qu’ils ne doivent pas être trop petits en valeur
absolue. En effet, si a
(k)
kk est proche de zéro, des erreurs d’arrondi affectant
les coefficients a
(k)
kj risquent d’être très amplifiées.
Exemple 5.8 Considérons la matrice inversible
A =
⎡
⎣
1 1 + 0.5 · 10
−15 3
2
2
2 0
3
6
4
⎤
⎦ .
Aucun pivot nul n’apparaît durant la factorisation effectuée par le Programme
5.1. Pourtant, les facteurs L et U s’avèrent très imprécis, comme on le constate
en calculant le résidu A − LU (qui serait égal à la matrice nulle si toutes les
opérations avaient été effectuées en arithmétique exacte)
A − LU =
⎡
⎣
0 0 0
0 0 0
0 0 k
⎤
⎦ .
Avec MATLAB, nous obtenons k = 4, et avec Octave k = 4 ou 6. Le résultat
dépend de l’implémentation de l’arithmétique flottante, c’est-à-dire à la fois
du matériel et de la version du logiciel.
Il est par conséquent recommandé d’utiliser une stratégie de pivot
à chaque étape de la factorisation, en choisissant parmi tous les pivots
possibles a
(k)
ik , i = k, . . . , n, celui de module maximum. L’algorithme de
5 Systèmes linéaires
et la deuxième ligne et vérifions si le nouveau coefficient (2, 2) est encore
nul. En effectuant la deuxième étape de l’algorithme de factorisation, on
trouve la matrice qu’on aurait obtenue en permutant a priori les lignes
correspondantes de A.
On peut donc effectuer une permutation de ligne seulement quand
c’est nécessaire, et éviter ainsi de procéder à des transformations a priori
de A. Comme une permutation de ligne revient à changer le pivot,
cette technique s’appelle méthode du pivot par ligne. La factorisation
construite de cette manière redonne la matrice originale à une permutation de lignes près. Plus précisément, on a
PA = LU
(5.19)
où P est une matrice de permutation, initialement égale à l’identité.
Quand, au cours de l’algorithme, les lignes r et s de A sont permutées,
la même permutation est appliquée sur les lignes correspondantes de P.
On doit donc résoudre les systèmes triangulaires suivants
Ly = Pb,
Ux = y.
(5.20)
Dans (5.13), on voit non seulement que les pivots a
(k)
kk ne doivent
pas être nuls, mais aussi qu’ils ne doivent pas être trop petits en valeur
absolue. En effet, si a
(k)
kk est proche de zéro, des erreurs d’arrondi affectant
les coefficients a
(k)
kj risquent d’être très amplifiées.
Exemple 5.8 Considérons la matrice inversible
A =
⎡
⎣
1 1 + 0.5 · 10
−15 3
2
2
2 0
3
6
4
⎤
⎦ .
Aucun pivot nul n’apparaît durant la factorisation effectuée par le Programme
5.1. Pourtant, les facteurs L et U s’avèrent très imprécis, comme on le constate
en calculant le résidu A − LU (qui serait égal à la matrice nulle si toutes les
opérations avaient été effectuées en arithmétique exacte)
A − LU =
⎡
⎣
0 0 0
0 0 0
0 0 k
⎤
⎦ .
Avec MATLAB, nous obtenons k = 4, et avec Octave k = 4 ou 6. Le résultat
dépend de l’implémentation de l’arithmétique flottante, c’est-à-dire à la fois
du matériel et de la version du logiciel.
Il est par conséquent recommandé d’utiliser une stratégie de pivot
à chaque étape de la factorisation, en choisissant parmi tous les pivots
possibles a
(k)
ik , i = k, . . . , n, celui de module maximum. L’algorithme de