Affrontando lo studio dei sistemi lineari ho sempre utilizzato vari metodi per la loro risoluzione, eliminazione sostituzion...rouchè capelli, ma per curiosità in che maniera viene utilizzato il metodo Gauss-Jordan?E' più intuitivo ed efficace di R. Capelli?
e in cosa consiste la "riduzione a scalino" di una matrice?
Grazie
11 messaggi
• Vai alla pagina... • 1, 2
da Valerio Capraro » 19/10/2006, 23:29
è un pò difficile spiegarlo qua...
bisognerebbe avere la pazienza di scrivere mille matrici...
ed io non ce l'ho! perdonami!
comunque, fra tutti i procedimenti è il migliore...
non per nulla Gauss e Jordan sono due grandi matematici,
mentre Cramer, Rouchè e Capelli sono tre sconosciuti
bisognerebbe avere la pazienza di scrivere mille matrici...
ed io non ce l'ho! perdonami!
comunque, fra tutti i procedimenti è il migliore...
non per nulla Gauss e Jordan sono due grandi matematici,
mentre Cramer, Rouchè e Capelli sono tre sconosciuti
- Valerio Capraro
- Advanced Member
- Messaggio: 1593 di 2911
- Iscritto il: 03/02/2004, 23:58
- Località: Southampton (UK)
da lupo grigio » 20/10/2006, 09:07
Il metodo di Gauss Jordan per la soluzione di un sistema di equazioni lineari altro non è che il ‘metodo del liceo’ tradotto in forma matriciale. Dato il sistema…
$A*x=b$ (1)
dove $A$ è una matrice $nxn$ e $b$ è un vettore di $n$ elementi, il problema è determinare il vettore $x$ che soddisfa la (1). L’algoritmo di Gauss-Jordan affronta il problema trasformando il sistema (1) in un sistema equivalente del tipo…
$x_1+alpha_(1,2)x_2+…+alpha_(1,n-1) x_(n-1)+alpha_(1,n)x_n=beta_1$
$...............x_2+…+alpha_(2,n-1) x_(n-1)+alpha_(2,n)x_n=beta_2$
$............................................................................$
$......................................x_(n-1)+alpha_(n-1,n)x_n=beta_(n-1)$
$...........................................................x_n=beta_n$ (2)
Arrivati a questo punto si parte dall’ultima equazione che fornisce $x_n$. Sostituendo $x_n$ nella penultima equazione si trova $x_(n-1)$.Sostituendo quindi $x_n$ e $x_(n-1)$ nella terzultima equazione si trova $x_(n-2)$ e così via fino a che non si sono trovate tutte le componenti di $x$. Per ottenere il sistema (2) dal sistema (1) si procede in questo modo….
- supponendo $a_(1,1)ne 0$ si calcola $alpha_(1,i)= a_(1,i)/a_(1,1)$ per $i=1,2,…,n$ e $beta_1=b_1/a_(1,1)$. Se è $a_(1,1)=0$ si scambia la prima equazione con una qualsiasi delle altre purchè sia $a_(k,1) ne 0$ ottenendo un sistema equivalente all’originale
- per ognuna delle rimanti $n-1$ equazioni, supponendo sia $a_(k,1) ne 0$, si calcola $alpha_(k,i)= a_(k,i)/a_(k,1)-alpha(k,1)$ e $beta_k= b_k/a_(k,1)-beta_1$ per $k=2,3,…,n$ e $i=1,2,…,n$. Se è $a_(k,1)=0$ l’equazione k-esima resta inalterata
Al termine di questa prima fase si è ottenuto un sistema equivalente in cui è $alpha_(1,1)=1$ e $alpha_(k,1)=0$ per $k=2,3,…,n$. La fase successiva consisterà nell’operare sulla matrice di dimensione $n-1xn-1$ in modo identico a quanto fatto per la matrice originale $nxn$. Alla fine si ottiene un sistema del tipo (2) [detto ‘triangolare] equivalente a quello originale…
Il metodo di Gauss-Jordan è quello maggiormente impiegato soprattutto per la sua semplicità. Unico inconveniente è che non si può applicare ad un sistema in cui la matrice $A$ è ‘singolare’, ossia il cui determinante è nullo, oppure ad un sistema ‘mal condizionato’, nel quale il determinante della matrice $A$ è ‘quasi nullo’. Qualche volta [purtroppo] capita di procedere ‘ciecamente’ alla soluzione di un sistema mal condizionato senza una verifica preliminare del determinante e in quel caso la ‘soluzione’ che si ottiene rischia di essere una ‘farloccata’…
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
$A*x=b$ (1)
dove $A$ è una matrice $nxn$ e $b$ è un vettore di $n$ elementi, il problema è determinare il vettore $x$ che soddisfa la (1). L’algoritmo di Gauss-Jordan affronta il problema trasformando il sistema (1) in un sistema equivalente del tipo…
$x_1+alpha_(1,2)x_2+…+alpha_(1,n-1) x_(n-1)+alpha_(1,n)x_n=beta_1$
$...............x_2+…+alpha_(2,n-1) x_(n-1)+alpha_(2,n)x_n=beta_2$
$............................................................................$
$......................................x_(n-1)+alpha_(n-1,n)x_n=beta_(n-1)$
$...........................................................x_n=beta_n$ (2)
Arrivati a questo punto si parte dall’ultima equazione che fornisce $x_n$. Sostituendo $x_n$ nella penultima equazione si trova $x_(n-1)$.Sostituendo quindi $x_n$ e $x_(n-1)$ nella terzultima equazione si trova $x_(n-2)$ e così via fino a che non si sono trovate tutte le componenti di $x$. Per ottenere il sistema (2) dal sistema (1) si procede in questo modo….
- supponendo $a_(1,1)ne 0$ si calcola $alpha_(1,i)= a_(1,i)/a_(1,1)$ per $i=1,2,…,n$ e $beta_1=b_1/a_(1,1)$. Se è $a_(1,1)=0$ si scambia la prima equazione con una qualsiasi delle altre purchè sia $a_(k,1) ne 0$ ottenendo un sistema equivalente all’originale
- per ognuna delle rimanti $n-1$ equazioni, supponendo sia $a_(k,1) ne 0$, si calcola $alpha_(k,i)= a_(k,i)/a_(k,1)-alpha(k,1)$ e $beta_k= b_k/a_(k,1)-beta_1$ per $k=2,3,…,n$ e $i=1,2,…,n$. Se è $a_(k,1)=0$ l’equazione k-esima resta inalterata
Al termine di questa prima fase si è ottenuto un sistema equivalente in cui è $alpha_(1,1)=1$ e $alpha_(k,1)=0$ per $k=2,3,…,n$. La fase successiva consisterà nell’operare sulla matrice di dimensione $n-1xn-1$ in modo identico a quanto fatto per la matrice originale $nxn$. Alla fine si ottiene un sistema del tipo (2) [detto ‘triangolare] equivalente a quello originale…
Il metodo di Gauss-Jordan è quello maggiormente impiegato soprattutto per la sua semplicità. Unico inconveniente è che non si può applicare ad un sistema in cui la matrice $A$ è ‘singolare’, ossia il cui determinante è nullo, oppure ad un sistema ‘mal condizionato’, nel quale il determinante della matrice $A$ è ‘quasi nullo’. Qualche volta [purtroppo] capita di procedere ‘ciecamente’ alla soluzione di un sistema mal condizionato senza una verifica preliminare del determinante e in quel caso la ‘soluzione’ che si ottiene rischia di essere una ‘farloccata’…
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
Ultima modifica di lupo grigio il 22/10/2006, 20:05, modificato 2 volte in totale.
- lupo grigio
da Valerio Capraro » 20/10/2006, 14:01
forse vale la pena aggiungere che i problemi di condizionamento escono fuori
quando si usa l'algoritmo su un programma di computer... ed in tal caso spesso
si vanno ad usare algoritmi più sofisticati.
quando si usa l'algoritmo su un programma di computer... ed in tal caso spesso
si vanno ad usare algoritmi più sofisticati.
- Valerio Capraro
- Advanced Member
- Messaggio: 1594 di 2911
- Iscritto il: 03/02/2004, 23:58
- Località: Southampton (UK)
da lupo grigio » 20/10/2006, 14:55
Per dare l'idea di che cosa sia un 'sistema mal condizionato' consideriamo due esempi semplici esempi...
1)
$x_1-x_2=1$
$x_1-1.00001x_2=0$
soluzione: $x_1= 100001$, $x_2= 100000$
2)
$x_1-x_2=1$
$x_1-.99999x_2=0$
soluzione: $x_1=-99999$, $x_2=-100000$
Qui due sistemi 'quasi identici' danno suluzioni enormemente differenti. Il problema nasce dal fatto che in entrambi i casi il determinante di $A$ è dell'ordine di $10^(-5)$ a fronte di coefficienti dell'ordine dell'unità. Il criterio da me sempre usato nell'affrontare un sistema lineare, quale che sia il metodo usato [nel mio caso sia il metodo di Gauss Jordan sia il metodo della matrice inversa...] è stato quello del calcolo preventivo del determinante di $A$. Indicando con $a_m$ il valor medio quadratico dei termini di $A$, ogni volta che mi risultava $|det*A|< 10^(-3) * a_m$ ho preferito considerare il problema 'mal condizionato' e cercare una soluzione differente...
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
1)
$x_1-x_2=1$
$x_1-1.00001x_2=0$
soluzione: $x_1= 100001$, $x_2= 100000$
2)
$x_1-x_2=1$
$x_1-.99999x_2=0$
soluzione: $x_1=-99999$, $x_2=-100000$
Qui due sistemi 'quasi identici' danno suluzioni enormemente differenti. Il problema nasce dal fatto che in entrambi i casi il determinante di $A$ è dell'ordine di $10^(-5)$ a fronte di coefficienti dell'ordine dell'unità. Il criterio da me sempre usato nell'affrontare un sistema lineare, quale che sia il metodo usato [nel mio caso sia il metodo di Gauss Jordan sia il metodo della matrice inversa...] è stato quello del calcolo preventivo del determinante di $A$. Indicando con $a_m$ il valor medio quadratico dei termini di $A$, ogni volta che mi risultava $|det*A|< 10^(-3) * a_m$ ho preferito considerare il problema 'mal condizionato' e cercare una soluzione differente...
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
Ultima modifica di lupo grigio il 20/10/2006, 15:20, modificato 1 volta in totale.
- lupo grigio
da GIOVANNI IL CHIMICO » 20/10/2006, 15:04
Ciao Lupo Grigio,, quello che dici è corretto ed il tuo esempio si trova anche sui testi di analisis numerica più famosi, ma come fai a calcolare il determinante di una matrice sparsa 100*100?
- GIOVANNI IL CHIMICO
- Senior Member
- Messaggio: 1155 di 1931
- Iscritto il: 31/05/2004, 15:44
- Località: Italy
da lupo grigio » 20/10/2006, 15:48
Dunque... Diciamo prima di tutto che da trent'anni sono disponibili 'linguaggi' per PC che contengono specifiche istruzioni per il calcolo matriciale per cui il deterrminante di $A$ diviene semplicemente 'DET A' e la inversa di $A$ è indicata come 'INV(A)'...
Se non si dispone di questi linguaggi e si deve calcolare il determinante di $A$ il metodo di Gauss Jordan prima descritto si presta egregiamente allo scopo. Innanzittuto osservamo che ad ogni iterazione del metodo in questione si è divisa una riga della matrice $A$ per un cofficiente chimato pivot per cui ad ogni iterazione anche il determinante è stato diviso per il pivot. Dal momento che il detrminante della matrice finale è $1$, il determinante inziale è dato dal prodotto di tutti i pivot... niente di drammatico dunque poichè memorizzando i pivot ad ogni iterazione alla fine delle iterazioni si ha anche il determinante ... semplice no?...
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
Se non si dispone di questi linguaggi e si deve calcolare il determinante di $A$ il metodo di Gauss Jordan prima descritto si presta egregiamente allo scopo. Innanzittuto osservamo che ad ogni iterazione del metodo in questione si è divisa una riga della matrice $A$ per un cofficiente chimato pivot per cui ad ogni iterazione anche il determinante è stato diviso per il pivot. Dal momento che il detrminante della matrice finale è $1$, il determinante inziale è dato dal prodotto di tutti i pivot... niente di drammatico dunque poichè memorizzando i pivot ad ogni iterazione alla fine delle iterazioni si ha anche il determinante ... semplice no?...
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
- lupo grigio
da ELWOOD » 20/10/2006, 16:39
splendida la tua spiegazione lupo grigio.....ma se non chiedo troppo vi andrebbe di farmi una interpretazione pratica tanto per riuscire ad assimilare meglio il concetto ad esempio con questo sistema lineare
${(2x +y +5z +w = 5),(x +y -3z -4w = -1),(3x +6y -2z +w = 8),(2x +2y +2z -3w = 2):}$
Grazie ancora
${(2x +y +5z +w = 5),(x +y -3z -4w = -1),(3x +6y -2z +w = 8),(2x +2y +2z -3w = 2):}$
Grazie ancora
\( \displaystyle e^{\pi \cdot i}+1=0 \)
- ELWOOD
- Cannot live without
- Messaggio: 43 di 4028
- Iscritto il: 25/07/2006, 10:32
- Località: Trento
da lupo grigio » 23/10/2006, 13:14
Chiedo scusa se rispondo solo ora ma il fine settimana e la giornata di oggi sono state assai ‘cariche’. Allora è dato il sistema…
${(2x +y +5z +w = 5),(x +y -3z -4w = -1),(3x +6y -2z +w = 8),(2x +2y +2z -3w = 2):}$
La soluzione con il metodo di Gauss-Jordan e quanto mai ‘meccanica’. Essendo i termini della prima colonna $a_(i,1) ne 0$ per i=1,2,3,4, possiamo divedere tutte e quattro le righe per il rispettivo la prima riga per il rispettivo coefficiente ottenendo…
${(x +1/2y +5/2z +1/2w = 5/2),(x +y -3z -4w = -1),(x +2y –2/3z +1/3w = 8/3),(x +y +z –3/2w = 1):}$
Ora mantengo la prima riga e aggiungo la prima riga alle altre tre cambiate di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x-1/2y +11/2z +9/2w = 7/2),(0x –3/2y +25/6z +1/6w = -1/6),(0x –1/2y +3/2z +2w = 3/2):}$
Dal momento che tutti i coefficienti della $y$ nella seconda , terza e quarta riga sono $ne0$, divido seconda, terza e quarta riga per il rispettivo coefficiente…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x +y -25/9z -1/9w = 1/9),(0x +y -3z -4w = -3):}$
A questo punto lascio inalterate le prime due righe e sommo la seconda riga alla terza e quarta cambiate di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +74/9z -80/9w = -64/9),(0x +0y -8z -5w = 4):}$
Dal momento che i coefficienti della z della terza e quarta riga sono $ne0$ divido terza e uarta riga per il rispettivo coefficiente e ottengo…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +z -40/37w = -32/37),(0x +0y +z +5/8w = -1/2):}$
A questo punto sommo alla la terza riga alla quarta cambiata di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +z -40/37w = -32/37),(0x +0y +0 z –505/296w = -27/64):}$
A questo punto il sistema è ridotto in forma ‘triangolare’ e la soluzione dovrebbe essere abbastanza agevole. Dal momento che nel calcolo manuale sono da tempo una vera frana, mi auguro che sia stato compreso il procedimento e suggerirei di verificare il risultato…
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
${(2x +y +5z +w = 5),(x +y -3z -4w = -1),(3x +6y -2z +w = 8),(2x +2y +2z -3w = 2):}$
La soluzione con il metodo di Gauss-Jordan e quanto mai ‘meccanica’. Essendo i termini della prima colonna $a_(i,1) ne 0$ per i=1,2,3,4, possiamo divedere tutte e quattro le righe per il rispettivo la prima riga per il rispettivo coefficiente ottenendo…
${(x +1/2y +5/2z +1/2w = 5/2),(x +y -3z -4w = -1),(x +2y –2/3z +1/3w = 8/3),(x +y +z –3/2w = 1):}$
Ora mantengo la prima riga e aggiungo la prima riga alle altre tre cambiate di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x-1/2y +11/2z +9/2w = 7/2),(0x –3/2y +25/6z +1/6w = -1/6),(0x –1/2y +3/2z +2w = 3/2):}$
Dal momento che tutti i coefficienti della $y$ nella seconda , terza e quarta riga sono $ne0$, divido seconda, terza e quarta riga per il rispettivo coefficiente…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x +y -25/9z -1/9w = 1/9),(0x +y -3z -4w = -3):}$
A questo punto lascio inalterate le prime due righe e sommo la seconda riga alla terza e quarta cambiate di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +74/9z -80/9w = -64/9),(0x +0y -8z -5w = 4):}$
Dal momento che i coefficienti della z della terza e quarta riga sono $ne0$ divido terza e uarta riga per il rispettivo coefficiente e ottengo…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +z -40/37w = -32/37),(0x +0y +z +5/8w = -1/2):}$
A questo punto sommo alla la terza riga alla quarta cambiata di segno…
${(x +1/2y +5/2z +1/2w = 5/2),(0x+y -11z -9w = -7),(0x + 0y +z -40/37w = -32/37),(0x +0y +0 z –505/296w = -27/64):}$
A questo punto il sistema è ridotto in forma ‘triangolare’ e la soluzione dovrebbe essere abbastanza agevole. Dal momento che nel calcolo manuale sono da tempo una vera frana, mi auguro che sia stato compreso il procedimento e suggerirei di verificare il risultato…
cordiali saluti
lupo grigio
An old wolf may lose his teeth, but never his nature
Ultima modifica di lupo grigio il 28/10/2006, 19:01, modificato 1 volta in totale.
- lupo grigio
11 messaggi
• Vai alla pagina... • 1, 2
Torna a Geometria e algebra lineare
Chi c’è in linea
Visitano il forum: Nessuno e 1 ospite