Inversion de matrices

Bonjour à tous,

En ce moment on a pas mal de problème sur nos inversions de matrices.
9 fois sur 10 on a le message

Code:

---

La Matrice est singulière....bla,bla

---

On utilise le librairie imsl, et on vient de s'apercevoir qu'il existait deux fonctions d'inversion: d_lsag et d_lslcg (on utilise actuellement d_lslcg).

Et on cherchait simplement à connaitre la différence entre les deux, et si le fait d'utiliser l'une plutôt que l'autre de ces méthodes donnait plus de chances de "planter" les calculs du pivot de Gauss.

Est-il possible que le calcul d'inversion de Fortran soit responsable de la singularité de nos matrices (à un pas de calcul informatique donné), alors que le matrice soit "manuellement" inversible ?

Merci pour toute réponse...

A+.

Bonjour,

Je ne connais pas la librairie IMSL plus que ça, mais il y a certainement un bout de doc qui dit, ne serait-ce qu'en deux lignes, quelles sont les méthodes employées par chacune des routines (inversion via une décomposition LU, gauss avec permutation des lignes et/ou colonnes,...). De là, on peut savoir si l'une est plus efficace (au moins en théorie) que l'autre.

Sinon, tu peux toujours tester si d'autres librairies (par ex LAPACK, connue pour être une des meilleures librairies pour ce genre de calculs) ne font pas mieux. Mais j'imagine que tu y as déjà songé.

Merci pour ta réponse,

En fait les deux méthodes sont basées sur la décomposition LU, mais une des deux est "itérative" et pas l'autre. Et je suis pas sûr de comprendre la signification exacte de ce mot...

Il me semble (pas sûr parceque ça date de plusieurs années déjà) que IMSL est issu de LAPACK, et doit donc en être une version amélioré. Sinon, existe-t-il des méthodes d'inversion plus "stable" informatiquement que d'autre, ou alors c'est comme en maths pures: quand une matrice est inversible ou non peut importe la méthode?

A+.

Il est effectivement possible que IMSL soit basée sur LAPACK; beaucoup ont repris cette librairie puisqu'elle est libre et efficace...

Pour ce qui est des méthodes, en règle générale les méthodes itératives (où on obtient la solution par approximations successives, au bout d'un nombre d'étapes que l'on ne peut pas prévoir à l'avance) sont typiquement plus rapide mais moins stables que les méthodes directes (où le nombre d'opérations est fixé à l'avance).

Par contre, il y a effectivement un "monde" entre une matrice inversible 'sur le papier' et le fait de parvenir à en calculer l'inverse par une méthode où une autre. C'est lié au conditionnement de la dite matrice; plus la matrice est mal conditionnée, plus il y aura des accumulations de petites erreurs qui peuvent mener à de gros problèmes (du type que tu rencontres, échec au cours d'une des étapes du calcul) alors que formelement l'inverse existe bel et bien.

Les décompositions LU intègrent en général une stratégie de pertmutation des lignes pour minimiser les accumulations d'erreurs numériques. Une méthode directe plus efficace, en principe, mais plus chère et plus rarement implémentée, est la bonne vielle méthode de Gauss avec permutation des lignes et colonnes.

Il existe également des méthodes de préconditionnement (que je connais moins bien) pour parvenir à calculer l'inverse de matrice particulièrement récalcitrantes.

Merci beaucoup pour tes conseils, notamment sur la notion "itérative".

Nous avons opter pour une méthodes stables (non-itératives)...Rien. :aie:
nous avons tester plusieurs méthodes...Rien. :aie:
D'autres langages: Matlab, C...Rien. :aie:
Nous avons même créer un algorithme personnel...Toujours Rien. :aie:
Alors on a revu notre façon de remplir notre matrice, et on a trouvé un gros bug qui datait du début du logiciel. :mur:

En tout cas merci pour toutes ces précisions qui vont nous être très utiles.

A+.

Dur dur ...

Bon courage pour la suite.

Tout d'abord, une question qui vous semblera peut-être étrange: avez-vous vraiment besoin d'inverser une matrice? En effet, c'est une maladresse que l'on voit très fréquemment: pour résoudre un système A * x = B, beacoup de gens commencent par calculer la matrice inverse inv(A), puis effectuent le produit x = inv(A) * B. C'est en principe correct, mais assez inefficace parce que l'inversion de matrice prend plus de temps que la résolution d'un système linéaire par une "bonne" méthode.

Si vous voulez écrire un programme efficace, commencez par vous demander si votre matrice ne présente pas des propriétés qui permettrons d'optimiser le temps de calcul.

Si ce n'est pas le cas, factorisez votre matrice, c'est-à-dire décomposez-la en le produit d'une matrice tridiagonale gauche et d'une tridiagonale droite (méthode LU). J'utilise pour cela la routine DGECO ou DGEFA de la bibliothèque LINPACK. Ensuite, résolvez-le système à l'aide de DGESL.

Si la matrice est de type "bande", utilisez DGBCO ou DGBFA, puis DGBSL.

Sil a matrice est symétrique, vous pouvez utiliser DSICO ou DSIFA, puis DSISL. Vous pouvez aussi économiser près de la moitié de la place en mémoire en utilisant DSPCO ou DSPFA, puis DSPSL.

Si la nature du problème que vous étudiez vous indique que la matrice est définie positive (toutes ses valeurs propres positives) préférez les routines dont les noms commencent par DPO, DPP ou DPB.

Pour mémoire, la bibliothèque LINPACK est disponible gratuitement sur le site www.netlib.org

Bonne chance
Jean-Marc Blanc

Salut,

Je confirme que certains algorithmes d'IMSL - en particulier ceux traitant de l'algèbre linéaire - sont basés sur LAPACK, qui est très largement répandu dans le domaine du calcul scientifique.

S'agissant des méthodes utilisées, je ne peux que conseiller d'aller voir la documentation en ligne (très exhaustive), téléchargeable par tout un chacun à l'URL suivante : http://www.vni.com/products/imsl/doc...tion/index.php


SebGR

bonjour,

vous pourrez aussi trouver des informations interessantes sur les algorithmes d'inversion à cette adresse:

http://www.nrbook.com/a/bookfpdf.php

(chapitre 2 - solution of linear algebraic equations)

qui permettent parfois d'opter pour telle ou telle méthode en fonction de la forme de la matrice (creuse, tridiagonale, bandes...).

Salut !

Tout d'abord, on ne répétera jamais trop ma mise en garde: n'inversez une matrice que lorsque c'est strictement nécessaire, ce qui est rare.

A part ça, lorsqu'il se passe des choses peu orthodoxes avec une matrice, il est de bonne politique de passer par la méthode des valeurs singulières (fonction svd dans MatLab, routine DSVDC dans Linpack). Si la singularité résulte d'une erreur lors de la construction de la matrice, en général le diagnostic saute aux yeux.

Jean-Marc Blanc

Bonjour
Comme le dit FR119492, l'inversion de matrice est extrêmement coûteuse. On s'en sert rarement.
Peut-être pourrait-tu nous donner plus de détail sur les raisons pour lesquelles tu veux inverser des matrices. Il est probable qu'une solution plus élégante (ou tout au moins, moins couteuse) existe.

je viens de regarder la doc imsl.

les fonctions que tu utilise ne semblent pas inverser la matrice (j'ai regardé rapidement mais c'est ce qu'il me semble avoir compris...)

LSARG (et pas LSAG) donne l'information suivante :
(traduction sommaire)
LSARG résoud un système d'équations linéaire à coefficients réels. Elle utilise LFCRG pour calculer une factorisation LU des coefficients de la matrice et calculer le conditionnement puis utilise LFIRG pour résoudre le système itérativement.

et LFIRG semble utiliser cette factorisation LU pour résoudre le système


LSLCG fait sensiblement la même chose pour résoudre un système a coefficients complexes

Premièrement, merci pour toutes vos réponses et votre aide.

En regardant de plus, il semble en effet que le problème d'inversion ne vienne pas de l'algorithme mais de la construction de notre matrice...Matlab ne pouvant pas inverser notre matrice par svd non plus. On va tenter de reposer le problème car on a peut-être une sous-détermination de notre système dû au fait que certaines lignes de notre matrice ne comporte que des zéros parfois.

A+.