Fattorizzazione LU con pivoting parziale.
Qualcuno mi spiega il motivo per il quale nel fare pivoting io debba cercare il massimo per colonna?
Mi spiego, il pivoting lo introduciamo affinché si possano fattorizzare LU tutte le matrici non singolari, e quindi allargare il campo di applicabilità di questo tipo di fattorizzazione.
Ma, a rigor di logica, per lo scopo per il quale questo viene fatto, non ho necessità di fare scambi con la riga che ha l'elemento massimo sulla colonna, ma bensì mi potrei accontentare di scambiare la riga corrente con una qualsiasi che abbia l'elemento diagonale non nullo, ovvero non fare scambi se già l'elemento diagonale è non nullo. è vero che dal punto di vista della complessità asintotica la ricerca del massimo non peggiora le prestazioni della fattorizzazione, ma comunque introduco un buon numero di operazioni (di ordine quadratico rispetto al rango della matrice) per trovare tutti i pivot.
Qualcuno mi suggerì, ma senza entrare nel dettaglio, che la ricerca del massimo aiuta nel condizionamento del problema, ma da solo non riesco a capirlo (credo c'entri qualcosa sulla norma della matrice PA rispetto alla matrice A di partenza).
Questa è quindi la mia domanda: di preciso, quanto migliora la cosa scegliendo il massimo?
E poi, per estensione: ottengo ulteriori benefici (sempre dal punto di vista del condizionamento, a quanto credo) se anziché pivoting parziale faccio pivoting totale (cioè cercando il massimo non solo per colonna, ma anche per riga)?
Grazie in anticipo!!
Mi spiego, il pivoting lo introduciamo affinché si possano fattorizzare LU tutte le matrici non singolari, e quindi allargare il campo di applicabilità di questo tipo di fattorizzazione.
Ma, a rigor di logica, per lo scopo per il quale questo viene fatto, non ho necessità di fare scambi con la riga che ha l'elemento massimo sulla colonna, ma bensì mi potrei accontentare di scambiare la riga corrente con una qualsiasi che abbia l'elemento diagonale non nullo, ovvero non fare scambi se già l'elemento diagonale è non nullo. è vero che dal punto di vista della complessità asintotica la ricerca del massimo non peggiora le prestazioni della fattorizzazione, ma comunque introduco un buon numero di operazioni (di ordine quadratico rispetto al rango della matrice) per trovare tutti i pivot.
Qualcuno mi suggerì, ma senza entrare nel dettaglio, che la ricerca del massimo aiuta nel condizionamento del problema, ma da solo non riesco a capirlo (credo c'entri qualcosa sulla norma della matrice PA rispetto alla matrice A di partenza).
Questa è quindi la mia domanda: di preciso, quanto migliora la cosa scegliendo il massimo?
E poi, per estensione: ottengo ulteriori benefici (sempre dal punto di vista del condizionamento, a quanto credo) se anziché pivoting parziale faccio pivoting totale (cioè cercando il massimo non solo per colonna, ma anche per riga)?
Grazie in anticipo!!
Risposte
non conosco questa differenziazione tra pivoting parziale e totale.
L'introduzione del pivoting è stato fatto per evitare la divisione per 0 e per numeri troppo piccoli.
Se abbiamo una matrice (facciamo non singolare), c'è questa possibilità di divisione, utilizzando il massimo si evitano queste cause di errore. Se si divide per numeri piccoli, un calcolatore ha problemi di gesitione, e si ha una propagazione di errore.
Se si ha una matrice invertibile e definita positiva (norma > 0) non si hanno questi problemi, la divisione per 0 non esiste.
Scegliere il massimo fa parte dell'algortitmo LUP per matrici non singolari, se non ci fosse questo passaggio (il pivoting) errori di propagazione sono assicurati.
Per la complessità: la fattorizzazione LU ha complessità algoritmica $Theta(n^3)$; la fattorizzazione LUP cioè con il pivoting, la complessità cresce al più di un fattore costante, è sempre $Theta(n^3)$
se hai altri dubbi, chiedi pure
PS: per qualche spunto in più, per chiarirti altri dubbi, vedi questo vecchio post
L'introduzione del pivoting è stato fatto per evitare la divisione per 0 e per numeri troppo piccoli.
Se abbiamo una matrice (facciamo non singolare), c'è questa possibilità di divisione, utilizzando il massimo si evitano queste cause di errore. Se si divide per numeri piccoli, un calcolatore ha problemi di gesitione, e si ha una propagazione di errore.
Se si ha una matrice invertibile e definita positiva (norma > 0) non si hanno questi problemi, la divisione per 0 non esiste.
Scegliere il massimo fa parte dell'algortitmo LUP per matrici non singolari, se non ci fosse questo passaggio (il pivoting) errori di propagazione sono assicurati.
Per la complessità: la fattorizzazione LU ha complessità algoritmica $Theta(n^3)$; la fattorizzazione LUP cioè con il pivoting, la complessità cresce al più di un fattore costante, è sempre $Theta(n^3)$
se hai altri dubbi, chiedi pure
PS: per qualche spunto in più, per chiarirti altri dubbi, vedi questo vecchio post
Come dice ham_burst, quando fai pivoting, per motivi di stabilità della soluzione (contenimento dell'errore), conviene dividere per il massimo pivot, presumo per ridurre gli errori di arrotondamento.
Sul pivotig totale, mi ricordo che il prof. disse che il gioco non valeva la candela, dovendo tenere traccia degli scambi di colonna (cambia l'ordine delle incognite).
Sul pivotig totale, mi ricordo che il prof. disse che il gioco non valeva la candela, dovendo tenere traccia degli scambi di colonna (cambia l'ordine delle incognite).
Ok, quindi la divisione per il massimo per colonna è solo un discorso di problemi di arrotondamento insomma... Mi piacerebbe trovare un esempio per vedere la cosa con gli occhi. Nel senso, una matrice per la quale applicando l'algoritmo LU con pivoting classico (con scambio con il massimo) funziona bene, mentre usando, per dire, lo scambio con il primo non nullo, ottengo degli evidenti errori nella soluzione...
Chiamalo piccolo problema...
questo tipo di errore e sottigliezze hanno fatto danni inimmaginabili nel mondo (es http://it.wikipedia.org/wiki/Ariane_5)
Semplice, prova a farti una matrice con la possibilità di divisione con numeri piccoli, cioè con numeri reali, vicini allo zero.
utilizza la fattorizzazione LU, con $P=I_n$.
L'errore lo vedrai utilizzando un calcolatore...se lo fai a mano è un altro discorso (e sarebbe pure inutile).
La propagazione dell'errore, in campo informatico è un classico errore di programmazione (precisione in virgola mobile), questo tipo di valutazione nello scovare questi errori è sotto il nome di Formal Method.
questo tipo di errore e sottigliezze hanno fatto danni inimmaginabili nel mondo (es http://it.wikipedia.org/wiki/Ariane_5)
Semplice, prova a farti una matrice con la possibilità di divisione con numeri piccoli, cioè con numeri reali, vicini allo zero.
utilizza la fattorizzazione LU, con $P=I_n$.
L'errore lo vedrai utilizzando un calcolatore...se lo fai a mano è un altro discorso (e sarebbe pure inutile).
La propagazione dell'errore, in campo informatico è un classico errore di programmazione (precisione in virgola mobile), questo tipo di valutazione nello scovare questi errori è sotto il nome di Formal Method.
"canemacchina":
Mi piacerebbe trovare un esempio per vedere la cosa con gli occhi.
Un esempio è riportato in questa pagina di wikipedia.
grassssssie! 
Siccome ultimamente mi sto occupando molto di questo argomento (farò domanda al GSOC 2011 su una cosa di questo tipo) aggiungo qualche commento.
Il partial pivoting è molto usato ma non è l'unico metodo di pivoting. Una misura (imprecisa) dell'efficienza nel ridurre gli errori di arrotondamento di una strategia di pivoting è il fattore di crescita [tex]\rho[/tex]. Questa misura consiste nel rapporto tra il massimo elemento della matrice dopo la fattorizzazione e la norma della matrice. Si può dimostrare che nel partial pivoting [tex]\rho \le 2^{n-1}[/tex] e che esiste una matrice per cui [tex]\rho = 2^{n-1}[/tex]. Nella pratica questo non succede mai e il partial pivoting è considerato sufficientemente robusto per quasi ogni uso. Si osservi che la versione scaled ha lo stesso fattore di crescita.
Il rook pivoting e il complete pivoting hanno fattori di crescita non esponenziali ma performance nettamente inferiori (sono anche meno parallelizzabili purtroppo).
Esistono poi alcune vie di mezzo tra il pivoting "normale" a cui facevi riferimento tu e il partial pivoting. Per esempio il threshold partial pivoting (esistono anche il threshold rook pivoting e il threshold complete pivoting) oppure, sopratutto nel caso parallelo, il pairwise pivoting e l'incremental pivoting. Tutti questi metodi di pivoting hanno rapporti prestazioni/robustezza/parallelismo differenti e a seconda di quali sono i tuoi scopi ne usi uno o l'altro.
Vi sono inoltre metodi di pivoting che cercano nella riga o nella diagonale. In ogni caso usare una strategia di pivoting basata sulla dimensione dei valori assoluti serve a cercare di moltiplicare le righe per valori sempre minori di zero così da lavorare con numeri bassi. Ma non sempre è la migliore, soprattutto se si sta lavorando con le matrici sparse o se si vogliono mantenere alcune caratteristiche dalla matrice come l'essere simmetrica, l'essere a bande...
Per le matrici sparse un metodo di pivoting particolare consiste nel cercare quell'elemento della riga con meno elementi non nulli che ha meno elementi non nulli sulla colonna. Il suo scopo è quello di rendere la matrice sparsa ancora più sparsa mentre metodi come il partial o il complete pivoting possono aumentare gli elementi non nulli.
Il partial pivoting è molto usato ma non è l'unico metodo di pivoting. Una misura (imprecisa) dell'efficienza nel ridurre gli errori di arrotondamento di una strategia di pivoting è il fattore di crescita [tex]\rho[/tex]. Questa misura consiste nel rapporto tra il massimo elemento della matrice dopo la fattorizzazione e la norma della matrice. Si può dimostrare che nel partial pivoting [tex]\rho \le 2^{n-1}[/tex] e che esiste una matrice per cui [tex]\rho = 2^{n-1}[/tex]. Nella pratica questo non succede mai e il partial pivoting è considerato sufficientemente robusto per quasi ogni uso. Si osservi che la versione scaled ha lo stesso fattore di crescita.
Il rook pivoting e il complete pivoting hanno fattori di crescita non esponenziali ma performance nettamente inferiori (sono anche meno parallelizzabili purtroppo).
Esistono poi alcune vie di mezzo tra il pivoting "normale" a cui facevi riferimento tu e il partial pivoting. Per esempio il threshold partial pivoting (esistono anche il threshold rook pivoting e il threshold complete pivoting) oppure, sopratutto nel caso parallelo, il pairwise pivoting e l'incremental pivoting. Tutti questi metodi di pivoting hanno rapporti prestazioni/robustezza/parallelismo differenti e a seconda di quali sono i tuoi scopi ne usi uno o l'altro.
Vi sono inoltre metodi di pivoting che cercano nella riga o nella diagonale. In ogni caso usare una strategia di pivoting basata sulla dimensione dei valori assoluti serve a cercare di moltiplicare le righe per valori sempre minori di zero così da lavorare con numeri bassi. Ma non sempre è la migliore, soprattutto se si sta lavorando con le matrici sparse o se si vogliono mantenere alcune caratteristiche dalla matrice come l'essere simmetrica, l'essere a bande...
Per le matrici sparse un metodo di pivoting particolare consiste nel cercare quell'elemento della riga con meno elementi non nulli che ha meno elementi non nulli sulla colonna. Il suo scopo è quello di rendere la matrice sparsa ancora più sparsa mentre metodi come il partial o il complete pivoting possono aumentare gli elementi non nulli.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo