Casi particolari

Caso 1 matrici hermitiane

Una matrice hermitiana è diagnalizzata attraverso matrici unitarie, cioè $A=Q\lambda Q_{h}$$A=Q\lambda Q_{h}$ con $\lambda$$\lambda$ diagonale e $QQ_{h}=Q_{h}Q=I$$QQ_{h}=Q_{h}Q=I$, cioè ho 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}}}$$

$$\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$$

$$={\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 pongo

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

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

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

$$={\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})}}$$

$$={\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}$$A^{k}{\boldsymbol {y}}_{j}=\lambda _{j}^{k}{\boldsymbol {y}}_{j}$ mettendo in evidenza $\lambda _{1}^{k}$$\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}]}}$$

$$\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}$$(|\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$${\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})}}$$

$$\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$${\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})}}$$

$$\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$$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}]}}$$

$$\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 }}}}$$

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

$$=\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}]$$

$$\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})$$

$$=\lambda _{1}*(1-|\alpha _{1}/\alpha _{2}|^{2}|\lambda _{2}/\lambda _{1}|^{2k})$$

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

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

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

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

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

Caso 2 matrici hermitiane definite positive

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

Risparmio del costo computazionale: Cerco $\lambda _{min}(A)$$\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}$$

$$A{\boldsymbol {z}}_{k+1}={\boldsymbol {y}}_{k}$$

con costo di fattorizzazione $o(n^{3})$$o(n^{3})$. La fattorizzazione viene fatta una sola volta. Ad ogni iterazione, risolvo i sistemi triangolari. Se $R$$R$ è triangolare superiore piena il costo è $o(n^{2})$$o(n^2)$. Se invece $R$$R$ è a banda, il costo è $o(n)$$o(n)$. Lo stesso vale se $R$$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$$A$ in una matrice tridiagonale $B$$B$. A questo punto il costo della fattorizzazione di Cholesky è $o(n)$$o(n)$, perché $R$$R$ è bidiagonale, e anche il costo delle singole operazioni si riduce.

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

$$A_{k+1}=T_{k}^{-1}A_{k}T_{k},\quad k=1,\dots ,n-2$$

$$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$$A$ in modo da ottenere una matrice tridiagonale. Questa operazione costa $o(n^{3})$$o(n^{3})$.

Condizionamento

Considero il caso in cui la fattorizzazione di Cholesky non può avvenire (cioè $\lambda _{min}$$\lambda _{min}$ molto piccolo e $A$$A$ definita positiva). Invece che considerare $A$$A$, considero ${\hat {A}}=A+cI$${\hat {A}}=A+cI$, che è ancora hermitiana e definita positiva. Si usa la tecnica di shift. Gli autovalori di ${\hat {A}}$$\hat A$ sono gli autovalori di $A$$A$ shiftati di $c$$c$. $K_{2}(A)={\frac {\lambda _{max}}{\lambda _{mi}}}$$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)$$

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

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

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

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

e si ha come rischio l'errore di cancellazione. Bisogna bilanciare $c$$c$ rispetto a $\lambda _{min}(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}$$\lambda _{max}$ di molteplicità r.

$$|\lambda _{1}|=|\lambda _{2}|=\lambda _{r}|>|\lambda _{r+1}|\geq \dots \geq |\lambda _{n}|$$

$$|\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}$$

$${\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})$$

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

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