Eliminazione Gauss

di il
9 risposte

Eliminazione Gauss

Salve,
ho scritto questo frammento di codice che dovrebbe operare una eliminazione di Gauss su una matrice azzerando gli elementi della prima colonna sotto il primo e modificando di conseguenza anche le altre colonne. La variabile iterazione è stata inizializzata a 0 nella main e sarà poi opportunamente incrementata ad ogni chiamata della funzione. Il problema è che quando vado a stampare la matrice restituita dalla funzione risulta che solo gli elementi della prima colonna sono stati azzerati, le altre colonne rimangono invariate. Non riesco a capire il motivo. Potete gentilmente aiutarmi ?

void eliminazione_gauss ( tMatrice M, int m, int n, int iterazione)
{
int i, j,s;
tMatrice T;
    
      for ( j = iterazione; j < n; j++ ) {
         for ( i = iterazione; i < m; i++ ) {
            if ( M[i][j] == 0 ) { s = i+1; }
            else {
               s = 0;
               i = m;
               j = n; } } }
  
   if ( M[iterazione][iterazione] == 0 ) {
      for ( j = iterazione; j < n; j++ ) {
         T[s][j] = M[s][j];
         M[s][j] = M[0][j];
         M[0][j] = T[s][j]; } }
   else {
      for ( i = iterazione+1; i < m; i++ ) {
         for ( j = iterazione; j < n; j++ ) {
            M[i][j] = M[i][j] - M[i][iterazione]*M[iterazione][j]/M[iterazione][iterazione]; } } }

   for ( i=0; i<m; i++ ) {
      for ( j=0; j<n; j++ ) {
         printf ("%.2f\t", M[i][j] ); }
      printf("\n"); }

}

9 Risposte

  • Re: Eliminazione Gauss

    Ciao, da uno sguardo veloce non ti saprei dire di preciso dov'è il problema, in ogni caso ti consiglio di scrivere una funzione a parte che si occupa di stampare la matrice e una funzione scambia_righe() che si occupa di scambiare due generiche righe della matrice. Relativamente alla funzione
    void eliminazione_gauss(double m[N][N], unsigned int rig, unsigned int col, unsigned int k);
    essa avrà lo scopo di azzerare tutti gli elementi al di sotto di m[k][k]. L'algoritmo sarà il seguente:
    - se m[k][k]=0 cerchi un elemento m[i.][k] (con i>k) non nullo;
    - se non lo trovi esci dalla funzione;
    - se lo trovi scambi le righe i e k e fai quello che c'è da fare (la parte di codice relativa a questa parte mi sembra corretta ).
  • Re: Eliminazione Gauss

    Sono riuscito a risolvere. È bastato assegnare il calcolo per l'eliminazione non più a M[j] stessa, ma alla matrice temporanea T, e poi prima di stampare riassegnare M=T. Non ho capito perché ma il fatto di calcolare "M=una formula dove compare M" causava problemi. Sarebbe interessante capire il perché (meccanismi di memoria?).

    Scusa se te lo chiedo, ma se voglio portare la matrice ridotta "fuori" dalla funzione, ossia restituirla alla main, devo usare i puntatori?
  • Re: Eliminazione Gauss

    beowulf ha scritto:


    Sono riuscito a risolvere. È bastato assegnare il calcolo per l'eliminazione non più a M[j] stessa, ma alla matrice temporanea T, e poi prima di stampare riassegnare M=T. Non ho capito perché ma il fatto di calcolare "M=una formula dove compare M" causava problemi. Sarebbe interessante capire il perché (meccanismi di memoria?).
    Mi fa piacere che tu abbia risolto, ma sinceramente non capisco a cosa serva la matrice temporanea.

    beowulf ha scritto:


    Scusa se te lo chiedo, ma se voglio portare la matrice ridotta "fuori" dalla funzione, ossia restituirla alla main, devo usare i puntatori?
    Se tMatrice è un array statico bidimensionale già li stai usando i puntatori!

    Comunque se ti può essere utile io farei qualcosa del genere:
    #include <stdio.h>
    
    #define N 3
    
    void scambia_righe(double m[N][N], unsigned int col, unsigned int i_1, unsigned int i_2)
    {
        for(unsigned int j = 0; j < col; ++j)
        {
            double temp = m[i_1][j];
            m[i_1][j] = m[i_2][j];
            m[i_2][j] = temp;
        }
    }
    
    void eliminazione_gauss(double m[N][N], unsigned int rig, unsigned int col, unsigned int k)
    {
        if(!m[k][k])
        {
            for(unsigned int i = k + 1; ; ++i)
            {
                if(i == rig)
                {
                    return;
                }
                if(m[i][k])
                {
                    scambia_righe(m, col, k, i);
                    break;
                }
            }
        }
        for(unsigned int i = k + 1; i < rig; ++i)
        {
            if(m[i][k])
            {
                double r = m[i][k] / m[k][k];
                for(unsigned int j = k; j < col; ++j)
                {
                    m[i][j] -= r * m[k][j];
                }
            }
        }
    }
    
    void stampa_matrice(double m[N][N], unsigned int rig, unsigned int col)
    {
        for(unsigned int i = 0; i < rig; ++i)
        {
            for(unsigned int j = 0; j < col; ++j)
            {
                printf("%.2f\t", m[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    
    int main()
    {
        double m[N][N] = {{8, 5, 6},
                          {2, 7, 7},
                          {1, 2, 9}};
        stampa_matrice(m, N, N);
        double D = 1;
        for(unsigned int k = 0; k < N; ++k)
        {
            D *= m[k][k];
            eliminazione_gauss(m, N, N, k);
        }
        stampa_matrice(m, N, N);
        printf("D = %.2f\n", D);
        return 0;
    }
    il calcolo del determinante l'ho messo per controllare la correttezza delle operazioni svolte.
  • Re: Eliminazione Gauss

    Ciao Nippolo,
    ho cercato di implementare i tuoi consigli, in particolar modo sul dividere i compiti in pezzetti creando varie funzioni "base".
    È uscito fuori il seguente programma. A funzionare funziona, testato già con varie matrici ridotte a scala sul mio quaderno di algebra, oltre che con matrici appartenenti a casi limite, tipo quelle fatte ad L. È stata una faticaccia ma sono contento. Si accettano comunque consigli. Grazie.
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    #define MAX 20
    #define PRECISIONE 100
    
    typedef float tMatrice[MAX][MAX];
    tMatrice M;
    
    unsigned int validazione_input_intero ( unsigned int );
    void stampa_matrice ( tMatrice, unsigned int, unsigned int );
    void controllo_gradini ( tMatrice, unsigned int, unsigned int );
    void scambia_righe ( tMatrice, unsigned int, unsigned int, unsigned int );
    void azzera (tMatrice, unsigned int, unsigned int, unsigned int );
    void eliminazione_gauss ( tMatrice, unsigned int, unsigned int );
    
    unsigned int validazione_input_intero ( unsigned int v )
    {
    	int c;
    	do
    	    { c=scanf("%d", &v);
    	      if (c==0)
    	          {
    	      	scanf ("%*[^\n]");
    	      	printf ("Attenzione: input non valido. Inserire input valido: ");
    	           }
    	     } while (c==0);
    	  
    if(v>MAX)
    	   {   printf ("%u", v);
    	             printf(" viene scalato a %u", MAX);
    	        v=MAX;
    	    }
    else
    	    { printf("%u", v); }
    	  
    return v; }
    
    void stampa_matrice ( tMatrice M, unsigned int rig, unsigned int col)
    {
    unsigned int i, j;
    
     for ( i=0; i<rig; i++ ) {
      for ( j=0; j<col; j++ ) {
       printf ("%.2f\t", M[i][j]); }
      printf ("\n"); }
     printf ("\n");
    }
    
    void controllo_gradini ( tMatrice M, unsigned int rig, unsigned int col )
    {
     unsigned int i, j, k1 = 0, k2 = 1;
    
      for ( i =1; i < rig - 1; i++ ) {
        for ( j = 0; j < col; j++ ) {
          if ( (int)( M[i][j] * PRECISIONE) != 0 ) { 
            k2 = j;
              if ( k2 > k1 ) {
                unsigned int z, u;
                float coeff;
    
            for (z = i + 1; z < rig; z++) {
      if ( (int)( M[z][k2] * PRECISIONE) != 0 ) {
      coeff = M[z][k2] / M[i][k2] ; 
      for ( u = k2; u < col; u++) {
         M[z][u] = M[z][u] - coeff * M[i][u] ;
    } } }
     }  
     k1 = k2; 
     j = col;
           } 
         }
      }
    }
    
    void scambia_righe ( tMatrice M, unsigned int rig, unsigned int col, unsigned int iterazione )
    {
    unsigned int i, j;
    unsigned int rig_1, rig_2;
    float temp;
    
    rig_1 = iterazione;
    
    for ( j=iterazione; j < col; j++ ) {
     for ( i=iterazione; i < rig; i++ ) {
      if ( (int)( M[i][j] * PRECISIONE) != 0 ) {
       rig_2 = i;
       i = rig;
       j = col; } } }
    
    if ( rig_2 != rig_1 ) {
     for( j = iterazione; j < col; j++ )
        {
            temp = M[iterazione][j];
            M[iterazione][j] = M[rig_2][j];
            M[rig_2][j] = temp;
        } }
    } 
    
    void azzera (tMatrice M, unsigned int rig, unsigned int col, unsigned int iterazione )
    {
      int i, j;
      float coeff;
      
     for (i = iterazione + 1; i < rig; i++) {
      if ( (int)( M[i][iterazione] * PRECISIONE) != 0 ) {
      coeff = M[i][iterazione] / M[iterazione][iterazione] ; 
      for ( j = iterazione; j < col; j++) {
         M[i][j] = M[i][j] - coeff * M[iterazione][j] ;
    } } }
    
     }
         
    void eliminazione_gauss ( tMatrice M, unsigned int rig, unsigned int col )
    {
     unsigned int passi, iterazione;
    
    if ( rig >= col ) { passi = col - 1; }
    else { passi = rig - 1; }
    
    for ( iterazione = 0; iterazione <= passi; iterazione++ ) {
      scambia_righe ( M, rig, col, iterazione );
      azzera ( M, rig, col, iterazione );
      stampa_matrice ( M, rig, col ); }
    
      controllo_gradini ( M, rig, col );
      stampa_matrice ( M, rig, col );
      
    }
    
    int main()
    {
    unsigned int i, j, rig, col, v;
    double t;
    
       printf ("\nInserisci il numero di righe della matrice: ");
    	rig = validazione_input_intero (v);
    
       printf ("\nInserisci il numero di colonne della matrice: ");
       col = validazione_input_intero (v);
    
       printf("\nInserisci i valori della matrice da sx a dx in ordine di riga:\n");
    	 
    	 for (i=0; i<rig; i++) {
    	    for (j=0; j<col; j++) { 
              scanf("%f", &M[i][j]) ; }
           printf ("\n"); }
    
       stampa_matrice (M, rig, col);
    
       srand(time(NULL));
    
       clock_t start=clock();
    
       eliminazione_gauss ( M, rig, col );
    
       clock_t end=clock();
         t=((double)(end-start)) / CLOCKS_PER_SEC;
         printf("\nTempo di esecuzione = %f secondi\n", t) ;
    
       return 0;
    }
    
  • Re: Eliminazione Gauss

    Ciao!

    Alcune osservazioni:
    - innanzitutto al fine di rendere il codice più chiaro e leggibile ti consiglio di rispettare l'indentazione e la spaziatura;
    - sempre per una questione di leggibilità (e non solo), ti consiglio (quando possibile) di dichiarare le variabili del ciclo direttamente all'interno del for;
    - evita di utilizzare variabili globali e quando lo fai evita di utilizzare gli stessi identificatori anche per altre variabili locali;
    - perché includi la libreria math.h?
    - perché utilizzi la funzione srand()?
    - sinceramente non capisco l'utilità di calcolare il tempo di esecuzione della funzione eliminazione_gauss(), ma se proprio lo vuoi fare devi togliere le printf() dalla funzione, altrimenti la misurazione risulta falsata;
    - relativamente alla funzione validazione_input_intero() ti faccio notare che input come 4a e 0 risultano validi. Inoltre a cosa serve il parametro v che gli passi?
    - la parte sulla PRECISIONE la toglierei proprio e mi limiterei ad un semplice
    if(m[i][j] != 0)
    - per quanto riguarda l'impostazione logica dell'algoritmo di Gauss mi sono un po' perso, ma penso che il tutto possa essere implementato in modo più semplice.

    Sulla base dei suddetti suggerimenti io farei qualcosa del genere:
    #include <stdio.h>
    
    #define MAX 20
    
    typedef float tMatrice[MAX][MAX];
    
    void stampa_matrice(tMatrice m, unsigned int rig, unsigned int col)
    {
        for(unsigned int i = 0; i < rig; ++i)
        {
            for(unsigned int j = 0; j < col; ++j)
            {
                printf("%.2f\t", m[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    
    void scambia_righe(tMatrice m, unsigned int col, unsigned int i_1, unsigned int i_2)
    {
        for(unsigned int j = 0; j < col; ++j)
        {
            float temp = m[i_1][j];
            m[i_1][j] = m[i_2][j];
            m[i_2][j] = temp;
        }
    }
    
    void eliminazione_gauss(tMatrice m, unsigned int rig, unsigned int col, unsigned int *pivot)
    {
        unsigned int k = 0;
        unsigned int min = col;
        if(rig < col)
        {
            min = rig;
        }
        for(unsigned int j = 0; j < col && k < min; ++j)
        {
            if(!m[k][j])
            {
                for(unsigned int i = k + 1; i < rig; ++i)
                {
                    if(m[i][j])
                    {
                        scambia_righe(m, col, k, i);
                        break;
                    }
                }
            }
            if(m[k][j])
            {
                for(unsigned int i = k + 1; i < rig; ++i)
                {
                    if(m[i][j])
                    {
                        float coeff = m[i][j] / m[k][j];
                        for(unsigned int j_2 = j; j_2 < col; ++j_2)
                        {
                            m[i][j_2] -= coeff * m[k][j_2];
                        }
                    }
                }
                ++k;
            }
        }
        *pivot = k;
    }
    
    int main()
    {
        tMatrice m = {{0, 0, 4, 7},
                      {8, 1, 9, 0},
                      {3, 5, 7, 5}};
        unsigned int rig = 3;
        unsigned int col = 4;
        unsigned int pivot;
        stampa_matrice(m, rig, col);
        eliminazione_gauss(m, rig, col, &pivot);
        stampa_matrice(m, rig, col);
        printf("RANGO = %d\n", pivot);
        return 0;
    }
    Il programma dovrebbe ridurre a scalini qualsiasi tipo di matrice, sia quadrata che rettangolare.

    In ogni caso lo sforzo che hai fatto è sicuramente da apprezzare, d'altronde sbatterci la testa risulta fondamentale per assimilare determinati meccanismi!
    Se hai qualche dubbio chiedi pure.


    P.S.
    Per curiosità, cosa intendi con "matrici a L"?
  • Re: Eliminazione Gauss

    Grazie per i consigli.
    Con le mie attuali conoscenze di C senza usare le variabili globali non avrei saputo come fare. Infatti per quanto ne so io una funzione non può restituire una matrice. Come facevo quindi a far manipolare la matrice M dalle varie funzioni se poi non la restituiscono ?
    Con matrici ad L intendo ad esempio una matrice fatta da soli zeri ad eccezione della prima colonna e dell'ultima riga, o in generale una matrice rettangolare che presenta elementi non nulli solo su due bordi.
  • Re: Eliminazione Gauss

    beowulf ha scritto:


    Con le mie attuali conoscenze di C senza usare le variabili globali non avrei saputo come fare. Infatti per quanto ne so io una funzione non può restituire una matrice. Come facevo quindi a far manipolare la matrice M dalle varie funzioni se poi non la restituiscono ?
    Allora, andiamo per gradi:
    - se una variabile globale ha lo stesso identificatore di una variabile locale, a prevalere è quella locale:
    #include <stdio.h>
    
    int n = 5;
    
    int main()
    {
        int n = 2;
        printf("%d", n);
        return 0;
    }
    e più in generale a prevalere è la variabile che si trova nell'ambito di visibilità più interno:
    #include <stdio.h>
    
    int main()
    {
        int n = 2;
        if(1 == 1)
        {
            int n = 5;
            printf("%d", n);
        }
        return 0;
    }
    - detto questo, si deduce che in un caso del genere
    #include <stdio.h>
    
    int N = 5;
    
    void fun(int N)
    {
        printf("%d", N);
    }
    
    int main()
    {
        int a = 2;
        fun(a);
        return 0;
    }
    venga stampato il valore 2 e non 5.
    E, a scanso di inutili equivoci, sarebbe meglio utilizzare come nome del parametro della funzione un identificatore diverso da quello di altre variabili globali; per esempio, relativamente al precedente codice:
    #include <stdio.h>
    
    int N = 5;
    
    void fun(int var)
    {
        printf("%d", var);
    }
    
    int main()
    {
        int a = 2;
        fun(a);
        return 0;
    }
    - fatte le dovute premesse, passiamo all'argomento "variabili globali". In un codice del genere (equivalente a quello da te postato relativamente all'utilizzo delle variabili globali)
    #include <stdio.h>
    
    int N = 5;
    
    void fun(int var)
    {
        printf("%d", var);
    }
    
    int main()
    {
        fun(N);
        return 0;
    }
    non si stanno sfruttando appieno le potenzialità delle variabili globali, in quanto la loro "utilità" è proprio quella di evitare di doverle passare ad ogni funzione (perché appunto visibili dall'intero programma). Una maniera "corretta" (in contrapposizione al precedente codice) di sfruttare le variabili globali è invece la seguente:
    #include <stdio.h>
    
    int N = 5;
    
    void fun()
    {
        printf("%d", N);
    }
    
    int main()
    {
        fun();
        return 0;
    }
    - da tutto ciò si deduce che nel codice che hai postato non stavi lavorando direttamente sulla variabile globale M. Ed inoltre, volendo seguire il mio consiglio di non utilizzare variabili globali, sarebbe bastato (proprio perché non utilizzate propriamente) spostare la riga di codice
    tMatrice M;
    dall'ambito globale all'inizio del main().

    Riguardo invece alla questione di come modificare una variabile esterna attraverso una funzione ti chiedo: sai cosa sono i puntatori? sai in cosa consiste il passaggio di un parametro ad una funzione?
  • Re: Eliminazione Gauss

    Ok, allora ho messo la dichiarazione di matrice nel main e tolto variabili inutili, oltre la sistemazione delle identazioni.
    Detto questo, per quanto riguarda i puntatori li sto studiando, ho capito che contengono l'indirizzo di una variabile. Dal punto di vista pratico devo esercitarmi, non li so ancora maneggiare.
    Una cosa però che ancora non ho letto e che nessuno mi ha spiegato è forse la più semplice:

    a cosa servono?
    qual'é il vantaggio di usarli?
  • Re: Eliminazione Gauss

    beowulf ha scritto:


    Una cosa però che ancora non ho letto e che nessuno mi ha spiegato è forse la più semplice:

    a cosa servono?
    qual'é il vantaggio di usarli?
    Probabilmente quando avrai finito di studiare l'argomento ti sarà tutto più chiaro.
    In ogni caso se proprio vuoi qualche esempio:
    - consentono di modificare una variabile locale attraverso una funzione;
    - consentono di utilizzare memoria allocata dinamicamente;
    - consentono di creare strutture dati come le liste concatenate;
    - ...

    Senza dimenticare che quando usi gli array stai implicitamente utilizzando dei puntatori.
Devi accedere o registrarti per scrivere nel forum
9 risposte