Inversion et déterminant d'une matrice

Version imprimable

15/12/2005, 16h58
coline

Inversion et déterminant d'une matrice

voilà je dois réaliser un projet sur les calculs matriciel!
il me faudrait une solution pour faire une procedure pour faire linverse dune matrice! son determinant!
et son exponentielle!tout ça pour des matrices de toutes dimensions!pas forcement des matrices carrés!
jai déja réaliser le produi laffichage la somme....
merci d'avance!

[titre édité par Nono40]
Ancien titre : bonjour !
Merci de respecter les règles
15/12/2005, 17h12
Giovanny Temgoua

Bonjour !

Merci d'utiliser le forum approprié pour poser votre problème, et d'utiliser des titres plus explicites. "Bonjour" n'est pas très approprié...

Je déplace votre message dans le forum Algorithme où il aura certainement de solutions plus adéquates.

Ce forum est réservé aux questions spécifiques à Delphi. (questions que vous aurez probablement à l'implémentation de votre algorithme)
15/12/2005, 18h16
xxiemeciel

Dois tu developper tes propres solutions ?

Parceque au niveau des calculs matricielles je te suggere de regarder la librarie LAPACK. anciennement en FORTRAN mais qui possede un equivalent C nommé CLAPACK.

Cette librairie est actuellement la plus performante en matiere de matrice, elle est utilisé par MATLAB.

Le code est disponible sur le web si tu veux l'analyser et je pense que il y a beaucoup de doc dessus aussi. Mais attention c compliqué

XXiemeciel
15/12/2005, 20h01
j.p.mignot

L'écriture que je préfère pour M^-1 est

M^-1 = 1/ Det(M) * Transposée ( Commatrice(M))

car elle est compacte et montre très bien sa construction.
Numériquement cela est en général peu approprié car il y a un très grand nombre de det à calculer, chacun d'entre eux etant une fonction récursive en fonction d'un développement suivant une ligne ou une colonne.

Numériquement le plus sur et + rapide devrait être une décomposition L.U de M

L est une matrice triangulaire Low ( Lij > 0 si j > i) et U est une matrice triangulaire Up ( Uij = 0 si i > j ).
il y a N^2 + N inconnues pour N^2 équations. On peut fixer Lii=1.

Le système restant se résoud alors sans diffculté

M^-1 et det(M) en découlent immédiatement.
15/12/2005, 20h09
xxiemeciel

Oui effectivement la decomposition LU est efficace, c'est un des algorithmes utilisé par LAPACK.

XXiemeciel
15/12/2005, 20h15
j.p.mignot

une bonne description se trouve sur :

http://www.library.cornell.edu/nr/bookcpdf/c2-3.pdf
16/12/2005, 09h34
Gnux

Bonjour
Que veut dire le ^? J'arrive jamais à savoir en logique ça désigne ET mais ici? Un quotient?
Merci
16/12/2005, 09h37
progfou

C 'est le symbole de l'élévation à la puissance.
N^2 => N²
16/12/2005, 13h22
Matthieu Brucher

Re: Inversion et déterminant d'une matrice

Citation:

Envoyé par coline

voilà je dois réaliser un projet sur les calculs matriciel!
il me faudrait une solution pour faire une procedure pour faire linverse dune matrice! son determinant!
et son exponentielle!tout ça pour des matrices de toutes dimensions!pas forcement des matrices carrés!
jai déja réaliser le produi laffichage la somme....
merci d'avance!

L'inverse d'une matrice non carrée n'existe pas, il faut plutôt voir du côté de la pseudo-inverse.
Il y a plusieurs algos qui existent pour l'inverse.
Pour le déterminant, qqs opérations de houseolder te permettront de rendre ta matrice triangulaire supérieure ou inférieure.
Pour l'exponentielle, tu diagonalises ta matrice puis tu prends l'exponentielle des valeurs propres. Si tu ne peux pas diagonaliser la matrice, c'est qu'elle n'a peut-être pas d'exponentielle.
17/12/2005, 16h25
DrTopos

Re: Inversion et déterminant d'une matrice
Citation:

Envoyé par Miles

Si tu ne peux pas diagonaliser la matrice, c'est qu'elle n'a peut-être pas d'exponentielle.

Désolé de te contredire Miles. Toute matrice carrée réelle a une exponentielle, tout simplement parce que la série:
Code:

1 2 exp(M) = I + M + (M^2)/(2!) + ... + (M^n)/(n!) + ...
est normalement convergente.

Je pense que dans le cas d'une matrice carrée réelle qui commute avec sa transposée (chose facile à vérifier), le calcul de l'exponentielle doit pouvoir se faire de manière efficace. En effet, une telle matrice représente un endomorphisme normal de l'espace euclidien R^n. Or pour un tel endomorphisme, R^n se décompose en somme directe orthogonale de droites et plans tous stables par cet endomorphisme. Une fois cette décomposition établie, on a juste a calculer des exponentielles de réels ou de matrice 2x2 de similitudes (donc de nombre complexes) ou de matrice 2x2 symétriques. La démonstration de ce théorème est très certainement assez constructive pour être programmée. On la trouvera par exemple ici.
18/12/2005, 19h47
Matthieu Brucher

Oups, pardon :)
20/12/2005, 13h37
Nemerle

Pour l'inverse, y a + simple:

Tu accoles à droite de te matrice M la matrice I (diagonale avec que des 1).
Puis tu fais sur MI un "full"-pivot de Gauss (i.e. une ligne ayant déjà été choisi pour pivot sera modifiée par les autres pivots), de telle sorte que tu arrives à IN.

L'inverse de M, c'est N !

Et si tu ne pas arrive à I à gauche (i.e. il y a des lignes à zéro), c'est que M n'est pas inversible, soit detM=0...
20/06/2006, 19h56
babycrash

pb avec la methode de gauss jordan

Bonjour,

Je cherche aussi a inverser des matrices (carrees pour ma part).
J'utlise actuellement la methode de Gauss-jordan qui constite comme decrit precedemment a ajouter la matrice identite I puis d'utliser la methode du pivot de Gauss pour retrouver cette matrice I.
Je compte mettre en place un petit test sur le determinant afin de verifier qu'il ne soit pas nul.
Le pb est que cette methode doit etre mal implementee car je rencontre de nombreux pb lorsque je la teste avec des matrices simples.

Auriez vou une proposition de code (pour cette methode ou une autre du type:1/det(A) *trans(com(A)) )

Merci!

Voici un petit code que j'ai utilisé bien des fois. Il est en pascal et utilisable sous Delphi.

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
 
unit mat17_inv;
 
interface
 
const   C_17  = 17;
const   C_32  = 32;
 
type Matrice  = array[1..C_32,1..C_32] of Extended;
 
function inverse_M( rg : integer; M: matrice; var M_1 : Matrice) : boolean;
 
implementation
 
procedure Somme(rg : integer; MatA,MatB:Matrice;  var MatC:Matrice);
var i,j       : byte;
   begin
   for i:=1 to rg do  for j:=1 to rg do
      MatC[i,j]               :=  MatA[i,j] + MatB[i,j]
   end;
procedure Difference(rg : integer; MatA,MatB:Matrice;var MatC:Matrice);
var i,j       : byte;
   begin
   for i:=1 to rg do for j:=1 to rg do
      MatC[i,j]               :=  MatA[i,j] - MatB[i,j]
   end;
procedure Produit(rg : integer; MatA,MatB:Matrice;var MatC:Matrice);
var i,j,k     : byte;
   begin
   fillchar(MatC,sizeof(MatC),0);
   for i:=1 to rg do for j:=1 to rg do for k:=1 to rg do
      MatC[i,j]               :=  MatC[i,j]+MatA[i,k] * MatB[k,j]
   end;
function Norme_Ligne(rg : integer; B:Matrice):Extended;
var Tmp,Tmp2  : Extended;
    i,j       : byte;
   begin
   Tmp                        :=  0;
   for i:=1 to rg do
      begin
      Tmp2                    :=  0;
      for j:=1 to rg do
         Tmp2                 :=  Tmp2 + abs(B[i,j]);
      if Tmp2>Tmp then
         Tmp                  :=  Tmp2
      end;
   Norme_Ligne                :=  Tmp
   end;
function Norme_Colonne(rg : integer; B:Matrice):Extended;
var Tmp,Tmp2  : Extended;
    i,j       : byte;
   begin
   Tmp                        :=  0;
   for i:=1 to rg do
      begin
      Tmp2                    :=  0;
      for j:=1 to rg do
         Tmp2                 :=  Tmp2 + abs(B[j,i]);
      if Tmp2>Tmp then
         Tmp                  :=  Tmp2
      end;
   Norme_Colonne              :=  Tmp
   end;
procedure Calcule_E(rg : integer; var A, B, E, Id : matrice);
var C         : Matrice;
   begin
   Produit(rg, B, A, C);
   Difference(rg, Id, C, E)
   end;
procedure Init(rg : integer; A:Matrice;var B,Id :Matrice;var OK:boolean);
var i,j       : byte;
    T         : Extended;
   begin
   fillchar(Id,SizeOf(Id),0);
   T                          :=  Norme_Ligne(rg, A) * Norme_Colonne(rg, A);
   if abs(T)>1E-100 then
      begin
      OK                      :=  True;
      for i:=1 to rg do
         begin
         Id[i,i]              :=  1;
         B[i,i]               :=  A[i,i]/T;
         for j:=i+1 to rg do
            begin
            B[i,j]            :=  A[j,i]/T;
            B[j,i]            :=  A[i,j]/T
            end
         end
      end
   else
      OK                      :=  false
   end;
procedure Calcule_B( rg : integer; var B,E,Id : Matrice);
var C,D       : Matrice;
   begin
   Somme(rg,Id,E,D);
   Produit(rg,D,B,C);
   B                          :=  C
   end;
const Seuil_  = 1e-17;
const max_CPT = 225;
function Inverse_M(rg : integer; M : Matrice; var  M_1 : Matrice) : boolean;
var Id,E,B    : Matrice;
    Old,New   : Extended;
    Cpt       : byte;
    Ok        : boolean;
   begin
   Init(rg, M, B, Id, Ok);
   if  OK then
       begin
       Calcule_E(rg, M, B, E, Id );
       Old                    :=  Norme_Ligne(rg, E);
       New                    :=  Old;
       Cpt                    :=  0;
       while not ( (New < Seuil_) or ((New > Old) and (Cpt>max_CPT))) do
          begin
          Old                 :=  New;
          Calcule_B(rg, B, E, Id);
          Calcule_E(rg, M, B, E, Id );
          New                 :=  Norme_Ligne(rg, E);
          inc(Cpt)
          end;
       Ok                     :=  New < Seuil_;
       M_1                    :=  B
       end;
   Inverse_M                  :=  Ok
   end;
end.

20/06/2006, 20h43
babycrash

Merci

Merci, pour ce code mais etant nouveau dans la programmation je me noie un peu avec ce langage qui m'est inconnu
Aurais tu le meme sous C. Ou peut etre des docs a me conseiller

Merci en tout cas ;)
23/06/2006, 00h02
j.p.mignot

voir les Numerical Recipes que j'ai déjà bien souvent proposé.

http://www.library.cornell.edu/nr/cbookcpdf.html

pour les matrices / déterminants chapitre 2
23/06/2006, 09h01
progfou

J'ai regardé le chapitre 2.3.
J'aimerais bien comprendre (car ce n'est pas très bien expliqué, à mon goût) en quoi une décomposition LU aide à calculer A^-1.B ?
Qui peut me donner l'explication "mathématique" ?