180
5 Systèmes linéaires
voir calculer le produit matrice-vecteur pour des vecteurs arbitraires.
Cette propriété est particulièrement intéressante dans les problèmes où
la matrice n’est pas construite explicitement.
5.14 Ce qu’on ne vous a pas dit
Il existe de nombreuses variantes très efficaces de la factorisation LU
de Gauss pour les systèmes creux de grande dimension. Parmi les plus
avancées, citons les méthodes multifrontales qui réordonnent les inconnues du système afin de rendre les matrices triangulaires L et U aussi
creuses que possible. La méthode multifrontale est implémentée dans le
logiciel UMFPACK. On trouvera plus de renseignements sur ce point
dans [GL96] et [DD99].
Concernant les méthodes itératives, le gradient conjugué et GMRES
sont des cas particuliers des méthodes de Krylov. Pour une description
des méthodes de Krylov voir p.ex. [Axe94], [Saa03] et [vdV03].
Comme on l’a dit, les méthodes itératives convergent lentement si la
matrice est très mal conditionnée. De nombreuses stratégies de préconditionnement ont été développées (voir p.ex. [dV89] et [vdV03]). Certaines
d’entre elles sont purement algébriques, c’est-à-dire basées sur des factorisations incomplètes (ou inexactes) de la matrice du système. C’est
le cas des méthodes implémentées dans les fonctions MATLAB luinc
luinc
ou cholinc (déjà mentionnée plus haut). Des stratégies de préconditionnement ad hoc tirent profit de l’origine physique ou de la structure du
problème qui a conduit au système linéaire considéré.
Il est enfin important de mentionner les méthodes multigrilles. Elles
sont basées sur la résolution séquentielle d’une hiérarchie de systèmes
de dimension variable “ressemblant” au système original, qui permet de
réduire astucieusement l’erreur (voir p.ex [Hac85], [Wes04] et [Hac94]).
Octave 5.3 Dans Octave, cholinc n’est pas encore disponible. Seul
luinc a été implémenté.
5.15 Exercices
Exercice 5.1 Pour une matrice A ∈ R
n×n , déterminer le nombre d’opérations (en fonction de n) nécessaire au calcul du déterminant par la formule de
récurrence (1.8).
Exercice 5.2 Utiliser la commande magic(n), de MATLAB, pour construire
magic
les carrés magiques d’ordre n, avec n=3, 4, . . . , 500, c’est-à-dire les matrices
dont les sommes de coefficients par lignes, par colonnes ou par diagonales sont
5 Systèmes linéaires
voir calculer le produit matrice-vecteur pour des vecteurs arbitraires.
Cette propriété est particulièrement intéressante dans les problèmes où
la matrice n’est pas construite explicitement.
5.14 Ce qu’on ne vous a pas dit
Il existe de nombreuses variantes très efficaces de la factorisation LU
de Gauss pour les systèmes creux de grande dimension. Parmi les plus
avancées, citons les méthodes multifrontales qui réordonnent les inconnues du système afin de rendre les matrices triangulaires L et U aussi
creuses que possible. La méthode multifrontale est implémentée dans le
logiciel UMFPACK. On trouvera plus de renseignements sur ce point
dans [GL96] et [DD99].
Concernant les méthodes itératives, le gradient conjugué et GMRES
sont des cas particuliers des méthodes de Krylov. Pour une description
des méthodes de Krylov voir p.ex. [Axe94], [Saa03] et [vdV03].
Comme on l’a dit, les méthodes itératives convergent lentement si la
matrice est très mal conditionnée. De nombreuses stratégies de préconditionnement ont été développées (voir p.ex. [dV89] et [vdV03]). Certaines
d’entre elles sont purement algébriques, c’est-à-dire basées sur des factorisations incomplètes (ou inexactes) de la matrice du système. C’est
le cas des méthodes implémentées dans les fonctions MATLAB luinc
luinc
ou cholinc (déjà mentionnée plus haut). Des stratégies de préconditionnement ad hoc tirent profit de l’origine physique ou de la structure du
problème qui a conduit au système linéaire considéré.
Il est enfin important de mentionner les méthodes multigrilles. Elles
sont basées sur la résolution séquentielle d’une hiérarchie de systèmes
de dimension variable “ressemblant” au système original, qui permet de
réduire astucieusement l’erreur (voir p.ex [Hac85], [Wes04] et [Hac94]).
Octave 5.3 Dans Octave, cholinc n’est pas encore disponible. Seul
luinc a été implémenté.
5.15 Exercices
Exercice 5.1 Pour une matrice A ∈ R
n×n , déterminer le nombre d’opérations (en fonction de n) nécessaire au calcul du déterminant par la formule de
récurrence (1.8).
Exercice 5.2 Utiliser la commande magic(n), de MATLAB, pour construire
magic
les carrés magiques d’ordre n, avec n=3, 4, . . . , 500, c’est-à-dire les matrices
dont les sommes de coefficients par lignes, par colonnes ou par diagonales sont