Problema matrici di permutazione e pivoting parziale
Supponiamo di avere una matrice di permutazione che sintetizza la storia degli scambi effettuati dall'algoritmo di Gauss per determinare la fattorizzazione LU di una matrice A. Ovvero $ P*A=L*U $ esiste una tecnica che permette di conoscere il numero totale di scambi che l'algoritmo ha effettuato , avendo come dati $ L $ $U$ , la matrice di partenza $A$ e la matrice di permutazione $P$ ?? Praticamente devo determinare il segno del determinante di $A$ qualora questo sia calcolato sfruttando la proprietà $ Det(A)=Det(L*U)=Det(L)*Det(u) $ , ma poichè $L $ e $U$ sono matrice triangolare il determinante di queste ultime si calcola come il prodotto degli elementi sulla diagonali, mentre il segno se il numero di scambi è dispari è
$ det(L)*det(U)=-det(A) $ se è pari allora $det(L)*det(U)=det(A) $ grazie
$ det(L)*det(U)=-det(A) $ se è pari allora $det(L)*det(U)=det(A) $ grazie
Risposte
Durante l'algoritmo puoi calcolarlo senza problemi. Inoltre esistono metodi di memorizzare la matrice P che contengono questa informazione. Per esempio se scrivi P come prodotto di scambi di righe allora ti basta contare il numero di scambi (e moltiplicarlo per il numero di elementi della riga). Per ragioni computazionali è spesso utile memorizzarla in questo modo.
Riguardo invece al prodotto di matrici in se, non è possibile in quanto puoi ricavare solo se il numero è pari o dispari. Che io sappia non è sempre possibile ricavare dalla matrice P, gli scambi che hanno portato a crearla neanche se conosci bene la loro forma, ma ci dovrei pensare con calma.
Riguardo invece al prodotto di matrici in se, non è possibile in quanto puoi ricavare solo se il numero è pari o dispari. Che io sappia non è sempre possibile ricavare dalla matrice P, gli scambi che hanno portato a crearla neanche se conosci bene la loro forma, ma ci dovrei pensare con calma.
Comunque il determinante di P è il segno che cerchi.
"vict85":
Per esempio se scrivi P come prodotto di scambi di righe allora ti basta contare il numero di scambi (e moltiplicarlo per il numero di elementi della riga).
Ti chiedo scusa ma non ho capito minimamente quello che hai voluto dire !!
"vict85":
Riguardo invece al prodotto di matrici in se, non è possibile in quanto puoi ricavare solo se il numero è pari o dispari. Che io sappia non è sempre possibile ricavare dalla matrice P, gli scambi che hanno portato a crearla neanche se conosci bene la loro forma, ma ci dovrei pensare con calma.
Non capisco a quale parte della mia domanda ti riferisci!
La matrice di permutazione viene prodotta dalla moltiplicazione di tante matrici di determinante \(\displaystyle -1 \) (che scambiano la n-esima riga con la riga del pivoting). Il loro numero fornisce il determinante della matrice \(\displaystyle P \).
Ora se io segno con \(\displaystyle P_{i,j} \) la permutazione che scambia gli indici \(\displaystyle i \) e \(\displaystyle j \) e mantiene fisso gli altri (una permutazione è di fatto una biiezione degli indici della base) allora la nostra \(\displaystyle P \) coincide con il prodotto:
\(\displaystyle P = P_{(n-1), i_{n-1}}\dotsb P_{3, i_3}P_{2, i_2}P_{1, i_1} \)
dove alcune di queste saranno \(\displaystyle P_{ii} = I \) e gli \(\displaystyle i_j \) sono la riga dove c'é l'elemento più grande della colonna.
Quello che intendevo io è che non sono sicuro che da \(\displaystyle P \) si possa ricavare il prodotto (sostanzialmente il prodotto potrebbe non essere unico). Ma forse \(\displaystyle L \) e \(\displaystyle U \) possono aiutare. Computazionalmente comunque non conviene.
Tieni conto che se tu hai il prodotto il segno del determinate è uguale a \(\displaystyle (-1)^{k} \) dove \(\displaystyle k \) è il numero di \(\displaystyle P_{j, i_j} \) diversi dall'identità. Il segno delle permutazione si può comunque calcolare a partire dalla permutazione finita (è il suo determinante)*.
* non se se conosci il gruppo delle permutazioni. Nel caso tu lo conosca dovresti già saper calcolare il segno in vari modi.
Ora se io segno con \(\displaystyle P_{i,j} \) la permutazione che scambia gli indici \(\displaystyle i \) e \(\displaystyle j \) e mantiene fisso gli altri (una permutazione è di fatto una biiezione degli indici della base) allora la nostra \(\displaystyle P \) coincide con il prodotto:
\(\displaystyle P = P_{(n-1), i_{n-1}}\dotsb P_{3, i_3}P_{2, i_2}P_{1, i_1} \)
dove alcune di queste saranno \(\displaystyle P_{ii} = I \) e gli \(\displaystyle i_j \) sono la riga dove c'é l'elemento più grande della colonna.
Quello che intendevo io è che non sono sicuro che da \(\displaystyle P \) si possa ricavare il prodotto (sostanzialmente il prodotto potrebbe non essere unico). Ma forse \(\displaystyle L \) e \(\displaystyle U \) possono aiutare. Computazionalmente comunque non conviene.
Tieni conto che se tu hai il prodotto il segno del determinate è uguale a \(\displaystyle (-1)^{k} \) dove \(\displaystyle k \) è il numero di \(\displaystyle P_{j, i_j} \) diversi dall'identità. Il segno delle permutazione si può comunque calcolare a partire dalla permutazione finita (è il suo determinante)*.
* non se se conosci il gruppo delle permutazioni. Nel caso tu lo conosca dovresti già saper calcolare il segno in vari modi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo