5.5 Quelle est la précision de la solution d’un système linéaire ?
149
(5.13) avec pivot par ligne effectué à chaque itération a la forme suivante :
poser A
(1) = A et P=I, puis
pour k = 1, . . ., n − 1,
trouver ¯
r tel que |a
(k)
¯
rk | = max
r=k,...,n
|a
(k)
rk |,
échanger les lignes k et ¯
r
dans A et P,
pour i = k + 1, . . ., n
l ik =
a
(k)
ik
a
(k)
kk
,
pour j = k + 1, . . . , n
a
(k+1)
ij
= a
(k)
ij − l ik a
(k)
kj
(5.21)
Comme pour l’algorithme (5.13) (celui sans permutation), on peut stocker les coefficients (a
(k)
ij ) et les multiplicateurs (l ik ) dans une unique
matrice. Ainsi, à chaque étape, on applique la même permutation aux
multiplicateurs qu’à A et P.
Le programme lu de MATLAB mentionné précédemment calcule
la factorisation de Gauss avec pivot par ligne. Sa syntaxe complète est
[L,U,P]=lu(A), P étant la matrice de permutation. Quand on l’utilise
sous sa forme abrégée [L,U]=lu(A), la matrice L est égale à P*M, où M est
triangulaire inférieure et P est la matrice de permutation obtenue avec la
technique du pivot par ligne. Le programme lu active automatiquement
la stratégie de pivot par ligne quant un pivot est nul (ou très petit).
Quand la matrice A est stockée sous forme creuse (voir les Sections 5.6
et 5.8), la permutation de lignes n’est effectuée que pour un pivot nul
(ou très petit).
Voir Exercices 5.6–5.8.
5.5 Quelle est la précision de la solution d’un
système linéaire ?
On a déjà remarqué dans l’Exemple 5.8 que le produit LU n’est pas
exactement égal à A en pratique, à cause des erreurs d’arrondi. Bien que
la stratégie du pivot atténue ces erreurs, le résultat n’est pas toujours
très satisfaisant.
Exemple 5.9 Considérons le système linéaire Anxn = bn, où An ∈ R
n×n est
la matrice de Hilbert dont les éléments sont
aij = 1/(i + j − 1),
i,j = 1, . . . , n,
149
(5.13) avec pivot par ligne effectué à chaque itération a la forme suivante :
poser A
(1) = A et P=I, puis
pour k = 1, . . ., n − 1,
trouver ¯
r tel que |a
(k)
¯
rk | = max
r=k,...,n
|a
(k)
rk |,
échanger les lignes k et ¯
r
dans A et P,
pour i = k + 1, . . ., n
l ik =
a
(k)
ik
a
(k)
kk
,
pour j = k + 1, . . . , n
a
(k+1)
ij
= a
(k)
ij − l ik a
(k)
kj
(5.21)
Comme pour l’algorithme (5.13) (celui sans permutation), on peut stocker les coefficients (a
(k)
ij ) et les multiplicateurs (l ik ) dans une unique
matrice. Ainsi, à chaque étape, on applique la même permutation aux
multiplicateurs qu’à A et P.
Le programme lu de MATLAB mentionné précédemment calcule
la factorisation de Gauss avec pivot par ligne. Sa syntaxe complète est
[L,U,P]=lu(A), P étant la matrice de permutation. Quand on l’utilise
sous sa forme abrégée [L,U]=lu(A), la matrice L est égale à P*M, où M est
triangulaire inférieure et P est la matrice de permutation obtenue avec la
technique du pivot par ligne. Le programme lu active automatiquement
la stratégie de pivot par ligne quant un pivot est nul (ou très petit).
Quand la matrice A est stockée sous forme creuse (voir les Sections 5.6
et 5.8), la permutation de lignes n’est effectuée que pour un pivot nul
(ou très petit).
Voir Exercices 5.6–5.8.
5.5 Quelle est la précision de la solution d’un
système linéaire ?
On a déjà remarqué dans l’Exemple 5.8 que le produit LU n’est pas
exactement égal à A en pratique, à cause des erreurs d’arrondi. Bien que
la stratégie du pivot atténue ces erreurs, le résultat n’est pas toujours
très satisfaisant.
Exemple 5.9 Considérons le système linéaire Anxn = bn, où An ∈ R
n×n est
la matrice de Hilbert dont les éléments sont
aij = 1/(i + j − 1),
i,j = 1, . . . , n,