Calcolo di determinanti? (informatica - matematica)?

Question

Il determinante di una matrice si può calcolare in diversi modi (due principali):
- ricorrendo allo sviluppo per colonne o per righe (e relativi determinanti di "sottomatrici");
- ricorrendo alla formula di Leibniz.

Il calcolo del determinante non è così semplice, soprattutto da matrici 4x4 in su. Per una matrice n x n ci sono n! termini da calcolare e quindi i calcoli man mano che cresce n diventeranno sempre più lunghi.

Ora veniamo alla domanda:
gli algoritmi che si usano per calcolare un determinante fanno uso di uno di questi due metodi? O ci sono metodi più semplici?
Quale, in ogni modo, tra le due è il metodo più veloce?

Un ultima domanda, che non c'entra più nulla con informatica però:
ci hanno dato per esercizio una matrice 175x175 (naturalmente definendo i componenti della matrice in funzione della riga-colonna, non di certo scrivendola per esteso!), cosa mi suggerireste di utilizzare come metodo di calcolo? Sono ad un punto morto..

Grazie mille in anticipo...

Scusate non ho specificato:
devo calcolare il determinante della matrice 175x175, ma non so quale dei due metodi sarebbe più adatto per calcolarlo.

Giulio... Grazie! Non sapevo niente della fattorizzazione LU...sembra un buon metodo anche questo...
Grazie mille a tutti per le risposte!

Metto la matrice 175x175.
C=(c_kl) k,l sono gli indici riga-colonna

c_kl = k^2 + 1, se k=l ... l*k, se k<>l

Vediamo cosa vi esce...
Buona fortuna ;-)

Answer 1

Ottima domanda. Interessante, ben formulata e dettagliata. Cercherò di dare una risposta della stessa qualità.


Ci sono sistemi efficienti per il calcolo di determinanti nel caso di matrici particolari. Tra le classi di matrici più interessanti da questo punto di vista, abbiamo le matrici triangolari e le matrici sparse.

Per il determinante di una matrice triangolare basta fare il prodotto degli elementi sulla diagonale.

Per il determinante di una matrice sparsa puoi usare una ricerca preliminare per individuare la riga o colonna che contiene il maggior numero di zeri e poi usare l'algoritmo di Laplace (scegliendo ogni volta con accortezza la riga o colonna migliore). S'intende che se durante la ricerca della riga o colonna con più zeri se ne trova una con solo zeri, il calcolo termina e il risultato è zero.

Esiste una tecnica per ricondursi a questi due casi, molto usata in analisi numerica per la risoluzione di sistemi lineari di grandi dimensioni o per il calcolo di determinanti di matrici molto grandi. Si tratta della tecnica di fattorizzazione LU. Ogni matrice A può essere scritta in questo modo P*A=L*U ovvero A=L*U*P^(-1) dove L è una matrice triangolare inferiore, U una matrice triangolare superiore e P una matrice per la permutazione di righe (le cifre che contiene sono solo 0 e 1). Il determinante di L e U si calcola in tempo lineare e il determinante di P in genere costa poco per la presenza di molti zeri, n^2-n su un totale di n^2 elementi, dove n è la dimensione della matrice. La fattorizzazione LU ha un costo polinomiale di O(2/3*n^3).

Nel caso in cui la matrice sia semidefinita positiva (autovalori non negativi), si può usare una variante della fattorizzazione di LU: la fattorizzazione di Cholesky. Il costo è circa lo stesso, ma la costante davanti è diversa: solo O(n^3/3) operazioni.

Esiste una versione della fattorizzazione detta fattorizzazione incompleta che sostanzialmente introduce delle perturbazioni all'interno della matrice allo scopo di eliminare gli elementi di modulo più piccolo e di velocizzare il calcolo aumentando il numero degli zeri. Su quest'argomento si trova poco, ma se ti interessa prova l'ultimo link.

Answer 2

Vengono utilizzati questi due metodi, ma alle volte si ricorre anche al metodo di Gauss che trasforma la matrice in una equivalente, ma in forma triangolare superiore, così il calcolo del determinante si riduce alla sola moltiplicazione di tutti gli elementi presenti sulla diagonale principale.

Ciao!!!
Lulisja

Answer 3

Intanto osserviamo che è una matrice simmetrica definita positiva.
Il metodo di Cholevsky dice che esistono e sono uniche:
D matrice diagonale, A triangolarei inferiore speciale, tale che A = L D Lt
Allora esiste ed è unica matrice L triang.inferiore tale che A = L Lt (è un corollario del metodo di Cholevsky)
Si dimostra che il costo della fattorizzazione è n^3/6 + n^2/2 + n/3
le formule compatte sono
a(i,j) = somma (k=1..min(i,j)) l(i,k) (l(k,j)t)
=somma (k=1..min(i,j)) l(i,k) (l(j,k))
essendo A simmetrica considero solo gli aij per i>=j
a(i,i) = somma(k=1..i) (l(i,k)^2) = somma(k=1..i-1)l(i,k)+l(i,i)
a(i,j) = somma(k=1..j) (l(i,k)l(j,k) = somma(k=1..j-1) l(i,k)l(j,k) + l(i,j)l(j,j)

Da cui si ricavano le formule per l(j,j) e l(i,j):
l(i,i)= sqr(a(i,i) - somma(k=1..i-1)l(i,k))
l(i,j)= (a(i,j) - somma(k=1..j-1)l(i,k)l(j,k) ) / l(j,j) (per j L'ordine con cui effettuare il calcolo è:
1
2 3
4 5 6
7 8 9 10
...

Queste sono le formule generiche.
Un algoritmo potrebbe essere:
int N=175
double Somma;
for (int i=1; i<=N i++){
for (int j=1; j Somma=0; //somma(k=1..j-1)l(i,k)l(j,k)
for (int k=1; k Somma=Somma+L[i,k]L[j,k]
}
L[i,j]= (A[i,j]-Somma)/A[j,j]
}
Somma=0; //somma(k=1..i-1)l(i,k))
for (int k=1; k Somma=Somma+L[i,k]
}
L[i,i]= sqr(A[i,i] - Somma)
}
(l'ho buttato giù in un minuto, non lo garantisco!)

Non sono riuscito ad ottimizzarla, forse anche perché preso da altre cose (mio figlio ha la febbre!)

Answer 4

non sono sicuro della risposta comunque so per certo che esistono delle applicazioni scritte in c\c++ che utilizzano un'algoritmo ricorsivo che sfrutta il primo dei due metodi che hai citato, penso perche' essendo molto ripetitivo e' piu' "facile" da gestire in termini di struttura dati e di funzioni, personalmente in C cosi' a occhi non mi sembra molto difficile da implementare basta gestire bene gli indici di riga e colonna il resto sono operazioni banali. In alternativa esistono software nati per la gestione di matrici, il piu' noto, almeno per me :), e' sicuramente Matlab che e' un software di calcolo matriciale molto potente e molto facile da usare in termini di gestione della base di dati.
Gli algoritmi di quest'ultimo pero' non mi sono noti quindi non saprei quali dei due metodi funziona. Per arrivare alla tua seconda domanda ovviamente risolverla a mano sarebbe un suicidio, con matlab ad esempio potresti risolverla in pochi minuti, giusto il tempo di inserire i dati... spero di esserti stato di aiuto, ciao e in bocca al lupo

Answer 5

Qualsiasi metodo utilizzi il numero di operazioni sarà lo stesso.
Per scrivere meno codice
1 dimensiona una matrice 175 righe e 175+174 colonne
2 copia le prime 174 colonne a destra (la 1 va al 176° posto ...)
3 moltiplica tra loro i numeri delle 175 diagonali da alto a sx a basso a dx e somma
4 lo stesso per le diagonali da basso dx a alto sx e somma
5 sottrai la somma del punto 3 meno quella del punto 4

auguri!

Answer 6

boh