inverse d'une matrice

Version imprimable

17/05/2011, 11h54
3aychoucha

inverse d'une matrice

Bonjour,
je cherche à trouver l'inverse d'une matrice de taille quelconque (généralement carrée) , je cherche un algorithme ou bien des fonctions en C++ permettant ce calcul.
S'il ya plusieurs alg quelle est la différence entre eux? comment choisir le meilleur?
Merci d'avance
17/05/2011, 12h13
Aleph69

Bonjour,

il est très rare de devoir calculer l'inverse d'une matrice. Dans quel but souhaites-tu le faire?
17/05/2011, 12h22
Meseira

Citation:

Envoyé par 3aychoucha

je cherche à trouver l'inverse d'une matrice de taille quelconque (généralement carrée)

Citation:

Envoyé par Aleph69

il est très rare de devoir calculer l'inverse d'une matrice.

Et encore plus rare d'inverser une matrice qui ne soit pas carrée... :mrgreen:

Sinon, tu as toujours la bonne vieille méthode du pivot (Gauss-Jordan) mais c'est lourd et impraticable si ta matrice est trop grande.

Comme le dit Aleph69, cela dépend de ce que tu cherches à faire avec ton inverse...
17/05/2011, 13h11
3aychoucha

Bonjour,
surement pas pour le plaisir!!!!!!! :aie: :aie: :aie:
j'en ai besoin pour faire un certains calcul numérique
(Gauss-Jordan)est pratique pour une matrice qui ne dépasse pas 3x3
Mais je veux une méthode qui sera élégante et pratique
Merci d'avance
17/05/2011, 13h25
ZnhaarX

Citation:

Envoyé par Aleph69

il est très rare de devoir calculer l'inverse d'une matrice.

Gné ? :aie:
Le nombre de fois où j'ai du calculer l'inverse du matrice en mathsup/mathspé et en école d'ingénieur avec l'utilisation des matrices jacobiennes et autres rende ton propos un peu sournois vis à vis de mes yeux :lol:

Quoiqu'il en soit.
Le pivot de Gauss est une bonne solution pour des dimensions petites, mais relativement chiante d'une part et pas vraiment optimisé d'autre part.
Tu as aussi la méthode par les co-facteurs (ma préférée à faire à la main pour des matrices de dimension 4x4 max).
http://upload.wikimedia.org/math/c/4...306ffd712f.png
Et tu as aussi la méthode de Jacobi (avec itérations):
http://pagerank.suchmaschinen-doktor...inversion.html

Tu as l’embarra du choix :)
17/05/2011, 13h54
3aychoucha

Merci pour la réponse,
je cherche à trouver l'inverse mais pour un n quelconque et une complexité plus au moins résonable
Merci d'avance
17/05/2011, 15h49
Joel F

Citation:

Envoyé par ZnhaarX

Gné ? :aie:
Le nombre de fois où j'ai du calculer l'inverse du matrice en mathsup/mathspé et en école d'ingénieur avec l'utilisation des matrices jacobiennes et autres rende ton propos un peu sournois vis à vis de mes yeux :lol:

90% du temps, tu ne veux pas l'inverse, tu veux la resolution de AX = B
17/05/2011, 16h20
oodini

Jette un œil dans Numerical Recipes.
17/05/2011, 16h38
ZnhaarX

Citation:

Envoyé par Joel F

90% du temps, tu ne veux pas l'inverse, tu veux la resolution de AX = B

Tout à fait d'accord avec toi (cf. mon lien au dessus sur les itérations de Jacobi) :)
Mais je rebondissais juste sur le "très rare" :D
Quoiqu'il en soit pour des petites dimensions l'utilisation de matrice inverse peut-être une solution (moi j'aime bien la transposée de la comatrice sur le déterminant, ça fait pédant :aie:).

En passant, ma bible :lol::
http://apps.nrbook.com/c/index.html (ou) http://www.nrbook.com/a/bookcpdf.php
(cf. Chapitre 2)

[edit] Fichtre le temps de partir quelque minutes discuter avec le chef, on avait déjà posté les Numerical Recipe... Bref, très bon à lire ;)
17/05/2011, 16h47
Aleph69

Bonjour,

tu peux oublier toutes les formules faisant intervenir le déterminant de ta matrice.

Les cas où le calcul de l'inverse d'une matrice sont extrêmement rares. Comme l'écrit Joel F, dans 90% des cas, l'inverse de la matrice est multipliée par un ou plusieurs vecteurs et on se ramène à la résolution d'un système linéaire, ce qui est bien moins coûteux. Si tu es dans le cas peu probable où tu n'as aucun système linéaire à résoudre, il reste encore à savoir si tu as besoin de calculer entièrement l'inverse de ta matrice ou de déterminer quelques coefficients seulement.

Bonjour,
Pour le calcul d'inverse d'une matrice, tu peux voir les différents souroutines de Alejandro Garcia: http://www.algarcia.org/

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include "NumMeth.h"
 
// Compute inverse of matrix
double inv(Matrix A, Matrix& Ainv) 
// Input
//    A    -    Matrix A (N by N)
// Outputs
//   Ainv  -    Inverse of matrix A (N by N)
//  determ -    Determinant of matrix A	(return value)
{
 
  int N = A.nRow();
  assert( N == A.nCol() );
 
  Ainv = A;  // Copy matrix to ensure Ainv is same size
 
  int i, j, k;
  Matrix scale(N), b(N,N);	 // Scale factor and work array
  int *index;  index = new int [N+1];
 
  //* Matrix b is initialized to the identity matrix
  b.set(0.0);
  for( i=1; i<=N; i++ )
    b(i,i) = 1.0;
 
  //* Set scale factor, scale(i) = max( |a(i,j)| ), for each row
  for( i=1; i<=N; i++ ) {
    index[i] = i;			  // Initialize row index list
    double scalemax = 0.;
    for( j=1; j<=N; j++ ) 
      scalemax = (scalemax > fabs(A(i,j))) ? scalemax : fabs(A(i,j));
    scale(i) = scalemax;
  }
 
  //* Loop over rows k = 1, ..., (N-1)
  int signDet = 1;
  for( k=1; k<=N-1; k++ ) {
	//* Select pivot row from max( |a(j,k)/s(j)| )
    double ratiomax = 0.0;
	int jPivot = k;
    for( i=k; i<=N; i++ ) {
      double ratio = fabs(A(index[i],k))/scale(index[i]);
      if( ratio > ratiomax ) {
        jPivot=i;
        ratiomax = ratio;
      }
    }
	//* Perform pivoting using row index list
	int indexJ = index[k];
	if( jPivot != k ) {	          // Pivot
      indexJ = index[jPivot];
      index[jPivot] = index[k];   // Swap index jPivot and k
      index[k] = indexJ;
	  signDet *= -1;			  // Flip sign of determinant
	}
	//* Perform forward elimination
    for( i=k+1; i<=N; i++ ) {
      double coeff = A(index[i],k)/A(indexJ,k);
      for( j=k+1; j<=N; j++ )
        A(index[i],j) -= coeff*A(indexJ,j);
      A(index[i],k) = coeff;
      for( j=1; j<=N; j++ ) 
        b(index[i],j) -= A(index[i],k)*b(indexJ,j);
    }
  }
  //* Compute determinant as product of diagonal elements
  double determ = signDet;	   // Sign of determinant
  for( i=1; i<=N; i++ )
	determ *= A(index[i],i);
 
  //* Perform backsubstitution
  for( k=1; k<=N; k++ ) {
    Ainv(N,k) = b(index[N],k)/A(index[N],N);
    for( i=N-1; i>=1; i--) {
      double sum = b(index[i],k);
      for( j=i+1; j<=N; j++ )
        sum -= A(index[i],j)*Ainv(j,k);
      Ainv(i,k) = sum/A(index[i],i);
    }
  }
 
  delete [] index;	// Release allocated memory
  return( determ );        
}

good Luck,

24/07/2011, 11h51
loufoque

Utilise LAPACK.
Ça le fait avec une décomposition LU, et non du Gauss-Jordan.
24/07/2011, 13h08
3aychoucha

Bonjour,
Merci solarium pour le code
J'ai pas compris loufoque

Merci
25/07/2011, 23h40
solarium.

inverse matrice

Avec plaisir aychoucha, bonne chance.

Moi aussi j'ai du mal à comprendre comment ajouter le LAPACK,

Merci de bien vouloir me l'expliquer, car je ne comprends pas comment l'installer sous mac (j'utilise le xcode pour la programmation C++)

as tu résolu ton problème 3aychoucha??
28/07/2011, 14h29
St4nl3y

Inverse ou transposer ?

Je sais pas pourquoi on ta dis que c'est pas commun mais au contraire ...
Encore plus dans le domaine de l'analyse informatique, notamment le domaine de l'analyse de donnée où on se sert UNIQUEMENT de formules de matrices, pour analyser des tableaux etc...
Sinon si c'est la transposer rien de plus simple :

tableau[i][j] = tableau[j][i]

Si c'est l'inverse même :

Il faut calculer le déterminant, puis transposer ta matrice (cf si dessous), et enfin parcourir ta matrice par itérations et diviser chaque élément par le déterminant et c'est plié ! :)
28/07/2011, 21h19
lezurp

Salut,

+1 moi assui pour LAPACK
entre autre
:google2:
http://en.wikipedia.org/wiki/LAPACK
http://mac.softpedia.com/get/Develop...s/LAPACK.shtml

Tres puissant, tres polivalent et c est pas seulement en F90 tu ^peux aussi l utiliser en c++.
Par contre c est pas toujours trivial a mettre en place compilation/configurer/etc...
Quoi que tu fasse tu ne ferra JAMMAIS :sm: mieux que les fonction qui sont dans LAPACK pour faire ca.
MMM peut etre si tu fait tout en assambleur. bon ok j exagerer a peine.
Oui c est bon je sorte.
29/07/2011, 08h43
Gandalf

Déjà on n'inverse que des matrices carrées.
Ensuite les caractéristiques de la matrice vont nous guider vers l'algorithme, donc pour une matrice quelconque, il en reste peu.

Il faut penser que la matrice est peut-être singulière, ou au moins mal conditionnée, il sera alors difficile d'obtenir l'inverse, et là un algorithme pourra donner un résultat.... ....qui ne sera pas l'inverse. Il faut en être conscient.

Ensuite si la matrice est grande (taille supérieur à 200 environ) les algorithme directs deviennent suspects, le grand nombre d'opérations pour obtenir le résultat ayant pu produire des erreurs d'arrondies qui deviennent non négligeables. Autrement dit, plus la matrice est grande, plus sont conditionnement doit être bon pour obtenir un résultat valable.

Le Pivot de Gauss donne toujours un résultat (sauf matrice singulière) il est possible de l'accélérer en ne faisant qu'un pivotage partiel, mais alors des cas d'echecs sont possible, même pour des matrices non singulières.

La décomposition LU reviens à un pivot de gauss, mais est plus orienté inversion de matrice alors que le pivot est plus orienté résolution de système d'équations, mes prédécesseurs dans le topic ont déjà abordé ce point.

Il existe des méthodes itératives, où on approche le vecteur résultat d'un système d'équations par itérations successives, ces méthodes ont l'avantage de donner un résultat dont la validité est confirmée (ou infirmée) par une erreur tout en étant moins sensible à la taille pour la précision du résultat.
29/07/2011, 09h34
St4nl3y

Citation:

Envoyé par Gandalf

Déjà on n'inverse que des matrices carrées.
Ensuite les caractéristiques de la matrice vont nous guider vers l'algorithme, donc pour une matrice quelconque, il en reste peu.

Il faut penser que la matrice est peut-être singulière, ou au moins mal conditionnée, il sera alors difficile d'obtenir l'inverse, et là un algorithme pourra donner un résultat.... ....qui ne sera pas l'inverse. Il faut en être conscient.

Ensuite si la matrice est grande (taille supérieur à 200 environ) les algorithme directs deviennent suspects, le grand nombre d'opérations pour obtenir le résultat ayant pu produire des erreurs d'arrondies qui deviennent non négligeables. Autrement dit, plus la matrice est grande, plus sont conditionnement doit être bon pour obtenir un résultat valable.

Le Pivot de Gauss donne toujours un résultat (sauf matrice singulière) il est possible de l'accélérer en ne faisant qu'un pivotage partiel, mais alors des cas d'echecs sont possible, même pour des matrices non singulières.

La décomposition LU reviens à un pivot de gauss, mais est plus orienté inversion de matrice alors que le pivot est plus orienté résolution de système d'équations, mes prédécesseurs dans le topic ont déjà abordé ce point.

Il existe des méthodes itératives, où on approche le vecteur résultat d'un système d'équations par itérations successives, ces méthodes ont l'avantage de donner un résultat dont la validité est confirmée (ou infirmée) par une erreur tout en étant moins sensible à la taille pour la précision du résultat.

Bah alors faut pas le décourager comme ça !
Déjà en programmation, grace aux variables float, double et autres on sera toujours plus précis qu'avec votre calculette je peux vous l'assurer !
Ensuite pour le calcul simple du déterminant je préconise la méthode des mineurs : http://homeomath.imingo.net/determin.htm
Méthode itérative, de complexité (n) je crois, et là où l'homme se retrouve trop vite déborder, l'ordinateur n'étant pas faignant, avec un bon algo s'attaquera à la bête très facilement !
Bon courage.
29/07/2011, 11h07
Joel F

non stop. on n'inverse jamais de matrice car 99% du temps on cherche en fait a resodure un systeme. Ensuite, ta tirade sur les réels est assez affligeantes, je te conseille de te renseigner sur le sproblematiques de stabilités numeriques et tout le sproblemes *recurrent* des calculs en reels a virgule flottantes ...