Matrice simmetrica e definita positiva
Premessa, lavoriamo in $RR^n$, dove complica le cose, lasciamo perdere $CC^n$
Io so che una matrice è definita positiva se e solo se possiede tutti gli autovalori non nulli, (quindi, tra l'altro, è anche invertibile).
So che le matrici simmetriche sono definite positive.
So che le matrici simmetriche hanno autovalori tutti reali.
Ma ne abbiamo sempre $n$ distinti?
E soprattutto, se ho autovalori tutti reali e positivi, allora la matrice è sicuramente definita positiva,
ma è anche sicuramente simmetrica?
Io so che una matrice è definita positiva se e solo se possiede tutti gli autovalori non nulli, (quindi, tra l'altro, è anche invertibile).
So che le matrici simmetriche sono definite positive.
So che le matrici simmetriche hanno autovalori tutti reali.
Ma ne abbiamo sempre $n$ distinti?
E soprattutto, se ho autovalori tutti reali e positivi, allora la matrice è sicuramente definita positiva,
ma è anche sicuramente simmetrica?
Risposte
Una matrice è definita positiva se tutti gli autovalori di M sono numeri reali positivi e non non nulli.
Sinceramente non credo, ma non ne sono sicuro, che tutte le matrici simmetriche siano definite positive. Infatti $((-1,0),(0,0))$ è senz'altro simmetrica ma i suoi autovalori sono $-1,0$ quindi in base alla definizione di prima essa non è definita positiva.
Sinceramente non credo, ma non ne sono sicuro, che tutte le matrici simmetriche siano definite positive. Infatti $((-1,0),(0,0))$ è senz'altro simmetrica ma i suoi autovalori sono $-1,0$ quindi in base alla definizione di prima essa non è definita positiva.
Ma certo mistake che esistono matrici simmetriche e non definite positive. La tua ne è un esempio valido. Inoltre per venire alla domanda di markowitz
Assolutamente no. Fatti da solo un esempio usando questo teoremino:
Teorema Sia $A$ una matrice quadrata $n \times n$. Se $A$ è triangolare, per esempio triangolare superiore
$A=[[a_{1, 1} , **, \ldots, **], [0, a_{2, 2}, \ldots, **], [\vdots, , \ddots,], [0,\ldots,0,a_{n, n}]]$
allora i suoi autovalori sono $a_{1, 1} \ldots a_{n,n}$.
E soprattutto, se ho autovalori tutti reali e positivi, allora la matrice è sicuramente definita positiva,
ma è anche sicuramente simmetrica?
Assolutamente no. Fatti da solo un esempio usando questo teoremino:
Teorema Sia $A$ una matrice quadrata $n \times n$. Se $A$ è triangolare, per esempio triangolare superiore
$A=[[a_{1, 1} , **, \ldots, **], [0, a_{2, 2}, \ldots, **], [\vdots, , \ddots,], [0,\ldots,0,a_{n, n}]]$
allora i suoi autovalori sono $a_{1, 1} \ldots a_{n,n}$.
Come non detto hai ragione tu,
non è vero che le matrici simmetriche sono tutte definite positive.
Inoltre nella seconda riga avevo dimenticato la parola positivi
Però confermo che, le simmetriche, possiedono tutti autovalori reali.
Le mie domande rimangono le stesse
non è vero che le matrici simmetriche sono tutte definite positive.
Inoltre nella seconda riga avevo dimenticato la parola positivi
Però confermo che, le simmetriche, possiedono tutti autovalori reali.
Le mie domande rimangono le stesse
"markowitz":
Ma ne abbiamo sempre $n$ distinti?
In generale no. Possono esserci delle radici di molteplicità algebrica maggiore di uno. La cosa importante è che per le matrici simmetriche la molteplicità algebrica è uguale a quella geometrica, in altre parole puoi sempre trovare una base di autovettori.
Vi ringrazio, avevo in realtà il seguente problema:
ho in "mano" una matrice di covarianza o correlazione che sono entrambe per costruzione simmetriche E definite positive.
A causa di vari problemi, anche solo la "battitura" a mano potrebbe capitare che queste due condizioni non siano, entrambe, rispettate
nei dati che ho.
Il fatto e che il programma "gira" ugualmente, e dai risultati, tipicamente, non si deduce l'errore.
Quindi volevo un modo (meccanico e veloce) per controllare, preventivamente, il rispetto delle 2 condizioni.
Per la positività me la cavo con gli autovalori, ma con la simmetria? Gli autovalori offrono informazioni sufficienti?
direi necessarie ma non sufficienti.
Alternative?
ho in "mano" una matrice di covarianza o correlazione che sono entrambe per costruzione simmetriche E definite positive.
A causa di vari problemi, anche solo la "battitura" a mano potrebbe capitare che queste due condizioni non siano, entrambe, rispettate
nei dati che ho.
Il fatto e che il programma "gira" ugualmente, e dai risultati, tipicamente, non si deduce l'errore.
Quindi volevo un modo (meccanico e veloce) per controllare, preventivamente, il rispetto delle 2 condizioni.
Per la positività me la cavo con gli autovalori, ma con la simmetria? Gli autovalori offrono informazioni sufficienti?
direi necessarie ma non sufficienti.
Alternative?
Controllare se una matrice è simmetrica calcolandone gli autovalori significa fare le cose alla rovescia: controllare la simmetria è banalissimo, calcolare gli autovalori è uno dei problemi più complicati di tutta l'algebra lineare.
Si ne sono consapevole ma adesso ti spiego.
In sostanza se il controllo deve farlo una persona, partire dagli autovalori non ha senso, ma quando a lavorare sono i computer non è detto
che il concetto di facile e difficile rimanga lo stesso che per le persone.
Gli applicativi, come Matlab, calcolano gli autovalori di grandi matrici in pochi istanti; in termini di programmazione "costa poco"
imporre un "se" su una condizione che vale per un'autovalore (ad esempio il minore); costa molto di più,
almeno in base alle mie conoscenze, controllare l'uguaglianza tra tutti i termini $a_(i,j)=a_(j,i)$ della matrice
In sostanza se il controllo deve farlo una persona, partire dagli autovalori non ha senso, ma quando a lavorare sono i computer non è detto
che il concetto di facile e difficile rimanga lo stesso che per le persone.
Gli applicativi, come Matlab, calcolano gli autovalori di grandi matrici in pochi istanti; in termini di programmazione "costa poco"
imporre un "se" su una condizione che vale per un'autovalore (ad esempio il minore); costa molto di più,
almeno in base alle mie conoscenze, controllare l'uguaglianza tra tutti i termini $a_(i,j)=a_(j,i)$ della matrice
"markowitz":
Gli applicativi, come Matlab, calcolano gli autovalori di grandi matrici in pochi istanti; in termini di programmazione "costa poco"
Guarda che non è affatto così semplice la questione...
Cosa intendi dire?
Forse ti riferisci ad errori di calcolo/approssimazione?
Comunque ho trovato un metodo non troppo oneroso per
controllare direttamente la simmetria.
Per la positività lavoro con gli autovalori.
Forse ti riferisci ad errori di calcolo/approssimazione?
Comunque ho trovato un metodo non troppo oneroso per
controllare direttamente la simmetria.
Per la positività lavoro con gli autovalori.
Sinceramente non riesco a convincermi di quanto dici. Cosa usi, Matlab? Se si, basta avviare due cicli for, uno annidato nell'altro, e controllare ogni coppia di elementi simmetrici: se sono tutti "uguali" (ovvero se la loro differenza è molto piccola in modulo) allora la matrice è simmetrica, altrimenti no. Mi pare la soluzione più elementare, ma non direi che va male. Infatti ci metterai un tempo trascurabile rispetto a quello necessario a calcolare gli autovalori: come dice Alvin che di queste cose ne capisce, il problema di calcolare numericamente gli autovalori di una matrice non è PER NIENTE così scontato come lo stai mettendo tu, anzi è uno dei più delicati (se non IL più delicato) dell'algebra lineare numerica. Inoltre così facendo ti scansi tutta una serie di problemi collegati al condizionamento: ci sono (ed emergono facilmente nelle applicazioni) matrici particolarmente bislacche (malcondizionate) per le quali le tecniche di calcolo numerico sono di difficile applicazione.
Non so se può tornare utile, però per quanto riguarda il problema delle matrici simmetriche definite positive ho visto a lezione un "criterio" (detto di Sylvester, come quello della legge di inerzia) che forse può aiutare un po' a semplificare la faccenda.
Il criterio afferma che data una matrice (quadrata) simmetrica di ordine $n$, essa è definita positiva se tutti i determinanti delle sottomatrici principali sono strettamente positivi. Per sottomatrice principale intendo una matrice della forma
$A_k = ( ( a_(11) , cdots , a_(1k) ),( vdots , ddots , vdots ),( a_(k1) , cdots , a_(kk) ) )$ con $1<=k<=n$
In pratica il discorso è questo: prendi una matrice e controlli se è simmetrica come dice dissonance. Se è simmetrica, prendi tutte le sotomatrici principali e ne calcoli il determinante: guardi $a_(11)$. E' negativo? Ti fermi: la matrice non è definita positiva. E' positivo: bene, vai avanti. Guardi $A_2 = ( ( a_(11) , a_(12) ),( a_(21) , a_(22)))$: il determinante è positivo o negativo? Positivo: vai avanti con la sottomatrice 3x3, se invece è negativo ti fermi.
Hai capito come funziona? Io non me ne intendo per nulla di tempo di calcolo e efficienza algoritmica, però qui anzichè calcolarti gli autovalori e vedere se sono tutti positivi (come detto, calcolarsi gli autovalori è affare delicato: devi calcolare un solo determinante, è vero, ma poi devi risolvere un'equazione di grado $n$) ti calcoli $n$ determinanti. Ripeto, non so se questo può essere un vantaggio per l'algoritmo, di certo lo è quando devi fare le cose a mano
(sempre che il problema non ti chieda esplicitamente di trovare gli autovalori, allora anche a mano è un'altra storia).
Spero di essere stato chiaro e utile.
Se ci sono dubbi/curiosità sono qui
P.S. Ah, una cosa: non ho (ancora) una dimostrazione del criterio che ho citato.
Il criterio afferma che data una matrice (quadrata) simmetrica di ordine $n$, essa è definita positiva se tutti i determinanti delle sottomatrici principali sono strettamente positivi. Per sottomatrice principale intendo una matrice della forma
$A_k = ( ( a_(11) , cdots , a_(1k) ),( vdots , ddots , vdots ),( a_(k1) , cdots , a_(kk) ) )$ con $1<=k<=n$
In pratica il discorso è questo: prendi una matrice e controlli se è simmetrica come dice dissonance. Se è simmetrica, prendi tutte le sotomatrici principali e ne calcoli il determinante: guardi $a_(11)$. E' negativo? Ti fermi: la matrice non è definita positiva. E' positivo: bene, vai avanti. Guardi $A_2 = ( ( a_(11) , a_(12) ),( a_(21) , a_(22)))$: il determinante è positivo o negativo? Positivo: vai avanti con la sottomatrice 3x3, se invece è negativo ti fermi.
Hai capito come funziona? Io non me ne intendo per nulla di tempo di calcolo e efficienza algoritmica, però qui anzichè calcolarti gli autovalori e vedere se sono tutti positivi (come detto, calcolarsi gli autovalori è affare delicato: devi calcolare un solo determinante, è vero, ma poi devi risolvere un'equazione di grado $n$) ti calcoli $n$ determinanti. Ripeto, non so se questo può essere un vantaggio per l'algoritmo, di certo lo è quando devi fare le cose a mano
(sempre che il problema non ti chieda esplicitamente di trovare gli autovalori, allora anche a mano è un'altra storia).Spero di essere stato chiaro e utile.
Se ci sono dubbi/curiosità sono qui
P.S. Ah, una cosa: non ho (ancora) una dimostrazione del criterio che ho citato.
@Paolo: Purtroppo dal punto di vista computazionale calcolare un determinante è sempre sconsigliabile. Infatti in ultima analisi un determinante è ottenuto facendo $(n+1)!$ moltiplicazioni, un numero immenso se tieni conto che nelle applicazioni è cosa normale avere a che fare con matrici $10^6 \times 10^6$... I tempi di calcolo sono biblici.
Cominciamo col dire sicuramente voi ne sapete più di me, ma il mio era solo un tentativo
di compilare un programmino per un'applicazione finanziaria.
Devo inserire a mano (o copiare) in input una matrice di correlazione/covarianza che deve essere, come noto, simmetrica e definita positiva per costruzione.
Inserendo i dati a "caso" può capitare di sbagliare a digitare ed introdurre matrici non simmetriche e soprattutto non definite positive (ad occhio di questo non te ne accorgi facilmente).
Per la simmetria come dice dissonance si può impostare un doppio clclo for, io ci avevo provato ma
mi dava problemi chiaramente sbagliavo qualcosa ma non so cosa.
Comunque ho risolto usando una funzione che si chiama isequal.
Per la positività non è sempre garantita se e solo se gli autovalori sono tutti positivi?
Poi il procedimento che suggerisce paolo90 non mi è nuovo, da qualche parte l'avevo sentito chiamare, se non erro, controllo sui minori principali di nord ovest (forse era un nome allegorico). Ma anche ragionando a mano non vedo tanto guadagno, i determinanti per $n>2$ sono incasinati.
In termini di programmazione (più che al tempo di calcolo mi riferisco alla lunghezza e difficoltà del codice) fare un if su min(eig(sigma)) mi sembra il top della snellezza
lavorare con cicli for sui determinati non credo possa essere più semplice.
Inoltre con la mia, non molta, esperienza ho visto che sono proprio i cicli for while e compagnia bella quelli che richiedono più tempo.
Per quello che dicevo sulla difficoltà di fare i conti a mano ed a macchina intendevo dire che, in generale, i pc lavorano bene per operazione rutinarie. Tu, programmatore non devi fare nulla se non al più andare a prenderti un caffé ed aspettare gli output. Con le persone non è così principalmente a causa di distrazione, confusione, stanchezza....
Se invece devi "spiegare" una cosa nuova, non troppo difficile, tipicamente con le persone la sbrighi in fretta ed hai finito; viceversa con le macchine tu programmatore devi fare attenzione a scrivere un buon codice, quindi lavorare potenzialmente non poco specie se non sei un buon programmatore.
Se poi il pc sbaglia i conti.....andiamo davvero male.... ma almeno non è colpa tua
Mi perdo qualche pezzo?
di compilare un programmino per un'applicazione finanziaria.
Devo inserire a mano (o copiare) in input una matrice di correlazione/covarianza che deve essere, come noto, simmetrica e definita positiva per costruzione.
Inserendo i dati a "caso" può capitare di sbagliare a digitare ed introdurre matrici non simmetriche e soprattutto non definite positive (ad occhio di questo non te ne accorgi facilmente).
Per la simmetria come dice dissonance si può impostare un doppio clclo for, io ci avevo provato ma
mi dava problemi chiaramente sbagliavo qualcosa ma non so cosa.
Comunque ho risolto usando una funzione che si chiama isequal.
Per la positività non è sempre garantita se e solo se gli autovalori sono tutti positivi?
Poi il procedimento che suggerisce paolo90 non mi è nuovo, da qualche parte l'avevo sentito chiamare, se non erro, controllo sui minori principali di nord ovest (forse era un nome allegorico). Ma anche ragionando a mano non vedo tanto guadagno, i determinanti per $n>2$ sono incasinati.
In termini di programmazione (più che al tempo di calcolo mi riferisco alla lunghezza e difficoltà del codice) fare un if su min(eig(sigma)) mi sembra il top della snellezza
lavorare con cicli for sui determinati non credo possa essere più semplice.
Inoltre con la mia, non molta, esperienza ho visto che sono proprio i cicli for while e compagnia bella quelli che richiedono più tempo.
Per quello che dicevo sulla difficoltà di fare i conti a mano ed a macchina intendevo dire che, in generale, i pc lavorano bene per operazione rutinarie. Tu, programmatore non devi fare nulla se non al più andare a prenderti un caffé ed aspettare gli output. Con le persone non è così principalmente a causa di distrazione, confusione, stanchezza....
Se invece devi "spiegare" una cosa nuova, non troppo difficile, tipicamente con le persone la sbrighi in fretta ed hai finito; viceversa con le macchine tu programmatore devi fare attenzione a scrivere un buon codice, quindi lavorare potenzialmente non poco specie se non sei un buon programmatore.
Se poi il pc sbaglia i conti.....andiamo davvero male.... ma almeno non è colpa tua
Mi perdo qualche pezzo?
No, va bene. Per vedere se la matrice è definita positiva, min(eig(sigma)) è una scelta valida. In realtà ci sono algoritmi molto più veloci, perché eig calcola tutti gli autovalori e a te non servono tutte queste informazioni. Volendo puoi provare a spulciare l'help di Matlab - mi pare che ci siano delle function di libreria fatte apposta che non usano gli autovalori ma la cosiddetta SVD, decomposizione ai valori singolari. Comunque dipende dalle matrici che stai usando: se non sono troppo grosse, e se i tempi che ottieni sono accettabili, lascia pure eig.
Per quanto riguarda la simmetria, con isequal puoi controllarla in una sola riga di codice:
dovrebbe funzionare. Altrimenti prova a chiedere nella sezione di Informatica, se passa apatriarca lui conosce sicuramente qualche soluzione elegantissima.
Per quanto riguarda la simmetria, con isequal puoi controllarla in una sola riga di codice:
isequal(triu(sigma, 1), tril(sigma, -1)')
dovrebbe funzionare. Altrimenti prova a chiedere nella sezione di Informatica, se passa apatriarca lui conosce sicuramente qualche soluzione elegantissima.
A quanto ne so, il metodo più veloce (o uno dei più veloci) per testare se una matrice simmetrica è o meno definita positiva, è usare la fattorizzazione di Choleski: http://en.wikipedia.org/wiki/Cholesky_decomposition
L'algoritmo che procede per colonne (o per righe) termina se e solo se (in aritmetica esatta) la matrice è definita positiva, e ci mette circa [tex]n^3/3[/tex] FLOPs.
L'algoritmo che procede per colonne (o per righe) termina se e solo se (in aritmetica esatta) la matrice è definita positiva, e ci mette circa [tex]n^3/3[/tex] FLOPs.
"markowitz":
In termini di programmazione (più che al tempo di calcolo mi riferisco alla lunghezza e difficoltà del codice) fare un if su min(eig(sigma)) mi sembra il top della snellezza
Inoltre con la mia, non molta, esperienza ho visto che sono proprio i cicli for while e compagnia bella quelli che richiedono più tempo.
Ma perchè secondo te le funzioni di Matlab (o qualunque altra) che calcolano gli autovalori, non usano cicli for e while?
Vi ringrazio per le segnalazioni, per adesso sono a posto.
@alvinlee88
Vado per ipotesi,
non so cosa faccia Matlab, o altri applicativi, per trovare gli autovalori (o altro)
ma ipotizzando che cerchi di risolvere, in qualche modo, l'equazione di grado $n$,
a cui ci si riconduce nella ricerca degli autovalori, sicuramente non usa una forma chiusa
perché non esiste.
Allora sicuro procede in modo iterativo quindi: for,e compagnia bella
Tuttavia non posso farci niente, non conosco (specie non conoscevo prima di parlare con voi)
metodi più efficienti.
Inoltre, anche se siamo enormemente al di la di quello che mi serviva, visto che siamo in tema
mi viene una domanda:
Se un'applicativo ha un modo per fare i conti tramite una funzione che ti propone,
se un programmatore cerca di costruire artigianalmente, sullo stesso applicativo, un programma/funzione che faccia lo stesso identico lavoro (stesse identiche funzionalità)
non dovrebbe trovare sempre una soluzione meno efficiente?
Nel senso
1) la strada migliore, su quel linguaggio, si spera l'abbiano trovata i programmatori che vendono l'applicativo
2) ad esempio so che in Python esistono librerie (mi sembra si chiamino cosi)
che offrono funzioni matematiche.
Ma quelle non sono, a loro volta, scritte in Python ma (se non prendo lucciole per lanterne)
sono compilate in C++
che è decisamente più veloce perché è un linguaggio di più basso livello.
In sostanza più ti avvicini al linguaggio macchina meno decodifiche servono più sei veloce;
quindi scrivere programmi in linguaggio "A" per ricostruire funzioni già presenti in linguaggio "A"
è, magari didatticamente ottimo, ma inefficiente dal punto di vista computazionale.
Spero di non aver detto castronerie
come dicevo non è il mio campo e sto andando oltre
@alvinlee88
Vado per ipotesi,
non so cosa faccia Matlab, o altri applicativi, per trovare gli autovalori (o altro)
ma ipotizzando che cerchi di risolvere, in qualche modo, l'equazione di grado $n$,
a cui ci si riconduce nella ricerca degli autovalori, sicuramente non usa una forma chiusa
perché non esiste.
Allora sicuro procede in modo iterativo quindi: for,e compagnia bella
Tuttavia non posso farci niente, non conosco (specie non conoscevo prima di parlare con voi)
metodi più efficienti.
Inoltre, anche se siamo enormemente al di la di quello che mi serviva, visto che siamo in tema
mi viene una domanda:
Se un'applicativo ha un modo per fare i conti tramite una funzione che ti propone,
se un programmatore cerca di costruire artigianalmente, sullo stesso applicativo, un programma/funzione che faccia lo stesso identico lavoro (stesse identiche funzionalità)
non dovrebbe trovare sempre una soluzione meno efficiente?
Nel senso
1) la strada migliore, su quel linguaggio, si spera l'abbiano trovata i programmatori che vendono l'applicativo
2) ad esempio so che in Python esistono librerie (mi sembra si chiamino cosi)
che offrono funzioni matematiche.
Ma quelle non sono, a loro volta, scritte in Python ma (se non prendo lucciole per lanterne)
sono compilate in C++
che è decisamente più veloce perché è un linguaggio di più basso livello.
In sostanza più ti avvicini al linguaggio macchina meno decodifiche servono più sei veloce;
quindi scrivere programmi in linguaggio "A" per ricostruire funzioni già presenti in linguaggio "A"
è, magari didatticamente ottimo, ma inefficiente dal punto di vista computazionale.
Spero di non aver detto castronerie
come dicevo non è il mio campo e sto andando oltre
"markowitz":In generale per risolvere problemi agli autovalori si cercano fattorizzazioni particolari della matrice che li mettano in luce, come il metodo QR, o metodi iterativi come il metodo delle potenze: in ogni caso stai sicuro che i for ci sono
@alvinlee88
Vado per ipotesi,
non so cosa faccia Matlab, o altri applicativi, per trovare gli autovalori (o altro)
ma ipotizzando che cerchi di risolvere, in qualche modo, l'equazione di grado $n$,
a cui ci si riconduce nella ricerca degli autovalori, sicuramente non usa una forma chiusa
perché non esiste.
Allora sicuro procede in modo iterativo quindi: for,e compagnia bella
"markowitz":
Inoltre, anche se siamo enormemente al di la di quello che mi serviva, visto che siamo in tema
mi viene una domanda:
Se un'applicativo ha un modo per fare i conti tramite una funzione che ti propone,
se un programmatore cerca di costruire artigianalmente, sullo stesso applicativo, un programma/funzione che faccia lo stesso identico lavoro (stesse identiche funzionalità)
non dovrebbe trovare sempre una soluzione meno efficiente?
Beh, le funzioni presenti in applicativi come Matlab sono "le migliori", nel senso che sono implementati algoritmi efficienti, come il QR, e altri, con tutte le accortezze tecniche del caso, in termini di memoria ecc.. (non conosco bene il Matlab, ma è un discorso valido in generale)
Il punto è che hai molte funzioni a disposizione, molti mattoni, e sta a te decidere cosa usare per i tuoi scopi. Ad esempio tornando alla definitezza, in Matlab dovrebbe esserci la funzione chol che calcola la fattorizzazione di Choleski della tua matrice, puoi usare quella come test. Non sapendo però io stesso cosa succeda in chol quando l'input non è definito positivo, personalmente mi farei un programmino facile che applichi l'algoritmo "Cholesky Banachiewicz", che trovi su wiki http://it.wikipedia.org/wiki/Decomposizione_di_Choleski, mettendo una guardia quando estrai le radici quadrate che blocchi l'esecuzione non appena incontra un radicando negativo: in tal caso la matrice (sempre ragionando in aritmetica esatta, si intende) non è definita positiva, se l'algoritmo termina invece lo è. Poi ovviamente se hai matrici di dimensioni modeste puoi usare tutti i cannoni che vuoi, come calcolare gli autovalori, ma così come dice dissonance fai le cose al contrario e non tieni conto di errori vari (invece la fatt. di cholesky è un metodo stabile).
"markowitz":
In sostanza più ti avvicini al linguaggio macchina meno decodifiche servono più sei veloce;
quindi scrivere programmi in linguaggio "A" per ricostruire funzioni già presenti in linguaggio "A"
è, magari didatticamente ottimo, ma inefficiente dal punto di vista computazionale.
Ciao, quello che hai detto è un po' i dubbi che vengono a chi non conosce molti di analisi degli algoritmi.
Lo studio dell'analisi degli algoritmi, è studiare i problemi e creare algoritmi che stanno ad un livello superiore al linguaggio con cui viene scritto.
Praticamente se ad un tal problema (con una certa complessità) esiste un algoritmo che lo risolve con una complessità fissata (varie soluzioni avranno complessità differente),
tu utente che vuole sapere i risultati a tale problema, applicherai l'algoritmo studiato e scritto in pseudo-codice, con una complessità studiata, avendo "tempo" (non computazionale) fissato.
Per il tuo problema:
- se definita positiva: si potrebbe usare la definizione di sottomatrice (come detto sopra), anchessa se si dimostra che è definita positiva, la matrice è definita positiva. Invece di usare il determinante perchè non usare il concetto di Norma euclidea (anche se per il discorso del numero di moltiplicazioni non si risolve).
- simmetrica: qua mi verrebbe in mente di usare la proprietà standard di matrice simmetrica $A=A^T$ e di applicare le proprietà dei grafi orientati e grafo orientato trasposto. Penso che se si riscrive il problema in termini di grafi è possibile risolvere il problema, utilizzando la matrice, come matrice di adiacenza (solo per particolari matrici). Anche se sicuramente ci saranno già metodi molto più efficenti e strutturati in maniera migliore di questo (sempre se corretto).
Bho se ti è utile
"ham_burst":
..Invece di usare il determinante perchè non usare il concetto di Norma euclidea (anche se per il discorso del numero di moltiplicazioni non si risolve)
Potresti essere più preciso?
"ham_burst":
- simmetrica: qua mi verrebbe in mente di usare la proprietà standard di matrice simmetrica $A=A^T$ e di applicare le proprietà dei grafi orientati e grafo orientato trasposto. Penso che se si riscrive il problema in termini di grafi è possibile risolvere il problema, utilizzando la matrice, come matrice di adiacenza (solo per particolari matrici).
Non capisco perchè proprio non vi garba fare la cosa ovvia, ovvero controllare che [tex]a_{ij}=a_{ji}[/tex]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo