Discussion :

[FR119492]

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.

[Sylvain Togni]

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.

[FR119492]

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

[Zavonen]

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.

[FR119492]

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

[david31170]

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...)

[TheOyoStyledMan]

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

[Aleph69]

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!