Metodo di Gauss
Ciao a tutti. Sto realizzando un programma che esegua l'algoritmo di Gauss, per ridurre una matrice a scala. Credo di aver fatto praticamente tutto ma mi resta un solo problema. Vi incollo il programma e poi vi esplicito il mio dubbio.
/* Algoritmo di Gauss */
#include
#include
#include
void Genera(int m, int n, int a[m][n]);
void Stampa(int m, int n, int a[m][n]);
void Scambio(int m, int n, int i, int j, int a[m][n]);
void Gauss(int m, int n, int a[m][n]);
int main(void) {
int r, c;
printf("Inserisci l'ordine della matrice nr:nc: ");
scanf("%d:%d", &r, &c);
int a[r][c]; /* Alloca la matrice */
Genera(r, c, a);
Stampa(r, c, a);
Gauss(r, c, a);
Stampa(r, c, a);
return 0;
}
void Genera(int m, int n, int a[m][n]) {
int i, j, cod;
srand((unsigned) time(NULL));
printf("Generare una matrice casuale 1) - Inserire le entrate 2): ");
scanf("%d", &cod);
if(cod == 1) {
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
a[j] = rand() % 100;
}
}
}
else if(cod == 2) {
printf("Inserisci le entrate: ");
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &a[j]);
}
}
}
}
void Stampa(int m, int n, int a[m][n]) {
int i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
printf("%d ", a[j]);
}
printf("\n");
}
printf("\n \n");
}
void Scambio(int m, int n, int i, int j, int a[m][n]) {
int p, q;
for(p = 0; p < n; p++) {
q = a
/* Algoritmo di Gauss */
#include
#include
#include
void Genera(int m, int n, int a[m][n]);
void Stampa(int m, int n, int a[m][n]);
void Scambio(int m, int n, int i, int j, int a[m][n]);
void Gauss(int m, int n, int a[m][n]);
int main(void) {
int r, c;
printf("Inserisci l'ordine della matrice nr:nc: ");
scanf("%d:%d", &r, &c);
int a[r][c]; /* Alloca la matrice */
Genera(r, c, a);
Stampa(r, c, a);
Gauss(r, c, a);
Stampa(r, c, a);
return 0;
}
void Genera(int m, int n, int a[m][n]) {
int i, j, cod;
srand((unsigned) time(NULL));
printf("Generare una matrice casuale 1) - Inserire le entrate 2): ");
scanf("%d", &cod);
if(cod == 1) {
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
a[j] = rand() % 100;
}
}
}
else if(cod == 2) {
printf("Inserisci le entrate: ");
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &a[j]);
}
}
}
}
void Stampa(int m, int n, int a[m][n]) {
int i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
printf("%d ", a[j]);
}
printf("\n");
}
printf("\n \n");
}
void Scambio(int m, int n, int i, int j, int a[m][n]) {
int p, q;
for(p = 0; p < n; p++) {
q = a
; = a[j] ; = q;
a
a[j]
}
}
void Gauss(int m, int n, int a[m][n]) {
int col, riga, i, j;
double cost;
for(col = 0; col < m-1; col++) {
riga = col;
while(a[riga][col] == 0)
riga++;
if(riga != col)
Scambio(m, n, riga, col, a);
for(i = col+1; i < m; i++) { /* Parto dalla riga (col+1) */
cost = a[col]/a[riga][col];
for(j = col; j < n; j++) { /* Seleziono la colonna */
a[j] = a[j] - cost * a[riga][j];
}
}
}
}
Il problema secondo me si trova nell' ultimo for della funzione Gauss perchè a[j] = a[j] - cost * a[riga][j] non cambia il valore come dovrebbe. In pratica la variabile cost risulta uguale ad un intero e non a un double come dichiarato e quindi non mi annulla per esempio gli elementi della colonna ma a questi sottrae il multiplo piu grande del pivot che sia minore dell'elemento stesso. Per esempio, 55 - (55/10) *10 non fa 0 ma fa 5.
Come dovrei secondo voi risolvere questo dettaglio? Grazie per la pazienza.
Risposte
(Ti verranno un paio d'etti di warning a compilare quel codice...)
Il "dettaglio" di cui parli si risolve con il typecast.
Il "dettaglio" di cui parli si risolve con il typecast.
"Rggb":
Il "dettaglio" di cui parli si risolve con il typecast.
Questo è sbagliato due volte: sia perché non c'è alcun cast da fare che non sia già implicito, sia perché nessun cast risolverebbe il problema.
Il problema è che hai dichiarato una matrice di [inline]int[/inline] quanto invece dovrebbe essere di [inline]double[/inline].
@Albirz: è il caso di riprendere il libro di testo se non sai che il C implementa un sistema di conversione implicita dei tipi di dato numerici, chiamato "promozione". Non mollare il libro finché non hai capito perché 55 - (55/10) *10 = 5 e 55 - (55.0/10) *10 = 55 - (55/10.0) *10 = 0.
... cost risulta uguale ad un intero e non a un double come dichiarato ...
dove sarebbe che il mio suggerimento è "sbagliato due volte"?
Poi, cosa voglia fare il codice non mi interessa: a domanda ho risposto.
@Rggb: il primo messaggio indicava "l'ultimo ciclo [inline]for[/inline]", per cui io stavo guardando la riga
Mi pare invece che tu stessi parlando di
che è più sopra.
Riguardo quest'ultima riga citata, è vero che il risultato della divisione può essere forzato a [inline]double[/inline] con un opportuno cast di tipo; è anche vero che questa modifica non rende corretto il programma, però tu, giustamente, hai risposto correttamente alla domanda posta. Che poi la domanda non centrasse il vero problema del codice, è effettivamente un'altra questione; io l'ho letto in una manciata di secondi [data l'ora tarda] e davo per scontato che anche tu stessi commentando la stessa riga.
In ogni caso, cambiando il tipo della matrice si risolvono tutti i problemi contemporaneamente.
a[i][j] = a[i][j] - cost * a[riga][j];non essendomi accorto che il [inline]for[/inline] era innestato in un altro.
Mi pare invece che tu stessi parlando di
cost = a[i][col]/a[riga][col];
che è più sopra.
Riguardo quest'ultima riga citata, è vero che il risultato della divisione può essere forzato a [inline]double[/inline] con un opportuno cast di tipo; è anche vero che questa modifica non rende corretto il programma, però tu, giustamente, hai risposto correttamente alla domanda posta. Che poi la domanda non centrasse il vero problema del codice, è effettivamente un'altra questione; io l'ho letto in una manciata di secondi [data l'ora tarda] e davo per scontato che anche tu stessi commentando la stessa riga.
In ogni caso, cambiando il tipo della matrice si risolvono tutti i problemi contemporaneamente.
Grazie per l'aiuto. In pratica sto uguagliando un intero a qualcosa che seppur è un double comunque verrebbe troncato alla parte intera.
In ogni caso non ho avuto "etti di warnings", anzi il programma parte anche solo che per alcune mie mancanze non lavorava a dovere.
Grazie ancora, ora ultimo il programma perchè faccia quello che deve.
In ogni caso non ho avuto "etti di warnings", anzi il programma parte anche solo che per alcune mie mancanze non lavorava a dovere.
Grazie ancora, ora ultimo il programma perchè faccia quello che deve.
Scusate un ultimo problema: il programma adesso dovrebbe andare bene, andrebbe perfezionato circa le approssimazioni ma per ora non è questo il problema. Il problema sorge quando nella funzione Gauss viene chiamata la funzione Scambio. Quando ciò avviene, al momento di stampare la matrice ridotta a scala mi ritrovo alcuni numeri e in altre entrate della matrice "nan", creod debba essere il "not a number". Come mai? Ho provato anche a evitare overflow usando long double come elementi della matrice ma nulla. Qual è il motivo?
PS: nella funzione scambio ho già corretto l'errore per cui q era un intero e l'ho dichiarato come long double, come gli altri elementi della matrice.
PS: nella funzione scambio ho già corretto l'errore per cui q era un intero e l'ho dichiarato come long double, come gli altri elementi della matrice.
Non devi resettare [inline]riga[/inline] dopo aver chiamato [inline]Scambio[/inline]?
in che senso?
Il valore dopo il ciclo while è quello che devi usare dopo?
Ma effettuando lo scambio tra la riga "riga" e "col" non dovrei non cmabiare nulla? Forse non intendo bene...
In ogni caso non ho avuto "etti di warnings", anzi il programma parte anche solo che per alcune mie mancanze non lavorava a dovere.
pensa che a me nemmeno compila, ma che editor usi? io codeblocks.
in ogni caso ciò è dovuto ad un uso scorretto degli array statici, la cui dimensione deve essere nota al momento della compilazione.
premesso che per postare codice qui sul forum c'è la funzione "code", esso risulta molto poco chiaro e leggibile a causa della mancata indentazione e dell'utilizzo di variabili con nomi poco significativi.
non conosco il C, ma credo ci sia qualcosa di sbagliato qui:
scanf("%d:%d", &r, &c);mettendo un printf subito dopo, noto che "r" è uguale al valore inserito, mentre c assume un valore casuale.
la funzione "Scambio" non necessita del numero di righe della matrice.
la riduzione di una matrice a scalini viene spesso effettuata per trovare il determinante, ma anche per il semplice calcolo del rango non so se le approssimazioni dovute all'uso dei double (al posto per esempio di un'apposita classe che gestisca i numeri razionali) possano generare un qualche tipo di errore.
inoltre visto che anche le matrici non quadrate possono essere ridotte a scalini, secondo me vale la pena implementare la funzione "Gauss" per il caso generale.
comunque la funzione da te scritta presenta più di un problema dal punto di vista logico. per esempio:
- se la prima colonna è costituita solo da zeri, il ciclo while diventa potenzialmente infinito
- nel momento in cui entra in gioco la funzione "Scambio" l'elemento a[riga][col] sarà zero e quindi nella riga
cost = a[i][col]/a[riga][col];
si effettua una divisione per zero (come detto da Raptorista, se dopo aver scambiato le righe poni "riga = col" questo problema può essere evitato)
"Super Squirrel":
in ogni caso ciò è dovuto ad un uso scorretto degli array statici, la cui dimensione deve essere nota al momento della compilazione.
È vero che questa pratica non è standard, ma molti compilatori [e.g. gcc] la gestiscono correttamente.
"Super Squirrel":
non conosco il C, ma credo ci sia qualcosa di sbagliato qui:
scanf("%d:%d", &r, &c);
mettendo un printf subito dopo, noto che "r" è uguale al valore inserito, mentre c assume un valore casuale.
Questo, invece, mi sembra C corretto, e a me funziona. Devi inserire due valori in [inline]scanf[/inline] seguendo la sintassi suggerita.
"Super Squirrel":
la riduzione di una matrice a scalini viene spesso effettuata per trovare il determinante, ma anche per il semplice calcolo del rango non so se le approssimazioni dovute all'uso dei double (al posto per esempio di un'apposita classe che gestisca i numeri razionali) possano generare un qualche tipo di errore.
A parte casi molto eccezionali, le approssimazioni numeriche non sono di intralcio a questa procedura: una matrice singolare risulterebbe al più con un determinante dell'ordine di grandezza dell'epsilon macchina, un campanello di allarme molto chiaro. Credo che l'utilizzo di questa funzione sia per risolvere sistemi lineari determinati.
L'utilizzo di una libreria apposta per i razionali è abbastanza esotico e di solito non necessario.
"Super Squirrel":
- se la prima colonna è costituita solo da zeri, il ciclo while diventa potenzialmente infinito
Vero, ma generalmente escluso dal fatto che si tenta di risolvere un sistema lineare determinato.
"Super Squirrel":
- nel momento in cui entra in gioco la funzione "Scambio" l'elemento a[riga][col] sarà zero e quindi nella riga
cost = a[i][col]/a[riga][col];
si effettua una divisione per zero (come detto da Raptorista, se dopo aver scambiato le righe poni "riga = col" questo problema può essere evitato)
E questo, finalmente, è quello a cui io speravo Albirz arrivasse da solo. Anche perché avrei potuto dirglielo io, altrimenti.
Vi ringrazio tutti e Raptorista per aver fatto emergere l'errore che non trovavo e anche per aver "difeso" alcune mie scelte nel programma. Adesso il programma pare che faccia quello che deve finalmente! Grazie mille.
Alcuni dei punti sollevati da Super Squirrel rimangono validi. Se il codice ti serve solo per fare questo esercizio, può ignorarli, ma se invece hai intenzione di usarlo estensivamente dovresti occupartene, in particolare del caso in cui la matrice sia inaspettatamente singolare.
Si, me ne sono resto conto. In realtà mi interessa anche estendere il programma. Mi resta un problema principale: il fatto del while infinito credo di averlo risolto così:
while(riga < m && a[riga][col] == 0)
riga++;
if(riga >= m)
continue;
Tuttavia, mi rendo conto che quando una colonna è zero (o tutta la sua "parte" che il programma analizza in cerca del pivot) allora nella colonna a destra va azzerato un elemento in più, quello della riga precedente a quella che il programma inizia a modificare.
while(riga < m && a[riga][col] == 0)
riga++;
if(riga >= m)
continue;
Tuttavia, mi rendo conto che quando una colonna è zero (o tutta la sua "parte" che il programma analizza in cerca del pivot) allora nella colonna a destra va azzerato un elemento in più, quello della riga precedente a quella che il programma inizia a modificare.
Se vuoi estendere il programma inizia con generalizzare la funzione "Gauss" per matrici rettangolari. Poi potresti aggiungere il calcolo del rango e dell'eventuale determinante.
può andare (e comunque la condizione dell'if può essere sostituita con "riga == m").
non credo di aver capito quello che intendi, in ogni caso dopo aver aggiustato un po' la funzione "Gauss" postala che cerco di aiutarti.
while(riga < m && a[riga][col] == 0)
riga++;
if(riga >= m)
continue;
può andare (e comunque la condizione dell'if può essere sostituita con "riga == m").
Tuttavia, mi rendo conto che quando una colonna è zero (o tutta la sua "parte" che il programma analizza in cerca del pivot) allora nella colonna a destra va azzerato un elemento in più, quello della riga precedente a quella che il programma inizia a modificare.
non credo di aver capito quello che intendi, in ogni caso dopo aver aggiustato un po' la funzione "Gauss" postala che cerco di aiutarti.
Come generalizzare per matrici rettangolari? La funzione gauss già accetta matrici di qualsiasi ordine...
Quanto al secondo punto, se ho la matrice, per es.,
0 2 1
0 1 2
0 1 1
diventa 0 2 1
0 1 2
0 0 -1
che non è evidentemente a scala.
Quanto al secondo punto, se ho la matrice, per es.,
0 2 1
0 1 2
0 1 1
diventa 0 2 1
0 1 2
0 0 -1
che non è evidentemente a scala.
Come generalizzare per matrici rettangolari? La funzione gauss già accetta matrici di qualsiasi ordine...
tra le varie cose consideriamo per esempio la seguente riga di codice:
for(col = 0; col < m-1; col++)
1) perchè m - 1 e non m? consideriamo una matrice quadrata 2x2 con prima colonna nulla e seconda no. la seconda colonna non verrà neanche presa in considerazione e alla fine la matrice sarà uguale a quella di partenza che ovviamente non è a scalini.
2) m è il numero di righe, quindi se hai una matrice rettangolare 2x4 con le prime 2 colonne nulle e gli altri elementi diversi da zero, supposto di aver corretto m - 1 con m, le colonne dopo la seconda non verranno neanche prese in considerazione e alla fine la matrice sarà uguale a quella di partenza che ovviamente non è a scalini.
e questo è solo uno dei motivi per cui la funzione non va bene per matrici rettangolari (e in questo caso anche per matrici quadrate).
Quanto al secondo punto, se ho la matrice, per es.,
0 2 1
0 1 2
0 1 1
diventa 0 2 1
0 1 2
0 0 -1
che non è evidentemente a scala.
il motivo è che c'è un errore logico di fondo, non devi porre riga = col, ma riga = pivot (con pivot variabile intera inizializzata a zero che aumenta di 1 ogni volta che viene trovato un pivot).
Probabilmente se avessi seguito il mio consiglio ti saresti accorto da solo di questi vari errori.
Quindi come dovrei risolvere i due problemi?
Devo dichiarare una variabile intera pivot e inizializzarla a 0 e poi in quali punti del ciclo for devo usarla precisamente?
Pongo riga = pivot e ok...ma poi i due for, for(col = 0; col < m-1; col++) e for(i = col+1; i < m; i++) come diventano?
Il primo for deve essere for(col = 0; col < n; col++) e nel caso in pivot raggiungesse il valore massimo, cioè il massimo tra n e m, devo fermarmi?
Credo di aver intuito quello che affermi, ma non riesco in questo momento a formalizzare l'algoritmo...scusami se ti tedio. Grazie
Devo dichiarare una variabile intera pivot e inizializzarla a 0 e poi in quali punti del ciclo for devo usarla precisamente?
Pongo riga = pivot e ok...ma poi i due for, for(col = 0; col < m-1; col++) e for(i = col+1; i < m; i++) come diventano?
Il primo for deve essere for(col = 0; col < n; col++) e nel caso in pivot raggiungesse il valore massimo, cioè il massimo tra n e m, devo fermarmi?
Credo di aver intuito quello che affermi, ma non riesco in questo momento a formalizzare l'algoritmo...scusami se ti tedio. Grazie
Ti mostro le mie modifiche alla funzione:
void Gauss(int m, int n, long double a[m][n]) {
int col, riga, i, j, pivot = 0;
long double cost;
for(col = 0; col < n; col++) {
riga = pivot;
while(riga < m && a[riga][col] == 0)
riga++;
if(riga == m)
continue; /* La colonna è già azzerata quindi ritorna al for esterno ?? */
if(riga != pivot) { /* Il pivot non è il primo a disposizione */
Scambio(m, n, riga, pivot, a);
riga = pivot;
}
for(i = pivot+1; i < m; i++) { /* Parto dalla riga (pivot+1) */
cost = a[col]/a[riga][col];
for(j = col; j < n; j++) { /* Seleziono la colonna */
a[j] = a[j] - cost * a[riga][j];
}
}
pivot++;
if(pivot == max(m,n)) /* con la define max(m,n) m>n?m:n */
return;
}
}
void Gauss(int m, int n, long double a[m][n]) {
int col, riga, i, j, pivot = 0;
long double cost;
for(col = 0; col < n; col++) {
riga = pivot;
while(riga < m && a[riga][col] == 0)
riga++;
if(riga == m)
continue; /* La colonna è già azzerata quindi ritorna al for esterno ?? */
if(riga != pivot) { /* Il pivot non è il primo a disposizione */
Scambio(m, n, riga, pivot, a);
riga = pivot;
}
for(i = pivot+1; i < m; i++) { /* Parto dalla riga (pivot+1) */
cost = a[col]/a[riga][col];
for(j = col; j < n; j++) { /* Seleziono la colonna */
a[j] = a[j] - cost * a[riga][j];
}
}
pivot++;
if(pivot == max(m,n)) /* con la define max(m,n) m>n?m:n */
return;
}
}
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo