[JS] Calcolo determinante di una matrice quadrata

[Necrofiend]

Volevo chiedere a qualcuno se può scrivermi/mostrarmi una funziona in JAVASCRIPT per il calcolo del determinante di una matrice quadrata maggiore di 2x2, quindi che sia: 3x3, 4x4, 5x5, ecc.

Sto impazzendo... ho provato e riprovato ma purtroppo non riesco =\

Ho trovato questo:

function complAlg(m,o,r,c)
{
  var om = o-1;
  var minore = new Array(om);
  for (i=0; i<om; i++)
    minore[i] = new Array(om);
  var a = -1;
  var b = -1;
  var i, j;
  for (i=0; i<o; i++)
    if (i!=r)
      {
        a++;
        b = -1;
        for (j=0; j<o; j++)
          if (j!=c)
            {
              b++;
              minore[a][b] = m[i][j];
            }
      }
  var d = determinante(minore,om);
  if (((r+c)%2)==1) d=-d;
  return d;
}

//---------------------------------------------------------------------
function determinante(m,o)
{
  if (o==1)
    return m[0][0];
  if (o==2)
    return m[0][0]*m[1][1]-m[0][1]*m[1][0];
  var dd = 0;
  var ca = 0;
  var p = 0;
  var e = 0;
  var i;
  for (i=0; i<o; i++)
    {
      e = m[0][i]
      if (e!=0)
        {
          ca = complAlg(m,o,0,i);
          p = e*ca;
          dd += p;
        }
    }
  return dd;  
}
//---------------------------------------------------------------------
function calcoloDet()
{
  if ((matrice==null)||(matrice==undefined))
    {
      alert("Impostare la matrice.");
      return null;
    }
  return determinante(matrice,ordine);
}

Ma non capisco il procedimento... :S

Se qualcuno caso mai sa spiegarmi almeno lo schema matematico di una funzione del genere o scrivermela in modo semplificato mi farebbe un grandissimo piacere.
Purtroppo la soluzione più facile sarebbe quella di scrivere il calcolo senza usare cicli e matrici, ma è troppo brutto così =\

Grazie in anticipo.

 

[imported_BlackLight]

Gli algoritmi per il calcolo matriciale generalmente sfruttano la triangolarizzazione della matrice attraverso il metodo di Gauss o simili. Il prodotto incrociato di Cramer è valido solo per le 2x2, Sarrus solo per le 3x3, mentre il teorema di Laplace è macchinoso da applicare a mano, e sarebbe troppo complesso da implementare come algoritmo. Quindi per una matrice di dimensione qualsiasi si preferisce portarla ad una matrice equivalente triangolare, e a quel punto il determinante, essendo una matrice triangolare, sarà semplicemente il prodotto degli elementi sulla diagonale principale.

Ti consiglio di guardare la mia libreria C++ Grassmann, dato che lì ho implementato tutte le operazioni del calcolo matriciale, compreso il calcolo del determinante applicando Gauss, o cercare su internet informazioni sull'algoritmo di triangolarizzazione di Gauss. Nella mia libreria in particolare trovi il metodo Matrix::det() che è qualcosa del genere:

float Matrix::det() throw()  {
        // Se il numero di righe è != dal numero di colonne, la matrice non è quadrata
        if (rows!=cols) 
                throw NotSquareMatrixException();

        // Se la matrice contiene un solo elemento, ritorno quell'elemento                
        if (rows==1)
                return matrix[0][0];

        // Se c'è almeno una riga o una colonna nulla, il determinante sarà 0
        for (int i=0; i<rows; i++)
                if (isNull(rowAt(i)))
                        return 0;
                
        for (int i=0; i<cols; i++)
                if (isNull(colAt(i)))
                        return 0;

        // Costruisco una matrice temporanea uguale a quella di partenza                                
        Matrix a(matrix, rows, cols);
                                
        int steps=0;

        // c è la versione triangolarizzata di a
        Matrix *c = triang(a,steps);
                        
        if (!c)
                throw NullMatrixDiagException();
                
        float d=1;                              
 
        // Faccio il prodotto degli elementi lungo la diagonale principale di c               
        for (int i=0; i < c->rows; i++)
                d *= c->matrix[i][i];
                                        
        return ((steps%2) ? -d : d);
}

Questo è invece il metodo Matrix::triang(), usato per triangolare la matrice applicando il metodo di Gauss:

Matrix* triang(Matrix &m) throw()  {
        vector<float> v;
        Matrix *a = new Matrix(m);
        
        for (int n=0; n < a->cols; n++)  {
                Matrix b(a->rows, a->cols);
                v.clear();
                float pivot = a->matrix[n][n];
               
                if (pivot==0)
                        throw NullMatrixDiagException();
                        
                for (int i=0; i < a->rows; i++)  {
                        if (i<n)
                                v.push_back(0);
                        else if (i==n)
                                v.push_back(1);
                        else  {
                                float tmp = -(a->matrix[i][n]);
                                tmp /= pivot;
                                v.push_back(tmp);
                        }
                }
                
                b.insertColumn(v,n);
               
                for (int i=0; i < a->cols; i++)  {
                        if (i!=n)  {
                                v.clear();
                                        
                                for (int j=0; j < a->rows; j++)  {
                                        if (i==j)
                                                v.push_back(1);
                                        else   
                                                v.push_back(0);
                                }
                               
                                b.insertColumn(v,i);
                        }
                }
                
                Matrix *c = b*(*a);
               
                for (int i=0; i < c->cols; i++)
                        for (int j=0; j < c->rows; j++)
                                a->matrix[i][j] = c->matrix[i][j];
        }
        
        return a;
}

 

[Necrofiend]

Quindi la funzione complAlg(m,o,r,c) dell'esempio che ho riportato prima che cosa fa?
"trasforma" una matrice di n ordine ad una matrice di 3° ordine (3x3) ?
Vedo che crea un'altra matrice di ordine minore di 1 poi non capisco bene come procede.... =\

 

[imported_BlackLight]

A occhio e croce (è scritta malissimo quindi ci rinuncio a interpretarla in modo deterministico) direi che, dato che tira fuori i minori da una matrice di ordine n, ovvero tira fuori le matrici fino ad ordine 2x2 e 3x3 per poi fare tutto separatamente, è un algoritmo che usa il metodo di Laplace. Ma non ti assicuro che funzioni per matrici di qualsiasi ordine. Per andare sul sicuro, usa la triangolarizzazione di Gauss.

 

[Necrofiend]

A occhio e croce (è scritta malissimo quindi ci rinuncio a interpretarla in modo deterministico) direi che, dato che tira fuori i minori da una matrice di ordine n, ovvero tira fuori le matrici fino ad ordine 2x2 e 3x3 per poi fare tutto separatamente, è un algoritmo che usa il metodo di Laplace. Ma non ti assicuro che funzioni per matrici di qualsiasi ordine. Per andare sul sicuro, usa la triangolarizzazione di Gauss.

OK grazie mille per l'aiuto. =)
Ora mi guardo un pò la tua libreria e mi studio la triangolarizzazione. Comunque mi sto rendendo conto che non è così facile come pensavo =P