Matrice tridiagonale simmetrica definita positiva

[DoraDora1]

Ciao a tutti!

Mi sapete indicare una strada veloce per vedere se una matrice tridiagonale e simmetrica è anche definita positiva??

Grazie mille

[Gi81]

Consideriamo una matrice tridiagonale e simmetrica di ordine $n$ (ne scrivo una con $n=6$):
$A=((a_1,b_2,0,0,0,0),(b_2,a_2,b_3,0,0,0),(0,b_3,a_3,b_4,0,0),(0,0,b_4,a_4,b_5,0),(0,0,0,b_5,a_5,b_6),(0,0,0,0,b_6,a_6))$
Poichè è simmetrica, vale il criterio di Jacobi. (lo scrivo il spoiler)

"Criterio di Jacobi":33tmfi9d:Sia $A in cc(M)_n(RR)$ matrice simmetrica. $AA i ={1,2,3,...,n}$ consideriamo i minori principali $Delta_i$.
La matrice $A$ è definita positiva se e solo se $|Delta_i|>0 AA i $

(data una matrice quadrata $A$ di ordine $n$, si definisce minore principale di $A$ di ordine $i,$ con $i in {1,2,...,n}$, e si indica con $Delta_i$, la sottomatrice di $A$ ottenuta con le prime $i$ righe e le prime $i$ colonne)

Detto ciò, sfruttiamo una proprietà delle matrici tridiagonali:

Consideriamo una generica matrice tridiagonale di ordine $n$ (ne scrivo una con $n=6$):
$A=((a_1,c_1,0,0,0,0),(b_2,a_2,c_2,0,0,0),(0,b_3,a_3,c_3,0,0),(0,0,b_4,a_4,c_4,0),(0,0,0,b_5,a_5,c_5),(0,0,0,0,b_6,a_6))$
Si definiscono ${\(d_0=1),(d_1=a_1),(d_k=a_k*d_(k-1)-b_k*c_(k-1)*d_(k-2) AA k>=2):}$
Vale questa proprietà, facilmente dimostrabile per induzione:

Sia $A in cc(M)_n (RR)$ tridiagonale, si ha che $|Delta_i|=d_i$, $AA i in {1,2,...,n}

Dunque, per verificare "abbastanza" velocemente che la matrice è definita positiva deve valere
$d_i>0$, $AA i in {1,2,...,n}$, con
$d_0=1$
$d_1=a_1$
$d_k=a_k*d_(k-1)-b_k^2*d_(k-2)$ , $AA k>1$

Spero che si capisca. Temendo di fare confusione, ho preferito mettere in spoiler le proprietà sfruttate

[angus89]

La risposta è: dipende

Ci possono esser modi più o meno veloci per farlo.

Ti elenco un po di situazioni

Un primo modo può esser quello di prendere i vettori della base canonica e calcolare
$e_i^t*T*e_i$ dove $T$ è la matrice tridiagonale.

Se la tua matrice è simmetrica puoi usare i teoremi di localizzazione degli autovalori, ad esempio gerschegorin (non so se l'ho scritto bene)
osservando che una matrice è definita positiva se ha autovalori positivi

Poi potresti avere una matrice strutturata, quindi potresti provarlo per induzione.

Insomma...dipende.

Se invece di questa matrice non sai nulla...bè anche qui dipende...i conti li fai tu o deve farli un computer?

[DoraDora1]

Siete stati molto più efficienti di quanto mi sarei mai aspettata! Fantastici! Grazie mille!!!!

I conti li può fare un computer perchè questa cosa mi serve per verificare che alcuni metodi numerici per la soluzione di sistemi lineari (Gradiente Coniugato e rilassamento SOR) siano convergenti sulla mia matrice. Solo che sto parlando di una 1600x1600 e già il programma è pesante quindi sarebbe meglio riuscire a capire qualcosa prima di sparargliela dentro C'è di buono che la matrice me la costruisco io per risolvere un problema alle differenze quindi posso provare a sfruttare l'espressione analitica e vedere cosa succede...
Ancora grazie!!!!

[angus89]

Allora...
ora si che mi è chiaro...
Certo se aggiungi dettagli sul problema aggingi dettagli su come fare il conto, ma mi sembra di capire che il problema alle differenze nasca dal tentativo di risolvere un'equazione differenziale...
Magari se ce la scrivi qualcosa di più possiamo dirla, comunque...

In genere quella matrice che ne esce fuori è strutturata...quindi puoi dimostrare che è definita positiva utilizzando i teoremi di gershegorin (se non li conosci dimmelo che ti posto qualche link, ma ci sono su qualsiasi libro di analisi numerica).
Daltronde, anche se la matrice è definita positiva e vuoi risolvere il problema alle differenze, non scrivere subito il programma sul gradiente coniugato, ad esempio a volte la soluzione generale si scrive a mano facendo un po di passaggi...
Non so se metti il problema esteso di certo ti sapremo dire di più.

Per ora puoi scrivere un pezzo di programma dove fai le somme per righe (ed eventualmente per colonne) per localizzare gli autovalori con gershegorin e verede se tutti gli zeri hanno parte reale positiva (sai daltronde che essendo la matrice simmetrica gli autovalori non hanno parte immaginaria). Se la condizione è rispettata allora puoi lanciare il programma e risolvere il sistema.
Altrimenti devi provare a vedere se la matrice è definita positiva in un altro modo (ammesso che lo sia)...