Calcolo autovalori

[lewis1]

Salve, avrei bisogno del vostro aiuto per un esercizio (che in realtà è una via di mezzo tra analisi numerica e algebra lineare, ma il mio problema sta più che altro nel secondo ambito...e se ho sbagliato sezione, chiedo venia! )

TESTO:
Data $A in M_n(RR)$ una matrice di elementi $a_{i,j} = epsilon$ con $epsilon in (0, 1/2)$ se $j !=i$, $a_{i,i} = v^{alpha}$ con $v=1024, alpha >=-1/10$ se $i+j$ dispari; altrimenti $a_{i,i}=1$
a) Si discuta l'esistenza della fattorizzazione di Choleski.
b) Si calcolino gli autovalori di A nel caso in cui $alpha=0$

RISOLUZIONE (beh forse è una parola grossa....)
Dunque, per Choleski la matrice deve essere definita positiva: sviluppando i conti in questo caso era una cosa da suicidio (ci ho pure provato), quindi ho cambiato strategia, e cioè: Hermitiana + autovalori maggiori di 0 implicano definita positiva, quindi sviluppo queste due condizioni.
Per la prima condizione, ok (è pure reale la mia matrice!)
Per la seconda, ho pensato di localizzare gli autovalori con i cerchi di Gerschgorin: quindi, ho due casi:
1) righe dispari $C_d={z in CC t.c. |z-1|<=(n-1) * epsilon}$
2) righe pari $C_p={|z- v^{alpha}|<=(n-1)*epsilon}$
(So che ci sarebbero i moduli a dx, ma sono tutte quantità positive)

Per qui non so bene nè se l'idea è corretta, nè come terminare: cioè, la cosa come mi aiuta? Sono tutti parametri variabili!

Poi il punto b)...Boh.
Io avevo pensato di scindere la matrice nel modo seguente, ma non mi è molto utile:
$A= I + E$ dove E è la matrice con tutti $epsilon$ eccetto la diagonale che è nulla.
Gli autovalori sarebbero quindi della forma: $lambda_A= 1+lambda_E$
Ma come calcolo gli autovalori?

Grazie in anticipo a chi riesce a darmi una mano!
Buona serata

[ZeroMemory]

probabilmente ho capito male io...la matrice è

$((bb a, epsilon, epsilon, cdots, epsilon), (epsilon, bb a, epsilon, cdots, epsilon), (epsilon, epsilon, bb a, cdots, epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, cdots, bb a))$

posto $a := v^{alpha}$, giusto? Se è così non capisco come mai distingui le righe pari da quelle dispari per i cerchi di Gerschgorin...gli n cerchi non dovrebbero essere tutti uguali, di centro $a$ e raggio $(n-1) epsilon$? (ci sta che dica cavolate eh, dimmi pure!)

Comunque potremmo fare così: si nota le righe hanno gli stessi termini (n-1 epsilon e un a), allora $(1, 1, 1, ..., 1)$ è autovettore, infatti


$((bb a, epsilon, epsilon, cdots, epsilon), (epsilon, bb a, epsilon, cdots, epsilon), (epsilon, epsilon, bb a, cdots, epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, cdots, bb a))((1), (1), (1), (vdots), (1))= ((bb a + epsilon + epsilon + cdots + epsilon), (epsilon + bb a + epsilon + cdots + epsilon), (epsilon + epsilon + bb a + cdots + epsilon), (vdots), (epsilon + epsilon + epsilon + cdots + bb a))=(((n-1)epsilon + bb a), ((n-1)epsilon + bb a), ((n-1)epsilon + bb a), (vdots), ((n-1)epsilon + bb a))=((n-1)epsilon + a)((1), (1), (1), (vdots), (1))$

perciò $(1, 1, 1, ..., 1)$ è autovettore, di autovalore $(n-1)epsilon + a$. Poiché $A$ è simmetrica, per il teorema spettrale si ha che $(1, 1, 1, ..., 1)^{_|_}$ è $A$-invariante, e lì bisogna cercare gli altri autovettori. Proviamo allora a vedere come si comporta $A$ sui vettori di $(1, 1, 1, ..., 1)^{_|_}$, cioè sui vettori della forma $(x_1, x_2, x_3, ...., x_{n-1}, -x_1 -x_2 -x_3 - ... -x_{n-1})$:

$((bb a, epsilon, epsilon, cdots, epsilon), (epsilon, bb a, epsilon, cdots, epsilon), (epsilon, epsilon, bb a, cdots, epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, cdots, bb a)) (x_1, x_2, x_3, cdots, x_{n-1}, (-x_1 - x_2 - x_3 - ... - x_{n-1}))^T =$

$= ((bb ax_1 + epsilonx_2 + epsilonx_3 + ... + epsilonx_{n-1} + epsilon(-x_1 - x_2 - x_3 - ... -x_{n-1})), (epsilonx_1 + bb ax_2 + epsilonx_3 + ... + epsilonx_{n-1} + epsilon(-x_1 - x_2 - x_3 - ... -x_{n-1})), (epsilonx_1 + epsilonx_2 + bb ax_3 + ... + epsilonx_{n-1} + epsilon(-x_1 - x_2 - x_3 - ... -x_{n-1})), (vdots), (epsilonx_1 + epsilonx_2 + epsilonx_3 + ... + bb ax_{n-1} + epsilon(-x_1 - x_2 - x_3 - ... -x_{n-1})), (epsilonx_1 + epsilonx_2 + epsilonx_3 + ... + epsilonx_{n-1} + bb a(-x_1 - x_2 - x_3 - ... -x_{n-1})))=$

$=((bb ax_1 + epsilonx_2 + epsilonx_3 + ... + epsilonx_{n-1} - epsilonx_1 - epsilonx_2 - epsilonx_3 - ... -epsilonx_{n-1}), (epsilonx_1 + bb ax_2 + epsilonx_3 + ... + epsilonx_{n-1} - epsilonx_1 - epsilonx_2 - epsilonx_3 - ... -epsilonx_{n-1}), (epsilonx_1 + epsilonx_2 + bb ax_3 + ... + epsilonx_{n-1} - epsilonx_1 - epsilonx_2 - epsilonx_3 - ... -epsilonx_{n-1}), (vdots), (epsilonx_1 + epsilonx_2 + epsilonx_3 + ... + bb ax_{n-1} - epsilonx_1 - epsilonx_2 - epsilonx_3 - ... -epsilonx_{n-1}), (epsilonx_1 + epsilonx_2 + epsilonx_3 + ... + epsilonx_{n-1} - bb ax_1 - bb ax_2 - bb ax_3 - ... - bb ax_{n-1}))=$

$= (((a - epsilon)x_1), ((a - epsilon)x_2), ((a - epsilon)x_3), (vdots), ((a - epsilon)x_{n-1}), ((epsilon - a)(x_1 + x_2 + x_3 + ... + x_{n-1})))=(((a - epsilon)x_1), ((a - epsilon)x_2), ((a - epsilon)x_3), (vdots), ((a - epsilon)x_{n-1}), ((a - epsilon)(-x_1 - x_2 - x_3 - ... - x_{n-1}))) =$

$=(a - epsilon)(x_1, x_2, x_3, cdots, x_{n-1}, (-x_1 - x_2 - x_3 - ... - x_{n-1}))^T$

quindi ogni vettore di $(1, 1, ..., 1)^{_|_}$ è autovettore, relativo a $a - epsilon$. Ne segue che gli autovalori sono $(n-1)epsilon + a$ e $a - epsilon$.

Tornando all'esercizio vero e proprio:
la $a$ è $v^{alpha}$, con $v = 1024$ e $alpha >= -1/{10}$, quindi $v^{alpha}$ assume valori in $[1/2, +infty)$ ($alpha |-> v^{alpha}$ è un esponenziale di base maggiore di $1$). Invece $epsilon in (0, 1/2)$. Gli autovalori sono $(n-1)epsilon + 1024^{alpha}$, che è sicuramente positivo, e $epsilon - 1024^{alpha}$, poisitivo se e solo se $alpha > -1/{10}$.

Quindi per il punto a) basta dire $alpha != -1/{10}$. Per il punto b) si ha che gli autovalori sono $(n-1)epsilon + 1$ e $1 - epsilon$.

[lewis1]

Sono un'idiota. Scusa ZeroMemory e mi scuso anche con tutti gli utenti del forum.
C'è un errore nel testo, che ora correggo.

In pratica gli elementi diagonali della matrice sono alternatamente $1$ e $v^{alpha}$.

Mi scuso ancora...

[ZeroMemory]

sennò puoi dire tutto in maniera più semplice in questo modo:

spezzi $A$ come $A=((epsilon, epsilon, epsilon, ..., epsilon), (epsilon, epsilon, epsilon, ..., epsilon), (epsilon, epsilon, epsilon, ..., epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, ..., epsilon)) + (a - epsilon)I$

A questo punto per conoscere gli autovalori di $A$ ti basta conoscere gli autovalori della matrice di tutti epsilon e aggiungere a questi $a - epsilon$. Ma la matrice di tutti epsilon è molto facile da studiare: ha ovviamente rango 1 (tutte le colonne sono uguali, ma non è la matrice nulla perché $epsilon$ non può essere nullo) perciò ha l'autovalore $0$, di molteplicità geometrica $n-1$. Ancora, poiché ha rango 1, i vettori dell'immagine sono per forza autovettori! L'immagine è $Span<(1, 1, ..., 1)>$, da cui:

$((epsilon, epsilon, epsilon, ..., epsilon), (epsilon, epsilon, epsilon, ..., epsilon), (epsilon, epsilon, epsilon, ..., epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, ..., epsilon)) ((1), (1), (1), (vdots), (1)) = (n epsilon) ((1), (1), (1), (vdots), (1))$

e $n epsilon$ è l'altro autovalore. Notare che anche questo procedimento ci dà gli autospazi: anche la matrice di tutti epsilon è simmetrica, poiché $Span<(1, 1, ..., 1)>$ è uno dei due autospazi, l'altro non può che essere $(1, 1, ..., 1)^{_|_}$.

[ZeroMemory]

non preoccuparti, capita!

...ora devo andare, semmai do un'occhiata più tardi!

[ZeroMemory]

ok, ora penso veramente di esserci, riscrivo tutto in forma concisa, dimmi cosa ne pensi.

Questi due lemmi sono fatti molto noti, li enuncia anche la pagina inglese di wikipedia sulle matrici definite positive: http://en.wikipedia.org/wiki/Positive-definite_matrix

Lemma1: Sia $A in M_n(RR)$: esiste la fattorizzazione di Cholesky di $A$ se e solo se $A$ è definita positiva.
Dim: se $A$ è fattorizzabile come $A=LL^T$, dove $L$ è triangolare inferiore con elementi principali positivi, allora $x^TAx=x^TLL^Tx=(L^Tx)^T(L^TX)=_{st}$ (prodotto scalare standard), quindi se $x!=0$ $x^TAx=_{st}>0$ (si noti che $L^T$ è non singolare: i suoi elementi principali sono positivi).

Lemma2: Sia $A in M_n(RR)$ definita positiva: ogni minore principale di testa o di coda di $A$ è a sua volta definito positivo
Dim: è una ovvia conseguenza del criterio di Sylvester.

Th1 (risolve il punto a, considera $a_i = v^{alpha}$ se i è dispari, $a_i = 1$ se i è pari)
consideriamo la matrice

$A=((a_1, epsilon, epsilon, ..., epsilon), (epsilon, a_2, epsilon, ..., epsilon), (epsilon, epsilon, a_3, ..., epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, ..., a_n)) in M_n(RR)$

dove tutti gli elementi non principali sono uguali a $epsilon > 0$. Se gli elementi principali $a_1, ..., a_n > epsilon$ allora $A$ è definita positiva.

Dim: prendiamo la matrice $B$ ottenuta orlando $A$ al seguente modo:

$B=((epsilon, epsilon, ..., epsilon), (epsilon, , , ), (vdots, ,A, ), (epsilon, , , ))=((epsilon, epsilon, epsilon, ...., epsilon), (epsilon, a_1, epsilon, ...., epsilon), (epsilon, epsilon, a_2, ...., epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, ...., a_n))$

proviamo a costruire la fattorizzazione di Cholesky di $B$. Scrivendo

$B=((epsilon, B_{21}^T), (B_{21}, A))=((l, 0), (L_{21}, T))((l, L_{21}^T), (0, T^T)) = ((l^2, lL_{21}^T), (lL_{21},L_{21}L_{21}^T+ TT^T))$

il primo passo si può fare in quanto $epsilon > 0$ e si pone
$l=sqrt(epsilon)$ e $L_{21} = (1/sqrt(epsilon))((epsilon), (epsilon), (vdots), (epsilon))=((1/sqrt(epsilon)), (vdots), (1/sqrt(epsilon)))$

il secondo passo è trovare la fattorizzazione di Cholesky di $A - L_{21}L_{21}^T = A - ((1/sqrt(epsilon)), (vdots), (1/sqrt(epsilon)))(1/sqrt(epsilon), ..., 1/sqrt(epsilon))=A - ((epsilon, epsilon, ..., epsilon), (epsilon, epsilon, ..., epsilon), (vdots, vdots, ddots, vdots), (epsilon, epsilon, ..., epsilon))=((a_1 - epsilon, , , ), ( , a_2 - epsilon, , ), ( , , ddots, ), ( , , , a_n - epsilon))$

ma questa è definita positiva in quanto $a_i>epsilon$. Perciò l'algoritmo che decompone $B$ in forma di Cholesky arriva a termine, quindi $B$ è definita positiva, allora lo è anche $A$ che si realizza come minore principale di coda di ordine n-1 di $B$.

Th2 (risolve il punto b, considera a=1):
la matrice

$A=((a, epsilon, epsilon, ..., epsilon), (epsilon, a, epsilon, ..., epsilon), (epsilon, epsilon, a, ..., epsilon), (vdots, vdots, vdots, ddots, vdots), (epsilon, epsilon, epsilon, ..., a)) in M_n(RR)$ con $epsilon != 0$

$A$ ha esattamente due autovalori,$ (n-1)epsilon + a$ e $a - epsilon$, e i rispettivi autospazi sono $<(1,1,...,1)>$ e $<(1,1,...,1)>^{_|_}$

Dim: valutare $A$ in $(1,1,...,1)$, $(1, 0, ..., 0, -1)$, $(0, 1, ..., 0, -1)$, $(0, 0, 1, ..., 0, -1)$. Sennò puoi spezzare $A$ come $((epsilon, epsilon, ..., epsilon), (epsilon, epsilon, ..., epsilon), (vdots, vdots, ddots, vdots), (epsilon, epsilon, ..., epsilon))+ (a - epsilon)I$ e studiare la prima matrice, come fatto nel post precedente.

...so che la soluzione del punto a è parecchio laboriosa, ma sinceramente non mi vengono in mente soluzioni dirette...

[lewis1]

Ciao,
innanzitutto grazie ancora per le risposte, ti ho fatto scrivere (e lavorare un sacco), e avevo pure sbagliato il testo dell'esercizio in origine!!

Sei stato chiaro ed esaustivo, grazie mille.
In effetti il punto a) mi sembra un po' elaborato (conoscendo il prof ci deve essere un qualche colpo di genio che risolve il tutto in 2 righe . E' che io i colpi di genio non ce li ho mai...)
Io avevo provato anche a sviluppare i conti (per quello avevo usato i cerchi di Gerschgorin, cercavo delle condizioni su epsilon e alpha, solo che non funziona)
Per il secondo punto, effettivamente non era così difficile, ma non c'ero arrivata a scomporre la matrice nel modo furbo che hai suggerito tu: grazie della dritta, sono sicura che mi tornerà utile.

Buona giornata!