Fattorizzazione LU - dubbio
Salve!
stò studiando questo algoritmo (LU-Decomposition) per la risoluzione di sistemi lineari $Ax=b$ , con A $nxn$ matrice non singolare (invertibile).
Ad un certo punto mi ritrovo con questa definizione :
Se A non è singolare, allora anche il complemento di Schur non è singolare, QUINDI posso trovare una decomposizione LU.
Quello che non capisco è appunto questo : perchè essendo Schur non singolare, posso procedere? Schur lo calcolo in maniera ricorsiva, non capisco cosa centri il fatto che deve essere invertibile. Qualcuno può illuminarmi?
Saluti
stò studiando questo algoritmo (LU-Decomposition) per la risoluzione di sistemi lineari $Ax=b$ , con A $nxn$ matrice non singolare (invertibile).
Ad un certo punto mi ritrovo con questa definizione :
Se A non è singolare, allora anche il complemento di Schur non è singolare, QUINDI posso trovare una decomposizione LU.
Quello che non capisco è appunto questo : perchè essendo Schur non singolare, posso procedere? Schur lo calcolo in maniera ricorsiva, non capisco cosa centri il fatto che deve essere invertibile. Qualcuno può illuminarmi?
Saluti
Risposte
Ma infatti quella proposizione mi pare falsa a meno che tu non ammetta la possibilità di permutare le colonne di $A$. Infatti ci sono matrici non singolari che non ammettono fattorizzazione $LU$. $((0, 1), (1, 0))$ dovrebbe essere un esempio valido.
Mah no, restando a parlare sempre di LU (LUP lo affronta dopo).
Grosso modo dice :
- Ogni matrice A non singolare ammette fattorizzazione;
- Poichè il complemento di Schur non è singolare, adesso possiamo trovare ricorsivamente una fattorizzazione LU;
P.S. l'esempio che hai postato con LU ovviamente non funziona, devo applicare il pivoting (quindi LUP). Ma quel esempio non funziona solo per quel motivo. Il Cormen invece dice che se non è singolare non posso trovare la fattorizzazione, ed è questo che mi lascia perplesso
Non credo che il Cormen sbagli Non riesco a collegare le due cose!!
Forse riguarda il ricavarsi LU (che non ho ancora capito come faccia questi passaggi) :
$((1,0),(v/(a11),In-1))*((a11,w^T),(0,L'U'))=((1,0),(v/(a11),L'))*((a11,w^T),(0,U'))=LU$
Grosso modo dice :
- Ogni matrice A non singolare ammette fattorizzazione;
- Poichè il complemento di Schur non è singolare, adesso possiamo trovare ricorsivamente una fattorizzazione LU;
P.S. l'esempio che hai postato con LU ovviamente non funziona, devo applicare il pivoting (quindi LUP). Ma quel esempio non funziona solo per quel motivo. Il Cormen invece dice che se non è singolare non posso trovare la fattorizzazione, ed è questo che mi lascia perplesso
Non credo che il Cormen sbagli
Non riesco a collegare le due cose!!Forse riguarda il ricavarsi LU (che non ho ancora capito come faccia questi passaggi) :
$((1,0),(v/(a11),In-1))*((a11,w^T),(0,L'U'))=((1,0),(v/(a11),L'))*((a11,w^T),(0,U'))=LU$
Mannaggia purtroppo non mi ricordo più bene come funziona questo argomento. E' spiegato proprio bene (IMHO) sul Bini-Capovani-Menchi Metodi numerici per l'algebra lineare, comunque. Una risorsa on-line invece è Gallier: la Proposizione 3.15 di pagina 78 dice che una matrice $A$ ammette fattorizzazione $LU$ se e solo se tutti i minori principali di testa sono non nulli, il che mi pare contraddire quanto affermato dal tuo libro di testo. Ma, non lo so, spero di non stare creando confusione.
per la fattorizzazione LUP la matrice deve essere simmetrica e definita positiva, per la questione che nel complemento di Schur (se non è definita positiva) e l'applicazione dell'algoritmo possono esserci divisioni per 0.
"Una matrice definita positiva è non singolare." per questo deve essere invertibile la matrice per applicare LUP.
qua chiesi qualcosa di simile.
https://www.matematicamente.it/forum/mat ... 63132.html
spero di non aver detto castronerie
"Una matrice definita positiva è non singolare." per questo deve essere invertibile la matrice per applicare LUP.
qua chiesi qualcosa di simile.
https://www.matematicamente.it/forum/mat ... 63132.html
spero di non aver detto castronerie
"ham_burst":Non mi pare proprio. Anzi, la fattorizzazione LUP esiste sempre quando $A$ è non singolare e questo corrisponde grossomodo al fatto che è sempre possibile, permutando le righe, portare a termine l'algoritmo di eliminazione di Gauss. Riferimento: Gallier, capitolo 1, teorema 3.18, pag.81.
per la fattorizzazione LUP la matrice deve essere simmetrica e definita positiva
@dissonance: forse hai frainteso ciò che ho detto, devi leggere l'intera frase, ma forse l'ho scritto male.
Intendo dire, non che per applicare la Fattorizzazione LUP la matrice DEVE essere simmetrica e definita positiva.
La fattorizzazione LUP banale deve avere matrici non singolari, ed applica l'eliminazione di Gauss.
Applicando l'algoritmo banale, però c'è il rischio di dividere per 0 o per numeri troppo piccoli (problema noto di riporto dell'errore nei calcolatori), per evatarlo si applica quello che dici te, il pivoting.
Ma se una matrice è simmetrica e definita positiva come proprietà intrinseche hanno che sono invertibili, e si può applicare l'algoritmo di fattorizzazione LUP banale, senza il pivoting, evitando anche la divisione per 0.
Se la matrice ha queste proprietà si abbassa il costo computazionale dell'algoritmo LUP.
Intendo dire, non che per applicare la Fattorizzazione LUP la matrice DEVE essere simmetrica e definita positiva.
La fattorizzazione LUP banale deve avere matrici non singolari, ed applica l'eliminazione di Gauss.
Applicando l'algoritmo banale, però c'è il rischio di dividere per 0 o per numeri troppo piccoli (problema noto di riporto dell'errore nei calcolatori), per evatarlo si applica quello che dici te, il pivoting.
Ma se una matrice è simmetrica e definita positiva come proprietà intrinseche hanno che sono invertibili, e si può applicare l'algoritmo di fattorizzazione LUP banale, senza il pivoting, evitando anche la divisione per 0.
Se la matrice ha queste proprietà si abbassa il costo computazionale dell'algoritmo LUP.
"ham_burst":
Ma se una matrice è simmetrica e definita positiva come proprietà intrinseche hanno che sono invertibili, e si può applicare l'algoritmo di fattorizzazione LUP banale, senza il pivoting, evitando anche la divisione per 0.
Se la matrice ha queste proprietà si abbassa il costo computazionale dell'algoritmo LUP.
Esatto, questo è chiaramente scritto anche sul Cormen
Fatto è che ancora non ho capito perchè deve essere invertibile (non singolare), altrimenti Schur non funziona...
Inoltre non vedo il motivo per cui, se è simmetrica e positiva, non potrei inciampare su uno zero nella diagonale, così che quando eseguo LU mi troverei a dividere per 0 e fallire l'operazione di decomposizione! Ma questo vabbè... è un altro argomento
Sul cormen c'è addirittura un capitolo apposta, lo leggerò più avanti, in caso aprirò un altro topic
No sbagli,
se è invertibile la matrice ANCHE la sottomatrice applicata con il complemento di Shur è invertibile. Essendo shur ricorsivo, come pensi che possa essere applicato se le sue proprietà cambiano a seconda della sottomatrice?
La matrice deve essere invertibile, per il semplice fatto che se una matrice è invertibile ha come conseguenza che ha rango massimo e perciò le colonne linearmente indipendenti.
per il secondo fatto della divisione per zero in una matrice definita positiva è una proprietà intrinseca, ti consiglio di rivederti la definizione.
se è invertibile la matrice ANCHE la sottomatrice applicata con il complemento di Shur è invertibile. Essendo shur ricorsivo, come pensi che possa essere applicato se le sue proprietà cambiano a seconda della sottomatrice?
La matrice deve essere invertibile, per il semplice fatto che se una matrice è invertibile ha come conseguenza che ha rango massimo e perciò le colonne linearmente indipendenti.
per il secondo fatto della divisione per zero in una matrice definita positiva è una proprietà intrinseca, ti consiglio di rivederti la definizione.
Quindi deve essere invertibile (non singolare) solo per il fatto che così (comprese le sue sottomatrici, quindi anche Schur) avrà tutte le colonne linearmente indipendenti (già, fin quì ho solo riscritto quello che hai detto).
Ma e se qualche colonna fosse linearmente dipendente perchè dovrebbe fallire? Per le soluzioni che (non)troverebbe?
Ma e se qualche colonna fosse linearmente dipendente perchè dovrebbe fallire? Per le soluzioni che (non)troverebbe?
Bhe la deconposizione LU, serve per calcolare le soluzioni si un sistema di equazioni nxn e trovare l'inversa di una matrice, se una matrice non fosse invertibile (e di conseguenza non avesse rango massimo) che senso avrebbe applicare la decomposizione LU??
per sistemi di equazioni mxn ci sono altri algoritmi.
mmm se la matrice avesse righe o colonne linearmente dipendenti e si desse in pasto all'algoritmo, sarebbe da vedere come è stato scritto o come si comporta, a naso prima o poi incontrerebbe una divisione per 0 (e non ci sono pivoting che tengano) e ti faccio immaginare a te cosa comporta
per sistemi di equazioni mxn ci sono altri algoritmi.
mmm se la matrice avesse righe o colonne linearmente dipendenti e si desse in pasto all'algoritmo, sarebbe da vedere come è stato scritto o come si comporta, a naso prima o poi incontrerebbe una divisione per 0 (e non ci sono pivoting che tengano) e ti faccio immaginare a te cosa comporta
"ham_burst":
Bhe la deconposizione LU, serve per calcolare le soluzioni si un sistema di equazioni nxn e trovare l'inversa di una matrice, se una matrice non fosse invertibile (e di conseguenza non avesse rango massimo) che senso avrebbe applicare la decomposizione LU??
E' questo che non capisco
Se non fosse invertibile, alcune colonne sarebbero linearmente dipendenti, ok! E allora? heheh N.B. LU-Decomposition calcola L e U, non il vettore soluzione di Ax=b (per quello ci pensa LU-Solve)...
cambi algoritmo 
la decomposizione LU deve avere matrici non singolari.
la decomposizione LU deve avere matrici non singolari.
Pensa all'eliminazione di Gauss. Quando la applichi ad una matrice singolare, per esempio una matrice di rango $n-1$, alla fine ti ritrovi con una riga nulla. E allora l'algoritmo di eliminazione si blocca: prova con $((1, 1), (1, 1))$. In realtà si potrebbe anche ottenere una fattorizzazione LU di matrici singolari, ma direi si debba ammettere che sulla diagonale di U compaiano degli zeri... o qualcosa del genere.
Nelle applicazioni comunque le matrici non sono MAI singolari. Non solo, ma anzi esiste tutta una teoria per scansare le matrici mal condizionate, che sono in un certo senso "vicine" alle matrici singolari, e di cui le matrici singolari sono il prototipo. Quindi non è davvero necessario preoccuparsi di trovare metodi numerici per matrici singolari.
Nelle applicazioni comunque le matrici non sono MAI singolari. Non solo, ma anzi esiste tutta una teoria per scansare le matrici mal condizionate, che sono in un certo senso "vicine" alle matrici singolari, e di cui le matrici singolari sono il prototipo. Quindi non è davvero necessario preoccuparsi di trovare metodi numerici per matrici singolari.
"ham_burst":
cambi algoritmo
la decomposizione LU deve avere matrici non singolari.
Hahah! Il gatto che si morde la coda. Non ci stiamo capendo mi sà
Quello che voglio sapere io non è "cosa fare se la matrice è singolare", ma "perchè LU non funziona se la matrice è singolare".Ho provato a fare l'esempio che ha citato dissonance, ed effettivamente l'algoritmo crasha.
Infatti prendo una matrice singolare (rango 2, le prime due colonne sono linearmente dipendenti):
$((1,2,5),(2,4,9),(3,6,2))$
Dopo il primo passo mi trovo ad avere :
$((1,2,5),(2,0,-1),(3,0,-13))$
Ed effettivamente (anche se fossi con LUP) la decomposizione fallirebbe (pivot sulla seconda colonna tutti a 0). Questo è quello che intendo per "ecco perchè la matrice deve essere invertibile"
Questo ora mi è chiaro. Però vorrei fare un'ultima osservazione. Se la matrice fosse stata la stessa (ma con le colonne scambiate) :
$((1,5,2),(2,9,4), (3,2,6))=((1,5,2),(2,-1,0), (3,-13,0))=((1,5,2),(2,-1,0), (3,13,0))$
allora in questo caso LU falliva perchè effettivamente non esiste la triangolare superiore?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo