IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Résolution des systèmes linéaires


Sujet :

Mathématiques

  1. #1
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 81
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : avril 2007
    Messages : 2 978
    Points : 5 157
    Points
    5 157
    Par défaut Résolution des systèmes linéaires
    Bonjour,

    Cette discussion sert à récupérer les retours sur l'article:

    Résolution des systèmes linéaires


    NB: Merci de lire ce message avant de poster.
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  2. #2
    Membre éclairé

    Profil pro
    Inscrit en
    septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Je trouve cet article très bien, très utile.
    J'ai particulièrement apprécié la pédagogie générale de l'article : chaque notion utilisée est bien introduite et définie, ce qui rend l'article très accessible.
    Je trouve néanmoins qu'un tableau/schéma récapitulatif des différentes méthodes et de leur caractéristiques serait le bienvenu.

  3. #3
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 81
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : avril 2007
    Messages : 2 978
    Points : 5 157
    Points
    5 157
    Par défaut
    Merci pour ton commentaire.
    Je trouve néanmoins qu'un tableau/schéma récapitulatif des différentes méthodes et de leur caractéristiques serait le bienvenu.
    De toute manière, ça n'est qu'une première version. Je me suis déjà rendu compte que j'avais oublié la méthode des gradients conjugués. Je retiens ta suggestion pour la prochaine révision. En attendant, je me suis attaqué à un descriptif des bibliothèques LinPack et LAPack, mais c'est assez monstrueux!
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  4. #4
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 74
    Localisation : France

    Informations forums :
    Inscription : novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    Salut Jean-Marc
    Je connais ton aversion pour les déterminants, les calculs d'inverse etc...
    Mais là tu fais quand-même un peu fort :
    On peut sérieusement douter de la signification physique du déterminant d'une matrice:
    Le déterminant d'un système de vecteurs ne sert-il pas entre autres à mesurer le volume du parallélotope construit sur ces vecteurs ? Si tu ne vois aucune signification physique à un volume ...
    Amicalement.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  5. #5
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 81
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : avril 2007
    Messages : 2 978
    Points : 5 157
    Points
    5 157
    Par défaut
    Salut Gilles!
    Tu as parfaitement raison dans le cas de petites matrices (2*2 ou 3*3) pour lesquelles les calculs se font à la main. Mais j'ai du mal à imaginer la signification du déterminant d'une matrice 100*100.
    Amitiés.
    Jean-Marc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  6. #6
    Futur Membre du Club
    Profil pro
    Inscrit en
    octobre 2009
    Messages
    7
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2009
    Messages : 7
    Points : 5
    Points
    5
    Par défaut Continues sur les éléments propres !
    C'est une très bonne syntèse.

    Peux tu rajouter les calculs de vec/val propres (iterratives, non iterratives) pour les matrices symétriques et NON symétrique dans le cas de R (pour C si tu peux...)

  7. #7
    Membre habitué
    Profil pro
    Inscrit en
    septembre 2004
    Messages
    110
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : septembre 2004
    Messages : 110
    Points : 130
    Points
    130
    Par défaut
    Bonjour,

    très bonne synthèse! (Ca faisait longtemps que je n'étais pas passé dans le coin ^^)

    Sinon, tu as pensé à introduire les méthodes itératives de descente de gradient (Krylov et cie) ?

    En tout cas merci, je recherchais ce genre de document de synthèse pour mes petits stagiaires

    Edit: je viens de voir que tu t'attaquais au gradient conjugué ... tu peux oublier ma remarque sur les méthodes de gradient

  8. #8
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : mars 2010
    Messages : 1 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonsoir,

    félicitations pour ce cours qui introduit beaucoup de notions importantes sur les systèmes d'équations linéaires. Vivement des sections sur les méthodes de Krylov et le préconditionnement!

    J'ai relevé quelques points obscurs qui pourraient être éclaircis dans une future version.

    Paragraphe II-B-2 : la définition d'une matrice orthogonale est incorrecte. Il est nécessaire d'imposer qu'elle soit réelle. Dans le cas contraire, la matrice est dite unitaire et c'est cette dernière notion qu'il faut retenir dans le cours à mon avis (notamment pour la factorisation QR). Par ailleurs, il serait bon de préciser qu'une matrice orthogonale/unitaire n'est pas nécessairement inversible et qu'il est nécessaire de supposer sa régularité pour affirmer que sa transposée est son inverse.

    Remarque générale : à plusieurs reprises, on peut lire à propos des algorithmes que "le nombre d'opérations élémentaires et le temps de calcul augmentent selon un polynôme de degré k par rapport à la taille n du système". Pour la complexité, c'est seulement vrai si le système est dense. Pour les systèmes creux, les complexités sont bien moindres. Quant au temps de calcul, je ne pense pas qu'il soit possible d'affirmer quoique ce soit à son propos : j'observe un comportement linéaire sur mes problèmes pour des factorisations LU (matrices creuses pour n de l'ordre de 10 000).

    Paragraphe II-D : je ne connaissais pas l'approche graphique développée c'est très intéressant. Pour indiquer l'influence négative du conditionnement sur la perturbation du second membre, je pense qu'il serait préférable de comparer l'erreur relative entre les solutions des systèmes perturbés et non pertubés plutôt que l'erreur absolue (relative_error = O(backward_error*condition_number).

    Le plus souvent, la cause de ce mauvais conditionnement réside dans une maladresse lors de la mise en équations du problème physique.
    Qu'entend-on par mise en équations? Le problème physique est tel qu'il est, on peut tout au plus les adimensionnées. C'est lors de la discrétisation du problème que des maladresses peuvent être faites me semble-t-il. Il existe d'ailleurs des résultats théoriques qui décrivent la croissance du conditionnement en fonction du pas de discrétisation.

    S'il n'est pas possible de l'éviter, parce que le problème est intrinsèquement instable, il faudra utiliser une méthode de résolution plus stable, mais plus coûteuse que la méthode de Gauss.
    C'est un vieux débat qui a eu lieu entre le père de l'analyse d'erreur de l'élimination gaussienne (Wilkinson) et plusieurs de ces contemporains. La théorie tend à montrer que l'élimination gaussienne est moins stable que d'autres mais en pratique on constate presque toujours une stabilité vers l'arrière de l'approche. On ne sait pas l'expliquer (voir le papier "Three mysteries about Gaussian elimination" de Trefethen). Je ne connais aucune application sérieuse qui résout directement ses systèmes linéaires inversibles par une approche autre que la factorisation LU (Cholesky,Gauss).

    S'il est du même ordre de grandeur que la précision de calcul, on doit considérer la matrice comme tellement mal conditionnée que les résultats perdront dans la plupart des cas toute signification.
    Je ne vois pas ce qui permet d'affirmer cela. L'erreur relative est bornée supérieurement par un terme dépendant du nombre de conditionnement. Cela ne signifie pas que l'erreur relative est du même ordre de grandeur que ce terme (terme de l'ordre de 1 dans ce cas extrême). Les contre-exemples numériques ne manquent pas.

    Paragraphe II-E : la permutation des équations correspond au pivotage partiel par ligne, la permutation des inconnues correspond au pivotage partiel par colonne.

    En revanche, le pivotage partiel est essentiel si la matrice du système est mal conditionnée ou si son ordre est élevé.
    Ce qui importe ici c'est le terme de croissance du pivot (pivot growth) et c'est le pivotage partiel qui permet de le borner. C'est totalement orthogonal au conditionnement.

    Paragraphe II-F : à ma connaissance, l'algorithme décrit est celui de Doolittle et non de Crout.

    Le raffinement itératif de la solution est une technique qui permet de retrouver la précision de l'ordinateur utilisé.
    C'est en contradiction avec ce qui a été déclaré précédemment dans le cours, à savoir que l'élimination gaussienne ne doit pas être employée pour les matrices mal conditionnées : on dit ici que finalement on peut quand même récupérer la solution à la précision machine en résolvant des systèmes triangulaires (temps de calcul dérisoire par rapport à celui de la factorisation). La théorie du raffinenement itératif est plus compliquée. On doit faire des calculs en précision mixte (localement, on double la précision de certains calcul pendant le raffinement) pour que ca soit vraiment efficace. C'est expliqué dans une note de LAPACK : wwwuser.gwdg.de/~applsw/Parallelrechner/scalapack/lawns/lawn104.pdf

    Paragraphe II-J : je rejoins la remarque de Zavonen, le déterminant correspond au volume orienté d'un parallélotope même en dimension 100. Il correspond par ailleurs au produit des valeurs propres qui peuvent avoir de véritables interprétations physiques notamment en mécanique. Enfin, les valeurs propres ont aussi une interprétation statistique (variance expliquée).

    Paragraphe II-K : je ne connais pas le théorème qui affirme que les matrices symétriques réelles et complexes symétriques/hermitiennes admettent des factorisations LDL'. Avec la définie positivité c'est sûre (Cholesky). Avec du pivotage on peut aller un peu plus loin (matrices indéfinies). Pouvez-vous citer vos sources?

    Paragraphe II-M : à ma connaissance, l'algorithme de factorisation QR exposé correspond à celui de Givens et non d'Householder.

    Paragraphe II-N : la première phrase ne veut rien dire, il doit y avoir une faute de frappe ou un oubli de mot.

    Paragraphe III : ce paragraphe est un petit peu brouillon. On introduit des techniques de régularisation dans la factorisation SVD (contrainte de minimisation de la norme) pour justifier le fait qu'elle s'applique alors que LU et QR non. La factorisation LU s'étend aux matrices rectangulaires et on peut tout autant régulariser les systèmes linéaires avec ces méthodes. L'exemple le plus connu consiste à multiplier à gauche par la transposée de la matrice (moindres carrés). Il y a également les pseudo-inverses (Drazin, Moore-Penrose) qui sont factorisables.

    Paragraphe III-E : le système tel qu'il est écrit n'a pas de sens (problème au niveau des dimensions).

    Voilà, j'espère que vous trouverez certaines de ces remarques intéressantes et bon courage pour la partie sur la méthode des gradients conjugués!

Discussions similaires

  1. Algorithme pour la résolution des systèmes linéaires
    Par natsuka dans le forum Mathématiques
    Réponses: 9
    Dernier message: 24/12/2010, 15h09
  2. Résolution des systèmes linéaires
    Par Rniamo dans le forum Mathématiques
    Réponses: 18
    Dernier message: 28/02/2009, 01h55
  3. Résolution de systèmes linéaires : une erreur
    Par delphidebutant dans le forum Mathématiques
    Réponses: 7
    Dernier message: 21/02/2009, 16h00
  4. Réponses: 4
    Dernier message: 10/03/2007, 18h45

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo