Fattorizzazione QR e eliminazione Gaussiana
Salve a tutti, come rispondereste alla seguente domanda:
"Per la risoluzione di un sistema lineare è più conveniente applicare la fattorizzazione QR o l'eliminazione Gaussiana?" ?
Grazie in anticipo
"Per la risoluzione di un sistema lineare è più conveniente applicare la fattorizzazione QR o l'eliminazione Gaussiana?" ?
Grazie in anticipo
Risposte
Vado un po' a memoria.
La QR è un metodo che fattorizza, mentre l'eliminazione Gaussiana lo fa implicitamente. I metodi di fattorizzazione hanno generalmente complessità superiore, ma abbassano la complessità della risoluzione di risolvere lo stesso sistema con \(\mathbf{b}\) diversi. Quindi applicare l'uno o l'altro dipende dalla situazione.
I rimanenti commenti li faccio tra fattorizzazione LU, PLU, PLUQ e similari contro la QR che essendo entrambi metodi di fattorizzazione sono più confrontabili.
1) La decomposizione LU ha una complessità inferiore di un termine costante (se non ricordo male intorno a 3).
2) La decomposizione QR, se calcolate usando Householder (il metodo Gram-Schmidt se non mi sbaglio è numericamente instabile), ha un errore generalmente inferiore della fattorizzazione LU e si comporta meglio con i sistemi mal condizionati, specialmente se ti limiti al partial pivoting. D'altra parte si può migliorare un risultato in un paio di passi di un metodo iterativo sulla soluzione del metodo usato. Nel caso di sistemi mal condizionati è penso sempre meglio usare QR.
3) Nel caso in cui si stiano usando metodi paralleli il rapporto tra i due potrebbe essere meno immediato da calcolare.
Quindi in generale direi:
1) Devi calcolare un sistema generico una sola volta -> eliminazione di Gauss con partial pivoting (a meno di sapere che non è necessario)
2) Devi calcolarlo più di una volta -> decomposizione LU con patial pivoting (a meno di sapere che non è necessario)
3) Sai che la matrice è mal condizionata o potrebbe esserlo -> decomposizione QR
In realtà ultimamente ho sentito parlare dell'uso delle Random Butterfly Transformations per eliminare il pivoting.
La QR è un metodo che fattorizza, mentre l'eliminazione Gaussiana lo fa implicitamente. I metodi di fattorizzazione hanno generalmente complessità superiore, ma abbassano la complessità della risoluzione di risolvere lo stesso sistema con \(\mathbf{b}\) diversi. Quindi applicare l'uno o l'altro dipende dalla situazione.
I rimanenti commenti li faccio tra fattorizzazione LU, PLU, PLUQ e similari contro la QR che essendo entrambi metodi di fattorizzazione sono più confrontabili.
1) La decomposizione LU ha una complessità inferiore di un termine costante (se non ricordo male intorno a 3).
2) La decomposizione QR, se calcolate usando Householder (il metodo Gram-Schmidt se non mi sbaglio è numericamente instabile), ha un errore generalmente inferiore della fattorizzazione LU e si comporta meglio con i sistemi mal condizionati, specialmente se ti limiti al partial pivoting. D'altra parte si può migliorare un risultato in un paio di passi di un metodo iterativo sulla soluzione del metodo usato. Nel caso di sistemi mal condizionati è penso sempre meglio usare QR.
3) Nel caso in cui si stiano usando metodi paralleli il rapporto tra i due potrebbe essere meno immediato da calcolare.
Quindi in generale direi:
1) Devi calcolare un sistema generico una sola volta -> eliminazione di Gauss con partial pivoting (a meno di sapere che non è necessario)
2) Devi calcolarlo più di una volta -> decomposizione LU con patial pivoting (a meno di sapere che non è necessario)
3) Sai che la matrice è mal condizionata o potrebbe esserlo -> decomposizione QR
In realtà ultimamente ho sentito parlare dell'uso delle Random Butterfly Transformations per eliminare il pivoting.
Grazie per la risposta
Quindi se devo calcolare un sistema generico una sola volta a livello di costo computazionale conviene la fattorizzazione LU?
Quindi se devo calcolare un sistema generico una sola volta a livello di costo computazionale conviene la fattorizzazione LU?
Direi di usare l'eliminazione gaussiana con pivoting parziale (a meno di avere un sistema con caratteristiche particolari).
Va bene grazie. Cercando su internet ho trovato:
"In questo articolo esaminiamo alcuni aspetti computazionali e implementativi relativi ai metodi di Gauss e di Householder per il calcolo delle fattorizzazioni LU e QR di una matrice A e per la risoluzione di un sistema lineare Ax=b. Analizzeremo il costo computazionale e la stabilità numerica di questi metodi. In particolare, per il metoso di Gauss vedremo che il costo è dell’ordine di (2/3)n^3 operazioni aritmetiche, e, da un’analisi all’indietro dell’errore vedremo che non ci sono garanzie di stabilità numerica del metoso di Gauss. Per questo introdurremo le strategie di massimo pivot che permettono di rendere il metodo di eliminazione Gaussiana numericamente affidabile. Per quanto riguarda il metodo di Householder, un’analisi computazionale ci mostra che il costo computazionale è sensibilmente più alto, cioè dell’ordine di (4/3)n^3 operazioni aritmetiche, e che il metodo non incontra problemi di stabilità numerica anche se applicato senza strategie di massimo pivot."
Quindi posso motivare la mia risposta dicendo che se si osserva il costo computazionale quello dell'eliminazione gaussiana è minore?
"In questo articolo esaminiamo alcuni aspetti computazionali e implementativi relativi ai metodi di Gauss e di Householder per il calcolo delle fattorizzazioni LU e QR di una matrice A e per la risoluzione di un sistema lineare Ax=b. Analizzeremo il costo computazionale e la stabilità numerica di questi metodi. In particolare, per il metoso di Gauss vedremo che il costo è dell’ordine di (2/3)n^3 operazioni aritmetiche, e, da un’analisi all’indietro dell’errore vedremo che non ci sono garanzie di stabilità numerica del metoso di Gauss. Per questo introdurremo le strategie di massimo pivot che permettono di rendere il metodo di eliminazione Gaussiana numericamente affidabile. Per quanto riguarda il metodo di Householder, un’analisi computazionale ci mostra che il costo computazionale è sensibilmente più alto, cioè dell’ordine di (4/3)n^3 operazioni aritmetiche, e che il metodo non incontra problemi di stabilità numerica anche se applicato senza strategie di massimo pivot."
Quindi posso motivare la mia risposta dicendo che se si osserva il costo computazionale quello dell'eliminazione gaussiana è minore?
Devi rispondere esattamente quello che hai scritto tu ora. Insomma, è la stessa cosa che intendevo io ma con i numeri (che io non ricordavo). Tieni conto che il pivoting influisce sul costo computazione e soprattutto sul tempo effettivo di calcolo.
Se non ricordo male il pivoting parziale non è numericamente stabile ma le matrici che danno problemi sono molto poche (online si trova l'articolo in cui si dimostra, insomma in cui si spiega perché nella pratica il pivoting parziale si sia dimostrato stabile anche se in teoria può avere un errore che cresce esponenzialmente rispetto a \(n\)).
Se non ricordo male il pivoting parziale non è numericamente stabile ma le matrici che danno problemi sono molto poche (online si trova l'articolo in cui si dimostra, insomma in cui si spiega perché nella pratica il pivoting parziale si sia dimostrato stabile anche se in teoria può avere un errore che cresce esponenzialmente rispetto a \(n\)).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo