Matrici definite positive
blu notte
Grazie
OyoOyo
> Data una matrice, come si puo' riconoscere se e' definita positiva?
> Grazie
fallo fare ad un PC... verifica se esiste la fattorizzazione
di Cholesky.
--
"We know Linux to be great...
it ends infinite loops in 5 seconds only" - Linus Torvalds
Roberto
roberto
"blu notte" <blun...@blunotte.blu> ha scritto nel messaggio
news:BYzE8.65198$5k4.1...@twister2.libero.it...
Enrico Gregorio
Direi di no: come li calcoli gli autovalori di una matrice 100x100?
Il metodo che si usa è quello dei minori principali, cioè i determinanti
delle matrici che si ottengono cancellando le ultime i colonne e
le ultime i righe, per i che va da 0 a n-1 (n è l'ordine della matrice).
Cioè si prendono le sottomatrici quadrate formate da righe e colonne
consecutive e che contengano il coefficiente di posto (1,1).
Una matrice è definita positiva se e solo se tutti i suoi minori
principali sono positivi.
Per esempio, data la matrice
1 -1 1
0 2 1
3 2 4
i suoi minori principali sono 1 (cancello le ultime due righe
e due colonne), 2 (cancello l'ultima riga e l'ultima colonna)
e 1 (determinante della matrice). Quindi la matrice è definita
positiva.
Ciao
Enrico
Alessandro Russo
>
> "Roberto" <rob...@libero.it> scrive:
>
> > Devi calcolare gli autovalori
> >
> > roberto
> >
> > "blu notte" <blun...@blunotte.blu> ha scritto nel messaggio
> > news:BYzE8.65198$5k4.1...@twister2.libero.it...
> > > Data una matrice, come si puo' riconoscere se e' definita positiva?
>
> Direi di no: come li calcoli gli autovalori di una matrice 100x100?
> Il metodo che si usa è quello dei minori principali, cioè i determinanti
> delle matrici che si ottengono cancellando le ultime i colonne e
> le ultime i righe, per i che va da 0 a n-1 (n è l'ordine della matrice).
> Cioè si prendono le sottomatrici quadrate formate da righe e colonne
> consecutive e che contengano il coefficiente di posto (1,1).
>
E mi spieghi come calcoli dei determinanti di matrici 99x99?
Il metodo da te proposto e' corretto, ma del tutto inapplicabile.
La risposta piu' giusta e' quella di OyoOyo: l'algortimo di
decomposizione di Choleski termina se e solo se la matrice simmetrica
di partenza e' definita positiva. Ci vogliono circa n^3/6 operazioni.
Ciao
Ale
Enrico Gregorio
Naturalmente quello che conta è il problema che si deve risolvere, no?
Se hai un esercizio da fare all'esame, con una matrice 4x4, lo fai
con i minori principali. Se hai un problema di calcolo numerico,
lo fai con il calcolatore e il metodo di Cholesky.
Ciao
Enrico
Alessandro Russo
Veramente sei proprio tu che hai parlato di matrici 100x100... Ti ricito:
>>>Direi di no: come li calcoli gli autovalori di una matrice 100x100?
>>>Il metodo che si usa è quello dei minori principali,...
Non parli di matrici 4x4; la mia risposta si riferisce proprio al
tuo esempio 100x100. Ovviamente una 4x4 ad un esamino si fa coi minori.
Ciao
Ale
OyoOyo
> Per esempio, data la matrice
>
> 1 -1 1
> 0 2 1
> 3 2 4
>
> i suoi minori principali sono 1 (cancello le ultime due righe e due
> colonne), 2 (cancello l'ultima riga e l'ultima colonna) e 1
> (determinante della matrice). Quindi la matrice è definita positiva.
l'esempio e' un po' infelice... la matrice non e' nemmeno hermitiana
quindi non ha nemmeno senso chiedersi se e' definita positiva usando
il teorema dei minori principali di testa, poi se non ho fatto male i
conti il determinante dell'intera matrice e' negativo.
> Fight Force <
"Alessandro Russo" <ru...@dragon.ian.pv.cnr.it> ha scritto nel messaggio
news:3CE384CE...@dragon.ian.pv.cnr.it...
> > Naturalmente quello che conta č il problema che si deve risolvere, no?
> > Se hai un esercizio da fare all'esame, con una matrice 4x4, lo fai
> > con i minori principali. Se hai un problema di calcolo numerico,
> > lo fai con il calcolatore e il metodo di Cholesky.
>
> Veramente sei proprio tu che hai parlato di matrici 100x100... Ti ricito:
>
> >>>Direi di no: come li calcoli gli autovalori di una matrice 100x100?
> >>>Il metodo che si usa č quello dei minori principali,...
>
> Non parli di matrici 4x4; la mia risposta si riferisce proprio al
> tuo esempio 100x100. Ovviamente una 4x4 ad un esamino si fa coi minori.
Che ne dite di farlo fare al matlab e si risolve il problema? ;-) Per gli
amanti del fortran poi possiamo usare le librerie del nag o del linpack.
Comunque rilancio. A prescinedere dal numero di operazione, a volte l' uomo
preferisce fare piů operazioni semplici dal puno di vista algoritmico che
meno operazioni ma piů complesse dal punto di vista... (indovina un po'?)
algoritmico . Il metodo di Enrico puň essere usato facilmente anche da un
nessere umano. Non credo che tutti avrebbero la pazienza di usare la
decomposizione di Cholesky nei calcoli a mano.
L' ho detta grosa questa volta ;-) E poi 100x100 non mi sembra una cosa
eccessiva si tratta di fare semplicemente 10000/6 operazioni con il metodo
di Cholesky ;-) Quante ce ne vogliono con il metodo di Enrico? Se qualcuno
lo sa evito di ricavarmelo ;-)
Bye.
Alessandro Russo
> L' ho detta grosa questa volta ;-) E poi 100x100 non mi sembra una cosa
> eccessiva si tratta di fare semplicemente 10000/6 operazioni con il metodo
> di Cholesky ;-) Quante ce ne vogliono con il metodo di Enrico? Se qualcuno
> lo sa evito di ricavarmelo ;-)
>
Veramente le operazioni con choleski sono 100^3/6 = 1000000/6 e non 10000/6 come hai scritto.
Per usare il metodo dei minori bisogna calcolare 100 determinanti, di grandezza crescente
da 1 a 100. Visto che per fare un determinante di ordine n applicando la definizione
bisogna sommare n! addendi fatto ciascuno da n-1 fattori, ci sono n!*(n-1) operazioni.
Quindi sommiamo n!*(n-1) per n che va da 1 a 100 e otteniamo 9.3317*10^159.
I computer piu' veloci non arrivano a un migliaio di teraflops, ovvero 10^15 operazioni
per secondo. Se ne avessimo uno a disposizione, ci metteremmo circa 2.9*10^137 anni.
Lo stesso calcolatore con l'algoritmo di Choleski ci metterebbe circa 0.3 miliardesimi
di secondo.
Ciao
Ale
Enrico Gregorio
OyoOyo <ciccioc...@kebab.it> wrote:
> On Thu, 16 May 2002 10:21:33 +0200, Enrico Gregorio wrote:
>
> > Per esempio, data la matrice
> >
> > 1 -1 1
> > 0 2 1
> > 3 2 4
> >
> > i suoi minori principali sono 1 (cancello le ultime due righe e due
> > colonne), 2 (cancello l'ultima riga e l'ultima colonna) e 1
> > (determinante della matrice). Quindi la matrice è definita positiva.
>
> l'esempio e' un po' infelice... la matrice non e' nemmeno hermitiana
> quindi non ha nemmeno senso chiedersi se e' definita positiva usando
> il teorema dei minori principali di testa, poi se non ho fatto male i
> conti il determinante dell'intera matrice e' negativo.
La fretta! Ovviamente dovevo farla simmetrica.
Ciao
Enrico
> Fight Force <
> Veramente le operazioni con choleski sono 100^3/6 = 1000000/6 e non
10000/6 come hai scritto.
evidentemente sě.
>
> Per usare il metodo dei minori bisogna calcolare 100 determinanti, di
grandezza crescente
> da 1 a 100. Visto che per fare un determinante di ordine n applicando la
definizione
> bisogna sommare n! addendi fatto ciascuno da n-1 fattori, ci sono n!*(n-1)
operazioni.
>
> Quindi sommiamo n!*(n-1) per n che va da 1 a 100 e otteniamo
9.3317*10^159.
>
> I computer piu' veloci non arrivano a un migliaio di teraflops, ovvero
10^15 operazioni
> per secondo. Se ne avessimo uno a disposizione, ci metteremmo circa
2.9*10^137 anni.
Certo con un calcolatore siě, ma io dicevo a mano ;-)))))))))))))))))))))))
>
> Lo stesso calcolatore con l'algoritmo di Choleski ci metterebbe circa 0.3
miliardesimi
> di secondo.
Ok, grazie delle precisazioni e spiegazioni.Ciao
Killer'
inn...@excite.it
personalmente però spesso uso strutture definibili matriciali che a
patto di condizioni opportune si construisconoe gestiscono nei modi
quasi classici, per le quali i numeri non sono realmente tali nè sono
associabili a strutture algebriche numerizzabili, se non al limite di
necessità o ...riconversioni, per le quali il concetto di positività o
non negatività non ha molto significato come di raggio spettrale o
altro. Quindi è un concetto che si riferisce a matrici prevalentemente
numeriche e per esse vale il teorema di Perron, piuttosto per matrici
pluriindicizzate come poter definire tale concetto di positività? Hans
blu notte
averlo precisato prima), il mio scopo era proprio quello di controllare se
una matrice e' definita positiva per verificare l'applicabilita' del metodo
di Cholesky. Di conseguenza l'unica soluzione applicabile tra quelle
proposte mi pare quella di Enrico Greggio.
Saluti
--
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
" O mordo tua nuora o aro un autodromo "
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
Alessandro Russo
>
> Ringrazio tutti per le risposte. Se puo' interessare (mi scuso per non
> averlo precisato prima), il mio scopo era proprio quello di controllare se
> una matrice e' definita positiva per verificare l'applicabilita' del metodo
> di Cholesky.
Ripeto: a meno che la matrice non sia una matrice da esercizio di algebra lineare
del primo anno, il modo migliore per "controllare se una matrice e'
definita positiva" e' applicare Choleski e vedere se termina!
> Di conseguenza l'unica soluzione applicabile tra quelle
> proposte mi pare quella di Enrico Greggio.
Non era Iacchetti? 8-)
> Saluti
>
Ciao
Ale
blu notte
> blu notte wrote:
> > Di conseguenza l'unica soluzione applicabile tra quelle
> > proposte mi pare quella di Enrico Greggio.
>
> Non era Iacchetti? 8-)
Ooops! Chiedo scusa a Enrico Gregorio. Non so proprio come ho fatto...
ciao
OyoOyo
> il mio scopo era proprio quello di controllare
> se una matrice e' definita positiva per verificare l'applicabilita' del
> metodo di Cholesky.
se non ricordo male...
puoi avviare la fattorizzazione di Cholesky... l'algoritmo deve
valutare delle radici quadrate, non appena l'argomendo di una radice
quadrata diventa negativo concludi che la fattorizzazione non e'
applicabile, quindi la matrice non e' def. pos.
Basterebbe che ci dicessi l'ordine delle matrici con cui devi operare,
per piccole matrici e' evidente che i calcoli si possono fare a
manina santa :-))
Antonello
news:BYzE8.65198$5k4.1...@twister2.libero.it...
> Data una matrice, come si puo' riconoscere se e' definita positiva?
Una matrice č definita positiva se i suoi autovalori sono maggiori di zero.
Tale condizione č facilmente verificabile utilizzando i polinomi di Sturm.
Antonello
Antonello
"Antonello" <ant...@NOSPAM.libero.it> ha scritto nel messaggio
news:ofdF8.74488$US3.1...@twister1.libero.it...
>
> Una matrice è definita positiva se i suoi autovalori sono maggiori di
zero.
> Tale condizione è facilmente verificabile utilizzando i polinomi di Sturm.
Il metodo dei polinomi di Sturm di può applicare solo per matrici hermitiane
tridiagonali.