Newsgroup: it.comp.lang.c
Titolo: inversione di matrici





Qualcuno mi potrebbe suggerire un algoritmo che consente l'inversione di 
matrici?


Grazie a tutti !



 matrici? Grazie a tutti !
Chiamiamo A la matrice che devi invertire: Gli affianchi una seconda 
matrice ( che chiamiamo B ). Inzialmente B e' pari alla matrice identita'.
Operi su A e su B le stesse operazioni. In particolari effettui una 
eliminazioni di gauss che ti porta ad avere A prima in forma triangolare, ( 
e gia' da qua' facendo il prodotto dei termini della diagonale fai saltar 
fuori il determinante ) poi diagonale ed infine la matrice identita'.
La matrice B che otterrai sara' la matrice inversa di A.
Occhio che se ti trovi uno zero sulla diagonale, devi fare uno swap di 
righe; se NON trovi nessuna riga che abbia quella colonna senza uno zero 
allora la matrice e' singolare.
Ci sarebbero anche considerazioni su effettuare swap in modo da avere 
calcoli non assurdi ( ovverro numeri grossi con numeri piccoli ) ma non 
ricordo i dettagli.
La teoria che sta alla base e' la seguente: se tu immagini che ogni 
operazioni che esegui su A ( quindi su B ) puo' essere vista come un 
prodotto fra matrici hai
A(j+1) = A(j) * Q(j)
Ovvero la matrice al passo j+1 e' ottenuta a partire dalla matrice del 
passo j per "una" matrice Q(j). Per cui puoi scrivere
A(j+1) = A(j-1 ) * Q ( j-1 ) * Q(j) = ... = A(1) * Q(1) * Q(2) * Q(j) = 
        A( 0 ) * Q1( J )
Avendo indicato Q1(j) come la produttoria di tutte le Q(i) per i che va da 
1 a J
Q1(j) = Q(1)*Q(2)*Q(3)* ... *Q(j)
Insomma alla fine avrai
I=A(j-finale)=A(1)*Q1(j-finale)
B(j-finale)=B(1)*Q1(j-finale)=Q1(j-finale)      B(1)=I
poiche' I=A(1)*Q1(j-finale) abbiamo che Q1(j-finale)=B(j-finale) e' 
l'inversa di A(1)=A.
L'importante e' che operi su B le stesse operazioni che operi su A. Poiche' 
su ha operi combinazioni lineari di righe che sono rappresentabili 
attraverso prodotti di matrici e' automatico che B alla fine sia l'inverso 
di A.
 

Grazie a tutti !
Un sistema standard e' quello chiamato delle "matrici gemelle";
si comincia con la matrice in ingresso "affiancata" da una matrice
identita' e a questo punto si procede a rendere prima triangolare
superiore e poi identita' la matrice in ingresso usando tre tipi
di operazione:
   1) scambio di righe
   2) moltiplicazione di una riga per una costante
   3) addizione ad una riga di un'altra riga moltiplicata
      per una costante
Le operazioni sono applicate all'intera riga e quindi agiscono
anche sulla matrice gemella che inizialmente e' la matrice
identita' e che nel processo si trasforma nell'inversa.
es (fatto con una matrice 2x2):
   2 3  1 0
   4 5  0 1
moltiplichiamo la prima riga per 0.5 (rendiamo m11 = 1)
   1 1.5   0.5 0
   4  5     0  1
sottraiamo alla seconda riga la prima moltiplicata per 4
(azzeriamo m21)
   1  1.5   0.5 0
   0  -1    -2  1
moltiplichiamo la seconda riga per -1 (rendiamo m22=1)
   1  1.5   0.5   0
   0   1     2   -1
sottraiamo alla prima riga la seconda riga
moltiplicata per 1.5 (azzeriamo m12)
   1   0   -2.5  1.5
   0   1     2   -1
La matrice in ingresso e' diventata l'identita' e quindi
la sua matrice inversa e'
   -2.5  1.5
     2   -1
per verificare basta rimoltiplicare per la matrice data
    2  3    -2.5  1.5     (-5+6)   (3-3)
    4  5      2   -1     (-10+10)  (6-5)
Nel programma e' importante includere anche una regola
che nei calcoli manuali non ho usato.
Quando durante la fase di discesa si deve dividere la
i-esima riga per l'elemento i-esimo della stessa (in
modo da rendere 1 l'elemento sulla diagonale) e' importante
scegliere fra le righe ancora da elaborare quella che alla
colonna i-esima ha l'elemento di valore assoluto massimo ed
eventualmente effettuare lo scambio di righe.
Facendo i calcoli a mano (a precisione infinita) lo scambio
e' obbligatorio solo se l'elemento alla colonna i-esima e'
nullo ma nei casi reali il non seguire questa regola puo'
portare a *grandi* errori di calcolo (per problemi di
precisione numerica).
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff