5.9 Méthodes itératives
159
Résumons-nous
1. La factorisation LU de A∈ R
n×n consiste à calculer un matrice triangulaire inférieure L et une matrice triangulaire supérieure U telles
que A = LU ;
2. la factorisation LU, quand elle existe, n’est pas unique. Cependant,
on peut la rendre unique en se donnant des conditions supplémentaires, par exemple en fixant les valeurs de éléments diagonaux de L
à 1. Ceci s’appelle factorisation de Gauss ;
3. la factorisation de Gauss existe et est unique si et seulement si les
mineurs principaux de A d’ordre 1 à n − 1 sont non nuls (autrement,
au moins un pivot est nul) ;
4. quand on trouve un pivot nul, un nouveau pivot peut être obtenu en
échangeant des lignes (ou colonnes) convenablement choisies. C’est
la stratégie du pivot ;
5. le calcul de la factorisation de Gauss nécessite de l’ordre de 2n
3 /3
opérations en général, et seulement de l’ordre de n opérations dans
le cas d’un système tridiagonal ;
6. pour les matrices symétriques définies positives, on peut utiliser la
factorisation de Cholesky A = R
T R, où R est une matrice triangulaire supérieure. Le coût de calcul est alors de l’ordre de n
3 /3
opérations ;
7. la sensibilité du résultat aux perturbations des données dépend du
conditionnement de la matrice du système : la solution calculée peut
être imprécise quand la matrice est mal conditionnée (c’est-à-dire
quand son conditionnement est beaucoup plus grand que 1) ;
8. la solution d’un système sur-déterminé peut être comprise au sens
des moindres carrés et obtenue par soit par factorisation QR soit par
décomposition en valeurs singulières (SVD).
5.9 Méthodes itératives
Considérons le système linéaire (5.1) avec A∈ R
n×n et b ∈ R
n . Résoudre
un tel système par une méthode itérative consiste à construire une suite
de vecteurs {x
(k) , k ≥ 0} de R
n qui converge vers la solution exacte x,
c’est-à-dire
lim
k→∞
x
(k) = x,
(5.44)
159
Résumons-nous
1. La factorisation LU de A∈ R
n×n consiste à calculer un matrice triangulaire inférieure L et une matrice triangulaire supérieure U telles
que A = LU ;
2. la factorisation LU, quand elle existe, n’est pas unique. Cependant,
on peut la rendre unique en se donnant des conditions supplémentaires, par exemple en fixant les valeurs de éléments diagonaux de L
à 1. Ceci s’appelle factorisation de Gauss ;
3. la factorisation de Gauss existe et est unique si et seulement si les
mineurs principaux de A d’ordre 1 à n − 1 sont non nuls (autrement,
au moins un pivot est nul) ;
4. quand on trouve un pivot nul, un nouveau pivot peut être obtenu en
échangeant des lignes (ou colonnes) convenablement choisies. C’est
la stratégie du pivot ;
5. le calcul de la factorisation de Gauss nécessite de l’ordre de 2n
3 /3
opérations en général, et seulement de l’ordre de n opérations dans
le cas d’un système tridiagonal ;
6. pour les matrices symétriques définies positives, on peut utiliser la
factorisation de Cholesky A = R
T R, où R est une matrice triangulaire supérieure. Le coût de calcul est alors de l’ordre de n
3 /3
opérations ;
7. la sensibilité du résultat aux perturbations des données dépend du
conditionnement de la matrice du système : la solution calculée peut
être imprécise quand la matrice est mal conditionnée (c’est-à-dire
quand son conditionnement est beaucoup plus grand que 1) ;
8. la solution d’un système sur-déterminé peut être comprise au sens
des moindres carrés et obtenue par soit par factorisation QR soit par
décomposition en valeurs singulières (SVD).
5.9 Méthodes itératives
Considérons le système linéaire (5.1) avec A∈ R
n×n et b ∈ R
n . Résoudre
un tel système par une méthode itérative consiste à construire une suite
de vecteurs {x
(k) , k ≥ 0} de R
n qui converge vers la solution exacte x,
c’est-à-dire
lim
k→∞
x
(k) = x,
(5.44)