Calcolo numerico/Casi particolari

Caso 1: matrici hermitiane

Una matrice hermitiana è diagonalizzata attraverso matrici unitarie, cioè $A=Q\lambda Q_h$ con $\lambda$ diagonale e $Q{Q}_h=Q_{h}Q=I$, cioè abbiamo una base ortonormale di autovettori. Allora in questo caso:

${\sigma }_k={𝒚}_k^h{𝒛}_{k+1}={𝒚}_k^{h}A{𝒚}_k=\frac{{𝒚}_k^{h}A{𝒚}_k}{{𝒚}_h^k{𝒚}_k}$

$=\frac{(A^k{𝒚}_0{)}^h\ast (A^{k+1}{𝒚}_0)}{(A^k{𝒚}_0{)}^h(A^k{𝒚}_0)}\text{formula }\mathrm{♡}$

e poniamo

${𝒚}_0=\sum _{j=1}^n{\alpha }_j{𝒚}_j$

e sostituendo questa scrittura nella formula $\mathrm{♡}$ otteniamo:

$=\frac{(A^k\sum _{j=1}^k{\alpha }_j{𝒚}_j{)}^h\ast (A^{k+1}\sum _{j=1}^n{\alpha }_j{𝒚}_j)}{(A^k\sum _{j=1}^n{\alpha }_j{𝒚}_j{)}^h(A^k\sum _{j=1}^n{\alpha }_j{𝒚}_j)}$

e tenendo conto che $A^k{𝒚}_j={\lambda }_j^k{𝒚}_j$ mettendo in evidenza ${\lambda }_1^k$:

${\sigma }_k=\frac{{\lambda }_1|{\lambda }_1^k{|}^2[{\overline{\alpha }}_1{𝒚}_1^h+\sum _{j=2}^n{\overline{\alpha }}_j{\overline{\frac{{\lambda }_j}{{\lambda }_1}}}^k{𝒚}_j^h]\ast [{\alpha }_1{𝒚}_1+\sum _j{\alpha }_j(\frac{{\lambda }_j}{{\lambda }_1}{)}^{k+1}{𝒚}_j]}{|{\lambda }_1^k{|}^2[{\overline{\alpha }}_1{𝒚}_1^h+\sum _j{\overline{\alpha }}_j{\overline{\frac{{\lambda }_j}{{\lambda }_1}}}^k{𝒚}_j^h]\ast [{\alpha }_1{𝒚}_1+\sum _{j=2}^n{\alpha }_j(\frac{{\lambda }_j}{{\lambda }_1}{)}^k{𝒚}_j]}$

Si può semplificare $(|{\lambda }_1{|}^k{)}^2$, inoltre, siccome gli autovettori costituiscono una base ortogonale, i prodotti misti del tipo ${𝒚}_i{𝒚}_j,i\ne j$ si annullano, e rimane solo:

${\sigma }_k=\frac{{\lambda }_1[|{\alpha }_1{|}^2{𝒚}_1^h{𝒚}_1+\sum _{j=2}^n|{\alpha }_j{|}^2(\frac{{\lambda }_j}{{\lambda }_1}{)}^{2k}\frac{{\lambda }_j}{{\lambda }_1}{𝒚}_j^h{𝒚}_j]}{{\lambda }_1\ast ({\alpha }_1^2{𝒚}_1^h{𝒚}_1+\sum _{j=2}^n|{\alpha }_j{|}^2(\frac{{\lambda }_j}{{\lambda }_1}{)}^{2k}{𝒚}_j^h{𝒚}_j)}$

per l'ortonormalità ${𝒚}_j^h{𝒚}_j=1$, allora

${\sigma }_k={\lambda }_1\frac{{\alpha }_1^2(1+\sum _{j=2}^n\frac{|{\alpha }_j{|}^2}{|{\alpha }_1{|}^2}\ast |{\lambda }_j/{\lambda }_1{|}^{2k}\ast |{\lambda }_j/{\lambda }_1|)}{|{\alpha }_1^2|\ast (1+\sum _{j=2}^n|\frac{{\alpha }_j^2}{{\alpha }_1^2}|({\lambda }_j/{\lambda }_1{)}^{2k})}$

Al primo ordine, nella sommatoria sopravvive il termine per $j=2$ (secondo autovalore più grande), quindi

$\sigma =\frac{{\lambda }_1[1+|{\alpha }_2/{\alpha }_1{|}^2|{\lambda }_2/{\lambda }_1{|}^{2k}|{\lambda }_2/{\lambda }_1|]}{[1+|{\alpha }_2/{\alpha }_1{|}^2|{\lambda }_2/{\lambda }_1{|}^{2k}]}$

$=\frac{{\lambda }_1(1+\epsilon )}{1+\overline{\epsilon }}$

$={\lambda }_1\ast (1+\epsilon )(1-\overline{\epsilon })$

${\sigma }_k={\lambda }_1[1+|{\alpha }_2/{\alpha }_1{|}^2({\lambda }_2/{\lambda }_1{)}^{2k}({\lambda }_2/{\lambda }_1)]\ast [(1-|{\alpha }_2/{\alpha }_1{|}^2|{\lambda }_2/{\lambda }_1{|}^{2k}]$

$={\lambda }_1\ast (1-|{\alpha }_1/{\alpha }_2{|}^2|{\lambda }_2/{\lambda }_1{|}^{2k})$

Allora ${\sigma }_k$ nel caso di matrici hermitiane:

${\sigma }_k={\lambda }_1(1+O(|{\lambda }_2/{\lambda }_1{|}^{2k}))$

A differenza del caso generale compare l'esponente $2k$ e la convergenza è più veloce.

Il metodo della potenza non converge su una matrice hermitiana quando la matrice ha autovalori $\alpha ,-\alpha$ di moduli massimo. Escludiamo anche il caso di autovalori complessi

Caso 2: matrici hermitiane definite positive

Consideriamo $A=Q\lambda Q_h$ con $Q$ unitaria e $\lambda \in {ℝ}^{+}$. Il caso $\alpha ,-\alpha$ non può verificarsi, quindi su una matrice hermitiana definita positiva il metodo delle potenze converge sempre.

Risparmio del costo computazionale: cerchiamo ${\lambda }_{min}(A)$ con il metodo delle potenze inverse. Ad ogni iterazione si risolve il sistema lineare

$A{𝒛}_{k+1}={𝒚}_k$

con costo di fattorizzazione $o(n^3)$. La fattorizzazione viene fatta una sola volta. Ad ogni iterazione, risolvo i sistemi triangolari. Se $R$ è triangolare superiore piena il costo è $o(n^2)$. Se invece $R$ è a banda, il costo è $o(n)$. Lo stesso vale se $R$ è sparsa.

Siccome le iterazioni fatte sono numerose, si cerca di ridurre il costo di ogni iterazione a scapito del costo iniziale.

Trasformo la matrice $A$ in una matrice tridiagonale $B$. A questo punto il costo della fattorizzazione di Cholesky è $o(n)$, perché $R$ è bidiagonale, e anche il costo delle singole operazioni si riduce.

Passo da $A$ generica a $B$ tridiagonale tramite trasformazioni di Hausolder:

$A_{k+1}=T_k^{-1}{A}_k{T}_k,k=1,\dots ,n-2$

La matrice di sinistra azzera la sottocolonna e quella di destra azzera la sottoriga di $A$ in modo da ottenere una matrice tridiagonale. Questa operazione costa $o(n^3)$.

Condizionamento

Consideriamo il caso in cui la fattorizzazione di Cholesky non può avvenire (cioè ${\lambda }_{min}$ molto piccolo e $A$ definita positiva). Invece che considerare $A$, consideriamo $\hat{A}=A+cI$, che è ancora hermitiana e definita positiva. Si usa la tecnica di shift. Gli autovalori di $\hat{A}$ sono gli autovalori di $A$ shiftati di $c$. $K_2(A)=\frac{{\lambda }_{max}}{{\lambda }_{mi}}$ ed è grande, invece si ha

$K_2(A+c)=\frac{{\lambda }_{max}(A+c)}{{\lambda }_{min}(A+c)}=o(1)$

${\sigma }_k(\hat{A})$ converge all'autovalore minimo di $\hat{A}$, invece

${\sigma }_k(A)={\sigma }_k(\hat{A})-c$

e si ha come rischio l'errore di cancellazione. Bisogna bilanciare $c$ rispetto a ${\lambda }_{min}(A)$.

Esercizio 3.1

Nel caso di matrici hermitiane, calcolare la velocità di convergenza nel caso di autovalore multiplo.

Sia ${\lambda }_{max}$ di molteplicità $r$.

$|{\lambda }_1|=|{\lambda }_2|={\lambda }_r|>|{\lambda }_{r+1}|\ge \dots \ge |{\lambda }_n|$

${𝒚}_0=\sum _{i=1}^r{\alpha }_{1,i}{𝒙}_{1,i}+\sum _{j=r+1}^n{\alpha }_j{𝒙}_j$

${\sigma }_k={\lambda }_1(1+O(|\frac{{\lambda }_{r+1}}{{\lambda }_1}{|}^{2k})$

si ritrova lo stesso risultato di prima con ${\lambda }_{r+1}$ che sostituisce ${\lambda }_2$, cioè, al posto di ${\lambda }_2$ compare il primo valore diverso da ${\lambda }_1$.