Decomposizione LU
Salve a tutti
Volevo domandarvi se c'era qualche anima pia che avesse la pazienza di spiegarmi i passi operativi per effettuare la decomposizione LU.
Questo perchè io vorrei scrivere un programma che mi permetta rapidamente di risolvere un sistema di equazioni lineari, di calcolare l'inversa di una matrice o per calcolare il determinante di una matrice.
Al momento il mio pià grosso probelma è come genero la matrice L e U (per il determinante non mi serve ancora la matrice P in quanto mi è parso di capire si possa sostituire con + se l'ordine è pari o - se è dispari) , in quanto non ho capito praticamente nulla del sistema usato da gauss (quello con i pivot)
Grazie in anticipo
Volevo domandarvi se c'era qualche anima pia che avesse la pazienza di spiegarmi i passi operativi per effettuare la decomposizione LU.
Questo perchè io vorrei scrivere un programma che mi permetta rapidamente di risolvere un sistema di equazioni lineari, di calcolare l'inversa di una matrice o per calcolare il determinante di una matrice.
Al momento il mio pià grosso probelma è come genero la matrice L e U (per il determinante non mi serve ancora la matrice P in quanto mi è parso di capire si possa sostituire con + se l'ordine è pari o - se è dispari) , in quanto non ho capito praticamente nulla del sistema usato da gauss (quello con i pivot)
Grazie in anticipo
Risposte
E' una cosa un po' scocciante da spiegare al computer perché bisogna scrivere un sacco di apici e pedici... Prova a dare un'occhiata qui:
http://docenti.ing.unipi.it/~d3253/libro/capitoli.html
capitolo "Sistemi di equazioni lineari". Se poi hai ancora problemi ne riparliamo.
http://docenti.ing.unipi.it/~d3253/libro/capitoli.html
capitolo "Sistemi di equazioni lineari". Se poi hai ancora problemi ne riparliamo.
"dissonance":
E' una cosa un po' scocciante da spiegare al computer perché bisogna scrivere un sacco di apici e pedici... Prova a dare un'occhiata qui:
http://docenti.ing.unipi.it/~d3253/libro/capitoli.html
capitolo "Sistemi di equazioni lineari". Se poi hai ancora problemi ne riparliamo.
Riapro questa discussione solo ora , perchè nel frattempo sono stato un pò impegnato e non avevo fatto tempo a studiare e capire la questione.
Il punto è che ho trovato un testo di algebra nella mia biblioteca che spiega molto bene questo argomento con molti esempi e commenti (e mi pare di averlo capito) il punto è che mi pare di aver capito dall'esempio che mi avevi likato tu un metodo leggermente diverso (anche se ammetto che non l'avevo compreso appieno) e sono un pò confuso

Ora provo a spiegare quello che ho capito del metodo che ho letto nel libro e poi a spiegare perchè mi sembrava differente da quello linkato e cosa non mi torna di modo che possiate dirmi dove mi confondo e cosa sbaglio-fraintendo.
Allora io avevo capito che se devo trovare il determinante di una matrice molto voluminosa (es n = 50) in tempi computazionalmente accettabili dovevo applicare questo metodo chiamato fattorizzazione LU che provvedeva attraverso determinati algoritmi a produrre 3 matrici :
Una matrice pivotale (avente determinante pari a 1 o -1 a seconda della parità o meno della matrice di partenza , pertanto posso trascurare la sua reale creazione e considerare solo la parità o meno della matrice di partenza ) una matrice L , triangolare superiore ed una matrice U triangolare inferiore il determinate della matrice di partenza era pari a :
det(pivotale ossia +o- 1) * det(L) * det(U)
essendo L ed U triangolari , basta moltiplicare solo la loro diagonale maggiore per trovare il determinante ed il calcolo è banale anche per n molto grandi.
Leggendo sul mio libro invece trovo scritto che :
se ho una matrice che per esempio è
1 5 3 4 0 0 = - 4 0 3 2 per calcolarne il determinate devo : assicurarmi che l'elemento i esimo sulla diagonale maggiore sia diverso da 0 se non lo è devo controllare se tra gli elementi che in colonna seguono quell'elemento ce ne è uno diverso da zero ( se ci fossero posso scambiare le righe altrimenti so già che il deterinante è 0 ) ; ogni volta che scambio una righa moltiplico una variabile che chiamerò pivotale per -1 , inizialmente tale costante vale 1. Una volta che l'elemento i esimo della diagonale è diverso da zero guardo che combinazioni lineari tra quella riga e quelle successive posso effettuare al fine di rendere nulli i valori sottostanti all'elemento i esimo della diagonale (sottostanti ed appartenenti a quella colonna). Alla fine otterei una matrice triangolare superiore e calcolando quel determinante e moltiplicandolo per il valore della variabile chiamata pivotale ottengo il determinante della matrice. Nell'esemio in quesione ho che : il primo elemento ossia l' (1,1) della matrice vale 1 != 0 quindi procedo osservo che per annullare i valori sottostanti all' (1,1) ossia (1,2) e (1,3) devo effettuare delle modifiche (ovviamente solo per (1,2) dato che l'altro è già nullo ) , pertanto sottrarrò alla seconda riga una riga avente valori pari a 4 * prima riga - seconda riga ossia ( 4 20 12 ) - ( 4 0 0 ) ottenendo così ( 0 20 12 ) a questo punto aggiorno la matrice che diventa 1 5 3 0 20 12 0 3 2 il secondo elemento ossia l' (2,2) della matrice vale 20 != 0 quindi procedo osservo che ora devo modificare solo l'elemento (3,2) , per farlo faccio l'mcm tra l'elemento (2,2) ed il (3,2) ed ottengo che : nuova riga = {[mcm/(2,2)] * secona riga } - {[mcm/(3,2)] * terza riga } esattamente come prima ed ora ottengo che : nuova riga = ( 0 60 36 ) - ( 0 60 40) = ( 0 0 -4) la nuova matrice è quindi 1 5 3 0 20 12 = pivotale * 1 * 20 * -4 = -80 come vedete i conti non mi tornano anche se l'algoritmo dovrebbe essere giusto 0 0 -4 Ad ogni modo vi posto un esempietto che ho sul libro in questione : inizialmenet 1 3 3 1 3 9 1 0 = 25 -1 0 2 1 3 8 1 1 pivotale = 1 1 3 3 1 0 0 -8 -3 0 3 5 2 0 -1 -8 -2 pivotale = 1 (2,2) = 0 permuto : pivotale = pivotale * -1 => pivotale = -1 1 3 3 1 0 3 5 2 0 0 -8 -3 0 -1 -8 -2 procedo come sorpra 1 3 3 1 0 3 5 2 0 0 -8 -3 0 0 -19/3 -4/3 1 3 3 1 0 3 5 2 = pivotale * 1 * 3 * -8 *25/24 = pivotale * - 25 = -1 * -25 => 25 Corretto 0 0 -8 -3 0 0 0 25/24
Dunque volevo chiedervi se sapevate dirmio che che passaggio sbagliavo in quella matricetta di prova che stavo facendo ma soprattutto come mai questo sistema pare funzionare mentre l'algoritmo LU (che dovrebbe essere questo) prevede 2 matrici triangolari per calcolare il determinante mentre io ne stò utilizzando una sola (e pare funzionare) ?
Grazie in anticipo e sucsate se sono stato così prolisso , ma ci tenevo a snocciolarvi tutti i miei pensieri e ragionamenti (evidentemente sbagliati) anche se temo di avervi annoiato.
Ps Ho usato il tag code per far si che le matrici vengano visualizzate impaginate