158
5 Systèmes linéaires
6. si A n’est pas carrée, on utilise des méthodes spécifiques, basées
sur la factorisation QR des systèmes indéterminés (pour le cas surdéterminé, voir Section 5.7).
La commande \ existe aussi dans Octave. Pour un système associé à
une matrice pleine, Octave utilise la procédure suivante :
1. si la matrice est triangulaire supérieure (resp. inférieure), Octave
appelle l’algorithme de remontée (resp. de descente) de LAPACK
(une bibliothèque d’algèbre linéaire très utilisée [ABB
+ 99]) ;
2. si la matrice est symétrique à coefficients diagonaux réels strictement
positifs, Octave tente une factorisation de Cholesky avec LAPACK ;
3. si la factorisation de Cholesky échoue ou si la matrice n’est pas symétrique à coefficients diagonaux strictement positifs, le système est résolu avec LAPACK par élimination de Gauss avec pivots par lignes ;
4. si la matrice n’est pas carrée, ou si toutes les tentatives précédentes ont conclu à une matrice singulière ou quasi-singulière, Octave
cherche une solution au sens des moindres carrés.
Quand la matrice est creuse, Octave, comme MATLAB, repose sur
UMFPACK et sur d’autres packages de la suite Suitesparse pour résoudre
le système, en particulier :
1. si la matrice est carrée et a une structure par bande, avec une densité
de bande “assez petite” continuer en a), sinon aller en 2 ;
a) si la matrice est tridiagonale et si le second membre n’est pas
creux continuer, sinon aller en b) ;
i. si la matrice est symétrique à coefficients diagonaux strictement positifs, Octave tente une factorisation de Cholesky ;
ii. si ce qui précède a échoué ou si la matrice n’est pas symétrique à coefficients diagonaux strictement positifs, Octave
utilise la méthode de Gauss avec pivot ;
2. si la matrice est triangulaire supérieure (en permutant des colonnes)
ou inférieure (en permutant des lignes), Octave fait une remontée ou
une descente creuse ;
3. si la matrice est carrée, symétrique avec coefficients diagonaux strictement positifs, Octave tente une factorisation de Cholesky creuse ;
4. si la factorisation de Cholesky creuse échoue ou si la matrice n’est pas
symétrique avec coefficients diagonaux strictement positifs, Octave
fait une factorisation avec la bibliothèque UMFPACK ;
5. si la matrice n’est pas carrée, ou si toutes les tentatives précédentes ont conclu à une matrice singulière ou quasi-singulière, Octave
cherche une solution au sens des moindres carrés.
5 Systèmes linéaires
6. si A n’est pas carrée, on utilise des méthodes spécifiques, basées
sur la factorisation QR des systèmes indéterminés (pour le cas surdéterminé, voir Section 5.7).
La commande \ existe aussi dans Octave. Pour un système associé à
une matrice pleine, Octave utilise la procédure suivante :
1. si la matrice est triangulaire supérieure (resp. inférieure), Octave
appelle l’algorithme de remontée (resp. de descente) de LAPACK
(une bibliothèque d’algèbre linéaire très utilisée [ABB
+ 99]) ;
2. si la matrice est symétrique à coefficients diagonaux réels strictement
positifs, Octave tente une factorisation de Cholesky avec LAPACK ;
3. si la factorisation de Cholesky échoue ou si la matrice n’est pas symétrique à coefficients diagonaux strictement positifs, le système est résolu avec LAPACK par élimination de Gauss avec pivots par lignes ;
4. si la matrice n’est pas carrée, ou si toutes les tentatives précédentes ont conclu à une matrice singulière ou quasi-singulière, Octave
cherche une solution au sens des moindres carrés.
Quand la matrice est creuse, Octave, comme MATLAB, repose sur
UMFPACK et sur d’autres packages de la suite Suitesparse pour résoudre
le système, en particulier :
1. si la matrice est carrée et a une structure par bande, avec une densité
de bande “assez petite” continuer en a), sinon aller en 2 ;
a) si la matrice est tridiagonale et si le second membre n’est pas
creux continuer, sinon aller en b) ;
i. si la matrice est symétrique à coefficients diagonaux strictement positifs, Octave tente une factorisation de Cholesky ;
ii. si ce qui précède a échoué ou si la matrice n’est pas symétrique à coefficients diagonaux strictement positifs, Octave
utilise la méthode de Gauss avec pivot ;
2. si la matrice est triangulaire supérieure (en permutant des colonnes)
ou inférieure (en permutant des lignes), Octave fait une remontée ou
une descente creuse ;
3. si la matrice est carrée, symétrique avec coefficients diagonaux strictement positifs, Octave tente une factorisation de Cholesky creuse ;
4. si la factorisation de Cholesky creuse échoue ou si la matrice n’est pas
symétrique avec coefficients diagonaux strictement positifs, Octave
fait une factorisation avec la bibliothèque UMFPACK ;
5. si la matrice n’est pas carrée, ou si toutes les tentatives précédentes ont conclu à une matrice singulière ou quasi-singulière, Octave
cherche une solution au sens des moindres carrés.