Casi particolari

Caso 1 matrici hermitiane[modifica | modifica wikitesto]

Una matrice hermitiana è diagnalizzata attraverso matrici unitarie, cioè con diagonale e , cioè ho una base ortonormale di autovettori. Allora in questo caso:

e pongo
e sostituendo questa scrittura nella formula ottengo:
e tenendo conto che mettendo in evidenza :
Si può semplificare , inoltre, siccome gli autovettori costituiscono una base ortogonale, i prodotti misti del tipo si annullano, e rimane solo:
per l'ortonormalità , allora
Al primo ordine, nella sommatoria sopravvive il termine per (secondo autovalore più grande), quindi
Allora nel caso di matrici hermitiane:
A differenza del caso generale compare l'esponente e la convergenza è più veloce.

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

Caso 2 matrici hermitiane definite positive[modifica | modifica wikitesto]

Considero con unitaria e . Il caso non può verificarsi, quindi su una matrice hermitiana definita positiva il metodo delle potenze converge sempre.

Risparmio del costo computazionale: Cerco con il metodo delle potenze inverse. Ad ogni iterazione si risolve il sistema lineare

con costo di fattorizzazione . La fattorizzazione viene fatta una sola volta. Ad ogni iterazione, risolvo i sistemi triangolari. Se è triangolare superiore piena il costo è . Se invece è a banda, il costo è . Lo stesso vale se è sparsa.

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

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

Passo da generica a tridiagonale tramite trasformazioni di Hausolder:

La matrice di sinistra azzera la sottocolonna e quella di destra azzera la sottoriga di in modo da ottenere una matrice tridiagonale. Questa operazione costa .

Condizionamento[modifica | modifica wikitesto]

Considero il caso in cui la fattorizzazione di Cholesky non può avvenire (cioè molto piccolo e definita positiva). Invece che considerare , considero , che è ancora hermitiana e definita positiva. Si usa la tecnica di shift. Gli autovalori di sono gli autovalori di shiftati di . ed è grande, invece si ha

converge all'autovalore minimo di , invece
e si ha come rischio l'errore di cancellazione. Bisogna bilanciare rispetto a .

Esercizio 3.1

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

 

Sia di molteplicità r.

si ritrova lo stesso risultato di prima con che sostituisce , cioè, al posto di compare il primo valore diverso da .

 Precedente