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 $QQ_{h}=Q_{h}Q=I$, cioè abbiamo una base ortonormale di autovettori. Allora in questo caso:

$\sigma _{k}={\boldsymbol {y}}_{k}^{h}{\boldsymbol {z}}_{k+1}={\boldsymbol {y}}_{k}^{h}A{\boldsymbol {y}}_{k}={\frac {{\boldsymbol {y}}_{k}^{h}A{\boldsymbol {y}}_{k}}{{\boldsymbol {y}}_{h}^{k}{\boldsymbol {y}}_{k}}}$

$={\frac {(A^{k}{\boldsymbol {y}}_{0})^{h}*(A^{k+1}{\boldsymbol {y}}_{0})}{(A^{k}{\boldsymbol {y}}_{0})^{h}(A^{k}{\boldsymbol {y}}_{0})}}\,{\hbox{formula }}\heartsuit$

e poniamo

${\boldsymbol {y}}_{0}=\sum _{j=1}^{n}\alpha _{j}{\boldsymbol {y}}_{j}$

e sostituendo questa scrittura nella formula $\heartsuit$ otteniamo:

$={\frac {(A^{k}\sum _{j=1}^{k}\alpha _{j}{\boldsymbol {y}}_{j})^{h}*(A^{k+1}\sum _{j=1}^{n}\alpha _{j}{\boldsymbol {y}}_{j})}{(A^{k}\sum _{j=1}^{n}\alpha _{j}{\boldsymbol {y}}_{j})^{h}(A^{k}\sum _{j=1}^{n}\alpha _{j}{\boldsymbol {y}}_{j})}}$

e tenendo conto che $A^{k}{\boldsymbol {y}}_{j}=\lambda _{j}^{k}{\boldsymbol {y}}_{j}$ mettendo in evidenza $\lambda _{1}^{k}$:

$\sigma _{k}={\frac {\lambda _{1}|\lambda _{1}^{k}|^{2}[{\bar {\alpha }}_{1}{\boldsymbol {y}}_{1}^{h}+\sum _{j=2}^{n}{\bar {\alpha }}_{j}{\bar {\frac {\lambda _{j}}{\lambda _{1}}}}^{k}{\boldsymbol {y}}_{j}^{h}]*[\alpha _{1}{\boldsymbol {y}}_{1}+\sum _{j}\alpha _{j}({\frac {\lambda _{j}}{\lambda _{1}}})^{k+1}{\boldsymbol {y}}_{j}]}{|\lambda _{1}^{k}|^{2}[{\bar {\alpha }}_{1}{\boldsymbol {y}}_{1}^{h}+\sum _{j}{\bar {\alpha }}_{j}{\bar {\frac {\lambda _{j}}{\lambda _{1}}}}^{k}{\boldsymbol {y}}_{j}^{h}]*[\alpha _{1}{\boldsymbol {y}}_{1}+\sum _{j=2}^{n}\alpha _{j}({\frac {\lambda _{j}}{\lambda _{1}}})^{k}{\boldsymbol {y}}_{j}]}}$

Si può semplificare $(|\lambda _{1}|^{k})^{2}$, inoltre, siccome gli autovettori costituiscono una base ortogonale, i prodotti misti del tipo ${\boldsymbol {y}}_{i}{\boldsymbol {y}}_{j},i\neq j$ si annullano, e rimane solo:

$\sigma _{k}={\frac {\lambda _{1}[|\alpha _{1}|^{2}{\boldsymbol {y}}_{1}^{h}{\boldsymbol {y}}_{1}+\sum _{j=2}^{n}|\alpha _{j}|^{2}({\frac {\lambda _{j}}{\lambda _{1}}})^{2k}{\frac {\lambda _{j}}{\lambda _{1}}}{\boldsymbol {y}}_{j}^{h}{\boldsymbol {y}}_{j}]}{\lambda _{1}*(\alpha _{1}^{2}{\boldsymbol {y}}_{1}^{h}{\boldsymbol {y}}_{1}+\sum _{j=2}^{n}|\alpha _{j}|^{2}({\frac {\lambda _{j}}{\lambda _{1}}})^{2k}{\boldsymbol {y}}_{j}^{h}{\boldsymbol {y}}_{j})}}$

per l'ortonormalità ${\boldsymbol {y}}_{j}^{h}{\boldsymbol {y}}_{j}=1$, allora

$\sigma _{k}=\lambda _{1}{\frac {\alpha _{1}^{2}(1+\sum _{j=2}^{n}{\frac {|\alpha _{j}|^{2}}{|\alpha _{1}|^{2}}}*|\lambda _{j}/\lambda _{1}|^{2k}*|\lambda _{j}/\lambda _{1}|)}{|\alpha _{1}^{2}|*(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+\varepsilon )}{1+{\bar {\varepsilon }}}}$

$=\lambda _{1}*(1+\varepsilon )(1-{\bar {\varepsilon }})$

$\sigma _{k}=\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}]$

$=\lambda _{1}*(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 \mathbb {R} ^{+}$. 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{\boldsymbol {z}}_{k+1}={\boldsymbol {y}}_{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},\quad 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}|\geq \dots \geq |\lambda _{n}|$

${\boldsymbol {y}}_{0}=\sum _{i=1}^{r}\alpha _{1,i}{\boldsymbol {x}}_{1,i}+\sum _{j=r+1}^{n}\alpha _{j}{\boldsymbol {x}}_{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}$.